Historical and Bibliographical Remarks

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 sum­mary 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 crypto­system 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 satisfiabil­ity 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 pre­sented 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 con­ferences 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 authentica­tion 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 Depart­ment, 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. Amster­dam 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 Trans­actions 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 Informa­tion 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 crypto­system. 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

Index

alphabet 3 authentication 72 avalanche effect 54

backward deterministic 167

strongly 171 Bacon requirements 4 balloting system 219 Beaufort square 30

CAESAR 5 Carmichael number 139 chameleon 210

Chinese Remainder Theorem 188 classical cryptosystem 10 CODE BOOK 37 coin flipping by telephone 184 commutative cryptosystem 65 complexity theory 245 compositeness tests 137 congruence 250 conjunctive normal form 247 Co-NP 248 cryptanalysis 6

initial setups for 7 cryptographic hashing 216 cryptographic machines 39 C-36 44

Jefferson wheel 39 M-209 Converter 44 cryptographic protocol 181 age problem 191 banking 200

coin flipping by telephone 184 elections 200,219 flipping numbers 186 interaction versus P-SPACE 207 minimum disclosure proof 203 non-interactive 195 oblivious transfer 194 partial disclosure of secrets 190 poker by telephone 74, 186 secret selling of secrets 196 sharing secrets 187 types of adversaries 182

without computers 234 zero-knowledge proof 208 cryptography 2

public-key 55 cryptology 2 cryptosystem 3 affine 14

AUTOCLAVE 35 automata-based 177 CAESAR 5 classical 10 CODE BOOK 37 coding-theory-based 178 commutative 5, 65 dense knapsack 121 DES 49 ElGamal 157 functional 168 Hill 8

HOMOPHONES 22 KEYWORD-CAESAR 20 knapsack 77

language-theory-based 174 McEliece 179 monoalphabetic 11 nonsymmetric 10 ONE-TIME PAD 38 one-way 10 periodic 31 PLAYFAIR 23 polyalphabetic 12 polynomial 19 public-key 6 RICHELIEU 11 RSA 125 substitution 11 symmetric 10 transposition 11 two-way 10 VIGENERE 29 Williams 159 cryptotext 2 space 3 data encryption standard 49

decoding 4 decryption 2

exponent (RSA) 126 density of knapsack vector 122 DES 49

digital signature 72 digram 25

diminishing sequence 98 discrete logarithm 118, 154, 251

eavesdropper 66 active 66 passive 66 elections 74,191,201,219 encoding 4 encryption 2

by coloring 175 exponent (RSA) 126 error correcting code 178 Goppa 179 linear 179 Euclid's algorithm 249 complexity of 249 Euler phi-function 250 Euler pseudoprime 140 Euler's Theorem 250

Fermat's Little Theorem 250 finite field 117,251 algebraic over 117 generator of 117,251 square roots in 251 flipping numbers 186

garbage-in-between 10 goal 98

growing sequence 97

handshaking 74 hash function 216 hit number 46

identification 213

zero-knowledge proof of 213 interactive proof 207

for graph non-isomorphism 207 intractable 246

Jacobi symbol 251

complexity of computation 252 Jefferson wheel 39

Kasiski's method 31 key exchange 156 key management 13,71 key space 3 knapsack-based cryptosystem 77 cryptanalysis 87, 96 signatures by 112 knapsack problem 58

instance of 77 knapsack vector 59, 77 dense 117 density of 122 hyper-reachable 96 increasing 78 injective 78 of low density 117 permutation-super-reachable 108 super-increasing 61, 78 super-reachable 96, 101

Language 3 Las Vegas 248

least nonnegative remainder 78, 250 Legendre symbol 251 letter 3

descendant 169 dummy 169 literal 247

lockable box 204, 207 assignment 212 truth-value 211 variable 211 L-system 169 DTOL 169 TOL 169 lug cage 45 lug matrix 45

Miller-Rabin test 141 minimum disclosure proof 203 graph isomorphism 206 three-coloring 205 modular exponentiation 127 modular multiplication 79 modulus 250

monoalphabetic cryptosystems 10 Monte Carlo 248 morphism 167

iteration of 166

NP 246

NP-complete 247 NP-hard 247 numerical encoding 13

oblivious transfer 194

combined 200 ONE-TIME PAD 38 one-way function 57

cryptographic 57 oracles 147

P 246

partial disclosure of secrets 190 password 71 plaintext 2

space 3 PLAYFAIR 23 periodic 37 poker by telephone 74, 186 polyalphabetic cryptosystems 22 Polybios checkerboard 14 polynomially bounded 246 polynomial time 246 deterministic 246 nondeterministic 246 random 248 preprocessing 10 primality 137 probabilistic algorithm 248 protocol 73,181

see cryptographic protocol pseudoprime 138

strong 141 P-SPACE 248

public-key cryptosystem 6, 66

quadratic reciprocity 252 quadratic residue 251 nonresidue 251

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

Printing: Druckhaus Beltz. Hemsbach Binding: Buchbinderei Schat'fcr. Griinstadl

[1] £ ^ai^ct = a(modm),

i= 1

where each c\ satisfies 0 < c_f < [ log₂ m] + 1. Thus, we allow the item a_i 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.

Date: 2015-02-16; view: 1256