In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the n th-residuosity problem) is one such problem. This problem is easier to solve than integer factorization, so the assumption that this problem is hard to solve is stronger than the assumption that integer factorization is hard.
Contents
Mathematical Background
If n is an integer, then the integers modulo n form a ring. If n=pq where p and q are primes, then the Chinese remainder theorem tells us that
The group of units of any ring form a group, and the group of units in
From the isomorphism above, we have
as an isomorphism of groups. Since p and q were assumed to be prime, the groups
The important point is that for any divisor d of p-1 (or q-1) the set of dth powers forms a subgroup of
Problem Statement
Given an integer n = pq where p and q are unknown, an integer d such that d divides p-1, and an integer x < n, it is infeasible to determine whether x is a dth power (equivalently dth residue) modulo n.
Notice that if p and q are known it is easy to determine whether x is a dth residue modulo n because x will be a dth residue modulo p if and only if
When d=2, this is called the quadratic residuosity problem.
Applications
The semantic security of the Benaloh cryptosystem and the Naccache-Stern cryptosystem rests on the intractability of this problem.