Lecture Notes on Cryptography

lecture notes cryptography and network security. how cryptography is applied for security, how cryptography is related with network security pdf free download
OliverFinch Profile Pic
Published Date:15-07-2017
Your Website URL(Optional)
Lecture Notes on Cryptography 1 2 Shafi Goldwasser Mihir Bellare July 2008 1 MIT Computer Science and Arti¯cial Intelligence Laboratory, The Stata Center, Building 32, 32 Vassar Street, Cambridge, MA 02139, USA. E-mail: shafitheory.lcs.mit.edu ; Web page: http://theory.lcs.mit.edu/ shafi 2 Department of Computer Science and Engineering, Mail Code 0404, University of California at San Diego, 9500 Gilman Drive, La Jolla, CA 92093, USA. E-mail: mihircs.ucsd.edu ; Web page: http://www-cse.ucsd.edu/users/mihirC h a p t e r 1 Introduction to Modern Cryptography Cryptographyisaboutcommunicationinthepresenceofanadversary. Itencompassesmanyproblems(encryp- tion, authentication, key distribution to name a few). The ¯eld of modern cryptography provides a theoretical foundation based on which we may understand what exactly these problems are, how to evaluate protocols that purport to solve them, and how to build protocols in whose security we can have con¯dence. We introduce the basic issues by discussing the problem of encryption. 1.1 Encryption: Historical Glance The most ancient and basic problem of cryptography is secure communication over an insecure channel. Party A wants to send to party B a secret message over a communication line which may be tapped by an adversary. The traditional solution to this problem is called private key encryption. In private key encryption A and B hold a meeting before the remote transmission takes place and agree on a pair of encryption and decryption algorithms E and D, and an additional piece of information S to be kept secret. We shall refer to S as the common secret key. The adversary may know the encryption and decryption algorithms E and D which are being used, but does not know S. After the initial meeting when A wants to send B the cleartext or plaintext message m over the insecure communication line, A encrypts m by computing the ciphertext c =E(S;m) and sends c to B. Upon receipt, B decrypts c by computing m =D(S;c). The line-tapper (or adversary), who does not know S, should not be able to compute m from c. Let us illustrate this general and informal setup with an example familiar to most of us from childhood, the substitution cipher. In this method A and B meet and agree on some secret permutation f:§ § (where § is the alphabet of the messages to be sent). To encrypt message m = m :::m where m 2 §, A computes 1 n i ¡1 ¡1 E(f;m)=f(m ):::f(m ). To decrypt c=c :::c where c 2§, B computesD(f;c)=f (c ):::f (c )= 1 n 1 n i 1 n m :::m = m. In this example the common secret key is the permutation f. The encryption and decryption 1 n algorithms E and D are as speci¯ed, and are known to the adversary. We note that the substitution cipher is easy to break by an adversary who sees a moderate (as a function of the size of the alphabet §) number of ciphertexts. 1 A rigorous theory of perfect secrecy based on information theory was developed by Shannon 192 in 1943. . In this theory, the adversary is assumed to have unlimited computational resources. Shannon showed that secure (properly de¯ned) encryption system can exist only if the size of the secret information S that A and B agree on prior to remote transmission is as large as the number of secret bits to be ever exchanged remotely using the encryption system. 1 Shannon's famous work on information theory was an outgrowth of his work on security (193). 1112 Goldwasser and Bellare Anexampleofaprivatekeyencryptionmethodwhichissecureeveninpresenceofacomputationallyunbounded adversary is the one time pad. A and B agree on a secret bit string pad = b b :::b , where b 2 f0;1g (i.e 1 2 n i R n pad is chosen in f0;1g with uniform probability). This is the common secret key. To encrypt a message m = m m :::m where m 2 f0;1g, A computes E(pad;m) = m©pad (bitwise exclusive or). To decrypt 1 2 n i n ciphertext c2f0;1g , B computesD(pad;c)=pad©c=pad©(m©pad)=m. It is easy to verify that8m;c 1 the Pr E(pad;m)=c = . From this, it can be argued that seeing c gives \no information" about what pad n 2 has been sent. (In the sense that the adversary's a posteriori probability of predicting m given c is no better than her a priori probability of predicting m without being given c.) 0 0 Now, suppose A wants to send B an additional message m. If A were to simply send c=E(pad;m), then the 0 sum of the lengths of messages m and m will exceed the length of the secret key pad, and thus by Shannon's 0 0 theorythesystemcannotbesecure. Indeed, theadversarycancomputeE(pad;m)©E(pad;m)=m©m which 0 gives information about m and m (e.g. can tell which bits of m and m` are equal and which are di®erent). To ¯x this, the length of the pad agreed upon a-priori should be the sum total of the length of all messages ever to be exchanged over the insecure communication line. 1.2 Modern Encryption: A Computational Complexity Based The- ory Modern cryptography abandons the assumption that the Adversary has available in¯nite computing resources, andassumesinsteadthattheadversary'scomputationisresourceboundedinsomereasonableway. Inparticular, in these notes we will assume that the adversary is a probabilistic algorithm who runs in polynomial time. Similarly, the encryption and decryption algorithms designed are probabilistic and run in polynomial time. The running time of the encryption, decryption, and the adversary algorithms are all measured as a function of a security parameter k which is a parameter which is ¯xed at the time the cryptosystem is setup. Thus, when we say that the adversary algorithm runs in polynomial time, we mean time bounded by some polynomial function in k. Accordingly, in modern cryptography, we speak of the infeasibility of breaking the encryption system and computinginformationaboutexchangedmessageswhereashistoricallyonespokeoftheimpossibility ofbreaking theencryptionsystemand¯ndinginformationaboutexchangedmessages. Wenotethattheencryptionsystems which we will describe and claim \secure" with respect to the new adversary are not \secure" with respect to a computationallyunboundedadversaryinthewaythattheone-timepadsystemwassecureagainstanunbounded adversary. But, on the other hand, it is no longer necessarily true that the size of the secret key that A and B meet and agree on before remote transmission must be as long as the total number of secret bits ever to be exchanged securely remotely. In fact, at the time of the initial meeting, A and B do not need to know in advance how many secret bits they intend to send in the future. We will show how to construct such encryption systems, for which the number of messages to be exchanged securely can be a polynomial in the length of the common secret key. How we construct them brings us to anther fundamental issue, namely that of cryptographic, or complexity, assumptions. As modern cryptography is based on a gap between e±cient algorithms for encryption for the legitimate users versus the computational infeasibility of decryption for the adversary, it requires that one have available prim- itives with certain special kinds of computational hardness properties. Of these, perhaps the most basic is a one-way function. Informally, a function is one-way if it is easy to compute but hard to invert. Other primi- tives include pseudo-random number generators, and pseudorandom function families, which we will de¯ne and discuss later. From such primitives, it is possible to build secure encryption schemes. Thus, a central issue is where these primitives come from. Although one-way functions are widely believed to exist, and there are several conjectured candidate one-way functions which are widely used, we currently do not know how to mathematically prove that they actually exist. We shall thus design cryptographic schemes assuming we are given a one-way function. We will use the conjectured candidate one-way functions for our working examples, throughout our notes. We will be explicit about what exactly can and cannot be proved and is thus assumed, attempting to keep the latter to a bare minimum.Cryptography: Lecture Notes 13 We shall elaborate on various constructions of private-key encryption algorithms later in the course. The development of public key cryptography in the seventies enables one to drop the requirement that A and 2 B must share a key in order to encrypt. The receiver B can publish authenticated information (called the public-key) for anyone including the adversary, the sender A, and any other sender to read at their convenience (e.g in a phone book). We will show encryption algorithms in which whoever can read the public key can send encrypted messages to B without ever having met B in person. The encryption system is no longer intended to be used by a pair of prespeci¯ed users, but by many senders wishing to send secret messages to a single recipient. The receiver keeps secret (to himself alone) information (called the receiver's private key) about the public-key, which enables him to decrypt the cyphertexts he receives. We call such an encryption method public key encryption. We will show that secure public key encryption is possible given a trapdoor function. Informally, a trapdoor function is a one-way function for which there exists some trapdoor information known to the receiver alone, with which the receiver can invert the function. The idea of public-key cryptosystems and trapdoor functions was introduced in the seminal work of Di±e and Hellman in 1976 71, 72. Soon after the ¯rst implementations of their idea were proposed in 176, 170, 143. A simple construction of public key encryption from trapdoor functions goes as follows. Recipient B can choose at random a trapdoor function f and its associated trapdoor information t, and set its public key to be a description of f and its private key to be t. If A wants to send message m to B, A computesE(f;m) = f(m). ¡1 ¡1 To decrypt c=f(m), B computes f (c)=f (f(m))=m. We will show that this construction is not secure enough in general, but construct probabilistic variants of it which are secure. 1.3 A Short List of Candidate One Way Functions As we said above, the most basic primitive for cryptographic applications is a one-way function which is \easy" to compute but \hard" to invert. (For public key encryption, it must also have a trapdoor.) By \easy", we mean that the function can be computed by a probabilistic polynomial time algorithm, and by \hard" that any probabilistic polynomial time (PPT) algorithm attempting to invert it will succeed with \small" probability (where the probability ranges over the elements in the domain of the function.) Thus, to qualify as a potential candidate for a one-way function, the hardness of inverting the function should not hold only on rare inputs to the function but with high probability over the inputs. Several candidates which seem to posses the above properties have been proposed. 1. Factoring. The function f : (x;y) 7 xy is conjectured to be a one way function. The asymptotically proven fastest factoring algorithms to date are variations on Dixon's random squares algorithm 131. It p p 2 lognloglogn is a randomized algorithm with running time L(n) where L(n)=e . The number ¯eld sieve by Lenstra, Lenstra, Manasee, and Pollard with modi¯cations by Adlemann and Pomerance is a factoring algorithm proved under a certain set of assumptions to factor integers in expected time 1 2 3 3 ((c+o(1))(logn) (loglogn) ) e 133, 3. ¤ 2. The discrete log problem. Let p be a prime. The multiplicative group Z = (fx pj(x;p) = 1g;¢modp) p ¤ i ¤ is cyclic, so thatZ =fg modpj1·i·p¡1g for some generator g2Z . The function f : (p;g;x)7 p p x ¤ (g modp;p;g) where p is a prime and g is a generator for Z is conjectured to be a one-way function. p Computing f(p;g;x) can be done in polynomial time using repeated squaring. However, The fastest known proved solution for its inverse, called the discrete log problem is the index-calculus algorithm, p 2 with expected running time L(p) (see 131). An interesting problem is to ¯nd an algorithm which will ¤ generate a prime p and a generator g for Z . It is not known how to ¯nd generators in polynomial time. p N However, in 8, E. Bach shows how to generate random factored integers (in a given range :::N). 2 2 Saying that the information is \authenticated" means that the sender is given a guarantee that the information was published by the legal receiver. How this can be done is discussed in a later chapter.14 Goldwasser and Bellare Coupled with a fast primality tester (as found in 131, for example), this can be used to e±ciently ¤ generate random tuples (p¡ 1;q ;:::;q ) with p prime. Then picking g 2 Z at random, it can be 1 k p p¡1 p¡1 q i checked if (g;p¡ 1) = 1, 8q , g modp = 6 1, and g modp = 1, in which case order(g) = p¡ 1 i i ¤ (order(g)=jfg modpj1·i·p¡1gj). It can be shown that the density ofZ generators is high so that p ¤ few guesses are required. The problem of e±ciently ¯nding a generator for a speci¯c Z is an intriguing p open research problem. n 3. Subset sum. Let a 2 f0;1g ;a = (a ;:::;a );s 2 f0;1g;s = (s ;:::;s ), and let f : (a;s) 7 i 1 n i 1 n P P P P n n n n 0 0 (a; s a ). An inverse of (a; s a ) under f is any (a;s ) so that s a = s a . This i i i i i i i i i i=1 i=1 i=1 i=1 function f is a candidate for a one way function. The associated decision problem (given (a;y), does P n there exists s so that s a = y?) is NP-complete. Of course, the fact that the subset-sum problem i i i=1 is NP-complete cannot serve as evidence to the one-wayness of f . On the other hand, the fact that the ss subset-sum problem is easy for special cases (such as \hidden structure" and low density) can not serve as evidence for the weakness of this proposal. The conjecture that f is one-way is based on the failure of known algorithm to handle random high density instances. Yet, one has to admit that the evidence in favor of this candidate is much weaker than the evidence in favor of the two previous ones. 4. DES with ¯xed message. Fix a 64 bit message M and de¯ne the function f(K)=DES (M) which takes K a 56 bit key K to a 64 bit output f(K). This appears to be a one-way function. Indeed, this construction can even be proven to be one-way assuming DES is a family of pseudorandom functions, as shown by Luby and Racko® 139. 5. RSA. This is a candidate one-way trapdoor function. Let N = pq be a product of two primes. It is e believed that such an N is hard to factor. The function is f(x)=x modN where e is relatively prime to (p¡1)(q¡1). The trapdoor is the primes p;q, knowledge of which allows one to invert f e±ciently. The functionf seemstobeone-way. TodatethebestattackistotrytofactorN,whichseemscomputationally infeasible. In Chapter 2 we discuss formal de¯nitions of one-way functions and are more precise about the above construc- tions. 1.4 Security De¯nitions So far we have used the terms \secure" and \break the system" quite loosely. What do we really mean? It is clear that a minimal requirement of security would be that: any adversary who can see the ciphertext and knows which encryption and decryption algorithms are being used, can not recover the entire cleartext. But, many more properties may be desirable. To name a few: 1. Itshouldbehardtorecoverthemessagesfromtheciphertextwhenthemessagesaredrawnfromarbitrary probability distributions de¯ned on the set of all strings (i.e arbitrary message spaces). A few examples of message spaces are: the English language, the set f0;1g). We must assume that the message space is known to the adversary. 2. It should be hard to compute partial information about messages from the ciphertext. 3. It should be hard to detect simple but useful facts about tra±c of messages, such as when the same message is sent twice. 4. The above properties should hold with high probability. In short, it would be desirable for the encryption scheme to be the mathematical analogy of opaque envelopes containing a piece of paper on which the message is written. The envelopes should be such that all legal senders can ¯ll it, but only the legal recipient can open it. We must answer a few questions:Cryptography: Lecture Notes 15 ² How can \opaque envelopes" be captured in a precise mathematical de¯nition? Much of Chapters 6 and 7 is dedicated to discussing the precise de¯nition of security in presence of a computationally bounded adversary. ² Are \opaque envelopes" achievable mathematically? The answer is positive . We will describe the the proposals of private (and public) encryption schemes which we prove secure under various assumptions. We note that the simple example of a public-key encryptions system based on trapdoor function, described in theprevioussection, doesnotsatisfytheaboveproperties. Wewillshowlater, however, probabilisticvariantsof thesimplesystemwhichdosatisfythenewsecurityrequirementsundertheassumptionthattrapdoorfunctions exist. More speci¯cally, we will show probabilistic variants of RSA which satisfy the new security requirement under, the assumption that the original RSA function is a trapdoor function, and are similar in e±ciency to the original RSA public-key encryption proposal. 1.5 The Model of Adversary Theentirediscussionsofarhasessentiallyassumedthattheadversarycanlistentocyphertextsbeingexchanged over the insecure channel, read the public-¯le (in the case of public-key cryptography), generate encryptions of any message on his own (for the case of public-key encryption), and perform probabilistic polynomial time computation. This is called a passive adversary. One may imagine a more powerful adversary who can intercept messages being transmitted from sender to receiverandeitherstoptheirdeliveryalltogetheroraltertheminsomeway. Evenworse,supposetheadversary can request a polynomial number of cyphertexts to be decrypted for him. We can still ask whether there exists encryption schemes (public or secret) which are secure against such more powerful adversaries. Indeed, such adversaries have been considered and encryption schemes which are secure against them designed. The de¯nition of security against such adversaries is more elaborate than for passive adversaries. In Chapters 6 and 7 we consider a passive adversary who knows the probability distribution over the message space. We will also discuss more powerful adversaries and appropriate de¯nitions of security. 1.6 Road map to Encryption To summarize the introduction, our challenge is to design both secure private-key and public-key encryption systemswhichprovablymeetourde¯nitionofsecurityandinwhichtheoperationsofencryptionanddecryption are as fast as possible for the sender and receiver. Chapters 6 and 7 embark on an in depth investigation of the topic of encryption, consisting of the following parts. For both private-key and public-key encryption, we will: ² Discuss formally how to de¯ne security in presence of a bounded adversary. ² Discuss current proposals of encryption systems and evaluate them respect to the security de¯nition chosen. ² Describe how to design encryption systems which we can prove secure under explicit assumptions such as the existence of one-way functions, trapdoor functions, or pseudo random functions. ² Discuss e±ciency aspects of encryption proposals, pointing out to possible ways to improve e±ciency by performing some computations o®-line, in batch mode, or in a incremental fashion. We will also overview some advanced topics connected to encryption such chosen-ciphertext security, non- malleability, key-escrow proposals, and the idea of shared decryption among many users of a network.C h a p t e r 2 One-way and trapdoor functions One Way functions, namely functions that are \easy" to compute and \hard" to invert, are an extremely important cryptographic primitive. Probably the best known and simplest use of one-way functions, is for passwords. Namely, in a time-shared computer system, instead of storing a table of login passwords, one can store, for each password w, the value f(w). Passwords can easily be checked for correctness at login, but even the system administrator can not deduce any user's password by examining the stored table. In Section 1.3 we had provided a short list of some candidate one-way functions. We now develop a theoretical treatment of the subject of one-way and trapdoor functions, and carefully examine the candidate one-way functions proposed in the literature. We will occasionaly refer to facts about number theory discussed in Chapter C. We begin by explaining why one-way functions are of fundamental importance to cryptography. 2.1 One-Way Functions: Motivation In this section, we provide motivation to the de¯nition of one-way functions. We argue that the existence of one-way functions is a necessary condition to the existence of most known cryptographic primitives (including secureencryptionanddigitalsignatures). Asthecurrentstateofknowledgeincomplexitytheorydoesnotallow to prove the existence of one-way function, even using more traditional assumptions as P 6=NP, we will have to assume the existence of one-way functions. We will later try to provide evidence to the plausibility of this assumption. As stated in the introduction chapter, modern cryptography is based on a gap between e±cient algorithms guaranteed for the legitimate user versus the unfeasibility of retrieving protected information for an adver- sary. To make the following discussion more clear, let us concentrate on the cryptographic task of secure data communication, namely encryption schemes. In secure encryption schemes, the legitimate user is able to decipher the messages (using some private infor- mation available to him), yet for an adversary (not having this private information) the task of decrypting the ciphertext(i.e., \breaking"theencryption)shouldbeinfeasible. Clearly, thebreakingtaskcanbeperformedby a non-deterministic polynomial-time machine. Yet, the security requirement states that breaking should not be feasible, namelycouldnotbeperformedbyaprobabilisticpolynomial-timemachine. Hence, theexistenceofse- cure encryption schemes implies that there are tasks performed by non-deterministic polynomial-time machines yet cannot be performed by deterministic (or even randomized) polynomial-time machines. In other words, a necessary condition for the existence of secure encryption schemes is that NP is not contained in BPP (and hence thatP 6=NP). However, theabovementionednecessarycondition(e.g.,P 6=NP)isnotasu±cientone. P 6=NP onlyimplies 16Cryptography: Lecture Notes 17 that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct \encryption schemes" forwhichthebreakingproblemisNP-completeandyetthereexistane±cientbreakingalgorithmthatsucceeds on 99% of the cases. Hence, worst-case hardness is a poor measure of security. Security requires hardness on mostcasesoratleastaverage-casehardness. Hence, anecessaryconditionfortheexistenceofsecureencryption schemes is the existence of languages in NP which are hard on the average. Furthermore, P 6= NP is not known to imply the existence of languages in NP which are hard on the average. The mere existence of problems (in NP) which are hard on the average does not su±ce. In order to be able to use such problems we must be able to generate such hard instances together with auxiliary information which enable to solve these instances fast. Otherwise, the hard instances will be hard also for the legitimate users and they gain no computational advantage over the adversary. Hence, the existence of secure encryption schemes implies the existence of an e±cient way (i.e. probabilistic polynomial-time algorithm) of generating instances with corresponding auxiliary input so that (1) it is easy to solve these instances given the auxiliary input; and (2) it is hard on the average to solve these instances (when not given the auxiliary input). We avoid formulating the above \de¯nition". We only remark that the coin tosses used in order to generate the instance provide su±cient information to allow to e±ciently solve the instance (as in item (1) above). Hence, without loss of generality one can replace condition (2) by requiring that these coin tosses are hard to retrieve from the instance. The last simpli¯cation of the above conditions essentially leads to the de¯nition of a one-way function. 2.2 One-Way Functions: De¯nitions In this section, we present several de¯nitions of one-way functions. The ¯rst version, hereafter referred to as strong one-way function (or just one-way function), is the most convenient one. We also present weak one-way functionswhichmaybeeasierto¯ndandyetcanbeusedtoconstructstrongonewayfunctios,andnon-uniform one-way functions. 2.2.1 (Strong) One Way Functions The most basic primitive for cryptographic applications is a one-way function. Informally, this is a function which is \easy" to compute but \hard" to invert. Namely, any probabilistic polynomial time (PPT) algorithm attemptingtoinverttheone-wayfunctiononaelementinitsrange, willsucceedwithnomorethan\negligible" probability, where the probability is taken over the elements in the domain of the function and the coin tosses of the PPT attempting the inversion. Thisinformalde¯nitionintroducesacoupleofmeasuresthatareprevalentincomplexitytheoreticcryptography. AneasycomputationisonewhichcanbecarriedoutbyaPPTalgorithm; andafunction º: NRisnegligible if it vanishes faster than the inverse of any polynomial. More formally, ¡c De¯nition 2.1 º is negligible if for every constant c¸0 there exists an integer k such that º(k)k for all c k¸k . c ¡(1) Another way to think of it is º(k)=k . A few words, concerning the notion of negligible probability, are in place. The above de¯nition and discussion considers the success probability of an algorithm to be negligible if as a function of the input length the success probability is bounded by any polynomial fraction. It follows that repeating the algorithm polynomially (in the input length) many times yields a new algorithm that also has a negligible success probability. In other words, events which occur with negligible (in n) probability remain negligible even if the experiment is repeated for polynomially (in k) many times. Hence, de¯ning negligible success as \occurring with probability smaller than any polynomial fraction" is naturally coupled with de¯ning feasible as \computed within polynomial18 Goldwasser and Bellare time". A \strong negation" of the notion of a negligible fraction/probability is the notion of a non-negligible fraction/probability. we say that a function º is non-negligible if there exists a polynomial p such that for all 1 su±ciently large k's it holds that º(k) . Note that functions may be neither negligible nor non-negligible. p(k) ¤ ¤ De¯nition 2.2 A function f:f0;1g f0;1g is one-way if: (1) there exists a PPT that on input x output f(x); (2) For every PPT algorithm A there is a negligible function º such that for su±ciently large k, A h i k k Pr f(z)=y : xÃf0;1g ; yÃf(x) ; zÃA(1 ;y) · º (k) A Remark 2.3 The guarantee is probabilistic. The adversary is not unable to invert the function, but has a low probability of doing so where the probability distribution is taken over the input x to the one-way function where x if of length k, and the possible coin tosses of the adversary. Namely, x is chosen at random and y is set to f(x). Remark 2.4 The advsersary is not asked to ¯nd x; that would be pretty near impossible. It is asked to ¯nd some inverse of y. Naturally, if the function is 1-1 then the only inverse is x. k Remark 2.5 Note that the adversary algorithm takes as input f(x) and the security parameter 1 (expressed in unary notatin) which corresponds to the binary length of x. This represents the fact the adversary can work in time polynomial in jxj, even if f(x) happends to be much shorter. This rules out the possibility that a function is considered one-way merely because the inverting algorithm does not have enough time to print the output. Consider for example the function de¯ned as f(x) = y where y is the logk least signi¯cant bits of x wherejxj=k. Since thejf(x)j=logjxj no algorithm can invert f in time polynomial injf(x)j, yet there exists an obvious algorithm which ¯nds an inverse of f(x) in time polynomial in jxj. Note that in the special case of length preserving functions f (i.e.,jf(x)j=jxj for all x's), the auxiliary input is redundant. Remark 2.6 By this de¯nition it trivially follows that the size of the output of f is bounded by a polynomial in k, since f(x) is a poly-time computable. Remark 2.7 The de¯nition which is typical to de¯nitions from computational complexity theory, works with asymptotic complexitywhat happens as the size of the problem becomes large. Security is only asked to hold for large enough input lengths, namely as k goes to in¯nity. Per this de¯nition, it may be entirely feasible to invert f on, say, 512 bit inputs. Thus such de¯nitions are less directly relevant to practice, but useful for studying things on a basic level. To apply this de¯nition to practice in cryptography we must typically envisage not a single one-way function but a family of them, parameterized by a security parameter k. That is, for each k ¤ value of the security parameter k there is be a speci¯c function f :f0;1g f0;1g . Or, there may be a family of functions (or cryptosystems) for each value of k. We shall de¯ne such familes in subsequent section. The next two sections discuss variants of the strong one-way function de¯nition. The ¯rst time reader is encouraged to directly go to Section 2.2.4. 2.2.2 Weak One-Way Functions One way functions come in two °avors: strong and weak. The de¯nition we gave above, refers to a strong way function. We could weaken it by replacing the second requirement in the de¯nition of the function by a weaker requirement as follows. ¤ ¤ De¯nition 2.8 A function f:f0;1g f0;1g is weak one-way if:Cryptography: Lecture Notes 19 (1) there exists a PPT that on input x output f(x); (2) There is a polynomial functions Q such that for every PPT algorithm A, and for su±ciently large k, h i 1 k k Pr f(z)= 6 y : xÃf0;1g ; yÃf(x) ; zÃA(1 ;y) ¸ Q(k) The di®erence between the two de¯nitions is that whereas we only require some non-negligible fraction of the inputs on which it is hard to invert a weak one-way function, a strong one-way function must be hard to invert on all but a negligible fraction of the inputs. Clearly, the latter is preferable, but what if only weak one-way functions exist ? Our ¯rst theorem is that the existence of a weak one way function implies the existence of a strong one way function. Moreover, we show how to construct a strong one-way function from a weak one. This is important in practice as illustarted by the following example. Example 2.9 Consider for example the function f : Z£Z7 Z where f(x;y) = x¢y. This function can be easily inverted on at least half of its outputs (namely, on the even integers) and thus is not a strong one way function. Still, we said in the ¯rst lecture that f is hard to invert when x and y are primes of roughly the same length which is the case for a polynomial fraction of the k-bit composite integers. This motivated the de¯nition of a weak one way function. Since the probability that an k-bit integer x is prime is approximately 1=k, we get 2 the probability that both x and y such that jxj = jyj = k are prime is approximately 1=k . Thus, for all k, 1 about 1¡ of the inputs to f of length 2k are prime pairs of equal length. It is believed that no adversary 2 k can invert f when x and y are primes of the same length with non-negligible success probability, and under this 2 belief, f is a weak one way function (as condition 2 in the above de¯nition is satis¯ed for Q(k)=O(k )). Theorem 2.10 Weak one way functions exist if and only if strong one way functions exist. Proof Sketch: By de¯nition, a strong one way function is a weak one way function. Now assume that f is a weakonewayfunctionsuchthatQisthepolynomialincondition2inthede¯nitionofaweakonewayfunction. De¯ne the function f (x :::x )=f(x ):::f(x ) 1 1 N 1 N where N =2kQ(k) and each x is of length k. i We claim that f is a strong one way function. Since f is a concatenation of N copies of the function f, to 1 1 correctly invert f , we need to invert f(x ) correctly for each i. We know that every adversary has a probability 1 i 1 k of at least to fail to invert f(x) (where the probability is taken over x2f0;1g and the coin tosses of the Q(k) adversary), and so intuitively, to invert f we need to invert O(kQ(k)) instances of f. The probability that the 1 adversary will fail for at least one of these instances is extremely high. Theformalproof(whichisomittedhereandwillbegiveninappendix)willtaketheformofareduction; thatis, we will assume for contradiction that f is not a strong one way function and that there exists some adversary 1 A that violates condition 2 in the de¯nition of a strong one way function. We will then show that A can be 1 1 used as a subroutine by a new adversary A that will be able to invert the original function f with probability 1 k better than 1¡ (where the probability is taken over the inputs x2f0;1g and the coin tosses of A). But Q(jxj) this will mean that f is not a weak one way function and we have derived a contradiction. This proof technique is quite typical of proofs presented in this course. Whenever such a proof is presented it is important to examine the cost of the reduction. For example, the construction we have just outlined is not length preserving, but expands the size of the input to the function quadratically. 2.2.3 Non-Uniform One-Way Functions In the above two de¯nitions of one-way functions the inverting algorithm is probabilistic polynomial-time. Stronger versions of both de¯nitions require that the functions cannot be inverted even by non-uniform families20 Goldwasser and Bellare of polynomial size algorithm We stress that the \easy to compute" condition is still stated in terms of uniform algorithms. For example, following is a non-uniform version of the de¯nition of (strong) one-way functions. De¯nition 2.11 A function f is called non-uniformly strong one-way if the following two conditions hold (1) easy to compute: as before There exists a PPT algorithm to compute for f. (2) hard to invert: For every (even non-uniform) family of polynomial-size algorithms A = fM g , there k k2N exists a negligble º such that for all su±ciently large k's A h i k Pr f(z)6=y : xÃf0;1g ; yÃf(x) ; zÃM (y) · º (k) k A k Note that it is redundent to give 1 as an auxiliary input to M . k Itcanbeshownthatiff isnon-uniformlyone-waythenitis(strongly)one-way(i.e., intheuniformsense). The proof follows by converting any (uniform) probabilistic polynomial-time inverting algorithm into a non-uniform 0 family of polynomial-size algorithm, without decreasing the success probability. Details follow. Let A be a 0 probabilistic polynomial-time (inverting) algorithm. Let r denote a sequence of coin tosses for A maximizing k 0 0 thesuccessprobabilityof A. Thedesiredalgorithm M incorporatesthecodeofalgorithm A andthesequence k r (which is of length polynomial in k). k It is possible, yet not very plausible, that strongly one-way functions exist and but there are no non-uniformly one-way functions. 2.2.4 Collections Of One Way Functions ¤ ¤ Instead of talking about a single function f :f0;1g f0;1g , it is often convenient to talk about collections of functions, each de¯ned over some ¯nite domain and ¯nite ranges. We remark, however, that the single function format makes it easier to prove properties about one way functions. De¯nition 2.12 Let I be a set of indices and for i2I let D and R be ¯nite. A collection of strong one way i i functions is a set F =ff :D Rg satisfying the following conditions. i i i i2I k k (1) There exists a PPT S which on input 1 outputs an i2f0;1g \I 1 (2) There exists a PPT S which on input i2I outputs x2D 2 i (3) There exists a PPT A such that for i2I and x2D , A (i;x)=f (x). 1 i 1 i (4) For every PPT A there exists a negligible º such that8 k large enough A h i Pr f (z)=y : iÃI ; xÃD ; yÃf (x) ; zÃA(i;y) · º (k) i i i A (here the probability is taken over choices of i and x, and the coin tosses of A). In general, we can show that the existence of a single one way function is equivalent to the existence of a collection of one way functions. We prove this next. Theorem 2.13 A collection of one way functions exists if and only if one way functions exist. Proof: Suppose that f is a one way function. ¤ jij Set F = ff : D Rg where I = f0;1g and for i 2 I, take D = R = f0;1g and f (x) = f(x). i i i i2I i i i k k jij Furthermore, S uniformly chooses on input 1 , i2f0;1g , S uniformly chooses on input i, x2D =f0;1g 1 2 iCryptography: Lecture Notes 21 and A (i;x) = f (x) = f(x). (Note that f is polynomial time computable.) Condition 4 in the de¯nition of a 1 i collection of one way functions clearly follows from the similar condition for f to be a one way function. k Now suppose that F = ff : D Rg is a collection of one way functions. De¯ne f (1 ;r ;r ) = i i i i2I F 1 2 k k A (S (1 ;r );S (S (1 ;r );r )) where A , S , and S are the functions associated with F as de¯ned in De¯ni- 1 1 1 2 1 1 2 1 1 2 k tion 2.12. In other words, f takes as input a string 1 ±r ±r where r and r will be the coin tosses of S F 1 2 1 2 1 and S , respectively, and then 2 k k ² Runs S on input 1 using the coin tosses r to get the index i=S (1 ;r ) of a function f 2F. 1 1 1 1 i ² Runs S on the output i of S using the coin tosses r to ¯nd an input x=S (i;r ). 2 1 2 2 2 k ² Runs A on i and x to compute f (1 ;r ;r )=A (i;x)=f (x). 1 F 1 2 1 i Note that randomization has been restricted to the input of f and since A is computable in polynomial time, F 1 the conditions of a one way function are clearly met. A possible example is the following, treated thoroughly in Section 2.3. Example 2.14 The hardness of computing discrete logarithms yields the following collection of functions. i ¤ De¯ne EXP =fEXP (i) = g mod p; EXPp;g : Z Z g for I =f p;g p prime, g generator p;g p p;g2I p ¤ for Z g. p 2.2.5 Trapdoor Functions and Collections Infromally, atrapdoor function f isaone-wayfunctionwithanextraproperty. Therealsoexistsasecretinverse function(thetrapdoor)thatallowsitspossessortoe±cientlyinvert f atanypointinthedomainofhischoosing. It should be easy to compute f on any point, but infeasible to invert f on any point without knowledge of the inverse function . Moreover, it should be easy to generate matched pairs of f's and corresponding trapdoor. Once a matched pair is generated, the publication of f should not reveal anything about how to compute its inverse on any point. ¤ ¤ De¯nition 2.15 A trapdoor function is a one-way function f : f0;1g f0;1g such that there exists a ¤ polynomial p and a probabilistic polynomial time algorithm I such that for every k there exists an t 2f0;1g k ¤ such thatjt j·p(k) and for all x2f0;1g , I(f(x);t )=y such that f(y)=f(x). k k An example of a function which may be trapdoor if factoring integers is hard was proposed by Rabin170. Let 2 ¤ f(x;n) = x modn where n = pq a product of two primes and x 2 Z . Rabin170 has shown that inverting n f is easy i® factoring composite numbers product of two primes is easy. The most famous candidate trapdoor l function is the RSA176 function f(x;n;l)=x modn where (l;Á(n))=1. Again it will be more convenient to speak of families of trapdoor functions parameterized by security parameter k. De¯nition 2.16 LetI be a set of indices and for i2I letD be ¯nite. A collection of strong one way trapdoor i functions is a set F =ff :D Dg satisfying the following conditions. i i i i2I k k (1) There exists a polynomial p and a PTM S which on input 1 outputs pairs (i;t ) where i2 I\f0;1g 1 i andjtjp(k) The information t is referred to as the trapdoor of i. i i (2) There exists a PTM S which on input i2I outputs x2D 2 i (3) There exists a PTM A such that for i2I, x2D A (i;x)=f (x). 1 i 1 i (4) There exists a PTM A such that A (i;t ;f (x)) = x for all x2D and for all i2I (that is, f is easy to 2 2 i i i i invert when t is known). i22 Goldwasser and Bellare (5) For every PPT A there exists a negligble º such that8 k large enough A h i Pr f (z)=y : iÃI ; xÃD ; yÃf (x) ; zÃA(i;y) · º (k) i i i A A possible example is the following treated in in detail in the next sections. ¤ Example 2.17 TheRSAcollectionsofpossibletrapdoorfunctionsLetp;q denoteprimes,n=pq,Z =f1· n x· n;(x;n) = 1g the multiplicative group whose cardinality is '(n) = (p¡1)(q¡1), and e2 Z relatively p¡1 prime to '(n). Our set of indices will be I =fn;e such that n=pq jpj=jqjg and the trapdoor associated ¤ ¤ withtheparticularindexn;ebedsuchthated=1modÁ(n). LetRSA=fRSA :Z Z g n;e n;e2I n n e where RSA (x)=x mod n n;e 2.3 In Search of Examples Number theory provides a source of candidates for one way and trapdoor functions. Let us start our search for examples by a digression into number theorey. See also the mini-course on number theory in Appendix C. ¤ Calculating Inverses in Z p ¤ ¤ Consider the set Z =fx : 1· x p and gcd(x;p) = 1g where p is prime. Z is a group under multiplicaton p p ¤ ¤ modulo p. Note that to ¯nd the inverse of x2Z ; that is, an element y2Z such that yx´ 1modp, we can p p use the Euclidean algorithm to ¯nd integers y and z such that yx+zp = 1 = gcd(x;p). Then, it follows that yx´1modp and so y modp is the desired inverse. The Euler Totient Function '(n) Euler's Totient Function ' is de¯ned by '(n) = jfx : 1 · x p and gcd(x;n) = 1g. The following are facts about '. ® ®¡1 (1) For p a prime and ®¸1, '(p )=p (p¡1). (2) For integers m;n with gcd(m;n)=1, '(mn)='(m)'(n). Using the rules above, we can ¯nd ' for any n because, in general, k Y ® i '(n) = '( p ) i i=1 k Y ® i = '(p ) i i=1 k Y ® ¡1 i = p (p ¡1) i i i=1 ¤ Z Is Cyclic p A group G is cyclic if and only if there is an element g2G such that for every a2G, there is an integer i such i that g =a. We call g a generator of the group G and we denote the index i by ind (a). gCryptography: Lecture Notes 23 ¤ Theorem 2.18 (Gauss) If p is prime then Z is a cyclic group of order p¡1. That is, there is an element p ¤ p¡1 i g2Z such that g ´1modp and g 6´1modp for ip¡1. p From Theorem 2.18 the following fact is immediate. ¤ ¤ Fact 2.19 Given a prime p, a generator g for Z , and an element a2Z , there is a unique 1·i·p¡1 such p p i that a=g . The Legendre Symbol ¤ Fact 2.20 If p is a prime and g is a generator of Z , then p c a b g =g g modp,c=a+bmodp¡1 ¤ From this fact it follows that there is an homomorphism f : Z Z such that f(ab)=f(a)+f(b). As p¡1 p ¤ a result we can work with Z rather than Z which sometimes simpli¯es matters. For example, suppose we p¡1 p ¤ wish to determine how many elements in Z are perfect squares (these elements will be referred to as quadratic p 1 ¤ residues modulo p). The following lemma tells us that the number of quadratic residues modulo p is jZ j. p 2 ¤ x Lemma 2.21 a2Z isaquadraticresiduemodulopifandonlyifa=g modpwherexsatis¯es1·x·p¡1 p and is even. ¤ Proof: Let g be a generator in Z . p 2x 2 x (() Suppose an element a=g for some x. Then a=s where s=g . y 2 2y e ()) Consider the square of an element b=g . b =g ´g modp where e is even since 2y is reduced modulo e p¡1 which is even. Therefore, only those elements which can be expressed as g , for e an even integer, are squares. ¤ Consequently, the number of quadratic residues modulo p is the number of elements in Z which are an even p 1 ¤ power of some given generator g. This number is clearly jZ j. p 2 ¤ The Legendre Symbol J (x) speci¯es whether x is a perfect square in Z where p is a prime. p p 8 ¤ 1 if x is a square in Z p J (x)= 0 if gcd(x;p)= 6 1 p : ¤ ¡1 if x is not a square in Z p The Legendre Symbol can be calculated in polynomial time due to the following theorem. p¡1 2 Theorem 2.22 Euler's Criterion J (x)´x modp. p p¡1 3 2 Using repeated doubling to compute exponentials, one can calculate x in O(jpj ) steps. Though this J (x) p canbecalculatedwhenpisaprime, itisnotknownhowtodetermineforgeneral xandn, whetherxisasquare ¤ in Z . n 2.3.1 The Discrete Logarithm Function x Let EXP be the function de¯ned by EXP(p;g;x) = (p;g;g modp). We are particularly interested in the case ¤ ¤ whenpisaprimeandgisageneratorofZ . DeineanindexsetI =f(p;g):p is prime and g is a generator of Z g. p p For (p;g) 2 I, it follows by Fact 2.19 that EXP(p;g;x) has a unique inverse and this allows us to de¯ne for24 Goldwasser and Bellare ¤ x y2Z the discrete logarithm function DL by DL(p;g;y) = (p;g;x) where x2Z and g ´ y modp. Given p¡1 p p and g, EXP(p;g;x) can easily be computed in polynomial time. However, it is unknown whether or not its inverse DL can be computed in polynomial time unless p¡1 has very small factors (see 164). Pohlig and Hellman 164 present e®ective techniques for this problem when p¡1 has only small prime factors. The best fully proved up-to-date algorithm for computing discrete logs is the Index-calculus algorithm. The p klogk expectedrunningtimeofsuchalgorithmispolynomialin e wherek isthesizeofthemodulos p. Thereis arecentvariantofthenumber ¯eldsievealgorithmfordiscretelogarithmwhichseemstoworkinfasterrunning 1 3 (klogk) k time of e . It interesting to note that working over the ¯nite ¯eld GF(2 ) rather than working modulo p seemstomaketheproblemsubstantiallyeasier(seeCoppersmith61andOdlyzko158). Curiously,computing discrete logarithms and factoring integers seem to have essentially the same di±culty at least as indicated by the current state of the art algorithms. Withallthisinmind,weconsiderEXPagoodcandidateforaonewayfunction. Wemakethefollowingexplicit assumptioninthisdirection. Theassumptionbasicallysaysthatthereexistsnopolynomialtimealgorithmthat can solvethe discrete log problem with prime modulos. 1 Strong Discrete Logarithm Assumption (DLA): For every polynomial Q and every PPT A, for all su±ciently large k, 1 x PrA(p;g;y)=x such that y´g modp where 1·x·p¡1 Q(k) ¤ ¤ (where the probability is taken over all primes p such thatjpj·k, the generators g of Z , x2Z and the coin p p tosses of A). An immediate consequence of this assumption we get Theorem 2.23 Underthestrongdiscretelogarithmassumptionthereexistsastrongonewayfunction;namely, exponentiation modulo a prime p. Some useful properties of EXP and DL follow. ¤ Remark 2.24 If DL(p;g ;y) is easy to calculate for some generator g 2 Z then it is also easy to calculate 1 1 p ¤ ¤ DL(p;g ;y) for any other generator g 2 Z . (The group Z has '(p¡1) generators.) To see this suppose 2 2 p p z x z 2 that x = DL(p;g ;y) and x = DL(p;g ;y). If g ´g modp where gcd(z;p¡1) then y ´ g modp and 1 1 2 2 2 1 1 ¡1 consequently, x ´z x modp¡1. 2 1 Thefollowingresultshowsthattoe±cientlycalculateDL(p;g;y)for(p;g)2I itwillsu±ceto¯ndapolynomial 1 ¤ time algorithm which can calculate DL(p;g;y) on at least a fraction of the possible inputs y 2 Z for p Q(jpj) some polynomial Q. Proposition 2.25 Let ², ±2(0;1) and let S be a subset of the prime integers. Suppose there is a probabilistic ¤ algorithm A such that for all primes p2S and for all generators g of Z p x PrA(p;g;y)=x such that g ´y modp² ¤ (wheretheprobabilityistakenover y2Z andthecointossesofA)andArunsintimepolynomialinjpj. Then p 0 ¡1 ¡1 there is a probabilistic algorithm A running in time polynomial in ² ;± , and jpj such that for all primes 1 We note that a weaker assumption can be made concerning the discrete logarithm problem, and by the standard construction one can still construct a strong one-way function. We will assume for the purpose of the course the ¯rst stronger assumption. Weak Discrete Logarithm Assumption: There is a polynomial Q such that for every PTM A there exists an integer k such 0 x 1 that 8k k PrA(p;g;y) = x such that y ´ g modp where 1· x· p¡1 1¡ (where the probability is taken over all 0 Q(k) ¤ ¤ primes p such thatjpj·k, the generators g of Z , x2Z and the coin tosses of A). p pCryptography: Lecture Notes 25 ¤ ¤ p2S, generators g of Z , and y2Z p p 0 x PrA(p;g;y)=x such that g ´y modp1¡± 0 (where the probability is taken over the coin tosses of A ). 1 Proof: Choose the smallest integer N for which ±. N e 0 ¤ ¤ Consider the algorithm A running as follows on inputs p2S, g a generator of Z and y2Z . p p ¡1 Repeat ² N times. Randomly choose z such that 1·z·p¡1. z Let w =A(p;g;g y) w z z+x If A succeeds then g =g y =g modp where x=DL (y) p;g and therefore DL (y)=w¡z modp¡1. p;g Otherwise, continue to next iteration. End loop 0 We can estimate the probability that A fails: ¡1 0 0 ² N PrA(p;g;y) fails =PrA single iteration of the loop of A fails ¡1 ² N (1¡²) ¡N (e ) ± ¡1 ¡1 0 Note that since N = O(log(± )) = O(± ), A is a probabilistic algorithm which runs in time polynomial in ¡1 ¡1 ² , ± , andjpj. The discrete logarithm problem also yields the following collection of functions. ¤ Let I =f(p;g):p is prime and g is a generator of Z g and de¯ne p ¤ x EXP=fEXP :Z Z where EXP (x)=g mod pg : p;g p¡1 p;g (p;g)2I p Then, under the strong discrete logarithm assumption, EXP is a collection of strong one way functions. This claim will be shown to be true next. Theorem 2.26 Under the strong discrete logarithm assumption there exists a collection of strong one way functions. Proof: We shall show that under the DLA EXP is indeed a collection of one way functions. For this we must show that it satis¯es each of the conditions in the de¯nition of a collection of one way functions. k For condition 1, de¯ne S to run as follows on input 1 . 1 (1) RunBach'salgorithm(givenin8)togetarandomintegernsuchthatjnj=k alongwithitsfactorization. (2) Test whether n+1 is prime. See primality testing in section C.9. ¤ (3) If so, let p=n+1. Given the prime factorization of p¡1 we look for generators g of Z as follows. p ¤ (1) Choose g2Z at random. p26 Goldwasser and Bellare Y p¡1 ® i q i (2) If p¡1= q is the prime factorization of p¡1 then for each q check that g 6´1modp. i i i ¤ If so, then g is a generator of Z . Output p and g. p Otherwise, repeat from step 1. p¡1 ¤ q Claim 2.27 g is a generator of Z if for each prime divisor q of p¡1, g 6´1modp. p ¤ p¡1 j Proof: The element g is a generator ofZ ifg ´1modp andg 6´1modp for all j such that 1·j p¡1; p ¤ that is, g has order p¡1 in Z . p ¤ Now, suppose that g satis¯es the condition of Claim 2.27 and let m be the order of g in Z . Then mj p¡1. p p¡1 p¡1 If m p¡1 then there exists a prime q such that mj ; that is, there is an integer d such that md = . q q p¡1 m d ¤ q Therefore g =(g ) ´1modn contradicting the hypothesis. Hence, m=p¡1 and g is a generator of Z . p ¤ Also, note that the number of generators in Z is '(p¡1) and in 178 it is shown that p k '(k) : 6loglogk Thus we expect to have to choose O(loglogp) candidates for g before we obtain a generator. Hence, S runs in 1 expected polynomial time. Forcondition2inthede¯nitionofacollectionofonewayfunctions,wecande¯ne S tosimplyoutputx2Z 2 p¡1 at random given i=(p;g). x Condition 3 is true since the computation of g modp can be performed in polynomial time and condition 4 follows from the strong discrete logarithm assumption. 2.3.2 The RSA function In1977Rivest,Shamir,andAdleman176proposedtrapdoorfunctioncandidatemotivatedby¯ndingapublic- key cryptosystem satisfying the requirements proposed by Di±e and Hellman. The trapdoor function proposed e is RSA(n;e;x) = x modn where the case of interest is that n is the product of two large primes p and q and gcd(e;Á(n))=1. The corresponding trapdoor information is d such that d¢e´1modÁ(n). ¤ ¤ e Viewd as a collection, let RSA =fRSA :Z Z where RSA (x) = x modng : for I =f n;e n;e n;e n n (n;e)2I s.t. n=pq jpj=jqj;(e;Á(n))=1g . RSA is easy to compute. How hard is it to invert? We know that if we can factor n we can invert RSA via the Chinese Remainder Theorem, however we don't know if the converse is true. Thus far, the best way known to invert RSA is to ¯rst factor n. There are a variety of algorithms for this task. The best running p lognloglogn time for a fully proved algorithm is Dixon's random squares algorithms which runs in time O(e ). In practice we may consider others. Let ` =jpj where p is the smallest prime divisor of n. The Elliptic Curve p p 2`log` lnnlnlnn algorithm takes expected time O(e ). The Quadratic Sieve algorithm runs in expected O(e ). Notice the di®erence in the argument of the superpolynomial component of the running time. This means that when we suspect that one prime factor is substantially smaller than the other, we should use the Elliptic Curve method, otherwise one should use the Quadratic sieve. The new number ¯eld sieve algorithm seems to achieve 1=3 2=3 1:9(lnn) (lnlnn) a O(e ) running time which is a substantial improvement asymptotically although in practice it still does not seem to run faster than the Quadratic Sieve algorithm for the size of integers which people currently attempt to factor. The recommended size for n these days is 1024 bits.Cryptography: Lecture Notes 27 Withallthisinmind,wemakeanexplicitassumptionunderwhichonecanprovethatRSAprovidesacollection of trapdoor functions. 2 Strong RSA Assumption: Let H = fn = pq : p 6= q are primes andjpj = jqj = kg. Then for every k polynomial Q and every PTM A, there exists an integer k such that8k k 0 0 1 PrA(n;e;RSA (x))=x n;e Q(k) ¤ (where the probability is taken over all n2H , e such that gcd(e;'(n))=1, x2Z , and the coin tosses of A). k n We need to prove some auxilary claims. ¤ Claim 2.28 For (n;e)2I, RSA is a permutation over Z . n;e n ¤ Proof: Since gcd(e;'(n))=1 there exists an integer d such that ed´1mod'(n). Given x2Z , consider the n d ¤ d d e ed ¤ ¤ element x 2Z . Then RSA (x )´ (x ) ´ x ´ xmodn. Thus, the function RSA :Z ¡Z is onto n;e n;e n n n ¤ ¤ and sincejZ j is ¯nite it follows that RSA is a permutation over Z . n;e n n Remark 2.29 NotethattheaboveisaconstructiveproofthatRSAhasanuniqueinverse. Sincegcd(e;'(n))= ¤ 1 if we run the extended Euclidean algorithm we can ¯nd d2Z such that n ¡1 e d ed RSA (x)=(x modn) modn=x modn=xmodn n;e . Note that once we found a d such that ed´ 1mod'(n) then we can invert RSA e±ciently because then n;e d ed RSA (x) ´x ´xmod'(n). n;e Theorem 2.30 Under the strong RSA assumption, RSA is a collection of strong one way trapdoor permuta- tions. ¤ Proof:FirstnotethatbyClaim2.28,RSA isapermutationofZ . WemustalsoshowthatRSAsatis¯eseach n;e n k k oftheconditionsinDe¯nition2.16. Forcondition1,de¯ne S tocompute,oninput1 ,apair(n;e)2I\f0;1g 1 and corresponding d such that ed ´ 1mod'(n). The algorithm picks two random primes of equal size by choosing random numbers and testing them for primality and setting n to be their procuct, then e2 Z is Á(n) chosen at random, and ¯nally d is computed in polynomial time by ¯rst computing '(n) = (p¡1)(q¡1) and ¤ then using the extended Euclidean algorithm. For condition 2, de¯ne S to randomly generate x2Z on input 2 n (n;e). Let A ((n;e);x) = RSA (x). Note that exponentiation modulo n is a polynomial time computation 1 n;e and therefore condition 3 holds. Condition 4 follows from the Strong RSA assumption. For condition 5, let d ed A ((n;e);d;RSA (x))´RSA (x) ´x ´xmodn and this is a polynomial time computation. 2 n;e n;e One of the properties of the RSA function is that if we have a polynomial time algorithm that inverts RSA n;e ¤ on at least a polynomial proportion of the possible inputs x 2 Z then a subsequent probabilistic expected n ¤ polynomial time algorithm can be found which inverts RSA on almost all inputs x2Z . This can be taken n;e n to mean that for a given n;e if the function is hard to invert then it is almost everywhere hard to invert. Proposition 2.31 Let ², ± 2 (0;1) and let S µ I. Suppose there is a probabilistic algorithm A such that for all (n;e)2S PrA(n;e;RSA (x))=x² n;e 2 A weaker assumption can be made which under standard constructions is equivalent to the stronger one which is made in this class. Weak RSA Assumption: Let H =fn = pq : p6= q are prime andjpj =jqj = kg. There is a polynomial Q such that for k 1 every PTM A, there exists an integer k such that8k k PrA(n;e;RSA (x))=x1¡ (where the probability is taken 0 0 n;e Q(k) ¤ over all n2H , e such that gcd(e;'(n))=1, x2Z , and the coin tosses of A). k n28 Goldwasser and Bellare ¤ (where the probability is taken over x 2 Z and the coin tosses of A) and A runs in time polynomial in jnj. n 0 ¡1 ¡1 Then there is a probabilistic algorithm A running in time polynomial in ² ;± , and jnj such that for all ¤ (n;e)2S, and x2Z n 0 PrA(n;e;RSA (x))=x1¡± n;e 0 (where the probability is taken over the coin tosses of A ). 1 Proof: Choose the smallest integer N for which ±. N e 0 Consider the algorithm A running as follows on inputs (n;e)2S and RSA (x). n;e ¡1 Repeat ² N times. ¤ Randomly choose z2Z . n Let y =A(n;e;RSA (x)¢RSA (z))=A(n;e;RSA (xz)). n;e n;e n;e ¡1 If A succeeds then y =xz and therefore x=yz modn. Output x. Otherwise, continue to the next iteration. End loop 0 We can estimate the probability that A fails: ¡1 0 0 ² N PrA(n;e;RSA (x))6=x =PrA single iteration of the loop of A fails n;e ¡1 ² N (1¡²) ¡N (e ) ± ¡1 ¡1 0 Note that since N = O(log(± )) = O(± ), A is a probabilistic algorithm which runs in time polynomial in ¡1 ¡1 ² , ± , andjnj. Open Problem 2.32 It remains to determine whether a similar result holds if the probability is also taken over the indices (n;e)2I. Speci¯cally, if ², ±2(0;1) and A is a PTM such that PrA(n;e;RSA (x))=x² n;e ¤ 0 (where the probability is taken over (n;e) 2 I, x 2 Z and the coin tosses of A), does there exist a PTM A n ¡1 ¡1 running in time polynomial in ² and ± such that 0 PrA(n;e;RSA (x))=x1¡± n;e 0 (where the probability is taken over (n;e)2I and the coin tosses of A )? 2.3.3 Connection Between The Factorization Problem And Inverting RSA 0 Fact 2.33 If some PPT algorithm A can factor n then there exists a PPT A that can invert RSA . hn;ei The proof is obvious as Á(n)=(p¡1)(q¡1). The trapdoor information d can be found by using the extended ¡1 Euclidean algorithm because d=e modÁ(n). Fact 2.34 If there exists a PTM B which on input hn;ei ¯nds d such that ed´ 1modÁ(n) then there exists 0 a PTM, B that can factor n. Open Problem 2.35 It remains to determine whether inverting RSA and factoring are equivalent. Namely, 0 if there is a PTM C which, on inputhn;ei, can invert RSA , does there exist a PTM C that can factor n? hn;ei The answer to this question is unknown. Note that Fact 2.34 does not imply that the answer is yes, as there may be other methods to invert RSA which do not necessarily ¯nd d.Cryptography: Lecture Notes 29 2.3.4 The Squaring Trapdoor Function Candidate by Rabin Rabin in 170 introduced a candidate trapdoor function which we call the squaring function. The squaring function resemble the RSA function except that Rabin was able to actually prove that inverting the squaring function is as hard as factoring integers. Thus, inverting the squaring function is a computation which is at least as hard as inverting the RSA function and possibly harder. De¯nition 2.36 Let I = fn = pq : p and q are distinct odd primes.g. For n 2 I, the squaring function ¤ ¤ 2 SQUARE :Z ¡Z is de¯ned by SQUARE (x)´ x modn. The trapdoor information of n = pq 2 I is n n n n ¤ ¤ t =(p;q). WewilldenotetheentirecollectionofRabin'sfunctionsbyRABIN=fSQUARE :Z ¡Z g . n n n2I n n Remark 2.37 ObservethatwhileRabin'sfunctionsquaresitsinput,theRSAfunctionusesavaryingexponent; namely, e where gcd(e;Á(n)) = 1. The requirement that gcd(e;Á(n))=1 guarentees that the RSA function is a permutation. On the other hand, Rabin's function is 1 to 4 and thus it does not have a uniquely de¯ned ¤ 2 inverse. Speci¯cally, let n=pq2I and let a2Z . As discussed in section C.4, if a´x modp then x and¡x p 2 are the distinct square roots of a modulo p and if a´y modq then y and¡y are the distinct square roots of a 2 modulo q. Then, there are four solutions to the congruence a´z modn, constructed as follows. Let c;d2Z n be the Chinese Remainder Theorem coe±cients as discussed in Appendix C.4. Then ½ 1modp c= 0modq and ½ 0modp d= 1modq and the four solutions are cx+dy, cx¡dy,¡cx+dy, and¡cx¡dy. The main result is that RABIN is a collection of strong one way trapdoor functions and the proof relies on an assumption concerning the di±culty of factoring. We state this assumption now. Factoring Assumption: Let H =fpq : p and q are prime andjpj =jqj = kg. Then for every polynomial Q k and every PTM A,9k such that8k k 0 0 1 PrA(n)=p:pjn and p6=1;n Q(k) (where the probability is taken over all n2H and the coin tosses of A). k Our ultimate goal is to prove the following result. Theorem 2.38 Under the factoring assumption, RABIN is a collection of one way trapdoor functions. Before proving this, we consider two auxiliary lemmas. Lemma 2.39 constructs a polynomial-time machine A whichcomputessquarerootsmoduloaprime. Lemma2.42constructsanotherpolynomial-timemachine,SQRT, that inverts Rabin's function using the trapdoor information; speci¯cally, it computes a square root modulo composites given the factorization. SQRT makes calls to A. Lemma 2.39 Let p be an odd prime and let a be a square modulo p. There exists a probabilistic algorithm A 2 running in expected polynomial time such that A(p;a)=x where x ´amodp. ¤ Proof: Let p be an odd prime and let a be a quadratic residue in Z . There are two cases to consider; p p´1mod4 and p´3mod4. Case 1 p´3mod4; that is, p=4m+3 for some integer m.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.