In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable.
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.
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 units of any ring form a group under multiplication, and the group of units in
is traditionally denoted
Since p and q were assumed to be prime, the groups
are cyclic of orders p−1 and q−1 respectively.
If d is a divisor of p−1, then the set of d th powers in
form a subgroup of index d. If gcd(d,q−1) = 1, then every element in
is also a subgroup of index d. In general, if gcd(d,q−1) = g, then there are (q−1)/g d th powers in
, so the set of d th powers in
has index dg.
This is most commonly seen when d = 2, and we are considering the subgroup of quadratic residues, it is well-known that exactly one quarter of the elements in
are quadratic residues (when n is the product of two primes, as it is here).
The important point is that for any divisor d of p−1 (or q−1) the set of d th powers forms a subgroup of
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 d th power (equivalently d th residue) modulo n. Notice that if p and q are known it is easy to determine whether x is a d th residue modulo n because x will be a d th residue modulo p if and only if When d = 2, this is called the quadratic residuosity problem.
The semantic security of the Benaloh cryptosystem and the Naccache–Stern cryptosystem rests on the intractability of this problem.