. 1
( : 2)



. . >>

Q QUADRATIC SIEVE
QUADRATIC RESIDUE
INTRODUCTION: The Quadratic Sieve (QS) and
Let n be an odd, positive integer and let x be an
its variants are the ¬rst of the modern integer
integer that is relatively prime to n (see modular
factoring algorithms to be able to routinely factor
arithmetic). The integer x is a quadratic residue
abitrary integers in the 60+ digit range on just
modulo n if the equation
a single PC. They are the successor to the ear-
x ≡ y2 (mod) n lier Continued Fraction Method of Morrison and
Brillhart [4] (see integer factoring) and the pre-
has an integer solution y. In other words, the in- decessor to the Number Field Sieve [2]. All three
teger x is a square modulo n. The integer x is a of these algorithms share features in common.
quadratic non-residue otherwise. They are based upon the observation that if A2 ≡
If n is an odd prime number, then exactly half of B2 mod N and A ≡ ±B mod N (see modular arith-
all integers x relatively prime to n are quadratic metic), then GC D (A + B, N) and GC D (A ’ B, N)
residues. If n is the product of two distinct odd are proper factors of N. The Quadratic Sieve will
primes p and q, then the fraction is one-quarter. factor an arbitrary integer N, in heuristic time
See also Jacobi symbol, Legendre symbol, and LN[1/2, 1] = exp((1 + o(1)) (log N)1/2 (log log N)1/2 )
Quadratic Residuosity Problem. (see L-notation). The entries integer factoring and
Number Field Sieve discuss the history of these
Burt Kaliski
algorithms and we do not repeat that discussion
here. For those interested in implementing QS,
reference [7] gives all of the necessary details. The
version of QS that is detailed here is known as
QUADRATIC RESIDUOSITY the Multiple Polynomial Quadratic Sieve (MPQS).
PROBLEM Other variants are known.

KEY IDEAS: The Quadratic Sieve, like other
Let n be the product of two distinct odd prime num-
sieving algorithms (and the Elliptic Curve
bers p, q, and let x be an integer such that the
Method for factoring), is based on the idea of
Jacobi symbol (x/n) = +1. The Quadratic Residu-
smooth numbers (see also smoothness). A number
osity Problem (QRP) is to determine, given x and
x is said to be y”smooth if all of its prime factors
n, whether x is a quadratic residue modulo n (see
are less than y. QS generates many relations of
modular arithmetic). (All quadratic residues have
the form
Jacobi symbol +1, but not necessarily the reverse.)
This problem is easy to solve given the factors p S 2 = r mod N,
and q, but is believed to be dif¬cult given only x
where the pair (S, r ) is generated from a quadratic
and n. However, it is not known whether the prob-
polynomial in such a way that r is small com-
lem is equivalent to factoring the modulus n.
pared to N. The algorithm then attempts to factor
The QRP is the basis for several cryptosys-
r using a ¬xed set of primes called a factor base.
tems, including the Goldwasser“Micali encryption
The largest prime in the factor base is then the
scheme and Cocks™ identity-based encryption
smoothness bound. Most such values will not fac-
scheme [1] (see identity-based cryptosystems).
tor. However, a sieve can be used to attempt to
Burt Kaliski factor many such rs simultaneously. It is the speed
of sieving on modern computers that makes QS
and NFS very effective methods. The sieve works
Reference
by observing that if a prime p divides the value of
a polynomial Q (x), then it divides Q (x + kp) for
[1] Cocks, Clifford (2001). “An identity based encryp-
all k.
tion scheme based on quadratic residues.” Cryp-
Once a suf¬cient number of smooth relations
tography and Coding, Lecture Notes in Computer
have been found, a subset is then extracted such
Science, vol. 2260, ed. B. Honary. Springer, Berlin,
that the product of the rs in the subset is a perfect
360“363.




493
494 Quadratic sieve


square. From that, A2 ≡ B2 mod N is easily com- chosen this way to minimize the maximum value
of Q(x) over the interval [’M, M]. The computa-
puted.
tion of B, C and S depends on A and is detailed
The subset is found by solving a system of equa-
in [7].
tions mod 2. This is referred to as the linear alge-
bra phase of the algorithm.
OPTIMIZATION PARAMETER SELECTION:
AND
GENERATION RELATIONS: The algorithm
OF It is often useful, rather than to factor just N
starts by computing a factor base FB = { pi |( N ) = 1, to factor kN for some small value of k. This can
pi
p prime, i = 1, . . . , F} for some appropriate value have the effect of allowing more small quadratic
of F and p0 = ’1 for the sign. ( N ) is the Legendre residues in the factor base. In this case, replace N
pi
symbol and indicates that pi must be a quadratic with kN in all of the computations outlined above.
residue of N. It may also be necessary in order for the algorithm
The following is then repeated until enough to work. Since N = B2 ’ 4AC and the right-hand
smooth relations have been collected:
r side is 0 or 1 mod 4, if N ≡ 3 mod 4, then we must
Construct a quadratic polynomial Q(x) = multiply N by k so that k N ≡ 1 mod 4. However,
Ax 2 + Bx + C and solve Q(x) ≡ 0 mod pi for all this requirement may be avoided by taking 2B,
i. There will be two roots r1i and r2i for each rather than just B as the middle coef¬cient for Q.
prime.
r The Knuth“Schroeppel function may be used to
Initialize a sieve array to zero over the interval evaluate the effectiveness of different values of k.
[’M, M] for an appropriate value of M.
r See [7] for details.
For all pi ∈ FB add the value log( pi ) to Rather than demand that r be fully factored over
the locations r1 , r1 ± pi , r1 ± 2 pi , . . . and r2 , r2 ± the factor base, it is very useful to allow a small
pi , r2 ± 2 pi , . . .
r √ number of somewhat larger primes to appear in
The value of Q(x) will be approximately M N the factorization of r. This is known as the large
over [’M, M] so compare each sieve location prime variation. Let
with T = log(M) + log(N)/2. Fully factored val-
F
ues will have their corresponding sieve value
pi±i P1 P2 . . . ,
r=
close to T. For these, construct the exact fac-
i=0
torization by division. It is also possible (and
where the Pi are allowed to be somewhat larger
usually quicker) to ¬nd the factorization by re-
primes than those in the factor base. The Birth-
sieving. See the section on optimization for how
day Paradox now becomes useful here. The set of
to do this. We then have
fully factored rs will now be quite large and we
F
pi±i
S ≡ Q(x) ≡
2
mod N. can expect many of the large primes Pi to appear
more than once. When it does, we may multiply
i=0

the corresponding relations together and obtain
The value of S is easily computed from the value
Pi2 on the right-hand side of each relation. For N
of x because of the special way the coef¬cients
up to about 85 digits, using one large prime is quite
of Q are computed. Let
’ = {± , ± , . . . , ± } mod 2.
’ effective. For N greater than about 85 digits, two
v 1 2 F
primes are effective. Limited experience suggests
Collect a total of at least F + 1 factored relations. that for N above 120 digits, three primes may be
One then ¬nds a set whose product is a square by effective. Once the factor base primes are removed,
¬nding a linear dependency over GF(2) from the P1 and P2 may then be split via Pollard™s rho (see
matrix formed by letting each ’ be a row in the
’v integer factoring) or SQUFOF algorithms (see [6]
matrix. for a de¬nition of SQUFOF). Both are effective.
The smallest primes pi take the longest time to
COMPUTATION POLYNOMIAL COEFFI- sieve and their logarithms contribute the least to
OF
CIENTS: The coef¬cients for each polynomial are the accumulated sum at each sieve location. It is
derived from a prime number D = 3 mod 4 with worthwhile to replace the smallest primes (up to
( N ) = 1. Each prime D yields a different polyno-
D
about 30) with small powers of those primes. This
mial. This makes parallel implementation of this has the effect of greatly speeding sieve time while
algorithm easy. Simply give different sets of Ds to losing only a tiny fraction of factored relations.
different machines and let each one run indepen- This is known as the small prime variation.
dently. It is also worthwhile to partition the sieve inter-
To compute the coef¬cients, we start by letting val [’M, M] into pieces that will ¬t in cache while

A = D2 with D ≈ (N/2)1/4 / M. The value of D is sieving. This too can greatly improve the speed
Quantum cryptography 495


of sieving, and it cuts down on memory require- Stephen Wiesner wrote “Conjugate Coding,” which
ments. unfortunately took more than 10 years to see the
The cost of changing polynomials is dominated light of print [50]. In the mean time, Charles H.
by the cost of computing (2A)’1 mod pi for each pi . Bennett (who knew of Wiesner™s idea) and Gilles
A method for greatly reducing this cost is known Brassard picked up the subject and brought it to
as the self-initializing Quadratic Sieve (SIQS). De- fruition in a series of papers that culminated with
tails may be found in [5]. the demonstration of an experimental prototype
A fair bit of time is taken by the reconstruction that established the technological feasibility of
of the actual factorization of r. The sieving pro- the concept [5]. Quantum cryptographic systems
cess merely identi¬es which r are smooth. It does take advantage of Heisenberg™s uncertainty rela-
not produce the factorization. This is readily ac- tions, according to which measuring a quantum
complished by trial division of r by the factor base system, in general, disturbs it and yields incom-
primes. However, as N, and hence the size of F in- plete information about its state before the mea-
creases, trial division starts taking a larger and surement. Eavesdropping on a quantum commu-
larger percentage of the run time. This may be al- nication channel therefore causes an unavoidable
leviated by ¬nding the factorizations by resieving. disturbance, alerting the legitimate users. This
Now, however, instead of accumulating log pi , one yields a cryptographic system for the distribution
simply stores the pi that hit the identi¬ed smooth of a secret random key between two parties ini-
locations. It is now a simple matter to produce the tially sharing no secret information (however they
actual factorization. must be able to authenticate messages) that is se-
Suggested values for the parameters M and F as cure against an eavesdropper having at her dis-
well as additional coding and computational con- posal unlimited computing power. Once this se-
siderations may be found in [7]. cret key is established, it can be used together
with classical cryptographic techniques such as
Robert D. Silverman the Vernam cipher (one-time pad) to allow the par-
ties to communicate meaningful information in
References absolute secrecy.
Quantum cryptography is best known for key
distribution [7]. A short summary of this so-
[1] Caron, T. and R.D. Silverman (1988). “Parallel im-
called BB84 protocol is provided in the Section
plementation of the quadratic sieve.” Journal of
Supercomputing, 1, 273“290. “Qnantum Key Distribution.” A remarkable surge
[2] Lenstra, A. and H.W. Lenstra, Jr. (eds.) (1992). The of interest in the international scienti¬c and
Development of the Number Field Sieve, Lecture industrial communities has propelled quantum
Notes in Mathematics, vol. 1554. Springer-Verlag, cryptography into mainstream computer science
Berlin.
and physics. Furthermore, quantum cryptogra-
[3] Lenstra, A. and M. Manasse (1994). “Factoring with
phy is becoming increasingly practical at a fast
two large primes.” Math. Comp., 63, 785“798.
pace. The ¬rst quantum key distribution proto-
[4] Morrison, M. and J. Brillhart (1975). “A method of
type, built in 1989, worked over a distance of 32 cm
factoring and the factorization of F7 .” Math. Comp.,
[5], [11]. Since then, many additional experimen-
29, 183“205.
tal demonstrations have been set up, covering dis-
[5] Pomerance, C., J.W. Smith, and R. Tuler (1988).
tances of tens of kilometers. Consult [46] or [42]
“A pipeline architecture for factoring large integers
with the quadratic sieve.” SIAM J. Comp., 17 (2), for popular accounts of the state of the art in ex-
387“403. perimental quantum cryptography.
[6] Riesel, H. (1987). Prime Numbers and Computer
Methods for Factorization. Volume 57 of Progress in
The Various Uses of Quantum Physics
¨
Mathematics. Birkhauser.
for Cryptography
[7] Silverman, R.D. (1987). “The multiple polynomial
quadratic sieve.” Math. Comp., 48, 329“339.
In addition to key distribution, quantum tech-
niques may also assist in the achievement of more
subtle cryptographic goals, important in the post-
cold war world, such as protecting private informa-
QUANTUM tion while it is being used to reach public decisions.
CRYPTOGRAPHY Such techniques, pioneered by Cr´ peau [10], [15],
e
allow two people to compute an agreed-upon func-
QUANTUM CRYPTOGRAPHY [A]: Quantum tion f (x, y) on private inputs x and y when one
Cryptography was born in the early 1970s when person knows x, the other knows y, and neither is
496 Quantum cryptography


willing to disclose anything about his private input may send to Bob a random bit-stream that she
to the other, except for what follows logically from knows exactly and of which Bob will randomly se-
one™s private input and the function™s output. The lect a constant fraction. These four possible states
may be the 0—¦ , 45—¦ , 90—¦ , and 135—¦ polarizations of a
classic example of such discreet decision making
is the “dating problem,” in which two people seek photon. According to quantum mechanics, orthog-
onally polarized photons ((0—¦ , 90—¦ ) or (45—¦ , 135—¦ ))
a way of making a date if and only if each likes
the other, without disclosing any further informa- are perfectly distinguishable whereas nonorthog-
onal photons ((0—¦ , 45—¦ ), (45—¦ , 90—¦ ), etc.) are not.
tion. For example, if Alice likes Bob but Bob does
not like Alice, the date should be called off without When Alice sends Bob a random state from these
Bob ¬nding out that Alice likes him. On the other four, he may choose to measure whether it is
(0—¦ , 90—¦ ) or (45—¦ , 135—¦ ). If he makes the correct mea-
hand, it is logically unavoidable for Alice to learn
that Bob does not like her, because if he did the surement then he detects perfectly the original
date would be on. state. If he makes the wrong measurement then
Indeed, two applications of quantum physics to he detects a random state among the two he was
cryptography were discovered well before quan- trying to distinguish. When Alice later tells him
tum key distribution: quantum bank notes that which was the correct measurement, he keeps the
are impossible to counterfeit and quantum mul- correctly measured states and discards the others.
tiplexing that allows one party to send two mes- Thus, in a perfect world, Bob would receive 50% of
sages to another party in a way that the receiver Alice™s photons in their exact original state and
can obtain either message at his choice, but read- discard the other 50% of the photons. If we assign
binary value 0 to 0—¦ and 45—¦ and value 1 to 90—¦ and
ing one destroys the other irreversibly [50]. (The
135—¦ , then their agreed bit-stream is obtained by
notion of multiplexing was reinvented 10 years
later by Michael Rabin in the context of classical the correctly measured 50% of the photons.
cryptography under the name of oblivious transfer However, the world is not perfect. Therefore, a
[43], [28].) Unfortunately, even its author, Stephen fraction of the correctly measured photons will
Wiesner, knew from the start that the quantum be detected incorrectly. Also, if an eavesdropper
multiplexing protocol could be defeated with arbi- (Eve) tries to measure Alice™s photons before they
trary measurements performed by the receiver of reach Bob, errors will be induced by the fact that
the strings. Thus, a more elaborate quantum obliv- she is measuring information about the photons™
ious transfer protocol was designed subsequently polarizations. Moreover, these two situations are
[10] under the assumption of the existence of a bit indistinguishable from each other: natural noise
commitment scheme [19], a result unlikely to be or induced noise looks the same. (Indeed, part
possible classically as argued by Impagliazzo and of the “natural” noise is produced by “nature”
Rudich [34]. Another quantum cryptographic task eavesdropping on Alice and Bob!) The beauty of
that has been studied extensively is indeed bit quantum cryptography is that an estimate on the
commitment [15]. Unfortunately it turned out that noise level leads to an estimate of the informa-
early claims of security of certain quantum proto- tion obtained by Eve. Consequently, a three-phase
cols for this task were after all insecure as showed classical protocol allows Alice and Bob to extract
by Mayers [39] and independently by Lo and Chau an agreed upon, smaller secret cryptographic key
[37]. This no-go theorem was later extended to from their noisy, partly eavesdropped bit-stream.
any Quantum Bit Commitment scheme consistent These three phases are called “error estimation,”
with quantum physics [40], [38]. “information reconciliation,” and “privacy ampli¬-
On a closely related topic, various Quantum cation.”
Coin Tossing protocols have been also introduced

[7] as well as a lower bound of 1/ 2 on the bias
of such a protocol in a very general quantum me- Error Estimation. Error estimation is performed
chanical framework [1]. by having one of Alice or Bob pick at random
a certain number t of bits previously transmit-
Quantum Key Distribution ted according to the correct measurement and
announce them to the other party. The latter
The purpose of quantum key distribution is to en- compares these bits with his/her own copy and an-
able two honest parties, Alice and Bob, to agree on nounces the number of errors e. For large enough
a random cryptographic key in a situation where samples, the ratio e/t should be a reasonable esti-
eavesdropping is possible. By transmitting one of mate of the fraction of errors left in the undisclosed
four possible nonorthogonal quantum states, Alice bits.
Quantum cryptography 497


Information Reconciliation. Although interactive tected by quantum mechanics even in storage,
error correction such as [16] was ¬rst encouraged rather than merely in transit. More interestingly,
in [5], Cr´ peau pointed out that traditional error-
e Ekert™s scheme can bene¬t from powerful quan-
correcting codes may be used here as well [10]. In tum techniques that were discovered only years
both cases, this process will disclose some extra in- later, such as entanglement distillation [12], [23].
formation about the remaining (corrected) bits to Prototypes of entanglement-based quantum cryp-
any potential eavesdropper. This extra informa- tography, working over kilometers of ¬ber, came
tion must be taken into account in the last privacy soon after the theoretical invention [26] as well as
ampli¬cation phase. much more recently [27].
The past decade has seen an explosion in experi-
mental demonstrations of quantum cryptography,
Privacy Ampli¬cation. Assume an eavesdropper is
with distances ever increasing, sometimes at the
left with only bits of R´ nyi (collision) entropy
e
expense of giving up the Holy Grail of uncondi-
about the bit-stream W of size n resulting from
tional security. We can mention only a few exam-
the information reconciliation phase. If Alice and
ples here. A plug-and-play device built in Switzer-
Bob can estimate from error estimation and er-
land was tested successfully using 67 km of optical
ror correction, they may produce a new smaller
¬ber laid out between Geneva and Lausanne [47].
bit-stream K of size nearly from W. Let H be a
More recent experiments achieve even further dis-
uniformly selected hash function from a Strongly
tances such as 150 km of optical ¬ber [35]. The
Universal Set [49] mapping n bits to ’ s bits.
notion of quantum repeaters has been discussed
Then we obtain a tight bound on the uncertainty
in order to achieve even greater distances [18].
H(H(W) | H, E) ¤ 2’s (see information theory for
Free-space prototypes have shown the possibility
de¬nitions) where E is the eavesdropping informa-
of line-of-sight quantum cryptography over dis-
tion (including error correction). This means that
tances of tens of kilometers [33], [36], making it
if one of Alice or Bob picks a random hash func-
legitimate to dream of a quantum-cryptographic
tion h and announces it publicly to the other, they
satellite-based global network [44]. A thorough
are able to use it to replace their longer string W
survey of quantum cryptography, with an empha-
by K = h(W) that is almost perfectly secret to the
sis on technological issues, can be found in [29]. A
eavesdropper [9] with nearly probability 1.
living roadmap of the work ahead can be obtained
in [6].
Finally, we point out that quantum key distribu-
Eavesdropping. The key distribution protocol de-
tion is now available as a commercial product. In-
scribed above has been proven secure regardless of
formation about quantum-cryptographic products
the eavesdropper™s strategy and computing power.
can be found at the Web sites of the Swiss com-
The ¬rst proof of this theorem is due to Mayers
pany id Quantique (www.idquantique.com) and
[41]. However, the very technical nature of that
the American corporation MagiQ Technologies
proof encouraged many alternate proofs to be de-
(magiqtech.com).
veloped such as those of Biham, et al. [14], Shor
and Preskill [45], Gottesman and Lo [31], etc. A
Cryptography on Quantum Data
more powerful security proof in the universal com-
posability framework was recently demonstrated
by Ben-Or, et al. [13]. The last component of quantum cryptography is
the cryptography on quantum data where cryp-
Alternative Quantum Key Distribution tographic tools are developed for information
Protocols and Implementations imbedded in quantum systems. A ¬rst example
is known as the one-time quantum pad where the
The original quantum key distribution protocol sender Alice and receiver Bob share a priori a pair
uses four different polarization states of single of maximally entangled particles and use them to
photons as carrier of quantum information [7], but teleport [8] an arbitrary qubit (quantum bit), for
other approaches have been put forward. Early example, from Alice to Bob. The only public trans-
variations were to use only two nonorthogonal mission of this scheme is a pair of classical random
states rather than four [4], and to use phase mod- bits from the sender to receiver, allowing him to
ulation rather than polarization [26], [48]. A more reconstruct the original state she wanted to com-
fundamental variation, due to Ekert [25], was to municate.
make use of Einstein“Podolsky“Rosen entangled A second example is the Quantum Vernam
pairs [24], which allows the key to remain pro- Cipher [2] where a classical key of four possible
498 Quantum cryptography


values is used by Alice who applies one of four Proceedings of the 41st IEEE Symposium on Foun-
dations of Computer Science, 547“553.
unitary (Pauli) operators to an arbitrary system
[3] Barnum, H., C. Cr´ peau, D. Gottesman, A. Smith,
e
of a single qubit that may then be transmitted
and A. Tapp (2002). “Authentication of quantum

. 1
( : 2)



. . >>