Quadratic residuosity problem

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 contemporary cryptography. (A note on terminology: mathematicians say "residuacity": "residuosity", something of a malapropism, has been adopted by most cryptographers.)

Given the specific case of "N" the product of distinct large prime numbers "p" and "q", the structure of the squaring

:"a" → "a"2 modulo "N"

on the multiplicative group of invertible residues modulo "N", is as a group homomorphism with kernel a Klein group of order four. The image is therefore, roughly speaking, of size "N"/4. More precisely, it is of order:

:frac{(p - 1)(q - 1)}{4}

If we consider the same mapping modulo "p" the kernel is of order 2, the order of the image is ("p" − 1)/2. In that case it is easy, computationally speaking, to characterise the image, since the quadratic residue symbol takes the value +1 precisely on squares.

In the composite case the corresponding symbol characterises a subgroup of the residues which is too large by factor of two; that is, it rules out roughly half of the residues mod "N", while the problem as posed is to characterise a subset of size a quarter of "N". This difference constitutes the quadratic residuosity problem, in this particular but essential case of "N" having two prime factors.

The working assumption is that bridging this gap, in effective computational terms, is only to be done by lengthy calculation, when quantified in terms of the size of "N".

The Quadratic residuosity problem is the foundation of the Goldwasser-Micali cryptosystem.

ee also

* Higher residuosity problem
* Computational hardness assumptions

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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 …   Wikipedia

  • Quadratic residue — 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: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract… …   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

  • Goldwasser-Micali cryptosystem — The Goldwasser Micali cryptosystem (GM) 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… …   Wikipedia

  • Cocks IBE scheme — is an Identity based encryption system proposed by Clifford Cocks in 2001 [1]. The security of the scheme is based on the hardness of the quadratic residuosity problem. Contents 1 Protocol 1.1 Setup 1.2 Extract …   Wikipedia

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

  • List of mathematics articles (Q) — NOTOC Q Q analog Q analysis Q derivative Q difference polynomial Q exponential Q factor Q Pochhammer symbol Q Q plot Q statistic Q systems Q test Q theta function Q Vandermonde identity Q.E.D. QED project QR algorithm QR decomposition Quadratic… …   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 number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   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