Higher residuosity problem

Higher residuosity problem

In cryptography most public key cryptosystems are founded on problems that are believed to be intractable. The higher 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}/nmathbb{Z} simeq mathbb{Z}/pmathbb{Z} imes mathbb{Z}/qmathbb{Z}

The group of units of any ring form a group, and the group of units in mathbb{Z}/nmathbb{Z} is traditionally denoted (mathbb{Z}/nmathbb{Z})^*.

From the isomorphism above, we have

:(mathbb{Z}/nmathbb{Z})^* simeq (mathbb{Z}/pmathbb{Z})^* imes (mathbb{Z}/qmathbb{Z})^*

as an isomorphism of "groups". Since "p" and "q" were assumed to be prime, the groups (mathbb{Z}/pmathbb{Z})^* and (mathbb{Z}/qmathbb{Z})^* 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}/pmathbb{Z})^* form a subgroup of index "d". If gcd("d","q"-1) = 1, then "every" element in (mathbb{Z}/qmathbb{Z})^* is a "d"th power, so the set of "d"th powers in (mathbb{Z}/nmathbb{Z})^* 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 (mathbb{Z}/qmathbb{Z})^*, so the set of "d"th powers in (mathbb{Z}/nmathbb{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 (mathbb{Z}/nmathbb{Z})^* arequadratic 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 "d"th powers forms a subgroup of (mathbb{Z}/nmathbb{Z})^*.

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.

ee also

*quadratic residuosity problem
*computational hardness assumptions


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Quadratic residuosity problem — The quadratic residuosity problem in computational number theory is the question of distinguishing by calculation the quadratic residues in modular arithmetic for a modulus N , where N is a composite number. This is an important consideration in… …   Wikipedia

  • Decisional composite residuosity assumption — The decisional composite residuosity assumption (DCRA) is a mathematical assumption used in cryptography. In particular, the assumption is used in the proof of the Paillier cryptosystem. Informally the DCRA states that given a composite n… …   Wikipedia

  • Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… …   Wikipedia

  • Naccache-Stern cryptosystem — Note: this is not to be confused with the Naccache Stern knapsack cryptosystem.The Naccache Stern cryptosystem is a homomorphic Public key cryptosystem whose security rests on the higher residuosity problem.The Naccache Stern cryptosystem was… …   Wikipedia

  • Computational hardness assumption — In cryptography, a major goal is to create cryptographic primitives with provable security. In some cases cryptographic protocols are found to have information theoretic security, the one time pad is a common example. In many cases, information… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Okamoto–Uchiyama cryptosystem — The Okamoto–Uchiyama cryptosystem was discovered in 1998 by T. Okamoto and S. Uchiyama. The system works in the group , where n is of the form p2q and p and q are large primes. Contents 1 Scheme definition 1.1 Key generation …   Wikipedia

  • Okamoto-Uchiyama cryptosystem — The Okamoto Uchiyama Cryptosystem was discovered in 1998 by T. Okamoto and S. Uchiyama. The system works in the group (mathbb{Z}/nmathbb{Z})^*, where n is of the form p 2 q . The Okamoto Uchiyama cryptosystem is a precursor to the Paillier… …   Wikipedia

  • Problème de la résiduosité quadratique — En théorie algorithmique des nombres, le problème de la résiduosité[1] quadratique est celui de distinguer, à l aide de calculs, les résidus quadratiques modulo un nombre composé N fixé. C est un problème important en cryptographie, en… …   Wikipédia en Français

  • Naccache–Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem. The Naccache–Stern Knapsack Cryptosystem is an atypical public key cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”