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[1]) 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.
The group of units of any ring form a group, and the group of units in is traditionally denoted .
From the isomorphism above, we have
as an isomorphism of groups. Since p and q were assumed to be prime, the groups and are cyclic of orders p-1 and q-1 respectively. If d is a divisor of p-1, then the set of dth powers in form a subgroup of indexd. If gcd(d,q-1) = 1, then every element in is a dth power, so the set of dth powers in is also a subgroup of index d. In general, if gcd(d,q-1) = g, then there are (q-1)/(g) dth powers in , so the set of dth 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 exactly two primes, as it is here).
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
^Zhang, Yuliang; Tsutomu Matsumoto; Hideki Imai (1988). "Cryptographic Applications of th-Residuosity Problem with an Odd Integer". Transactions of the IEICE. 71 (8): 759–767. CiteSeerX10.1.1.137.8511.
January 12, 2023
higher, residuosity, problem, cryptography, most, public, cryptosystems, founded, problems, that, believed, intractable, higher, residuosity, problem, also, called, residuosity, problem, such, problem, this, problem, easier, solve, than, integer, factorization. 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 1 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 1 Mathematical background 2 Problem statement 3 Applications 4 ReferencesMathematical background EditIf 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 Z n Z Z p Z Z q Z displaystyle mathbb Z n mathbb Z simeq mathbb Z p mathbb Z times mathbb Z q mathbb Z The group of units of any ring form a group and the group of units in Z n Z displaystyle mathbb Z n mathbb Z is traditionally denoted Z n Z displaystyle mathbb Z n mathbb Z From the isomorphism above we have Z n Z Z p Z Z q Z displaystyle mathbb Z n mathbb Z simeq mathbb Z p mathbb Z times mathbb Z q mathbb Z as an isomorphism of groups Since p and q were assumed to be prime the groups Z p Z displaystyle mathbb Z p mathbb Z and Z q Z displaystyle mathbb Z q mathbb Z are cyclic of orders p 1 and q 1 respectively If d is a divisor of p 1 then the set of dth powers in Z p Z displaystyle mathbb Z p mathbb Z form a subgroup of index d If gcd d q 1 1 then every element in Z q Z displaystyle mathbb Z q mathbb Z is a dth power so the set of dth powers in Z n Z displaystyle mathbb Z n mathbb Z is also a subgroup of index d In general if gcd d q 1 g then there are q 1 g dth powers in Z q Z displaystyle mathbb Z q mathbb Z so the set of dth powers in Z n Z displaystyle mathbb Z n mathbb Z 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 Z n Z displaystyle mathbb Z n mathbb Z are quadratic residues when n is the product of exactly two primes as it is here The important point is that for any divisor d of p 1 or q 1 the set of dth powers forms a subgroup of Z n Z displaystyle mathbb Z n mathbb Z Problem statement EditGiven an integer n pq where p and q are unknown an integer d such that d divides p 1 and an integer x lt 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 x p 1 d 1 mod p displaystyle x p 1 d equiv 1 pmod p When d 2 this is called the quadratic residuosity problem Applications EditThe semantic security of the Benaloh cryptosystem and the Naccache Stern cryptosystem rests on the intractability of this problem References Edit Zhang Yuliang Tsutomu Matsumoto Hideki Imai 1988 Cryptographic Applications of th Residuosity Problem with an Odd Integer Transactions of the IEICE 71 8 759 767 CiteSeerX 10 1 1 137 8511 Retrieved from https en wikipedia org w index php title Higher residuosity problem amp oldid 1013061005, wikipedia, wiki, book, books, library,