Higher residuosity problem

In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 ) 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 dth 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 dth power, so the set of dth 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)/g dth powers in (\mathbb{Z}/q\mathbb{Z})^{\times} , so the set of dth 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 dth 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 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} \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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1291060958 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001291060958 · captured 1747593732.0 · version history

Cite this page as: encyclopegia.org, “Higher residuosity problem”, snapshot enwiki-001291060958. https://encyclopegia.org/a/higher-residuosity-problem

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.