Higher residuosity problem
Encyclopedia
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.
, 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
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 index
d. 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
.
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
When d=2, this is called the quadratic residuosity problem
.
of the Benaloh cryptosystem
and the Naccache-Stern cryptosystem
rests on the intractability of this problem.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
most public key cryptosystems
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
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
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
, 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 integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
, then the integers modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
n form a ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
. If n=pq where p and q are primes
Prime number
A prime number 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 called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
, then the Chinese remainder theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
tells us that
The group of units
Unit (ring theory)
In mathematics, an invertible element or a unit in a ring R refers to any element u that has an inverse element in the multiplicative monoid of R, i.e. such element v that...
of any ring form a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, 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 cyclicCyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
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 indexIndex of a subgroup
In mathematics, specifically group theory, the index of a subgroup H in a group G is the "relative size" of H in G: equivalently, the number of "copies" of H that fill up G. For example, if H has index 2 in G, then intuitively "half" of the elements of G lie in H...
d. 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
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 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
When d=2, this is called the quadratic residuosity problem
Quadratic residuosity problem
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
.
Applications
The semantic securitySemantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
of the Benaloh cryptosystem
Benaloh cryptosystem
The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem created in 1994 by Josh 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.-Scheme...
and the Naccache-Stern cryptosystem
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...
rests on the intractability of this problem.
See also
- quadratic residuosity problemQuadratic residuosity problemThe quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
- computational hardness assumptionsComputational hardness assumptionsIn 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 theoretic security cannot be achieved, and in such...