Higher residuosity problem

Last updated December 21, 2023

In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the nth-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.

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

\mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z}

The units of any ring form a group under multiplication, and the group of units in $\mathbb {Z} /n\mathbb {Z}$ is traditionally denoted $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ .

From the ring isomorphism above, we have

(\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }

as an isomorphism of groups. Since p and q were assumed to be prime, the groups $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ and $(\mathbb {Z} /q\mathbb {Z} )^{\times }$ 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 $(\mathbb {Z} /p\mathbb {Z} )^{*}$ form a subgroup of index d. If gcd(d,q−1) = 1, then every element in $(\mathbb {Z} /q\mathbb {Z} )^{\times }$ is a d th power, so the set of d th powers in $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ is also a subgroup of index d. In general, if gcd(d,q−1) = g, then there are (q−1)/gd th powers in $(\mathbb {Z} /q\mathbb {Z} )^{\times }$ , so the set of d th powers in $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ 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 $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ 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 $(\mathbb {Z} /n\mathbb {Z} )^{\times }.$

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 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

x^{(p-1)/d}\equiv 1{\pmod {p}}

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.

Related Research Articles

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

In number theory, given a prime number $p$ , the $p$ -adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; $p$ -adic numbers can be written in a form similar to decimals, but with digits based on a prime number $p$ rather than ten, and extending to the left rather than to the right. Formally, given a prime number $p$ , a $p$ -adic number can be defined as a series

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

<span class="mw-page-title-main">Root of unity</span> Number that has an integer power equal to 1

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power $n$ . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers $and, whether is a quadratic residue modulo or not. Here for two unknown primes and, and is among the numbers which are not obviously quadratic non-residues.$

In modular arithmetic, the integers coprime to n from the set $of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n . Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n . Hence another name is the group of primitive residue classes modulo n . In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n . Here units refers to elements with a multiplicative inverse, which, in this ring, are exactly those coprime to n .$

The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most notably the ElGamal and Cramer–Shoup cryptosystems.

The Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as ciphertexts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely used definition of semantic security.

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r² ≡ n, where p is a prime: that is, to find a square root of n modulo p.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x³ ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x³ ≡ p is solvable if and only if x³ ≡ q is solvable.

The Okamoto–Uchiyama cryptosystem is a public key cryptosystem proposed in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the multiplicative group of integers modulo n, $, where n is of the form p 2 q and p and q are large primes.$

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

In number theory, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the probabilistic method of finding roots of polynomials over the field field $with elements. The method was discovered by Elwyn Berlekamp in 1970 as an auxiliary to the algorithm for polynomial factorization over finite fields. The algorithm was later modified by Rabin for arbitrary finite fields in 1979. The method was also independently discovered before Berlekamp by other researchers.$

References

↑ 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 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Zhang1988-1] 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 .

[1]

v t e Computational hardness assumptions
Number theoretic	Integer factorization Phi-hiding RSA problem Strong RSA Quadratic residuosity Decisional composite residuosity Higher residuosity
Group theoretic	Discrete logarithm Diffie-Hellman Decisional Diffie–Hellman Computational Diffie–Hellman
Pairings	External Diffie–Hellman Sub-group hiding Decision linear
Lattices	Shortest vector problem (gap) Closest vector problem (gap) Learning with errors Ring learning with errors Short integer solution
Non-cryptographic	Exponential time hypothesis Unique games conjecture Planted clique conjecture