cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the n th-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 An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

, then the integers modulo ''n'' form a

ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

. If ''n''=''pq'' where ''p'' and ''q'' are

primes A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

, then the Chinese remainder theorem tells us that :

\mathbb/n\mathbb \simeq \mathbb/p\mathbb \times \mathbb/q\mathbb

The group of units of any ring form a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

, and the group of units in

\mathbb/n\mathbb

is traditionally denoted

(\mathbb/n\mathbb)
^*

. From the isomorphism above, we have :

(\mathbb/n\mathbb)^* \simeq (\mathbb/p\mathbb)^* \times (\mathbb/q\mathbb)^*

as an isomorphism of ''groups''. Since ''p'' and ''q'' were assumed to be prime, the groups

(\mathbb/p\mathbb)^*

and

(\mathbb/q\mathbb)^*

are

cyclic Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in s ...

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/p\mathbb)^*

form a subgroup of index ''d''. If gcd(''d'',''q''-1) = 1, then ''every'' element in

(\mathbb/q\mathbb)^*

is a ''d''th power, so the set of ''d''th powers in

(\mathbb/n\mathbb)^*

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/q\mathbb)^*

, so the set of ''d''th powers in

(\mathbb/n\mathbb)^*

has index ''dg''. This is most commonly seen when ''d''=2, and we are considering the subgroup of

quadratic residues 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: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic non ...

, it is well known that exactly one quarter of the elements in

(\mathbb/n\mathbb)^*

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 ''d''th powers forms a subgroup of

(\mathbb/n\mathbb)^*.

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^ \equiv 1 \pmod p

When ''d''=2, this is called the

quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...

Applications

The semantic security of the

Benaloh cryptosystem 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 i ...

and the Naccache–Stern cryptosystem rests on the intractability of this problem.

References

{{DEFAULTSORT:Higher Residuosity Problem Computational number theory Computational hardness assumptions