Since some ideas in cryptography are several thousands of years old, it does not make sense to try to trace the original sources for matters discussed in Chapter 1. [Ka] is an excellent over-all reference. [Ga] discusses cryptanalytic methods before the age of computers. The cryptosystem of Example 1.2 was introduced in [Hil]. [Kon] and [BeP] discuss various cryptanalytic methods for classical systems. [Zim] could be mentioned as an example of the numerous books on cryptography before the era of public keys.
Public keys were introduced in [DH], The basic knapsack system discussed in Chapter 2 is from [MeH], and complexity issues from [Br 1] and [Kar 1]. Poker by telephone, coin flipping by telephone and oblivious transfer are due to [ShRA], [Bll] and [Rab2], respectively.
The theory presented in Sections 3.2 and 3.3 is from [Sh2], [Sa3] and [Sa4], See also [Adl], The cryptosystems in Section 3.4 are (in this order) from [EvY], [Sh3], [Sh 1] and due to Graham and Shamir. [Cho] is the basic reference for dense knapsacks.
The theory presented in Chapter 4 was initiated in [RSA], [Rabl] is an early contribution. See [Ko] for the original references for Section 4.3. Section 4.4 uses ideas from [Mil] and [Del]. Theorem 4.3 is from [GMT]. See also [SchA]. [Odl] is a comprehensive treatment about discrete logarithm, and [Ang] a good summary on the complexity of number theoretic problems.
The material in Section 5.1 is from [Wil] and that in Section 5.2 from [Sa2], [SaY], [Kar2] and [Kar3]. The cryptosystems based on group theory and hiding regular languages are due to [ WaM] and [Nie], respectively. [SiS] is also a cryptosystem based on language theory, and the system based on sequential machines is due to [Ren], The cryptosystem of Section 5.4 was introduced in [McE].
The signature scheme at the end of Section 6.1 is due to [Sh4], and the material in Section 6.2 to [Bll] and [GM], The method of sharing a secret given in Section 6.3 was presented in [Mig]. The age protocol of Section 6.4 is from [Yao], The notion of oblivious transfer is due to [Rab2], Section 6.5 presents a simple protocol for the secret selling of secrets; more sophisticated techniques are contained in [BCR], Section 6.6 follows [BuP] and [NuS], The subject matter has been treated in numerous other papers, for instance, [Ben] is a comprehensive treatment with somewhat different aims. [GMR] and [GMW] are basic papers concerning zero-knowledge proofs. The first protocol in Section 6.7 is from [Dam]. Ideas from [B12] are used in the proofs of Theorems 6.2 and 6.3. A protocol for the satisfiability problem different from the one of Theorem 6.5 is given in [BCC], where the gates of the corresponding logical circuit are considered. [DMP] and [BeG] deal with non-interactive zero-knowledge proof systems. The two proof methods presented in Section 6.9 are from [FFS] (see also [FiS]) and [Sh5], Cheating schemes are discussed in [DGB],
The information theoretic viewpoint, [Shan], is not discussed in this book. The following list of references contains only works referred to in this book. Further bibliographical details are contained, for instance, in [Fl], [SP], [Br 2], [Kra], [Til] and [Wei], Cryptologia and Journal of Cryptology are periodicals devoted to cryptography. Also other journals have papers and entire issues (for instance, May 1988 issue of Proceedings of IEEE) about cryptography. CRYPTO and EUROCRYPT are annual conferences whose proceedings are usually published in Springer Lecture Notes in Computer Science. Also the standard annual conferences on theoretical computer science (STOC, FOCS, ICALP, etc.) contain many papers dealing with cryptography.
References
[Adl] L. Adleman: On breaking the iterated Merkle-Hellman public key cryptosystem. Proceedings
15th ACM Symposium on the Theory of Computing, 1983, pp. 402-412 [Ang] D. Angluin: Lecture Notes on the Complexity of Some Problems in Number Theory. Yale
University, Computer Science Department, Technical Report 243, 1982 [BeP] H. Beker and F. Piper: Cipher systems. Northwood Books, London 1982 [BeG] M. Bellare and S. Goldwasser: New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. CRYPTO-89 Abstracts, University of California, Santa Barbara 1989, pp. 189-204 [Ben] J.D.C. Benaloh: Verifiable secret-ballot elections. Yale University, Computer Science Department, Technical Report 561, 1987 [BenT] J.D.C. Benaioh and D. Tuinstra: Receipt-free secret-ballot elections. Proceedings STOC-94, (1994)544-553
[BI 1] M. Blum: Coin flipping by telephone. A protocol for solving impossible problems. SIGACT News, 1981, pp. 23-27
[B12] M. Blum: How to prove a theorem so no one else can claim it. Proceedings International
Congress of Mathematicians, 1987, pp. 1444-1451 [Bo] B. den Boer: More efficient match-making and satisfiability; the five card trick. Proceedings EUROCRYPT-89, Lecture Notes in Computer Science, vol. 434. Springer, Berlin 1990, pp. 208-217
[BC] R.C. Bose and S. Chowla: Theorems in the additive theory of numbers. Comment. Math.
Helvet. 37 (1962) 141-147 [Brl] G. Brassard: A note on the complexity of cryptography. IEEE Transactions on Information
Theory IT-25 (1979) 232-233 [Br2] G. Brassard: Modern cryptology. Lecture Notes in Computer Science, vol. 325. Springer, Berlin 1988
[BCC] G. Brassard, D. Chaum and C. Crepeau: An introduction to minimum disclosure. Amsterdam CWI Quarterly 1 (1988) 3-17 [BCR] G. Brassard, C. Crepeau and J.-M. Robert: All-or-nothing disclosure of secrets. Lecture
Notes in Computer Science, vol. 263. Springer, Berlin 1987, pp. 234-238 [BuP] H. Burk and A. Pfitzmann: Digital payment systems enabling security and unobservability.
Computers and Security 9 (1989) 399-416 [Cho] B.-Z. Chor: Two issues in public key cryptography. MIT Press, Cambridge, Mass. 1986 [Cop] D. Coppersmith: Fast evaluation of logarithms in fields of characteristic two. IEEE Transactions on Information Theory IT-30 (1984) 587-594 [CrK] C. Crepeau and J. Kilian: Discreet solitary games. Proceedings CRYPTO-93, Lecture Notes
in Computer Science, vol. 773. Springer, Berlin 1994, pp. 319-330 [Dam] I.B. Damgaard: On the existence of bit commitment schemes and zero-knowledge proofs.
CRYPTO-89 Abstracts, University of California, Santa Barbara 1989, pp. 15-23 [Del] J.M. Delaurentis: A further weakness in the common modulus protocol for the RSA
cryptoalgorithm. Cryptologia 8 (1984) 253-259 [De] D.E. Denning: Cryptography and data security. Addison-Wesley, Reading, Mass. 1982 [DMP] A. De Santis, S. Micali and G. Persiano: Non-interactive zero-knowledge proof systems.
Lecture Notes in Computer Science, vol. 293. Springer, Berlin 1987, pp. 52-72 [DGB] Y. Desmedt, C. Goutier and S. Bengio: Special uses and abuses of the Fiat-Shamir passport
protocol. Lecture Notes in Computer Science, vol. 293. Springer, Berlin 1987, pp. 21-39 [DH] W. Diflie and M. Hellman: New directions in cryptography. IEEE Transactions on Information Theory 1T-22 (1976) 644-654 [EIG] T. El Gamal: A public key cryptosystem and signature scheme based on discrete logarithms.
IEEE Transactions on Information Theory IT-31 (1985) 469-473 [EvY] S. Even and Y. Yacobi: Cryptosystems which are /VP-hard to break. Technion, Computer Science Department, Technical Report 1979
[FFS] U. Feige, A. Fiat and A. Shamir: Zero knowledge proofs of identity. Journal of Cryptology 1 (1988) 77-94
[FiS] A. Fiat and A. Shamir: How to prove yourself: practical solutions to identification and signature problems. Lecture Notes in Computer Science, vol. 263. Springer, Berlin 1987, pp. 186-194
[Fl] D. Floyd: Annotated bibliography in conventional and public key cryptography. Crypto-
logia 7 (1983) 12-24 [Ga] H.F. Gaines. Cryptoanalysis. Dover Publications, New York 1939
[GMW] O. Goldreich, S. Micali and A. Widgerson: How to prove all /VP-statements in zero- knowledge, and a methodology of cryptographic protocol design. Lecture Notes in Computer Science, vol. 263. Springer, Berlin 1987, pp. 171-185 [GM] S. Goldwasser and S. Micali; Probabilistic encryption. Journal of Computer and Systems
Sciences 28 (1984) 270-299 [GMR] S. Goldwasser, S. Micali and C. Rackoff: The knowledge complexity of interactive proof systems. Proceedings 17th ACM Symposium on the Theory of Computing, 1985, pp. 291-304
[GMT] S. Goldwasser, S. Micali and P. Tong: Why and how to establish a private code on a public
network. Proceedings 23rd FOCS Symposium, 1982, pp. 134-144 [Hil] L.S. Hill: Cryptography in an algebraic alphabet. American Mathematical Monthly 36 (1929) 306-312
[Ka] D. Kahn: The codebreakers: the story of secret writing. Macmillan, New York 1967 [Karl] J. Kari: A cryptosystem based on propositional logic. Lecture Notes in Computer Science,
vol. 381. Springer, Berlin 1989, pp. 210-219 [Kar2] J. Kari: A cryptanalytic observation concerning systems based on language theory. Discrete
Applied Mathematics 21 (1988) 265-268 [Kar3] J. Kari: Observations concerning a public-key cryptosystem based on iterated morphisms.
Theoretical Computer Science 66 (1989) 45-53 [Ko] N. Koblitz: A course in number theory and cryptography. Springer, Berlin 1987 [Kon] A. Konheim: Cryptography: a primer. Wiley and Sons, New York 1982 [Kra] E. Kranakis: Primality and cryptography. Wiley-Teubner, Chichester New York Stuttgart 1986
[McE] R.J. McEliece: A public-key cryptosystem based on algebraic coding theory. Deep Space
Network Progress Report. Jet Propulsion Labs, Pasadena 42-44 (1978) 114-116 [MeH] R. Merkle and M. Hellman: Hiding information and signatures in trapdoor knapsacks. IEEE
Transactions on Information Theory IT-24 (1978) 525-530 [Mig] M. Mignotte: How to share a secret. Lecture Notes in Computer Science, vol. 149. Springer, Berlin 1983, pp. 371-375
[Mil] G.L. Miller: Riemann's hypothesis and tests for primality. Journal of Computer and System
Sciences 13 (1976) 300-317 [Nie] V. Niemi: Hiding regular languages: a public-key cryptosystem. Manuscript 1989 [NieR] V. Niemi and A. Renvall: Efficient voting with no selling of votes. Manuscript 1995, submitted for publication
[NieR2] V. Niemi and A. Renvall: Secure multiparty computations without computers. Theoretical
Computer Science, to appear [NuS] H. Nurmi and A. Salomaa: On the cryptography of secret ballot. Behavioral Science 36 (1991) 34-40
[NuSS] H. Nurmi, A. Salomaa and L. Santean: Secret-ballot elections in computer networks.
Computers and Security 10 (1991) 553-560 [Odl] A.M. Odlyzko: Discrete logarithms in finite fields and their cryptographic significance.
Lecture Notes in Computer Science, vol. 209. Springer, Berlin 1985, pp. 224-314 [PoH] S.C. Pohlig and M. Hellman: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory IT-24 (1978) 106-110 [PIK] C. Park, K. Itoh and K. Kurosawa: Efficient anonymous channel and all/nothing election scheme. Proceedings EUROCRYPT-93, Lecture Notes in Computer Science, vol. 765. Springer, Berlin 1994. pp. 248-259 [Rabl] M.O. Rabin: Digitalized signatures and public key functions as intractable as factorization.
MIT, Laboratory for Computer Science, Technical Report 212, 1979 [Rab2] M.O. Rabin: How to exchange secrets by oblivious transfer. Aiken Computation Laboratory,
Harvard University, Technical Report TR-S/, 1981 [Ren] Tao Renji: Some results on the structure of feedforward inverses. Scientia Sinica, Ser. A 27 (1984)157-162
[Renv] A. Renvall: Cryptographic protocols and techniques for communication. Dissertation, Univ. of Turku 1994
[RSA] M. Rivest, A. Shamir and L. Adleman: A method for obtaining digital signatures and
public-key cryptosystems. Commun. ACM 21 (1978) 120-126 [RS] G. Rozenberg and A. Salomaa: The mathematical theory of L systems. Academic Press, New York 1980
[Sal] A. Salomaa: Computation and automata. Cambridge University Press, Cambridge 1985.
Available also in French and Japanese [Sa2] A. Salomaa: A public-key cryptosystem based on language theory. Computers and Security 7 (1988) 83-87
[Sa3] A. Salomaa: A deterministic algorithm for modular knapsack problems. Theoretical
Computer Science 88 (1991) 127-138 [Sa4] A. Salomaa: Decision problems arising from knapsack transformations. Acta Cybernetica 9(1990)419-440
[SaY] A. Salomaa and S. Yu: On a public-key cryptosystem based on iterated morphisms and
substitutions. Theoretical Computer Science 48 (1986) 283-296 [SchA] C.P. Schnorr and W. Alexi: RSA-bits are 0.5 + £ secure. Lecture Notes in Computer Science,
vol. 209. Springer, Berlin 1985, pp. 113-126 [Schn] B. Schneier: Applied Cryptography. John Wiley, New York 1993, 2nd ed. 1995 [SP] J. Seberry and J. Pieprzyk: Cryptography: an introduction to computer security. Prentice Hall, New York 1989
[Shi] A. Shamir: A fast signature scheme. MIT, Laboratory for Computer Science, Technical Report 1978
[Sh2] A. Shamir: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. Proceedings 23rd FOCS Symposium, 1982, pp. 145-152 [Sh3] A. Shamir: Embedding cryptographic trapdoors in arbitrary knapsack systems. MIT,
Laboratory for Computer Science, Technical Report 230, 1982 [Sh4] A. Shamir: Identity based cryptosystems and signature schemes. Lecture Notes in Computer
Science, vol. 196. Springer, Berlin 1985, pp. 47-53 [Sh5] A. Shamir: An efficient identification scheme based on permuted kernels. Weizmann Institute,
Department of Applied Mathematics, Technical Report 1989 [ShRA] A. Shamir, R. Rivest and L. Adleman: Mental poker. In D.A. Klarner (ed.), The mathematical
gardener. Wadsworth International, Belmont 1981, pp. 37-43 [Shan] C.E. Shannon: Communication theory of secrecy systems. Bell System Technical Journal 28 (1949) 656-715
[SiS] R. Siromoney and G. Siromoney: A public key cryptosystem that defies cryptanalysis.
EATCS Bulletin 28 (1986) 37-43 [Til] H.C.A. Van Tilborg: An introduction to cryptology. Kluwer Academic Publishers, Boston 1988
[WaM] N.R. Wagner and M.R. Magyarik: A public key cryptosystem based on the word problem.
Lecture Notes in Computer Science, vol. 196. Springer, Berlin 1985, pp. 19-37 [Wei] D. Welsh: Codes and cryptography. Oxford University Press, Oxford 1988 [Wie] M.J. Wiener: Cryptanalysis of short RSA secret exponents. Proceedings EUROCRYPT-89.
Lecture Notes in Computer Science, vol. 434. Springer, Berlin 1990, p. 372. Full paper: IEEE Transactions on Information Theory IT-36 (1990) 553-558
[Wil] H.C. Williams: Some public-key crypto-functions as intractable as factorization. Cryptologia 9 (1985) 223-237
[Yao] A.C. Yao: Protocols for secure computations. Proceedings 23rd FOCS Symposium, 1982, pp. 160-164
[Zim] H.S. Zim: Codes and secret writing. Scholastic Book Services, New York 1948
random polynomial time 248 rescuer 99, 100 rotors 39 RSA 125
cryptanalysis versus factoring 143, 165 digital signatures 133 partial information in 147 security of 134
satisfiability problem 211, 247 S-boxes 51
scrambling strategy 224 secrecy of protocol 221 secret selling of secrets 196 selling of votes 228
sharing secrets 187 sieve of Eratosthenes 142 Solovay-Strassen test 139 soundness of protocol 221 space complexity 247 steganography 14 step figure 46 stochastic algorithm 248 substitution 5 finite 167
threshold scheme 187 time complexity 245 deterministic 246 function 246 tractable 246 transposed version 101 trapdoor 56 pair 171 Turing machine 245 deterministic 246 nondeterministic 246 polynomially bounded 246
verifiability of protocol 221 VIGENERE 29 square 29 violation point 97
wffpc 221
witness for primality 138 word 3
empty 3 lenght of 3 word problem 175
XOR 195
zero-knowledge proof 208 Hamilton cycle 208 non-interactive 213,243 of identity 213 of knowledge 214 of theorems 214 parallel version 210 perfect 213 satisfiability 211,243
where each c\ satisfies 0 < cf < [ log2 m] + 1. Thus, we allow the item ai to be used several times in forming the sum. However, the number of times allowed is small and never exceeds the number of bits in the modulus.
Before proceeding with the formal details, we discuss in general terms how such a knapsack system can be used to generate signatures. The sender chooses and publicizes a knapsack system determined by A = (a,, . . . ,a„) and m such that the system leads to apparently difficult knapsack problems but the problems can actually be solved quickly by some secret trapdoor information. The sender signs a message oc by using the trapdoor information to solve (*): the n-tuple (c,,.. ., cj constitutes the signature for a. The legal receiver who has received both a and the signature can verify the signature by checking that (*) holds. If the legal receiver or a cryptanalyst wants to forge the sender's signature for some message a', he/she has to solve the instance of the knapsack problem determined by the triple (A, n% a'). An additional requirement concerning the choice of the knapsack system is that all conceivable messages a must have a signature, that is, (*) must have a solution for all such a.