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