Cryptography Reference
In-Depth Information
manner. Specifically, on input (
σ, N ), algorithm D uniformly selects polynomially
many residues mod N and outputs the first residue with Jacobi symbol (
1) σ .
N )) are uniformly
distributed over the set of quadratic residues mod N . The difficulty of forming claws
follows from the fact that a claw yields two residues, x
The reader can easily verify that both f N ( D (0
,
N )) and f N ( D (1
,
J + 1
N
J N , such that
and y
J + 1
N
their squares modulo N are equal (i.e., x 2
y 2
(mod N )). Since
1
(and
the latter is a multiplicative subgroup), it follows that y
≡ ±
x
(mod N ), and so the
greatest common divisor (g.c.d.) of y
x and N yields a factorization of N .
The foregoing collection consists of pairs of functions that are 2-to-1 (and are defined
over disjoint domains). To obtain a collection of claw-free permutations , we slightly
modify the collection as follows. The index set consists of Blum integers that are the
products of two primes P and Q of the same length, so that P 3 (mod 8) and
Q 7 (mod 8). For such composites, neither 2 nor 2 is a quadratic residue modulo
N = P · Q (and in fact ± 2 J N ). Consider the functions f N and f N defined over the
set, denoted Q N , of quadratic residues modulo N :
±
f N ( x ) def
= 4 σ · x 2
mod N
(2.14)
Clearly, both f N and f N are permutations over Q N . The difficulty of forming claws
follows from the fact that a claw yields two quadratic residues, x and y , so that x 2
4 y 2
(mod N ). Thus, ( x / y ) 2
4 (mod N ), and so (2 ( x / y )) · (2 + ( x / y )) 0
(mod N ). Since ± 2 Q N (and the latter is a multiplicative subgroup), it follows that
( x / y ) ≡ ± 2
(mod N ), and so the g.c.d. of (2 ± x · y 1
mod N ) and N yields the
factorization of N .
The foregoing collections are not known to possess the additional property of having
an efficiently recognizable index set. In particular, it is not even known how to efficiently
distinguish products of two primes from products of more than two primes.
2.4.6. On Proposing Candidates
Although we do believe that one-way functions exist, their mere existence does not
suffice for practical applications. Typically, an application that is based on one-way
functions requires the specification of a concrete (candidate one-way) function. 9 Hence,
the problem of proposing reasonable candidates for one-way functions is of great
practical importance. Everyone understands that such a reasonable candidate (for a
one-way function) should have a very efficient algorithm for evaluating the function.
In case the “function” is presented as a collection of one-way functions, the domain
sampler and function-evaluation algorithm should be very efficient (whereas for index
sampling, “moderate efficiency” may suffice). However, people seem less careful about
seriously considering the difficulty of inverting the candidates that they propose. We
stress that the candidate has to be difficult to invert on “the average” and not only
in the worst case, and “the average” is taken with respect to the instance-distribution
determined by the candidate function. Furthermore, “hardness on the average” (unlike
9 As explained in Section 2.4.1, the observation concerning the existence of a universal one-way function is of
little practical significance.
Search WWH ::




Custom Search