AUTOSAR R21-11(3) Requirements on Diagnostics

AUTOSAR Advent Calendar 2021

12/16日の投稿です。

AUTOSARが、12/7 今年の版、R21-11を公開しました。

文書は検索してダウンロードできます。

AUTOSAR R21-11(0)公開 Specificationをダウンロード

https://qiita.com/kaizen_nagoya/items/9b3a1b9b8d1e8d7e288e

Diagnostics関連のAUTOSARの資料を順に確認。

技術的な内容に入る前に、用語、参照文献でわけわかめ。

# Specification of Secure Hardware Extensions

Document Title | Specification of Secure Hardware Extensions |
---|---|

Document Owner | AUTOSAR |

Document Responsibility | AUTOSAR |

Document Identification No | 948 |

Document Status | published |

Part of AUTOSAR Standard | Adaptive |

Part of Standard Release | R21-11 |

## Document Change R21 - 11

No content changes.(R19-11 が initial release。前回も変更なし)

そんな。initial releaseから見直しがないなんて。

A Appendix が空白なのやめてほしいかもしれない。

2.2 Definition term が空白。

# Term

Term | Description |
---|---|

HIS | Hersteller Initiative Software |

SHE | Security Hardware Extension |

AES | Advanced Encryption Standard |

TPM | Trusted Platform Module |

CBC | Cipher Block Chaining |

ECB | Electronic Code Book |

MAC | Message Authentication Code |

CMAC | Cipher-based Message Authentication Code |

IV | Initialization Vector |

UID | Unique IDentification item |

TRNG | True Random Number Generator |

PRNG | Pseudo Random Number Generator |

# 英日単語帳

日本語は仮訳

no. | count | word | 日本語 |
---|---|---|---|

1 | 911 | the | その |

2 | 422 | of | の |

3 | 337 | to | に |

4 | 302 | a | 一つの |

5 | 254 | be | です |

6 | 244 | x | x |

7 | 234 | is | です |

8 | 201 | and | と |

9 | 174 | she | Security Hardware Extension(短縮名） |

10 | 151 | e | e |

11 | 146 | for | にとって |

12 | 145 | in | の |

13 | 143 | secure | 安心 |

14 | 142 | by | に |

15 | 123 | key | 鍵 |

16 | 121 | memory | 記憶装置 |

17 | 115 | boot | 起動 |

18 | 102 | if | もし |

19 | 101 | has | 持つ |

20 | 94 | chapter | 章 |

21 | 87 | not | いいえ |

22 | 80 | b | b |

23 | 80 | document | 文書 |

24 | 80 | id | identifier, 識別子(短縮名） |

25 | 79 | autosar | AUTomotive Open System Architecture(短縮名) |

26 | 79 | specification | 仕様 |

27 | 77 | hardware | ハードウェア |

28 | 72 | r | r |

29 | 69 | extensions | 拡張機能 |

30 | 68 | autosar_tr_securehardwareextensions | autosar_tr_securehardwareextensions |

31 | 68 | fo | foundation(短縮名） |

32 | 66 | see | 見る |

33 | 63 | function | 関数 |

34 | 63 | or | または |

35 | 62 | c | c |

36 | 61 | as | なので |

37 | 59 | must | しなければならない |

38 | 56 | can | できる |

39 | 56 | only | だけ |

40 | 54 | m | m |

41 | 54 | on | の上 |

42 | 53 | d | d |

43 | 52 | are | です |

44 | 52 | it | それ |

45 | 52 | random | 無作為 |

46 | 51 | used | 使った |

47 | 50 | f | f |

48 | 49 | with | と |

49 | 48 | keys | 鍵 |

50 | 47 | error | 誤り |

51 | 44 | this | これ |

52 | 43 | an | 一つの |

53 | 43 | bit | binary digit(短縮名） |

54 | 43 | number | 番号 |

55 | 43 | value | 値 |

56 | 42 | may | かもしれない |

57 | 41 | update | 更新 |

58 | 38 | any | どれか |

59 | 37 | i | 私 |

60 | 37 | note | 覚書 |

61 | 37 | seed | 種 |

62 | 36 | aes | Advanced Encryption Standard（短縮名） |

63 | 36 | uid | Unique IDentification item（短縮名） |

64 | 35 | after | 後 |

65 | 35 | mac | Message Authentication Code（短縮名 |

66 | 35 | process | 処理する |

67 | 35 | slot | 枠 |

68 | 34 | code | 符号 |

69 | 33 | application | 応用 |

70 | 33 | data | 与件 |

71 | 33 | operation | 手術 |

72 | 33 | protocol | 規約 |

73 | 33 | slots | 枠 |

74 | 33 | write | 書く |

75 | 32 | message | 伝言 |

76 | 32 | volatile | 揮発性 |

77 | 31 | generation | 世代 |

78 | 31 | have | 持つ |

79 | 30 | all | すべて |

80 | 30 | flag | 旗 |

81 | 30 | generator | 発生器 |

82 | 29 | cipher | 暗号 |

83 | 29 | cpu | central processing unit(短縮名 |

84 | 29 | k | k |

85 | 29 | n | n |

86 | 28 | plaintext | 平文 |

87 | 28 | set | 設定する |

88 | 28 | verification | 検証 |

89 | 27 | before | 前 |

90 | 27 | codes | 符号 |

91 | 27 | internal | 内部 |

92 | 26 | bits | binary digits(短縮名） |

93 | 26 | during | その間 |

94 | 26 | g | g |

95 | 26 | non | 非 |

96 | 26 | that | それ |

97 | 26 | width | 幅 |

98 | 25 | at | で |

99 | 25 | block | 防ぐ |

100 | 25 | called | 呼ぶ |

101 | 25 | from | から |

102 | 25 | output | 出力 |

# References

[1] NIST: Announcing the Advanced Encryption Standard (AES) http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

[2] NIST Special Publication 800-38A: Recommendation for Block Cipher Modes of Operation: Methods and Techniques http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf

[3] NIST Special Publication 800-38B: Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf

Withdrow（廃止）

[4] NIST: Updated CMAC Examples http://csrc.nist.gov/publications/nistpubs/800-38B/Updated_CMAC_Examples.pdf

内容未確認。

[5] Handbook of Applied Cryptography http://www.cacr.math.uwaterloo.ca/hac/

[6] Recommendation for Key Derivation Using Pseudorandom Functions (Revised) https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-108.pdf

[7] BSI: A proposal for: Functionality classes and evaluation methodology for true (physical)random number generators, Version 3.1 http://www.bsi.bund.de/zertifiz/zert/interpr/trngk31e.pdf

[8] BSI: Application Notes and Interpretation of the Scheme (AIS) http://www.bsi.bund.de/zertifiz/zert/interpr/ais20e.pdf

(Fehler 404)

[9] Trusted Computing Group https://www.trustedcomputinggroup.org/

## References on References

### Appendix D - References on 1

[1] AES page available via http://www.nist.gov/CryptoToolkit.

[2] Computer Security Objects Register (CSOR): http://csrc.nist.gov/csor/.

[3] J. Daemen and V. Rijmen, AES Proposal: Rijndael, AES Algorithm Submission, September 3, 1999, available at [1].

[4] J. Daemen and V. Rijmen, The block cipher Rijndael, Smart Card research and Applications, LNCS 1820, Springer-Verlag, pp. 288-296.

[5] B. Gladman’s AES related home page http://fp.gladman.plus.com/cryptography_technology/.

[6] A. Lee, NIST Special Publication 800-21, Guideline for Implementing Cryptography in the Federal Government, National Institute of Standards and Technology, November 1999.

[7] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997, p. 81-83.

[8] J. Nechvatal, et. al., Report on the Development of the Advanced Encryption Standard (AES), National Institute of Standards and Technology, October 2, 2000, available at [1].

### Appendix G: References on [2] NIST 800-38A

[1] American National Standard for Financial Services X9.52-1998, “Triple Data Encryption Algorithm Modes of Operation.” American Bankers Association, Washington, D.C., July 29, 1998.

[2] FIPS Publication 197, “Advanced Encryption Standard (AES).” U.S. DoC/NIST, November 26, 2001.

[3] FIPS Publication 46-3, “Data Encryption Standard (DES).” U.S. DoC/NIST, October 25, 1999.

[4] FIPS Publication 81, “DES Modes of Operation.” U.S. DoC/NIST, December 1980.

[5] A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of Applied Cryptography.” CRC Press, New York, 1997.

### Reference on [3]

既出

AUTOSAR R21-11(7) Specification of Secure Onboard Communication Protocol(SecOC)

### Reference on [4]

### Reference on [5] Handbook of Applied Cryptography

M. ABADI AND R. NEEDHAM, “Prudent en- gineering practice for cryptographic proto- cols”, DEC SRC report #125, Digital Equip- ment Corporation, Palo Alto, CA, 1994.

M. ABADI AND M.R. TUTTLE, “A seman- tics for a logic of authentication”, Proceed- ings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 201– 216, 1991.

C. ADAMS, “Symmetric cryptographic sys- tem for data encryption”, U.S. Patent # 5,511,123, 23 Apr 1996.

, “IDUP and SPKM: Developing public-key-based APIs and mechanisms for communication security services”, Proceed- ings of the Internet Society Symposium on Net- work and Distributed System Security, 128– 135, IEEE Computer Society Press, 1996.

C. ADAMS AND H. MEIJER, “Security- related comments regarding McEliece’s public-key cryptosystem”, Advances in Cryptology–CRYPTO ’87 (LNCS 293), 224– 228, 1988.

, “Security-related comments regard- ing McEliece’s public-key cryptosystem”, IEEE Transactions on Information Theory, 35 (1989), 454–455. An earlier version appeared in [5].

C. ADAMS AND S.E. TAVARES, “Design- ing S-boxes for ciphers resistant to differen- tial cryptanalysis”, W. Wolfowicz, editor, Pro- ceedings of the 3rd Symposium on State and Progress of Research in Cryptography, Rome, Italy, 181–190, 1993.

L.M. ADLEMAN, “A subexponential algo- rithm for the discrete logarithm problem with applications to cryptography”, Proceedings of the IEEE 20th Annual Symposium on Founda- tions of Computer Science, 55–60, 1979.

, “The function field sieve”, Algorith- mic Number Theory (LNCS 877), 108–121, 1994.

, “Molecular computation of solutions to combinatorial problems”, Science, 266 (1994), 1021–1024.

[11] L.M. ADLEMAN AND J. DEMARRAIS, “A subexponential algorithm for discrete loga- rithms over all finite fields”, Mathematics of Computation, 61 (1993), 1–15.

[12] L.M. ADLEMAN, J. DEMARRAIS, AND M.- D. HUANG, “A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields”, Algorithmic Number Theory (LNCS 877), 28–40, 1994.

[13] L.M. ADLEMAN AND M.-D. A. HUANG,

Primality Testing and Abelian Varieties Over Finite Fields, Springer-Verlag, Berlin, 1992.

[14] L.M. ADLEMAN AND H.W. LENSTRA JR., “Finding irreducible polynomials over finite fields”, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 350– 355, 1986.

[15] L.M. ADLEMAN AND K.S. MCCURLEY, “Open problems in number theoretic com- plexity, II”, Algorithmic Number Theory (LNCS 877), 291–322, 1994.

[16] L.M. ADLEMAN, C. POMERANCE, AND R.S. RUMELY, “On distinguishing prime numbers from composite numbers”, Annals of Mathematics, 117 (1983), 173–206.

[17] G.B. AGNEW, “Random sources for crypto- graphic systems”, Advances in Cryptology– EUROCRYPT ’ 87 (LNCS 304), 77–81, 1988.

[18] G.B. AGNEW, R.C. MULLIN, I.M. ONYSZ- CHUK, AND S.A. VANSTONE, “An imple- mentation for a fast public-key cryptosystem”, Journal of Cryptology, 3 (1991), 63–79.

[19] G.B. AGNEW, R.C. MULLIN, AND S.A. VANSTONE, “Improved digital signature sch- eme based on discrete exponentiation”, Elec- tronics Letters, 26 (July 5, 1990), 1024–1025.

[20] S.G. AKL, “On the security of com- pressed encodings”, Advances in Cryptology– Proceedings of Crypto 83, 209–230, 1984.

[21] N. ALEXANDRIS, M. BURMESTER, V. CHR- ISSIKOPOULOS, AND Y. DESMEDT, “A se- cure key distribution system”, W. Wolfowicz,

editor, Proceedings of the 3rd Symposium on State and Progress of Research in Cryptogra- phy, Rome, Italy, 30–34, Feb. 1993.

W. ALEXI, B. CHOR, O. GOLDREICH, AND C.P. SCHNORR, “RSA/Rabin bits are 1 +

2

1/poly(logn) secure”, Proceedings of the IEEE 25th Annual Symposium on Founda- tions of Computer Science, 449–457, 1984.

, “RSA and Rabin functions: Certain parts are as hard as the whole”, SIAM Journal on Computing, 17 (1988), 194–209. An ear- lier version appeared in [22].

W.R. ALFORD, A. GRANVILLE, AND C. POMERANCE, “There are infinitely many Carmichael numbers”, Annals of Mathemat- ics, 140 (1994), 703–722.

H. AMIRAZIZI AND M. HELLMAN, “Time- memory-processor trade-offs”, IEEE Trans- actions on Information Theory, 34 (1988), 505–512.

R. ANDERSON, “Practical RSA trapdoor”, Electronics Letters, 29 (May 27, 1993), 995.

, “The classification of hash functions”, P.G. Farrell, editor, Codes and Cyphers: Cryptography and Coding IV, 83–93, Institute of Mathematics & Its Applications (IMA), 1995.

, “On Fibonacci keystream generators”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 346–352, Springer-Verlag, 1995.

, “Searching for the optimum correla- tion attack”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 137–143, Springer-Verlag, 1995.

R. ANDERSON AND E. BIHAM, “Two prac- tical and provably secure block ciphers: BEAR and LION”, D. Gollmann, editor, Fast Software Encryption, Third International Workshop (LNCS 1039), 113–120, Springer- Verlag, 1996.

R. ANDERSON AND R. NEEDHAM, “Robust- ness principles for public key protocols”, Ad- vances in Cryptology–CRYPTO ’95 (LNCS 963), 236–247, 1995.

N.C. ANKENY, “The least quadratic non residue”, Annals of Mathematics, 55 (1952), 65–72.

ANSI X3.92, “American National Standard – Data Encryption Algorithm”, American Na- tional Standards Institute, 1981.

[34] ANSI X3.106, “American National Standard for Information Systems – Data Encryption Algorithm – Modes of Operation”, American National Standards Institute, 1983.

[35] ANSI X9.8, “American National Standard for Financial Services – Banking – Personal Identification Number management and se- curity. Part 1: PIN protection principles and techniques; Part 2: Approved algorithms for PIN encipherment”, ASC X9 Secretariat – American Bankers Association, 1995.

[36] ANSIX9.9(REVISED),“AmericanNational Standard – Financial institution message au- thentication (wholesale)”, ASC X9 Secretariat – American Bankers Association, 1986 (re- places X9.9–1982).

[37] ANSI X9.17, “American National Stan- dard – Financial institution key management (wholesale)”, ASC X9 Secretariat – American Bankers Association, 1985.

[38] ANSI X9.19, “American National Standard – Financial institution retail message authen- tication”, ASC X9 Secretariat – American Bankers Association, 1986.

[39] ANSI X9.23, “American National Standard – Financial institution encryption of whole- sale financial messages”, ASC X9 Secretariat – American Bankers Association, 1988.

[40] ANSI X9.24, “American National Standard for Financial Services – Financial services re- tail key management”, ASC X9 Secretariat – American Bankers Association, 1992.

[41] ANSI X9.26, “American National Standard – Financial institution sign-on authentication for wholesale financial transactions”, ASC X9 Secretariat – American Bankers Association, 1990.

[42] ANSI X9.28, “American National Stan- dard for Financial Services – Financial in- stitution multiple center key management (wholesale)”, ASC X9 Secretariat – American Bankers Association, 1991.

[43] ANSI X9.30 (PART 1), “American National Standard for Financial Services – Public key cryptography using irreversible algorithms for the financial services industry – Part 1: The digital signature algorithm (DSA)”, ASC X9 Secretariat – American Bankers Association, 1995.

[44] ANSI X9.30 (PART 2), “American National Standard for Financial Services – Public key cryptography using irreversible algorithms for the financial services industry – Part 2: The secure hash algorithm (SHA)”, ASC X9 Secretariat – American Bankers Association, 1993.

[45] ANSI X9.31 (PART 1), “American National Standard for Financial Services – Public key cryptography using RSA for the financial ser- vices industry – Part 1: The RSA signature al- gorithm”, draft, 1995.

[46] ANSI X9.31 (PART 2), “American National Standard for Financial Services – Public key cryptography using RSA for the financial ser- vices industry – Part 2: Hash algorithms for RSA”, draft, 1995.

[47] ANSI X9.42, “Public key cryptography for the financial services industry: Management of symmetric algorithm keys using Diffie- Hellman”, draft, 1995.

[48] ANSI X9.44, “Public key cryptography us- ing reversible algorithms for the financial ser- vices industry: Transport of symmetric algo- rithm keys using RSA”, draft, 1994.

[49] ANSI X9.45, “Public key cryptography for the financial services industry – Enhanced management controls using digital signatures and attribute certificates”, draft, 1996.

[50] ANSI X9.52, “Triple data encryption algo- rithm modes of operation”, draft, 1996.

[51] ANSI X9.55, “Public key cryptography for the financial services industry – Extensions to public key certificates and certificate revoca- tion lists”, draft, 1995.

[52] ANSI X9.57, “Public key cryptography for the financial services industry – Certificate management”, draft, 1995.

[53] K. AOKI AND K. OHTA, “Differential-linear cryptanalysis of FEAL-8”, IEICE Transac- tions on Fundamentals of Electronics, Com- munications and Computer Science, E79-A (1996), 20–27.

[54] B. ARAZI, “Integrating a key distribution pro- cedure into the digital signature standard”, Electronics Letters, 29 (May 27, 1993), 966– 967.

[55] , “On primality testing using purely di- visionless operations”, The Computer Jour- nal, 37 (1994), 219–222.

[56] F. ARNAULT, “Rabin-Miller primality test: composite numbers which pass it”, Mathemat- ics of Computation, 64 (1995), 355–361.

[57] A.O.L. ATKIN AND R.G. LARSON, “On a primality test of Solovay and Strassen”, SIAM Journal on Computing, 11 (1982), 789–791.

[58] A.O.L. ATKIN AND F. MORAIN, “Elliptic curves and primality proving”, Mathematics of Computation, 61 (1993), 29–68.

[59] D. ATKINS, M. GRAFF, A.K. LENSTRA, AND P.C. LEYLAND, “The magic words are SQUEAMISH OSSIFRAGE”, Advances in Cryptology–ASIACRYPT ’ 94 (LNCS 917), 263–277, 1995.

[60] L.BABAI,“Tradinggrouptheoryforrandom- ness”, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 421– 429, 1985.

[61] L. BABAI AND S. MORAN, “Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes”, Journal of Computer and System Sciences, 36 (1988), 254–276.

[62] E. BACH, “Discrete logarithms and factor- ing”, Report No. UCB/CSD 84/186, Com- puter Science Division (EECS), University of California, Berkeley, California, 1984.

[63] , Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms, MIT Press, Cambridge, Massachusetts, 1985. An ACM Distinguished Dissertation.

[64] , “Explicit bounds for primality testing and related problems”, Mathematics of Com- putation, 55 (1990), 355–380.

[65] , “Number-theoretic algorithms”, An- nual Review of Computer Science, 4 (1990), 119–172.

[66] , “Realistic analysis of some random- ized algorithms”, Journal of Computer and System Sciences, 42 (1991), 30–53.

[67] , “Toward a theory of Pollard’s rho method”, Information and Computation, 90 (1991), 139–155.

[68] E. BACH AND J. SHALLIT, “Factoring with cyclotomic polynomials”, Proceedings of the IEEE 26th Annual Symposium on Founda- tions of Computer Science, 443–450, 1985.

[69] , “Factoring with cyclotomic polynomi- als”, Mathematics of Computation, 52 (1989), 201–219. An earlier version appeared in [68].

[70] , Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press, Cam- bridge, Massachusetts, 1996.

[71] E. BACH AND J. SORENSON, “Sieve algo- rithms for perfect power testing”, Algorith- mica, 9 (1993), 313–328.

[72] A. BAHREMAN, “PEMToolKit: Building a top-down certification hierarchy”, Proceed- ings of the Internet Society Symposium on Net- work and Distributed System Security, 161– 171, IEEE Computer Society Press, 1995.

[73] T. BARITAUD, M. CAMPANA, P. CHAU- VAUD, AND H. GILBERT, “On the security of the permuted kernel identification scheme”, Advances in Cryptology–CRYPTO ’92 (LNCS 740), 305–311, 1993.

[74] W. BARKER, Cryptanalysis of the Hagelin Cryptograph, Aegean Park Press, Laguna Hills, California, 1977.

[75] P. BARRETT, “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal proces- sor”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 311–323, 1987.

[76] R.K. BAUER, T.A. BERSON, AND R.J. FEIERTAG, “A key distribution protocol using event markers”, ACM Transactions on Com- puter Systems, 1 (1983), 249–255.

[77] U. BAUM AND S. BLACKBURN, “Clock- controlled pseudorandom generators on finite groups”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 6–21, Springer-Verlag, 1995.

[78] F. BAUSPIESS AND H.-J. KNOBLOCH, “How to keep authenticity alive in a com- puter network”, Advances in Cryptology– EUROCRYPT ’89 (LNCS 434), 38–46, 1990.

[79] D. BAYER, S. HABER, AND W.S. STOR- NETTA, “Improving the efficiency and reli- ability of digital time-stamping”, R. Capoc- elli, A. De Santis, and U. Vaccaro, editors, Sequences II: Methods in Communication, Security, and Computer Science, 329–334, Springer-Verlag, 1993.

[80] P. BEAUCHEMIN AND G. BRASSARD, “A generalization of Hellman’s extension to Shannon’s approach to cryptography”, Jour- nal of Cryptology, 1 (1988), 129–131.

[81] P. BEAUCHEMIN, G. BRASSARD, C. CRE ́PEAU, C. GOUTIER, AND C. POMER- ANCE, “The generation of random numbers

that are probably prime”, Journal of Cryptol- ogy, 1 (1988), 53–64.

[82] P. BE ́GUIN AND J.-J. QUISQUATER, “Se- cure acceleration of DSS signatures using insecure server”, Advances in Cryptology– ASIACRYPT ’94 (LNCS 917), 249–259, 1995.

[83] A. BEIMEL AND B. CHOR, “Interaction in key distribution schemes”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 444– 455, 1994.

[84] H. BEKER AND F. PIPER, Cipher Systems: The Protection of Communications, John Wi- ley & Sons, New York, 1982.

[85] H. BEKER AND M. WALKER, “Key manage- ment for secure electronic funds transfer in a retail environment”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 401–410, 1985.

[86] M. BELLARE, R. CANETTI, AND H. KRAW- CZYK, “Keying hash functions for message authenticaion”, Advances in Cryptology– CRYPTO ’96 (LNCS 1109), 1–15, 1996.

[87] M. BELLARE AND O. GOLDREICH, “On defining proofs of knowledge”, Advances in Cryptology–CRYPTO ’92 (LNCS 740), 390– 420, 1993.

[88] M. BELLARE, O. GOLDREICH, AND S. GOLDWASSER, “Incremental cryptogra- phy: The case of hashing and signing”, Ad- vances in Cryptology–CRYPTO ’ 94 (LNCS 839), 216–233, 1994.

[89] , “Incremental cryptography and appli- cation to virus protection”, Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 45–56, 1995.

[90] M. BELLARE, R. GUE ́RIN, AND P. RO- GAWAY, “XOR MACs: New methods for message authentication using finite pseudo- random functions”, Advances in Cryptology– CRYPTO ’95 (LNCS 963), 15–28, 1995.

[91] M. BELLARE, J. KILIAN, AND P. ROG- AWAY, “The security of cipher block chain- ing”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 341–358, 1994.

[92] M. BELLARE AND S. MICALI, “How to sign given any trapdoor function”, Advances in Cryptology–CRYPTO ’ 88 (LNCS 403), 200– 215, 1990.

M. BELLARE AND P. ROGAWAY, “Random oracles are practical: a paradigm for designing efficient protocols”, 1st ACM Conference on Computer and Communications Security, 62– 73, ACM Press, 1993.

, “Entity authentication and key dis- tribution”, Advances in Cryptology–CRYPTO ’ 93 (LNCS 773), 232–249, 1994.

, “Optimal asymmetric encryption”,

Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 92–111, 1995.

, “Provably secure session key distribu- tion – the three party case”, Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 57–66, 1995.

M.J. BELLER, L.-F. CHANG, AND Y. YA- COBI, “Privacy and authentication on a portable communications system”, IEEE Global Telecommunications Conference, 1922–1927, 1991.

, “Security for personal communica- tions services: public-key vs. private key approaches”, The Third IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC’92), 26–31, 1992.

, “Privacy and authentication on a portable communications system”, IEEE Journal on Selected Areas in Communica- tions, 11 (1993), 821–829.

M.J. BELLER AND Y. YACOBI, “Minimal asymmetric authentication and key agree- ment schemes”, October 1994 unpublished manuscript.

, “Fully-fledged two-way public key au- thentication and key agreement for low-cost terminals”, Electronics Letters, 29 (May 27, 1993), 999–1001.

S.M. BELLOVIN AND M. MERRITT, “Cryp- tographic protocol for secure communica- tions”, U.S. Patent # 5,241,599, 31 Aug 1993.

, “Limitations of the Kerberos authen- tication system”, Computer Communication Review, 20 (1990), 119–132.

, “Encrypted key exchange: password- based protocols secure against dictionary at- tacks”, Proceedings of the 1992 IEEE Com- puter Society Symposium on Research in Se- curity and Privacy, 72–84, 1992.

, “Augmented encrypted key exchange: a password-based protocol secure against dic- tionary attacks and password file compro- mise”, 1st ACM Conference on Computer and Communications Security, 244–250, ACM Press, 1993.

, “An attack on the Interlock Protocol when used for authentication”, IEEE Transac- tions on Information Theory, 40 (1994), 273– 275.

I. BEN-AROYA AND E. BIHAM, “Differ- ential cyptanalysis of Lucifer”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 187– 199, 1994.

, “Differential cryptanalysis of Lu- cifer”, Journal of Cryptology, 9 (1996), 21– 34. An earlier version appeared in [107].

M. BEN-OR, “Probabilistic algorithms in fi- nite fields”, Proceedings of the IEEE 22nd An- nual Symposium on Foundations of Computer Science, 394–398, 1981.

J. BENALOH, “Secret sharing homomor- phisms: Keeping shares of a secret secret”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 251–260, 1987.

J. BENALOH AND M. DE MARE, “One- way accumulators: A decentralized alter- native to digital signatures”, Advances in Cryptology–EUROCRYPT ’93 (LNCS 765), 274–285, 1994.

J. BENALOH AND J. LEICHTER, “General- ized secret sharing and monotone functions”, Advances in Cryptology–CRYPTO ’88 (LNCS 403), 27–35, 1990.

S.BENGIO,G.BRASSARD,Y.G.DESMEDT, C. GOUTIER, AND J.-J. QUISQUATER, “Se- cure implementation of identification sys- tems”, Journal of Cryptology, 4 (1991), 175– 183.

C. BENNETT, G. BRASSARD, S. BREID- BART, AND S. WIESNER, “Quantum cryp- tography, or unforgeable subway tokens”, Ad- vances in Cryptology–Proceedings of Crypto 82, 267–275, 1983.

C. BENNETT, G. BRASSARD, AND A. EK- ERT, “Quantum cryptography”, Scientific American, special issue (1997), 164–171.

S. BERKOVITS, “How to broadcast a secret”,

Advances in Cryptology–EUROCRYPT ’ 91 (LNCS 547), 535–541, 1991.

E.R. BERLEKAMP, “Factoring polynomials over finite fields”, Bell System Technical Jour- nal, 46 (1967), 1853–1859.

, Algebric Coding Theory, McGraw Hill, New York, 1968.

, “Factoring polynomials over large fi- nite fields”, Mathematics of Computation, 24 (1970), 713–735.

E.R. BERLEKAMP, R.J. MCELIECE, AND H.C.A. VAN TILBORG, “On the inherent intractability of certain coding problems”, IEEE Transactions on Information Theory, 24 (1978), 384–386.

D.J. BERNSTEIN, “Detecting perfect powers in essentially linear time”, preprint, 1995.

D.J. BERNSTEIN AND A.K. LENSTRA, “A general number field sieve implementation”, A.K. Lenstra and H.W. Lenstra Jr., editors, The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathemat- ics, 103–126, Springer-Verlag, 1993.

T. BETH, “Efficient zero-knowledge identifi- cation scheme for smart cards”, Advances in Cryptology–EUROCRYPT ’ 88 (LNCS 330), 77–84, 1988.

T. BETH AND Z.-D. DAI, “On the complex- ity of pseudo-random sequences – or: If you can describe a sequence it can’t be random”, Advances in Cryptology–EUROCRYPT ’89 (LNCS 434), 533–543, 1990.

T. BETH, H.-J. KNOBLOCH, M. OTTEN, G.J. SIMMONS, AND P. WICHMANN, “To- wards acceptable key escrow systems”, 2nd ACM Conference on Computer and Commu- nications Security, 51–58, ACM Press, 1994.

T. BETH AND F.C. PIPER, “The stop-and- go generator”, Advances in Cryptology– Proceedings of EUROCRYPT 84 (LNCS 209), 88–92, 1985.

J. BIERBRAUER, T. JOHANSSON, G. KA- BATIANSKII, AND B. SMEETS, “On fami- lies of hash functions via geometric codes and concatenation”, Advances in Cryptology– CRYPTO ’93 (LNCS 773), 331–342, 1994.

E. BIHAM, “New types of cryptanalytic attacks using related keys”, Advances in Cryptology–EUROCRYPT ’93 (LNCS 765), 398–409, 1994.

, “New types of cryptanalytic attacks using related keys”, Journal of Cryptology, 7 (1994), 229–246. An earlier version appeared in [128].

, “On modes of operation”, R. Ander- son, editor, Fast Software Encryption, Cam- bridge Security Workshop (LNCS 809), 116– 120, Springer-Verlag, 1994.

, “Cryptanalysis of multiple modes of operation”, Advances in Cryptology– ASIACRYPT ’94 (LNCS 917), 278–292, 1995.

, “On Matsui’s linear cryptanalysis”,

Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 341–355, 1995.

E. BIHAM AND A. BIRYUKOV, “How to strengthen DES using existing hardware”, Advances in Cryptology–ASIACRYPT ’ 94 (LNCS 917), 398–412, 1995.

E. BIHAM AND A. SHAMIR, “Differential cryptanalysis of DES-like cryptosystems”, Journal of Cryptology, 4 (1991), 3–72. An earlier version appeared in [135].

, “Differential cryptanalysis of DES- like cryptosystems”, Advances in Cryptology– CRYPTO ’90 (LNCS 537), 2–21, 1991.

, “Differential cryptanalysis of Feal and N-Hash”, Advances in Cryptology– EUROCRYPT ’91 (LNCS 547), 1–16, 1991.

, “Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI, and Lucifer”, Ad- vances in Cryptology–CRYPTO ’91 (LNCS 576), 156–171, 1992.

, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, New York, 1993.

, “Differential cryptanalysis of the full 16-round DES”, Advances in Cryptology– CRYPTO ’ 92 (LNCS 740), 487–496, 1993.

R. BIRD, I. GOPAL, A. HERZBERG, P. JANSON, S. KUTTEN, R. MOLVA, AND M. YUNG, “Systematic design of two- party authentication protocols”, Advances in Cryptology–CRYPTO ’91 (LNCS 576), 44– 61, 1992.

, “Systematic design of a family of attack-resistant authentication protocols”, IEEE Journal on Selected Areas in Commu- nications, 11 (1993), 679–693.

, “The KryptoKnight family of light- weight protocols for authentication and key distribution”, IEEE/ACM Transactions on Networking, 3 (1995), 31–41.

S. BLACKBURN, S. MURPHY, AND J. STE- RN, “The cryptanalysis of a public-key imple- mentation of finite group mappings”, Journal of Cryptology, 8 (1995), 157–166.

R.E. BLAHUT, Principles and Practice of In- formation Theory, Addison-Wesley, Reading, Massachusetts, 1987.

I.F. BLAKE, R. FUJI-HARA, R.C. MULLIN, AND S.A. VANSTONE, “Computing loga- rithms in finite fields of characteristic two”, SIAM Journal on Algebraic and Discrete Methods, 5 (1984), 276–285.

I.F. BLAKE, S. GAO, AND R. LAMBERT, “Constructive problems for irreducible poly- nomials over finite fields”, T.A. Gulliver and N.P. Secord, editors, Information Theory and Applications (LNCS 793), 1–23, Springer- Verlag, 1994.

B. BLAKLEY, G.R. BLAKLEY, A.H. CHAN, AND J.L. MASSEY, “Threshold schemes with disenrollment”, Advances in Cryptology– CRYPTO ’92 (LNCS 740), 540–548, 1993.

G . B L A K L E Y , “Safeguarding cryptographic keys”, Proceedings of AFIPS National Com- puter Conference, 313–317, 1979.

, “A computer algorithm for calculating the product AB modulo M”, IEEE Transac- tions on Computers, 32 (1983), 497–500.

G. BLAKLEY AND I. BOROSH, “Rivest- Shamir-Adleman public key cryptosystems do not always conceal messages”, Comput- ers and Mathematics with Applications, 5:3 (1979), 169–178.

G. BLAKLEY AND C. MEADOWS, “Security of ramp schemes”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 242–268, 1985.

M. BLAZE, “Protocol failure in the escrowed encryption standard”, 2nd ACM Conference on Computer and Communications Security, 59–67, ACM Press, 1994.

D. BLEICHENBACHER, “Generating ElGa- mal signatures without knowing the secret key”, Advances in Cryptology–EUROCRYPT ’96 (LNCS 1070), 10–18, 1996.

D. BLEICHENBACHER, W. BOSMA, AND A.K. LENSTRA, “Some remarks on Lucas- based cryptosystems”, Advances in Cryptolo- gy–CRYPTO ’ 95 (LNCS 963), 386–396, 1995.

D. BLEICHENBACHER AND U. MAURER, “Directed acyclic graphs, one-way func- tions and digital signatures”, Advances in Cryptology–CRYPTO ’ 94 (LNCS 839), 75– 82, 1994.

U.BLO ̈CHERANDM.DICHTL,“Fish:Afast software stream cipher”, R. Anderson, editor, Fast Software Encryption, Cambridge Secu- rity Workshop (LNCS 809), 41–44, Springer- Verlag, 1994.

R.BLOM,“Non-publickeydistribution”,Ad- vances in Cryptology–Proceedings of Crypto 82, 231–236, 1983.

, “An optimal class of symmet- ric key generation systems”, Advances in Cryptology–Proceedings of EUROCRYPT 84 (LNCS 209), 335–338, 1985.

L. BLUM, M. BLUM, AND M. SHUB, “Com- parison of two pseudo-random number gener- ators”, Advances in Cryptology–Proceedings of Crypto 82, 61–78, 1983.

, “A simple unpredictable pseudo- random number generator”, SIAM Journal on Computing, 15 (1986), 364–383. An earlier version appeared in [159].

M. BLUM, “Independent unbiased coin flips from a correlated biased source: a finite state Markov chain”, Proceedings of the IEEE 25th Annual Symposium on Foundations of Com- puter Science, 425–433, 1984.

M. BLUM, A. DE SANTIS, S. MICALI, AND G. PERSIANO, “Noninteractive zero- knowledge”, SIAM Journal on Computing, 20 (1991), 1084–1118.

M. BLUM, P. FELDMAN, AND S. MICALI, “Non-interactive zero-knowledge and its ap- plications”, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 103–112, 1988.

M. BLUM AND S. GOLDWASSER, “An ef- ficient probabilistic public-key encryption scheme which hides all partial informa- tion”, Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 289–299, 1985.

M.BLUMANDS.MICALI,“Howtogenerate cryptographically strong sequences of pseudo random bits”, Proceedings of the IEEE 23rd Annual Symposium on Foundations of Com- puter Science, 112–117, 1982.

, “How to generate cryptographically strong sequences of pseudo-random bits”,

SIAM Journal on Computing, 13 (1984), 850– 864. An earlier version appeared in [165].

C.BLUNDOANDA.CRESTI,“Spacerequire- ments for broadcast encryption”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 287–298, 1995.

C. BLUNDO, A. CRESTI, A. DE SANTIS, AND U. VACCARO, “Fully dynamic secret sharing schemes”, Advances in Cryptology– CRYPTO ’ 93 (LNCS 773), 110–125, 1994.

C.BLUNDO,A.DESANTIS,A.HERZBERG, S. KUTTEN, U. VACCARO, AND M. YUNG, “Perfectly-secure key distribution for dy- namic conferences”, Advances in Cryptology– CRYPTO ’92 (LNCS 740), 471–486, 1993.

R.V. BOOK AND F. OTTO, “The verifia- bility of two-party protocols”, Advances in Cryptology–EUROCRYPT ’85 (LNCS 219), 254–260, 1986.

A. BOOTH, “A signed binary multiplication technique”, The Quarterly Journal of Me- chanics and Applied Mathematics, 4 (1951), 236–240.

J. BOS AND D. CHAUM, “Provably unforge- able signatures”, Advances in Cryptology– CRYPTO ’ 92 (LNCS 740), 1–14, 1993.

J. BOS AND M. COSTER, “Addition chain heuristics”, Advances in Cryptology– CRYPTO ’89 (LNCS 435), 400–407, 1990.

W. BOSMA AND M.-P VAN DER HULST, “Faster primality testing”, Advances in Cryptology–EUROCRYPT ’89 (LNCS 434), 652–656, 1990.

A. BOSSELAERS, R. GOVAERTS, AND J. VANDEWALLE, “Cryptography within phase I of the EEC-RACE programme”, B. Preneel, R. Govaerts, and J. Vandewalle, editors, Computer Security and Industrial Cryptography: State of the Art and Evolution (LNCS 741), 227–234, Springer-Verlag, 1993.

, “Comparison of three modular re- duction functions”, Advances in Cryptology– CRYPTO ’93 (LNCS 773), 175–186, 1994.

, “Fast hashing on the Pentium”, Ad- vances in Cryptology–CRYPTO ’96 (LNCS 1109), 298–312, 1996.

A. BOSSELAERS AND B. PRENEEL, edi- tors, Integrity Primitives for Secure Informa- tion Systems: Final Report of RACE Integrity Primitives Evaluation RIPE-RACE 1040, LNCS 1007, Springer-Verlag, New York, 1995.

J. BOYAR, “Inferring sequences produced by a linear congruential generator missing low- order bits”, Journal of Cryptology, 1 (1989), 177–184.

, “Inferring sequences produced by pseudo-random number generators”, Journal of the Association for Computing Machinery, 36 (1989), 129–141.

J. BOYAR, D. CHAUM, I.B. DAMGA ̊ RD, AND T. PEDERSEN, “Convertible undeni- able signatures”, Advances in Cryptology– CRYPTO ’90 (LNCS 537), 189–205, 1991.

C.BOYD,“Digitalmultisignatures”,H.Beker and F. Piper, editors, Cryptography and Cod- ing, Institute of Mathematics & Its Applica- tions (IMA), 241–246, Clarendon Press, 1989.

C. BOYD AND W. MAO, “On a limitation of BAN logic”, Advances in Cryptology–EUROCRYPT 1994. ’ 93 (LNCS 765),240–247,

B.O. BRACHTL, D. COPPERSMITH, M.M. HYDEN, S.M. MATYAS JR., C.H.W. MEYER, J. OSEAS, S. PILPEL, AND M. SCHILLING, “Data authentication using modification detection codes based on a pub- lic one-way encryption function”, U.S. Patent # 4,908,861, 13 Mar 1990.

S. BRANDS, “Restrictive blinding of secret- key certificates”, Advances in Cryptology– EUROCRYPT ’ 95 (LNCS 921), 231–247, 1995.

J. BRANDT AND I. DAMGA ̊RD, “On gen- eration of probable primes by incremental search”, Advances in Cryptology–CRYPTO ’92 (LNCS 740), 358–370, 1993.

J. BRANDT, I. DAMGA ̊RD, AND P. LAN- DROCK, “Speeding up prime number gener- ation”, Advances in Cryptology–ASIACRYPT ’91 (LNCS 739), 440–449, 1993.

J. BRANDT, I. DAMGA ̊ RD, P. LANDROCK, AND T. PEDERSEN, “Zero-knowledge au- thentication scheme with secret key ex- change”, Advances in Cryptology–CRYPTO ’88 (LNCS 403), 583–588, 1990.

D.K. BRANSTAD, “Encryption protection in computer data communications”, Proceed- ings of the 4th Data Communications Sympo- sium (Quebec), 8.1–8.7, IEEE, 1975.

G. BRASSARD, “A note on the complexity of cryptography”, IEEE Transactions on Infor- mation Theory, 25 (1979), 232–233.

, “On computationally secure authen- tication tags requiring short secret shared keys”, Advances in Cryptology–Proceedings of Crypto 82, 79–86, 1983.

, Modern Cryptology: A Tutorial, LNCS 325, Springer-Verlag, New York, 1988.

G. BRASSARD, D. CHAUM, AND C. CRE ́PEAU- , “Minimum disclosure proofs of knowledge”, Journal of Computer and System Sciences, 37 (1988), 156–189.

G. BRASSARD AND C. CRE ́PEAU, “Zero- knowledge simulation of Boolean circuits”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 223–233, 1987.

, “Sorting out zero-knowledge”, Ad- vances in Cryptology–EUROCRYPT ’ 89 (LNCS 434), 181–191, 1990.

R.P.BRENT,“AnimprovedMonteCarlofac- torization algorithm”, BIT, 20 (1980), 176– 184.

R.P. BRENT AND J.M. POLLARD, “Factor- ization of the eighth Fermat number”, Math- ematics of Computation, 36 (1981), 627–630.

D.M.BRESSOUD,FactorizationandPrimal- ity Testing, Springer-Verlag, New York, 1989.

E.F. BRICKELL, “A fast modular multipli- cation algorithm with applications to two key cryptography”, Advances in Cryptology– Proceedings of Crypto 82, 51–60, 1983.

, “Breaking iterated knapsacks”,

Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 342–358, 1985.

, “The cryptanalysis of knapsack cryp- tosystems”, R.D. Ringeisen and F.S. Roberts, editors, Applications of Discrete Mathemat- ics, 3–23, SIAM, 1988.

E.F. BRICKELL AND J.M. DELAURENTIS, “An attack on a signature scheme proposed by Okamoto and Shiraishi”, Advances in Cryptology–CRYPTO ’85 (LNCS 218), 28– 32, 1986.

E.F. BRICKELL, D.M. GORDON, AND K.S. MCCURLEY, “Method for exponentiating in cryptographic systems”, U.S. Patent # 5,299,262, 29 Mar 1994.

[204] E.F. BRICKELL, D.M. GORDON, K.S. MC- CURLEY, AND D.B. WILSON, “Fast expo- nentiation with precomputation”, Advances in Cryptology–EUROCRYPT ’92 (LNCS 658), 200–207, 1993.

[205] E.F. BRICKELL, P.J. LEE, AND Y. YACOBI, “Secure audio teleconference”, Advances in Cryptology–CRYPTO ’87 (LNCS 293), 418– 426, 1988.

[206] E.F. BRICKELL AND K.S. MCCURLEY, “An interactive identification scheme based on dis- crete logarithms and factoring”, Advances in Cryptology–EUROCRYPT ’ 90 (LNCS 473), 63–71, 1991.

[207] , “An interactive identification scheme based on discrete logarithms and factoring”, Journal of Cryptology, 5 (1992), 29–39. An earlier version appeared in [206].

[208] E.F. BRICKELL AND A.M. ODLYZKO, “Cryptanalysis: A survey of recent results”, Proceedings of the IEEE, 76 (1988), 578–593.

[209] , “Cryptanalysis: A survey of recent re- sults”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information In- tegrity, 501–540, IEEE Press, 1992. An ear- lier version appeared in [208].

[210] J. BRILLHART, D. LEHMER, AND J. SELF- RIDGE, “New primality criteria and factoriza- tions of 2m ± 1”, Mathematics of Computa- tion, 29 (1975), 620–647.

[211] J. BRILLHART, D. LEHMER, J. SELFRIDGE, B. TUCKERMAN, AND S. WAGSTAFF JR., Factorizations of bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to High Powers, volume 22 of Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, 2nd edition, 1988.

[212] J. BRILLHART AND J. SELFRIDGE, “Some factorizations of 2n ± 1 and related results”, Mathematics of Computation, 21 (1967), 87– 96.

[213] D. BRILLINGER, Time Series: Data Analy- sis and Theory, Holden-Day, San Francisco, 1981.

[214] L. BROWN, M. KWAN, J. PIEPRZYK, AND J. SEBERRY, “Improving resistance to differential cryptanalysis and the re- design of LOKI”, Advances in Cryptology– ASIACRYPT ’91 (LNCS 739), 36–50, 1993.

[215] L. BROWN, J. PIEPRZYK, AND J. SEBERRY, “LOKI – a cryptographic primitive for authen- tication and secrecy applications”, Advances

J.BUCHMANNANDS.DU ̈LLMANN,“Onthe computation of discrete logarithms in class groups”, Advances in Cryptology–CRYPTO ’ 90 (LNCS 537), 134–139, 1991.

J. BUCHMANN, J. LOHO, AND J. ZAYER, “An implementation of the general num- ber field sieve”, Advances in Cryptology– CRYPTO ’93 (LNCS 773), 159–165, 1994.

J. BUCHMANN AND H.C. WILLIAMS, “A key-exchange system based on imaginary quadratic fields”, Journal of Cryptology, 1 (1988), 107–118.

J.P. BUHLER, H.W. LENSTRA JR., AND C. POMERANCE, “Factoring integers with the number field sieve”, A.K. Lenstra and H.W. Lenstra Jr., editors, The Development of the Number Field Sieve, volume 1554 of Lec- ture Notes in Mathematics, 50–94, Springer- Verlag, 1993.

M. BURMESTER, “On the risk of opening distributed keys”, Advances in Cryptology– CRYPTO ’94 (LNCS 839), 308–317, 1994.

M. BURMESTER AND Y. DESMEDT, “Re- marks on soundness of proofs”, Electronics Letters, 25 (October 26, 1989), 1509–1511.

, “A secure and efficient confer- ence key distribution system”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 275–286, 1995.

M. BURMESTER, Y. DESMEDT, F. PIPER, AND M. WALKER, “A general zero- knowledge scheme”, Advances in Cryptology– EUROCRYPT ’ 89 (LNCS 434), 122–133, 1990.

M. BURROWS, M. ABADI, AND R. NEED- HAM, “A logic of authentication”, Proceed- ings of the Royal Society of London Series A: Mathematical and Physical Sciences, 246 (1989), 233–271. Preliminary version ap- peared as 1989 version of [227].

, “A logic of authentication”, Proceed- ings of the 12th Annual ACM Symposium on Operating Systems Principles, 1–13, 1989.

, “A logic of authentication”, ACM Transactions on Computer Systems, 8 (1990), 18–36.

, “A logic of authentication”, DEC SRC report #39, Digital Equipment Corporation, Palo Alto, CA, Feb. 1989. Revised Feb. 1990.

in Cryptology–AUSCRYPT 229–236, 1990.’ 90(LNCS453),

J.L. CAMENISCH, J.-M. PIVETEAU, AND M.A. STADLER, “Blind signatures based on the discrete logarithm problem”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 428–432, 1995.

K.W. CAMPBELL AND M.J. WIENER, “DES is not a group”, Advances in Cryptology– CRYPTO ’92 (LNCS 740), 512–520, 1993.

C.M. CAMPBELL JR., “Design and speci- fication of cryptographic capabilities”, D.K. Branstad, editor, Computer security and the Data Encryption Standard, 54–66, NBS Spe- cial Publication 500-27, U.S. Department of Commerce, National Bureau of Standards, Washington, D.C., 1977.

E.R. CANFIELD, P. ERDO ̈ S, AND C. POM- ERANCE, “On a problem of Oppenheim con- cerning ‘Factorisatio Numerorum’”, Journal of Number Theory, 17 (1983), 1–28.

D.G. CANTOR AND H. ZASSENHAUS, “A new algorithm for factoring polynomials over finite fields”, Mathematics of Computation, 36 (1981), 587–592.

J.L. CARTER AND M.N. WEGMAN, “Uni- versal classes of hash functions”, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 106–112, 1977.

, “Universal classes of hash functions”, Journal of Computer and System Sciences, 18 (1979), 143–154. An earlier version appeared in [233].

F.CHABAUD,“Onthesecurityofsomecryp- tosystems based on error-correcting codes”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 131–139, 1995.

G.J.CHAITIN,“Onthelengthofprogramsfor computing finite binary sequences”, Journal of the Association for Computing Machinery, 13 (1966), 547–569.

W.G. CHAMBERS, “Clock-controlled shift registers in binary sequence generators”, IEE Proceedings E – Computers and Digital Tech- niques, 135 (1988), 17–24.

, “Two stream ciphers”, R. Ander- son, editor, Fast Software Encryption, Cam- bridge Security Workshop (LNCS 809), 51– 55, Springer-Verlag, 1994.

W.G. CHAMBERS AND D. GOLLMANN, “Lock-in effect in cascades of clock- controlled shift-registers”, Advances in Cryptology–EUROCRYPT ’ 88 (LNCS 330), 331–343, 1988.

B. CHAR, K. GEDDES, G. GONNET, B. LEONG, M. MONAGAN, AND S. WATT, Maple V Library Reference Manual, Springer- Verlag, New York, 1991.

C. CHARNES, L. O’CONNOR, J. PIEPRZYK, R. SAFAVI-NAINI, AND Y. ZHENG, “Com- ments on Soviet encryption algorithm”, Ad- vances in Cryptology–EUROCRYPT ’ 94 (LNCS 950), 433–438, 1995.

D. CHAUM, “Blind signatures for untrace- able payments”, Advances in Cryptology– Proceedings of Crypto 82, 199–203, 1983.

, “Security without identification: transaction systems to make big brother obso- lete”, Communications of the ACM, 28 (1985), 1030–1044.

, “Demonstrating that a public predicate can be satisfied without revealing any infor- mation about how”, Advances in Cryptology– CRYPTO ’ 86 (LNCS 263), 195–199, 1987.

, “Blinding for unanticipated signa- tures”, Advances in Cryptology–EUROCRYPT ’87 (LNCS 304), 227–233, 1988.

, “Zero-knowledge undeniable signa- tures”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 458–464, 1991.

, “Designated confirmer signatures”,

Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 86–91, 1995.

D.CHAUM,J.-H.EVERTSE,ANDJ.VANDE GRAAF, “An improved protocol for demon- strating possession of discrete logarithms and some generalizations”, Advances in Cryptology–EUROCRYPT ’87 (LNCS 304), 127–141, 1988.

D. CHAUM, J.-H. EVERTSE, J. VAN DE GRAAF, AND R. PERALTA, “Demonstrating possession of a discrete logarithm without re- vealing it”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 200–212, 1987.

D. CHAUM, A. FIAT, AND M. NAOR, “Untraceable electronic cash”, Advances in Cryptology–CRYPTO ’88 (LNCS 403), 319– 327, 1990.

D. CHAUM AND T.P. PEDERSEN, “Wal- let databases with observers”, Advances in Cryptology–CRYPTO ’92 (LNCS 740), 89– 105, 1993.

D. CHAUM AND H. VAN ANTWER- P E N, “Undeniable signatures”, Advances in Cryptology–CRYPTO ’ 89 (LNCS 435), 212– 216, 1990.

D. CHAUM AND E. VAN HEIJST, “Group sig- natures”, Advances in Cryptology–EUROCR- YPT ’ 91 (LNCS 547), 257–265, 1991.

D. CHAUM, E. VAN HEIJST, AND B. PFITZ- MANN, “Cryptographically strong undeni- able signatures, unconditionally secure for the signer”, Advances in Cryptology–CRYPTO ’91 (LNCS 576), 470–484, 1992.

L. CHEN AND T.P. PEDERSEN, “New group signature schemes”, Advances in Cryptology– EUROCRYPT ’ 94 (LNCS 950), 171–181, 1995.

V. CHEPYZHOV AND B. SMEETS, “On a fast correlation attack on certain stream ciphers”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 176–185, 1991.

B. CHOR AND O. GOLDREICH, “Unbiased bits from sources of weak randomness and probabilistic communication complexity”, Proceedings of the IEEE 26th Annual Sym- posium on Foundations of Computer Science, 429–442, 1985.

, “Unbiased bits from sources of weak randomness and probabilistic communication complexity”, SIAM Journal on Computing, 17 (1988), 230–261. An earlier version appeared in [257].

B. CHOR, S. GOLDWASSER, S. MICALI, AND B. AWERBUCH, “Verifiable secret shar- ing and achieving simultaneity in the presence of faults”, Proceedings of the IEEE 26th An- nual Symposium on Foundations of Computer Science, 383–395, 1985.

B. CHOR AND R.L. RIVEST, “A knap- sack type public key cryptosystem based on arithmetic in finite fields”, Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 54–65, 1985.

, “A knapsack-type public key cryp- tosystem based on arithmetic in finite fields”, IEEE Transactions on Information Theory, 34 (1988), 901–909. An earlier version appeared in [260].

A. CLARK, J. GOLIC ́, AND E. DAWSON, “A comparison of fast correlation attacks”, D. Gollmann, editor, Fast Software Encryp- tion, Third International Workshop (LNCS 1039), 145–157, Springer-Verlag, 1996.

H. COHEN, A Course in Computational Al- gebraic Number Theory, Springer-Verlag, Berlin, 1993.

H. COHEN AND A.K. LENSTRA, “Imple- mentation of a new primality test”, Mathemat- ics of Computation, 48 (1987), 103–121.

H. COHEN AND H.W. LENSTRA JR., “Pri- mality testing and Jacobi sums”, Mathematics of Computation, 42 (1984), 297–330.

D. COPPERSMITH, “Fast evaluation of loga- rithms in fields of characteristic two”, IEEE Transactions on Information Theory, 30 (1984), 587–594.

, “Another birthday attack”, Advances in Cryptology–CRYPTO ’85 (LNCS 218), 14– 17, 1986.

, “The real reason for Rivest’s phenomenon”, Advances in Cryptology– CRYPTO ’ 85 (LNCS 218), 535–536, 1986.

, “Modifications to the number field sieve”, Journal of Cryptology, 6 (1993), 169– 180.

, “Solving linear equations over GF (2): Block Lanczos algorithm”, Linear Algebra and its Applications, 192 (1993), 33– 60.

, “The Data Encryption Standard (DES) and its strength against attacks”, IBM Jour- nal of Research and Development, 38 (1994), 243–250.

, “Solving homogeneous linear equa- tions over GF(2) via block Wiedemann al- gorithm”, Mathematics of Computation, 62 (1994), 333–350.

, “Finding a small root of a bivari- ate integer equation; factoring with high bits known”, Advances in Cryptology– EUROCRYPT ’96 (LNCS 1070), 178–189, 1996.

, “Finding a small root of a univariate modular equation”, Advances in Cryptology– EUROCRYPT ’96 (LNCS 1070), 155–165, 1996.

, “Analysis of ISO/CCITT Document X.509 Annex D”, memorandum, IBM T.J. Watson Research Center, Yorktown Heights, N.Y., 10598, U.S.A., June 11 1989.

, “Two broken hash functions”, IBM Research Report RC 18397, IBM T.J. Wat- son Research Center, Yorktown Heights, N.Y., 10598, U.S.A., Oct. 6 1992.

D. COPPERSMITH, M. FRANKLIN, J. PATA- RIN, AND M. REITER, “Low-exponent RSA with related messages”, Advances in Cryptology–EUROCRYPT ’96 (LNCS 1070), 1–9, 1996.

D. COPPERSMITH, D.B. JOHNSON, AND S.M. MATYAS, “A proposed mode for triple- DES encryption”, IBM Journal of Research and Development, 40 (1996), 253–261.

D. COPPERSMITH, H. KRAWCZYK, AND Y. MANSOUR, “The shrinking generator”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 22–39, 1994.

D. COPPERSMITH, A.M. ODLZYKO, AND R. SCHROEPPEL, “Discrete logarithms in GF (p)”, Algorithmica, 1 (1986), 1–15.

D. COPPERSMITH AND P. ROGAWAY, “Software-efficient pseudorandom function and the use thereof for encryption”, U.S. Patent # 5,454,039, 26 Sep 1995.

T.H. CORMEN, C.E. LEISERSON, AND R.L. RIVEST, Introduction to Algorithms, MIT Press, Cambridge, Massachusetts, 1990.

M.J. COSTER, A. JOUX, B.A. LAMAC- CHIA, A.M. ODLYZKO, C.P. SCHNORR, AND J. STERN, “Improved low-density subset sum algorithms”, Computational Complexity, 2 (1992), 111–128.

J.-M. COUVEIGNES, “Computing a square root for the number field sieve”, A.K. Lenstra and H.W. Lenstra Jr., editors, The Develop- ment of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, 95–102, Springer-Verlag, 1993.

T. COVER AND R. KING, “A convergent gambling estimate of the entropy of English”, IEEE Transactions on Information Theory, 24 (1978), 413–421.

R.E.CRANDALL,“Methodandapparatusfor public key exchange in a cryptographic sys- tem”, U.S. Patent # 5,159,632, 27 Oct 1992.

, “Method and apparatus for pub- lic key exchange in a cryptographic sys- tem”, U.S. Patent # 5,271,061, 14 Dec 1993 (continuation-in-part of 5,159,632).

R.A. CROFT AND S.P. HARRIS, “Public-key cryptography and re-usable shared secrets”, H. Beker and F. Piper, editors, Cryptogra- phy and Coding, Institute of Mathematics & Its Applications (IMA), 189–201, Clarendon Press, 1989.

J. DAEMEN, Cipher and hash function de- sign, PhD thesis, Katholieke Universiteit Leu- ven (Belgium), 1995.

J. DAEMEN, R. GOVAERTS, AND J. VAN- DEWALLE, “A new approach to block ci- pher design”, R. Anderson, editor, Fast Soft- ware Encryption, Cambridge Security Work- shop (LNCS 809), 18–32, Springer-Verlag, 1994.

, “Resynchronization weaknesses in synchronous stream ciphers”, Advances in Cryptology–EUROCRYPT ’ 93 (LNCS 765), 159–167, 1994.

, “Weak keys for IDEA”, Advances in Cryptology–CRYPTO ’ 93 (LNCS 773), 224– 231, 1994.

Z.-D DAI, “Proof of Rueppel’s linear com- plexity conjecture”, IEEE Transactions on In- formation Theory, 32 (1986), 440–443.

Z.-D. DAI AND J.-H. YANG, “Linear complexity of periodically repeated ran- dom sequences”, Advances in Cryptology– EUROCRYPT ’ 91 (LNCS 547), 168–175, 1991.

I.B. DAMGA ̊ RD, “Collision free hash func- tions and public key signature schemes”, Advances in Cryptology–EUROCRYPT ’ 87 (LNCS 304), 203–216, 1988.

, “A design principle for hash func- tions”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 416–427, 1990.

, “Towards practical public key systems secure against chosen ciphertext attacks”, Ad- vances in Cryptology–CRYPTO ’91 (LNCS 576), 445–456, 1992.

, “Practical and provably secure re- lease of a secret and exchange of signatures”, Advances in Cryptology–EUROCRYPT ’93 (LNCS 765), 200–217, 1994.

I.B. DAMGA ̊RD AND P. LANDROCK, “Im- proved bounds for the Rabin primality test”, M.J. Ganley, editor, Cryptography and Cod- ing III, volume 45 of Institute of Mathematics & Its Applications (IMA), 117–128, Claren- don Press, 1993.

I.B. DAMGA ̊ RD, P. LANDROCK, AND C. POMERANCE, “Average case error esti- mates for the strong probable prime test”, Mathematics of Computation, 61 (1993), 177– 194.

H. DAVENPORT, “Bases for finite fields”, The Journal of the London Mathematical Society, 43 (1968), 21–39.

G.I. DAVIDA, “Chosen signature cryptanaly- sis of the RSA (MIT) public key cryptosys- tem”, Technical Report TR-CS-82-2, Depart- ment of Electrical Engineering and Computer Science, University of Wisconsin, Milwau- kee, WI, 1982.

D.W. DAVIES, “Some regular properties of the ‘Data Encryption Standard’ algo- rithm”, Advances in Cryptology–Proceedings of Crypto 82, 89–96, 1983.

, “A message authenticator algo- rithm suitable for a mainframe computer”, Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 393–400, 1985.

, “Schemes for electronic funds trans- fer at the point of sale”, K.M. Jackson and J. Hruska, editors, Computer Security Refer- ence Book, 667–689, CRC Press, 1992.

D.W. DAVIES AND D.O. CLAYDEN, “The message authenticator algorithm (MAA) and its implementation”, Report DITC 109/88, National Physical Laboratory, U.K., February 1988.

D.W. DAVIES AND G.I.P. PARKIN, “The average cycle size of the key stream in out- put feedback encipherment”, Advances in Cryptology–Proceedings of Crypto 82, 97–98, 1983.

D.W.DAVIESANDW.L.PRICE,Securityfor Computer Networks, John Wiley & Sons, New York, 2nd edition, 1989.

D. DAVIS, R. IHAKA, AND P. FENSTER- MACHER, “Cryptographic randomness from air turbulence in disk drives”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 114– 120, 1994.

D.DAVISANDR.SWICK,“Networksecurity via private-key certificates”, Operating Sys- tems Review, 24 (1990), 64–67.

J.A. DAVIS, D.B. HOLDRIDGE, AND G.J. SIMMONS, “Status report on factoring (at the Sandia National Labs)”, Advances in Cryptology–Proceedings of EUROCRYPT 84 (LNCS 209), 183–215, 1985.

E. DAWSON, “Cryptanalysis of summa- tion generator”, Advances in Cryptology– AUSCRYPT ’ 92 (LNCS 718), 209–215, 1993.

W. DE JONGE AND D. CHAUM, “Attacks on some RSA signatures”, Advances in Cryptology–CRYPTO ’ 85 (LNCS 218), 18– 27, 1986.

P. DE ROOIJ, “On the security of the Schnorr scheme using preprocessing”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 71–80, 1991.

, “On Schnorr’s preprocessing for digital signature schemes”, Advances in Cryptology–EUROCRYPT ’ 93 (LNCS 765), 435–439, 1994.

, “Efficient exponentiation using pre- computation and vector addition chains”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 389–399, 1995.

A. DE SANTIS, S. MICALI, AND G. PER- SIANO, “Non-interactive zero-knowledge proof systems”, Advances in Cryptology– CRYPTO ’ 87 (LNCS 293), 52–72, 1988.

A. DE SANTIS AND M. YUNG, “On the design of provably secure cryptographic hash functions”, Advances in Cryptology– EUROCRYPT ’ 90 (LNCS 473), 412–431, 1991.

D. DE WALEFFE AND J.-J. QUISQUATER, “Better login protocols for computer net- works”, B. Preneel, R. Govaerts, and J. Vande- walle, editors, Computer Security and Indus- trial Cryptography: State of the Art and Evo- lution (LNCS 741), 50–70, Springer-Verlag, 1993.

J.M. DELAURENTIS, “A further weakness in the common modulus protocol for the RSA cryptoalgorithm”, Cryptologia, 8 (1984), 253–259.

N. DEMYTKO, “A new elliptic curve based analogue of RSA”, Advances in Cryptology– EUROCRYPT ’93 (LNCS 765), 40–49, 1994.

B. DEN BOER, “Cryptanalysis of F.E.A.L.”,

Advances in Cryptology–EUROCRYPT ’88 (LNCS 330), 293–299, 1988.

, “Diffie-Hellman is as strong as dis- crete log for certain primes”, Advances in Cryptology–CRYPTO ’88 (LNCS 403), 530– 539, 1990.

B. DEN BOER AND A. BOSSELAERS, “An attack on the last two rounds of MD4”, Ad- vances in Cryptology–CRYPTO ’ 91 (LNCS 576), 194–203, 1992.

, “Collisions for the compression func- tion of MD5”, Advances in Cryptology– EUROCRYPT ’ 93 (LNCS 765), 293–304, 1994.

D.E. DENNING, Cryptography and Data Security, Addison-Wesley, Reading, Mas- sachusetts, 1983. Reprinted with corrections.

, “Digital signatures with RSA and other public-key cryptosystems”, Communi- cations of the ACM, 27 (1984), 388–392.

, “To tap or not to tap”, Communica- tions of the ACM, 36 (1993), 24–44.

D.E. DENNING AND D.K. BRANSTAD, “A taxonomy for key escrow encryption sys- tems”, Communications of the ACM, 39 (1996), 34–40.

D.E. DENNING AND G.M. SACCO, “Times- tamps in key distribution protocols”, Commu- nications of the ACM, 24 (1981), 533–536.

D.E. DENNING AND M. SMID, “Key escrow- ing today”, IEEE Communications Magazine, 32 (September 1994), 58–68.

J. B. DENNIS AND E. C. VAN HORN, “Pro- gramming semantics for multiprogrammed computations”, Communications of the ACM, 9 (1966), 143–155.

T. DENNY, B. DODSON, A.K. LENSTRA, AND M.S. MANASSE, “On the factoriza- tion of RSA-120”, Advances in Cryptology– CRYPTO ’93 (LNCS 773), 166–174, 1994.

DEPARTMENT OF DEFENSE (U.S.), “Depart- ment of defense password management guide- line”, CSC-STD-002-85, Department of De- fense Computer Security Center, Fort Meade, Maryland, 1985.

Y. D E S M E D T , “Unconditionally secure authentication schemes and practical and theoretical consequences”, Advances in Cryptology–CRYPTO ’85 (LNCS 218), 42– 55, 1986.

, “Society and group oriented cryp- tography: A new concept”, Advances in Cryptology–CRYPTO ’87 (LNCS 293), 120– 127, 1988.

, “Threshold cryptography”, Euro- pean Transactions on Telecommunications, 5 (1994), 449–457.

, “Securing traceability of ciphertexts – Towards a secure software key escrow sys- tem”, Advances in Cryptology–EUROCRYPT ’ 95 (LNCS 921), 147–157, 1995.

Y. DESMEDT AND M. BURMESTER, “To- wards practical ‘proven secure’ authenti- cated key distribution”, 1st ACM Conference on Computer and Communications Security, 228–231, ACM Press, 1993.

Y. DESMEDT, C. GOUTIER, AND S. BEN- GIO, “Special uses and abuses of the Fiat- Shamir passport protocol”, Advances in Cryptology–CRYPTO ’87 (LNCS 293), 21– 39, 1988.

Y. DESMEDT AND A.M. ODLYZKO, “A cho- sen text attack on the RSA cryptosystem and some discrete logarithm schemes”, Ad- vances in Cryptology–CRYPTO ’85 (LNCS 218), 516–522, 1986.

W.DIFFIE,“Thefirsttenyearsofpublic-key cryptography”, Proceedings of the IEEE, 76 (1988), 560–577.

, “The first ten years of public key cryp- tology”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information In- tegrity, 135–175, IEEE Press, 1992. An ear- lier version appeared in [342].

W. DIFFIE AND M.E. HELLMAN, “Mul- tiuser cryptographic techniques”, Proceed- ings of AFIPS National Computer Confer- ence, 109–112, 1976.

, “New directions in cryptography”, IEEE Transactions on Information Theory, 22 (1976), 644–654.

, “Exhaustive cryptanalysis of the NBS Data Encryption Standard”, Computer, 10 (1977), 74–84.

, “Privacy and authentication: An intro- duction to cryptography”, Proceedings of the IEEE, 67 (1979), 397–427.

W.DIFFIE,P.C.VANOORSCHOT,ANDM.J. WIENER, “Authentication and authenticated key exchanges”, Designs, Codes and Cryp- tography, 2 (1992), 107–125.

C. DING, “The differential cryptanalysis and design of natural stream ciphers”, R. Ander- son, editor, Fast Software Encryption, Cam- bridge Security Workshop (LNCS 809), 101– 115, Springer-Verlag, 1994.

B. DIXON AND A.K. LENSTRA, “Massively parallel elliptic curve factoring”, Advances in Cryptology–EUROCRYPT ’92 (LNCS 658), 183–193, 1993.

J.D. DIXON, “Asymptotically fast factoriza- tion of integers”, Mathematics of Computa- tion, 36 (1981), 255–260.

H. DOBBERTIN, “Cryptanalysis of MD4”, Journal of Cryptology, to appear.

, “RIPEMD with two-round compress function is not collision-free”, Journal of Cryptology, to appear; announced at rump session, Eurocrypt ’95.

, “Cryptanalysis of MD4”, D. Goll- mann, editor, Fast Software Encryption, Third International Workshop (LNCS 1039), 53–69, Springer-Verlag, 1996.

H. DOBBERTIN, A. BOSSELAERS, AND B. PRENEEL, “RIPEMD-160: a strengthened version of RIPEMD”, D. Gollmann, editor, Fast Software Encryption, Third International Workshop (LNCS 1039), 71–82, Springer- Verlag, 1996.

B. DODSON AND A.K. LENSTRA, “NFS with four large primes: An explosive experiment”, Advances in Cryptology–CRYPTO ’95 (LNCS 963), 372–385, 1995.

D. DOLEV, C. DWORK, AND M. NAOR, “Non-malleable cryptography”, Proceedings of the 23rd Annual ACM Symposium on The- ory of Computing, 542–552, 1991.

D. DOLEV AND A.C. YAO, “On the secu- rity of public key protocols”, Proceedings of the IEEE 22nd Annual Symposium on Foun- dations of Computer Science, 350–357, 1981.

, “On the security of public key proto- cols”, IEEE Transactions on Information The- ory, 29 (1983), 198–208. An earlier version appeared in [358].

P. DOWNEY, B. LEONG, AND R. SETHI, “Computing sequences with addition chains”, SIAM Journal on Computing, 10 (1981), 638– 646.

S.R. DUSSE ́ AND B.S. KALISKI JR., “A cryptographic library for the Motorola DSP 56000”, Advances in Cryptology– EUROCRYPT ’ 90 (LNCS 473), 230–244, 1991.

H. EBERLE, “A high-speed DES implemen- tation for network applications”, Advances in Cryptology–CRYPTO ’92 (LNCS 740), 521– 539, 1993.

W. F. EHRSAM, C.H.W. MEYER, R.L. POWERS, J.L. SMITH, AND W.L. TUCH- M A N, “Product block cipher system for data security”, U.S. Patent # 3,962,539, 8 Jun 1976.

W.F. EHRSAM, S.M. MATYAS, C.H. MEYER, AND W.L. TUCHMAN, “A crypto- graphic key management scheme for imple- menting the Data Encryption Standard”, IBM Systems Journal, 17 (1978), 106–125.

ELECTRONIC INDUSTRIES ASSOCIATION (EIA), “Dual-mode mobile station – base station compatibility standard”, EIA Interim Standard IS-54 Revision B (Rev. B), 1992.

T. ELGAMAL, Cryptography and logarithms over finite fields, PhD thesis, Stanford Univer- sity, 1984.

, “A public key cryptosystem and a sig- nature scheme based on discrete logarithms”, Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 10–18, 1985.

, “A public key cryptosystem and a sig- nature scheme based on discrete logarithms”, IEEE Transactions on Information Theory, 31 (1985), 469–472. An earlier version appeared in [367].

, “A subexponential-time algorithm for computing discrete logarithms over GF(p2)”, IEEE Transactions on Information Theory, 31 (1985), 473–481.

P. ELIAS, “The efficient construction of an unbiased random sequence”, The Annals of Mathematical Statistics, 43 (1972), 865–870.

, “Interval and recency rank source en- coding: Two on-line adaptive variable-length schemes”, IEEE Transactions on Information Theory, 33 (1987), 3–10.

E.D. ERDMANN, “Empirical tests of binary keystreams”, Master’s thesis, Department of Mathematics, Royal Holloway and Bedford New College, University of London, 1992.

P. ERDO ̈S AND C. POMERANCE, “On the number of false witnesses for a composite number”, Mathematics of Computation, 46 (1986), 259–279.

D. ESTES, L.M. ADLEMAN, K. KOMPELLA, K.S. MCCURLEY, AND G.L. MILLER, “Breaking the Ong-Schnorr-Shamir signa- ture scheme for quadratic number fields”, Ad- vances in Cryptology–CRYPTO ’85 (LNCS 218), 3–13, 1986.

A. EVANS JR., W. KANTROWITZ, AND E. WEISS, “A user authentication scheme not requiring secrecy in the computer”, Commu- nications of the ACM, 17 (1974), 437–442.

S. EVEN AND O. GOLDREICH, “On the power of cascade ciphers”, ACM Transactions on Computer Systems, 3 (1985), 108–116.

S. EVEN, O. GOLDREICH, AND S. MI- C A L I, “On-line/off-line digital signatures”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 263–275, 1990.

, “On-line/off-line digital signatures”, Journal of Cryptology, 9 (1996), 35–67. An earlier version appeared in [377].

S. EVEN AND Y. YACOBI, “Cryptocomplex- ity and NP-completeness”, J.W. de Bakker and J. van Leeuwen, editors, Automata, Lan- guages, and Programming, 7th Colloquium (LNCS 85), 195–207, Springer-Verlag, 1980.

D. EVERETT, “Identity verification and bio- metrics”, K.M. Jackson and J. Hruska, edi- tors, Computer Security Reference Book, 37– 73, CRC Press, 1992.

J.-H.EVERTSEANDE.VANHEIJST,“Which new RSA-signatures can be computed from certain given RSA-signatures?”, Journal of Cryptology, 5 (1992), 41–52.

R.C. FAIRFIELD, R.L. MORTENSON, AND K.B. COULTHART, “An LSI random number generator (RNG)”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 203–230, 1985.

U. FEIGE, A. FIAT, AND A. SHAMIR, “Zero- knowledge proofs of identity”, Journal of Cryptology, 1 (1988), 77–94.

U. FEIGE AND A. SHAMIR, “Witness indis- tinguishable and witness hiding protocols”, Proceedings of the 22nd Annual ACM Sym- posium on Theory of Computing, 416–426, 1990.

H. FEISTEL, “Block cipher cryptographic system”, U.S. Patent # 3,798,359, 19 Mar 1974.

, “Step code ciphering system”, U.S. Patent # 3,798,360, 19 Mar 1974.

, “Cryptography and computer pri- vacy”, Scientific American, 228 (May 1973), 15–23.

H. FEISTEL, W.A. NOTZ, AND J.L. SMITH, “Some cryptographic techniques for machine- to-machine data communications”, Proceed- ings of the IEEE, 63 (1975), 1545–1554.

F.A. FELDMAN, “Fast spectral tests for mea- suring nonrandomness and the DES”, Ad- vances in Cryptology–CRYPTO ’ 87 (LNCS 293), 243–254, 1988.

P. FELDMAN, “A practical scheme for non- interactive verifiable secret sharing”, Pro- ceedings of the IEEE 28th Annual Symposium on Foundations of Computer Science, 427– 437, 1987.

D.C. FELDMEIER AND P.R. KARN, “UNIX password security – ten years later”, Advances in Cryptology–CRYPTO ’ 89 (LNCS 435), 44– 63, 1990.

W. FELLER, An Introduction to Probability Theory and its Applications, John Wiley & Sons, New York, 3rd edition, 1968.

A. FIAT AND M. NAOR, “Rigorous time/space tradeoffs for inverting functions”, Proceedings of the 23rd Annual ACM Sym- posium on Theory of Computing, 534–541, 1991.

, “Broadcast encryption”, Advances in Cryptology–CRYPTO ’ 93 (LNCS 773), 480– 491, 1994.

A. FIAT AND A. SHAMIR, “How to prove yourself: Practical solutions to identifica- tion and signature problems”, Advances in Cryptology–CRYPTO ’ 86 (LNCS 263), 186– 194, 1987.

FIPS46,“Dataencryptionstandard”,Federal Information Processing Standards Publication 46, U.S. Department of Commerce/National Bureau of Standards, National Technical In- formation Service, Springfield, Virginia, 1977 (revised as FIPS 46-1:1988; FIPS 46-2:1993).

FIPS 74, “Guidelines for implementing and using the NBS data encryption standard”, Federal Information Processing Standards Publication 74, U.S. Department of Com- merce/National Bureau of Standards, National Technical Information Service, Springfield, Virginia, 1981.

FIPS81,“DESmodesofoperation”,Federal Information Processing Standards Publication 81, U.S. Department of Commerce/National Bureau of Standards, National Technical Information Service, Springfield, Virginia, 1980.

FIPS 112, “Password usage”, Federal Infor- mation Processing Standards Publication 112, U.S. Department of Commerce/National Bu- reau of Standards, National Technical Infor- mation Service, Springfield, Virginia, 1985.

FIPS 113, “Computer data authentication”, Federal Information Processing Standards

Publication 113, U.S. Department of Com- merce/National Bureau of Standards, National Technical Information Service, Springfield, Virginia, 1985.

[401] FIPS140-1,“Securityrequirementsforcryp- tographic modules”, Federal Information Pro- cessing Standards Publication 140-1, U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, Virginia, 1994.

[402] FIPS 171, “Key management using ANSI X9.17”, Federal Information Processing Stan- dards Publication 171, U.S. Department of Commerce/N.I.S.T., National Technical Infor- mation Service, Springfield, Virginia, 1992.

[403] FIPS 180, “Secure hash standard”, Fed- eral Information Processing Standards Pub- lication 180, U.S. Department of Com- merce/N.I.S.T., National Technical Informa- tion Service, Springfield, Virginia, May 11 1993.

[404] FIPS 180-1, “Secure hash standard”, Fed- eral Information Processing Standards Pub- lication 180-1, U.S. Department of Com- merce/N.I.S.T., National Technical Informa- tion Service, Springfield, Virginia, April 17 1995 (supersedes FIPS PUB 180).

[405] FIPS 185, “Escrowed encryption standard (EES)”, Federal Information Processing Stan- dards Publication 185, U.S. Department of Commerce/N.I.S.T., National Technical Infor- mation Service, Springfield, Virginia, 1994.

[406] FIPS 186, “Digital signature standard”, Federal Information Processing Standards Publication 186, U.S. Department of Com- merce/N.I.S.T., National Technical Informa- tion Service, Springfield, Virginia, 1994.

[407] FIPS196,“Entityauthenticationusingpublic key cryptography”, U.S. Department of Com- merce/N.I.S.T., February 18 1997.

[408] A.M. FISCHER, “Public key/signature cryp- tosystem with enhanced digital signature cer- tification”, U.S. Patent # 4,868,877, 19 Sep 1989.

[409] , “Public key/signature cryptosystem with enhanced digital signature certifica- tion”, U.S. Patent # 5,005,200, 2 Apr 1991 (continuation-in-part of 4,868,877).

[410] , “Electronic document authorization”,

Proceedings of the 13th National Computer Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

Security Conference, Washington D.C., spon- sored by N.I.S.T. and the National Computer Security Center, USA, 1990.

J.-B. FISCHER AND J. STERN, “An effi- cient pseudo-random generator provably as secure as syndrome decoding”, Advances in Cryptology–EUROCRYPT ’96 (LNCS 1070), 245–255, 1996.

M. FISCHER, S. MICALI, AND C. RACKOFF, “A secure protocol for oblivious transfer”, un- published (presented at Eurocrypt’84).

P. FLAJOLET AND A. ODLYZKO, “Random mapping statistics”, Advances in Cryptology– EUROCRYPT ’ 89 (LNCS 434), 329–354, 1990.

W. FORD, Computer Communications Se- curity: Principles, Standard Protocols and Techniques, Prentice Hall, Englewood Cliffs, New Jersey, 1994.

, “Standardizing information technol- ogy security”, StandardView, 2 (1994), 64–71.

, “Advances in public-key certificate standards”, Security, Audit and Control, 13 (1995), ACM Press/SIGSAC, 9–15.

W. FORD AND M. WIENER, “A key distri- bution method for object-based protection”, 2nd ACM Conference on Computer and Com- munications Security, 193–197, ACM Press, 1994.

R. FORRE ́, “A fast correlation attack on nonlinearly feedforward filtered shift- register sequences”, Advances in Cryptology– EUROCRYPT ’ 89 (LNCS 434), 586–595, 1990.

Y. FRANKEL AND M. YUNG, “Cryptanaly- sis of the immunized LL public key systems”, Advances in Cryptology–CRYPTO ’ 95 (LNCS 963), 287–296, 1995.

, “Escrow encryption systems visited: Attacks, analysis and designs”, Advances in Cryptology–CRYPTO ’95 (LNCS 963), 222– 235, 1995.

M.K. FRANKLIN AND M.K. REITER, “Verifiable signature sharing”, Advances in Cryptology–EUROCRYPT ’95 (LNCS 921), 50–63, 1995.

G. FREY AND H.-G. RU ̈ CK, “A remark con- cerning m-divisibility and the discrete loga- rithm in the divisor class group of curves”, Mathematics of Computation, 62 (1994), 865– 874.

W. FRIEDMAN, Military Cryptanalysis, U.S. Government Printing Office, Washington DC, 1944. Volume I – Monoalphabetic substitu- tion systems. Volume II – Simpler varieties of polyalphabetic substitution systems. Vol- ume III – Aperiodic substitutions. Volume IV – Transposition systems.

, “Cryptology”, Encyclopedia Brittan- ica, 6 (1967), 844–851.

, Elements of Cryptanalysis, Aegean Park Press, Laguna Hills, California, 1976. First published in 1923.

, The Index of Coincidence and its Applications in Cryptography, Aegean Park Press, Laguna Hills, California, 1979. First published in 1920.

A.M. FRIEZE, J. HA ̊STAD, R. KANNAN, J.C. LAGARIAS, AND A. SHAMIR, “Recon- structing truncated integer variables satisfying linear congruences”, SIAM Journal on Com- puting, 17 (1988), 262–280.

A. FUJIOKA, T. OKAMOTO, AND S. MIYA- GUCHI, “ESIGN: An efficient digital signa- ture implementation for smart cards”, Ad- vances in Cryptology–EUROCRYPT ’ 91 (LNCS 547), 446–457, 1991.

W. FUMY AND P. LANDROCK, “Principles of key management”, IEEE Journal on Selected Areas in Communications, 11 (1993), 785– 793.

W. FUMY AND M. LECLERC, “Placement of cryptographic key distribution within OSI: de- sign alternatives and assessment”, Computer Networks and ISDN Systems, 26 (1993), 217– 225.

W. FUMY AND M. MUNZERT, “A modular approach to key distribution”, Advances in Cryptology–CRYPTO ’90 (LNCS 537), 274– 283, 1991.

W. FUMY AND M. RIETENSPIESS, “Open systems security standards”, A. Kent and J.G. Williams, editors, Encyclopedia of Computer Science and Technology 34, 301–334, Marcel Dekker, 1996.

K. GAARDER AND E. SNEKKENES, “Apply- ing a formal analysis technique to the CCITT X.509 strong two-way authentication proto- col”, Journal of Cryptology, 3 (1991), 81–98.

E.M. GABIDULIN, “On public-key cryp- tosystems based on linear codes: Efficiency and weakness”, P.G. Farrell, editor, Codes and Cyphers: Cryptography and Coding IV, 17– 31, Institute of Mathematics & Its Applica- tions (IMA), 1995.

E.M. GABIDULIN, A.V. PARAMONOV, AND O.V. TRETJAKOV, “Ideals over a non-commutative ring and their application in cryptology”, Advances in Cryptology– EUROCRYPT ’ 91 (LNCS 547), 482–489, 1991.

H. GAINES, Cryptanalysis: A Study of Ci- phers and their Solutions, Dover Publications, New York, 1956.

J. GAIT, “A new nonlinear pseudorandom number generator”, IEEE Transactions on Software Engineering, 3 (1977), 359–363.

J.M. GALVIN, K. MCCLOGHRIE, AND J.R. D AV I N, “Secure management of SNMP net- works”, Integrated Network Management, II, 703–714, 1991.

R.A. GAMES AND A.H. CHAN, “A fast algo- rithm for determining the complexity of a bi- nary sequence with period 2n”, IEEE Trans- actions on Information Theory, 29 (1983), 144–146.

M. GARDNER, “A new kind of cipher that would take millions of years to break”, Scien- tific American, 237 (Aug 1977), 120–124.

M.R. GAREY AND D.S. JOHNSON, Comput- ers and Intractability: A Guide to the The- ory of NP-completeness, W.H. Freeman, San Francisco, 1979.

S. GARFINKEL, PGP: Pretty Good Privacy, O’Reilly and Associates, Inc., Sebastopol, California, 1995.

H. GARNER, “The residue number system”, IRE Transactions on Electronic Computers, EC-8 (1959), 140–147.

C.F. GAUSS, Disquisitiones Arithmeticae, 1801. English translation by Arthur A. Clarke, Springer-Verlag, New York, 1986.

K. GEDDES, S. CZAPOR, AND G. LABAHN, Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston, 1992.

P. GEFFE, “How to protect data with ciphers that are really hard to break”, Electronics, 46 (1973), 99–101.

J. GEORGIADES, “Some remarks on the se- curity of the identification scheme based on permuted kernels”, Journal of Cryptology, 5 (1992), 133–137.

J. GERVER, “Factoring large numbers with a quadratic sieve”, Mathematics of Computa- tion, 41 (1983), 287–294.

P.J. GIBLIN, Primes and Programming: An Introduction to Number Theory with Comput- ing, Cambridge University Press, Cambrige, 1993.

J.K. GIBSON, “Some comments on Damg- a ̊rd’s hashing principle”, Electronics Letters, 26 (July 19, 1990), 1178–1179.

, “Equivalent Goppa codes and trap- doors to McEliece’s public key cryptosys- tem”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 517–521, 1991.

, “Severely denting the Gabidulin ver- sion of the McEliece public key cryptosys- tem”, Designs, Codes and Cryptography, 6 (1995), 37–45.

, “The security of the Gabidulin public key cryptosystem”, Advances in Cryptology– EUROCRYPT ’ 96 (LNCS 1070), 212–223, 1996.

E.N. GILBERT, F.J. MACWILLIAMS, AND N.J.A. SLOANE, “Codes which detect de- ception”, Bell System Technical Journal, 53 (1974), 405–424.

H. GILBERT AND G. CHASSE ́, “A statistical attack of the Feal-8 cryptosystem”, Advances in Cryptology–CRYPTO ’90 (LNCS 537), 22– 33, 1991.

H. GILBERT AND P. CHAUVAUD, “A chosen plaintext attack of the 16-round Khufu cryp- tosystem”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 359–368, 1994.

M.GIRAULT,“Hash-functionsusingmodulo- n operations”, Advances in Cryptology– EUROCRYPT ’ 87 (LNCS 304), 217–226, 1988.

, “An identity-based identification sch- eme based on discrete logarithms modulo a composite number”, Advances in Cryptology– EUROCRYPT ’ 90 (LNCS 473), 481–486, 1991.

, “Self-certified public keys”, Advances in Cryptology–EUROCRYPT ’ 91 (LNCS 547), 490–497, 1991.

M. GIRAULT, R. COHEN, AND M. CAMO. GOLDREICH AND L.A. LEVIN, “A hard- core predicate for all one-way functions”, Proceedings of the 21st Annual ACM Sympo- sium on Theory of Computing, 25–32, 1989.

O. GOLDREICH, S. MICALI, AND A. WIG- DERSON, “Proofs that yield nothing but their validity and a methodology of cryptographic protocol design”, Proceedings of the IEEE 27th Annual Symposium on Foundations of Computer Science, 174–187, 1986.

, “How to prove all NP statements in zero-knowledge, and a methodology of cryptographic protocol design”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 171– 185, 1987.

, “Proofs that yield nothing but their validity or all languages in NP have zero- knowledge proof systems”, Journal of the Association for Computing Machinery, 38 (1991), 691–729. An earlier version appeared in [472].

O. GOLDREICH AND Y. OREN, “Definitions and properties of zero-knowledge proof sys- tems”, Journal of Cryptology, 7 (1994), 1–32.

S. GOLDWASSER, “The search for provably secure cryptosystems”, C. Pomerance, editor, Cryptology and Computational Number The- ory, volume 42 of Proceedings of Symposia in Applied Mathematics, 89–113, American Mathematical Society, 1990.

S. GOLDWASSER AND J. KILIAN, “Almost all primes can be quickly certified”, Proceed- ings of the 18th Annual ACM Symposium on Theory of Computing, 316–329, 1986.

S. GOLDWASSER AND S. MICALI, “Proba- bilistic encryption & how to play mental poker keeping secret all partial information”, Pro- ceedings of the 14th Annual ACM Symposium on Theory of Computing, 365–377, 1982.

, “Probabilistic encryption”, Journal of Computer and System Sciences, 28 (1984), 270–299. An earlier version appeared in [478].

S. GOLDWASSER, S. MICALI, AND C. RAC- KOFF, “The knowledge complexity of interac- tive proof-systems”, Proceedings of the 17th Annual ACM Symposium on Theory of Com- puting, 291–304, 1985.

, “The knowledge complexity of inter- active proof systems”, SIAM Journal on Com- puting, 18 (1989), 186–208. An earlier ver- sion appeared in [480].

P A N A , “A generalized birthday attack”,

vances in Cryptology–EUROCRYPT (LNCS 330), 129–156, 1988.

Ad- ’ 88

M. GIRAULT AND J.C. PAILLE`S, “An identity-based scheme providing zero- knowledge authentication and authenticated key-exchange”, First European Symposium on Research in Computer Security – ES- ORICS’ 90, 173–184, 1990.

M. GIRAULT AND J. STERN, “On the length of cryptographic hash-values used in identi- fication schemes”, Advances in Cryptology– CRYPTO ’94 (LNCS 839), 202–215, 1994.

V.D. GLIGOR, R. KAILAR, S. STUB- BLEBINE, AND L. GONG, “Logics for crypto- graphic protocols — virtues and limitations”, The Computer Security Foundations Work- shop IV, 219–226, IEEE Computer Security Press, 1991.

C.M. GOLDIE AND R.G.E. PINCH, Commu- nication Theory, Cambridge University Press, Cambridge, 1991.

O. GOLDREICH, “Two remarks concerning the Goldwasser-Micali-Rivest signature sch- eme”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 104–110, 1987.

O. GOLDREICH, S. GOLDWASSER, AND S. MICALI, “How to construct random func- tions”, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Sci- ence, 464–479, 1984.

, “On the cryptographic applications of random functions”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 276–288, 1985.

, “How to construct random functions”,

Journal of the Association for Computing Ma- chinery, 33 (1986), 792–807. An earlier ver- sion appeared in [466].

O. GOLDREICH AND H. KRAWCZYK, “On the composition of zero-knowledge proof sys- tems”, M.S. Paterson, editor, Automata, Lan- guages and Programming, 17th International Colloquium (LNCS 443), 268–282, Springer- Verlag, 1990.

O. GOLDREICH, H. KRAWCZYK, AND M. LUBY, “On the existence of pseudoran- dom generators”, Proceedings of the IEEE 29th Annual Symposium on Foundations of Computer Science, 12–24, 1988.

S. GOLDWASSER, S. MICALI, AND R.L. RIVEST, “A “paradoxical” solution to the sig- nature problem”, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Science, 441–448, 1984.

, “A “paradoxical” solution to the sig- nature problem”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 467, 1985.

, “A digital signature scheme secure against adaptive chosen-message attacks”, SIAM Journal on Computing, 17 (1988), 281– 308. Earlier versions appeared in [482] and [483].

J. GOLIC ́, “Correlation via linear sequen- tial circuit approximation of combiners with memory”, Advances in Cryptology– EUROCRYPT ’ 92 (LNCS 658), 113–123, 1993.

, “On the security of shift register based keystream generators”, R. Anderson, editor, Fast Software Encryption, Cambridge Secu- rity Workshop (LNCS 809), 90–100, Springer- Verlag, 1994.

, “Intrinsic statistical weakness of key- stream generators”, Advances in Cryptology– ASIACRYPT ’94 (LNCS 917), 91–103, 1995.

, “Linear cryptanalysis of stream ci- phers”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 154–169, Springer-Verlag, 1995.

, “Towards fast correlation attacks on ir- regularly clocked shift registers”, Advances in Cryptology–EUROCRYPT ’95 (LNCS 921), 248–262, 1995.

, “On the security of nonlinear fil- ter generators”, D. Gollmann, editor, Fast Software Encryption, Third International Workshop (LNCS 1039), 173–188, Springer- Verlag, 1996.

J. GOLIC ́ AND M. MIHALJEVIC ́, “A gener- alized correlation attack on a class of stream ciphers based on the Levenshtein distance”, Journal of Cryptology, 3 (1991), 201–212.

J. GOLIC ́ AND L. O’CONNOR, “Embed- ding and probabilistic correlation attacks on clock-controlled shift registers”, Advances in Cryptology–EUROCRYPT ’ 94 (LNCS 950), 230–243, 1995.

R.A. GOLLIVER, A.K. LENSTRA, AND K.S. MCCURLEY, “Lattice sieving and trial di- vision”, Algorithmic Number Theory (LNCS 877), 18–27, 1994.

D. GOLLMANN, “Pseudo random properties of cascade connections of clock controlled shift registers”, Advances in Cryptology– Proceedings of EUROCRYPT 84 (LNCS 209), 93–98, 1985.

, “Cryptanalysis of clock controlled shift registers”, R. Anderson, editor, Fast Soft- ware Encryption, Cambridge Security Work- shop (LNCS 809), 121–126, Springer-Verlag, 1994.

D. GOLLMANN AND W.G. CHAMBERS, “Clock-controlled shift registers: a review”, IEEE Journal on Selected Areas in Communi- cations, 7 (1989), 525–533.

D. GOLLMANN, Y. HAN, AND C. MITCHE- LL, “Redundant integer representations and fast exponentiation”, Designs, Codes and Cryptography, 7 (1996), 135–151.

S.W. GOLOMB, Shift Register Sequences, Holden-Day, San Francisco, 1967. Reprinted by Aegean Park Press, 1982.

L. GONG, “Using one-way functions for au- thentication”, Computer Communication Re- view, 19 (1989), 8–11.

, “A security risk of depending on syn- chronized clocks”, Operating Systems Re- view, 26 (1992), 49–53.

, “Variations on the themes of message freshness and replay”, The Computer Security Foundations Workshop VI, 131–136, IEEE Computer Society Press, 1993.

, “New protocols for third-party-based authentication and secure broadcast”, 2nd ACM Conference on Computer and Com- munications Security, 176–183, ACM Press, 1994.

, “Efficient network authentication pro- tocols: lower bounds and optimal implemen- tations”, Distributed Computing, 9 (1995), 131–145.

L. GONG, T.M.A. LOMAS, R.M. NEED- HAM,ANDJ.H.SALTZER,“Protectingpoorly chosen secrets from guessing attacks”, IEEE Journal on Selected Areas in Communica- tions, 11 (1993), 648–656.

L. GONG, R. NEEDHAM, AND R. YA- HALOM, “Reasoning about belief in crypto- graphic protocols”, Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy, 234–248, 1990.

L. GONG AND D.J. WHEELER, “A matrix key-distribution scheme”, Journal of Cryptol- ogy, 2 (1990), 51–59.

I.J.GOOD,“Theserialtestforsamplingnum- bers and other tests for randomness”, Pro- ceedings of the Cambridge Philosophical So- ciety, 49 (1953), 276–284.

, “On the serial test for random se- quences”, The Annals of Mathematical Statis- tics, 28 (1957), 262–264.

D.M. GORDON, “Designing and detecting trapdoors for discrete log cryptosystems”, Ad- vances in Cryptology–CRYPTO ’92 (LNCS 740), 66–75, 1993.

, “Discrete logarithms in GF(p) using the number field sieve”, SIAM Journal on Dis- crete Mathematics, 6 (1993), 124–138.

D.M. GORDON AND K.S. MCCURLEY, “Massively parallel computations of dis- crete logarithms”, Advances in Cryptology– CRYPTO ’92 (LNCS 740), 312–323, 1993.

J. GORDON, “Very simple method to find the minimum polynomial of an arbitrary nonzero element of a finite field”, Electronics Letters, 12 (December 9, 1976), 663–664.

, “Strong RSA keys”, Electronics Let- ters, 20 (June 7, 1984), 514–516.

, “Strong primes are easy to find”, Ad- vances in Cryptology–Proceedings of EURO- CRYPT 84 (LNCS 209), 216–223, 1985.

, “How to forge RSA key certificates”, Electronics Letters, 21 (April 25, 1985), 377– 379.

, “Fast multiplicative inverse in modu- lar arithmetic”, H. Beker and F. Piper, editors, Cryptography and Coding, Institute of Math- ematics & Its Applications (IMA), 269–279, Clarendon Press, 1989.

J. GORDON AND H. RETKIN, “Are big S- boxes best?”, Cryptography–Proceedings of the Workshop on Cryptography, Burg Feuer- stein (LNCS 149), 257–262, 1983.

M. GORESKY AND A. KLAPPER, “Feedback registers based on ramified extensions of the

2-adic numbers”, Advances in Cryptology– EUROCRYPT ’ 94 (LNCS 950), 215–222, 1995.

K.C. GOSS, “Cryptographic method and ap- paratus for public key exchange with authenti- cation”, U.S. Patent # 4,956,863, 11 Sep 1990.

R. GRAHAM, D. KNUTH, AND O. PATASH- NIK, Concrete Mathematics, Addison- Wesley, Reading, Massachusetts, 2nd edition, 1994.

A. GRANVILLE, “Primality testing and Carmichael numbers”, Notices of the Amer- ican Mathematical Society, 39 (1992), 696– 700.

E. GROSSMAN, “Group theoretic remarks on cryptographic systems based on two types of addition”, IBM Research Report RC 4742, IBM T.J. Watson Research Center, Yorktown Heights, N.Y., 10598, U.S.A., Feb. 26 1974.

L.C. GUILLOU AND J.-J. QUISQUATER, “Method and apparatus for authenticating ac- creditations and for authenticating and signing messages”, U.S. Patent # 5,140,634, 18 Aug 1992.

, “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory”, Advances in Cryptology–EUROCRYPT ’ 88 (LNCS 330), 123–128, 1988.

L.C. GUILLOU, J.-J. QUISQUATER, M. WA- LKER, P. LANDROCK, AND C. SHAER, “Pre- cautions taken against various potential at- tacks in ISO/IEC DIS 9796”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 465–473, 1991.

L.C. GUILLOU AND M. UGON, “Smart card – a highly reliable and portable security de- vice”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 464–479, 1987.

L.C. GUILLOU, M. UGON, AND J.-J. QUISQUATER, “The smart card: A standard- ized security device dedicated to public cryp- tology”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information In- tegrity, 561–613, IEEE Press, 1992.

C.G. GU ̈ NTHER, “Alternating step gener- ators controlled by de Bruijn sequences”, Advances in Cryptology–EUROCRYPT ’87 (LNCS 304), 5–14, 1988.

, “A universal algorithm for homo- phonic coding”, Advances in Cryptology–

⃝c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter.

, “An identity-based key-exchange pro- tocol”, Advances in Cryptology–EUROCRY- PT ’89 (LNCS 434), 29–37, 1990.

H. GUSTAFSON, Statistical Analysis of Sym- metric Ciphers, PhD thesis, Queensland Uni- versity of Technology, 1996.

H. GUSTAFSON, E. DAWSON, AND J. GOL- IC ́, “Randomness measures related to subset occurrence”, E. Dawson and J. Golic ́, editors, Cryptography: Policy and Algorithms, Inter- national Conference, Brisbane, Queensland, Australia, July 1995 (LNCS 1029), 132–143, 1996.

H. GUSTAFSON, E. DAWSON, L. NIELSEN, AND W. CAELLI, “A computer package for measuring the strength of encryption algo- rithms”, Computers & Security, 13 (1994), 687–697.

A. GUYOT, “OCAPI: Architecture of a VLSI coprocessor for the gcd and extended gcd of large numbers”, Proceedings of the 10th IEEE Symposium on Computer Arithmetic, 226– 231, IEEE Press, 1991.

S. HABER AND W.S. STORNETTA, “How to time-stamp a digital document”, Journal of Cryptology, 3 (1991), 99–111.

J.L. HAFNER AND K.S. MCCURLEY, “On the distribution of running times of certain in- teger factoring algorithms”, Journal of Algo- rithms, 10 (1989), 531–556.

, “A rigorous subexponential algorithm for computation of class groups”, Journal of the American Mathematical Society, 2 (1989), 837–850.

T. HANSEN AND G.L. MULLEN, “Primitive polynomials over finite fields”, Mathematics of Computation, 59 (1992), 639–643.

G.H. HARDY, A Mathematician’s Apology, Cambridge University Press, London, 1967.

G.H. HARDY AND E.M. WRIGHT, An Intro- duction to the Theory of Numbers, Clarendon Press, Oxford, 5th edition, 1979.

C. HARPES, G.G. KRAMER, AND J.L. MASSEY, “A generalization of linear crypt- analysis and the applicability of Matsui’s piling-up lemma”, Advances in Cryptology– EUROCRYPT ’ 95 (LNCS 921), 24–38, 1995.

EUROCRYPT 1988.’ 88(LNCS 330),405–414,

V. HARRIS, “An algorithm for finding the greatest common divisor”, Fibonacci Quar- terly, 8 (1970), 102–103.

J. HA ̊ STAD, A.W. SCHRIFT, AND A. SHAM- IR, “The discrete logarithm modulo a compos- ite hides O(n) bits”, Journal of Computer and System Sciences, 47 (1993), 376–404.

J. HA ̊ STAD, “Solving simultaneous modular equations of low degree”, SIAM Journal on Computing, 17 (1988), 336–341.

, “Pseudo-random generators under uniform assumptions”, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 395–404, 1990.

R. HEIMAN, “A note on discrete loga- rithms with special structure”, Advances in Cryptology–EUROCRYPT ’92 (LNCS 658), 454–457, 1993.

, “Secure audio teleconferencing: A practical solution”, Advances in Cryptology– EUROCRYPT ’ 92 (LNCS 658), 437–448, 1993.

M.E.HELLMAN,“AnextensionoftheShan- non theory approach to cryptography”, IEEE Transactions on Information Theory, 23 (1977), 289–294.

, “A cryptanalytic time-memory trade- off”, IEEE Transactions on Information The- ory, 26 (1980), 401–406.

M.E. HELLMAN AND C.E. BACH, “Method and apparatus for use in public-key data en- cryption system”, U.S. Patent # 4,633,036, 30 Dec 1986.

M.E. HELLMAN, B.W. DIFFIE, AND R.C. MERKLE, “Cryptographic apparatus and method”, U.S. Patent # 4,200,770, 29 Apr 1980.

M.E. HELLMAN, R. MERKLE, R. SCHROE- PPEL, L. WASHINGTON, W. DIFFIE, S. POHLIG, AND P. SCHWEITZER, “Results of an initial attempt to cryptanalyze the NBS Data Encryption Standard”, Technical Report SEL 76-042, Information Systems Labora- tory, Stanford University, Palo Alto, Califor- nia, Sept. 9 1976 (revised Nov 10 1976).

M.E. HELLMAN AND R.C. MERKLE, “Pub- lic key cryptographic apparatus and method”, U.S. Patent # 4,218,582, 19 Aug 1980.

M.E. HELLMAN AND S.C. POHLIG, “Ex- ponentiation cryptographic apparatus and method”, U.S. Patent # 4,424,414, 3 Jan 1984.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

M.E. HELLMAN AND J.M. REYNERI, “Fast computation of discrete logarithms in GF(q)”, Advances in Cryptology– Proceedings of Crypto 82, 3–13, 1983.

I.N. HERSTEIN, Topics in Algebra, Xerox College Pub., Lexington, Massachusetts, 2nd edition, 1975.

L.S. HILL, “Cryptography in an algebraic al- phabet”, American Mathematical Monthly, 36 (1929), 306–312.

L.J. HOFFMAN, Modern Methods for Com- puter Security and Privacy, Prentice Hall, En- glewood Cliffs, New Jersey, 1977.

R.V. HOGG AND E.A. TANIS, Probability and statistical inference, Macmillan Publish- ing Company, New York, 3rd edition, 1988.

W. HOHL, X. LAI, T. MEIER, AND C. WALDVOGEL, “Security of iterated hash functions based on block ciphers”, Advances in Cryptology–CRYPTO ’ 93 (LNCS 773), 379–390, 1994.

S.-M. HONG, S.-Y. OH, AND H. YOON, “New modular multiplication algorithms for fast modular exponentiation”, Advances in Cryptology–EUROCRYPT ’96 (LNCS 1070), 166–177, 1996.

P. HORSTER AND H.-J. KNOBLOCH, “Dis- crete logarithm based protocols”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 399–408, 1991.

P. HORSTER, M. MICHELS, AND H. PE- TERSEN, “Meta-message recovery and meta- blind signature schemes based on the dis- crete logarithm problem and their applica- tions”, Advances in Cryptology–ASIACRYPT ’94 (LNCS 917), 224–237, 1995.

P. HORSTER AND H. PETERSEN, “Gen- eralized ElGamal signatures (in German)”, Sicherheit in Informationssystemen, Proceed- ings der Fachtagung SIS’94, 89–106, Verlag der Fachvereine Zu ̈rich, 1994.

T.W. HUNGERFORD, Algebra, Holt, Rinehart and Winston, New York, 1974.

K. HWANG, Computer Arithmetic, Princi- ples, Architecture and Design, John Wiley & Sons, New York, 1979.

C. I’ANSON AND C. MITCHELL, “Security defects in CCITT Recommendation X.509 – The directory authentication framework”, Computer Communication Review, 20 (1990), 30–34.

R. IMPAGLIAZZO, L. LEVIN, AND M. LUBY, “Pseudo-random generation from one-way functions”, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 12–24, 1989.

R. IMPAGLIAZZO AND M. NAOR, “Efficient cryptographic schemes provably as secure as subset sum”, Proceedings of the IEEE 30th Annual Symposium on Foundations of Com- puter Science, 236–241, 1989.

I. INGEMARSSON AND G.J. SIMMONS, “A protocol to set up shared secret schemes with- out the assistance of a mutually trusted party”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 266–282, 1991.

I. INGEMARSSON, D.T. TANG, AND C.K. WONG, “A conference key distribution sys- tem”, IEEE Transactions on Information The- ory, 28 (1982), 714–720.

K. IRELAND AND M. ROSEN, A Classi- cal Introduction to Modern Number The- ory, Springer-Verlag, New York, 2nd edition, 1990.

ISO 7498-2, “Information processing sys- tems – Open Systems Interconnection – Ba- sic reference model – Part 2: Security archi- tecture”, International Organization for Stan- dardization, Geneva, Switzerland, 1989 (first edition) (equivalent to ITU-T Rec. X.800).

ISO 8372, “Information processing – Modes of operation for a 64-bit block cipher algo- rithm”, International Organization for Stan- dardization, Geneva, Switzerland, 1987 (first edition; confirmed 1992).

ISO 8730, “Banking – Requirements for message authentication (wholesale)”, Inter- national Organization for Standardization, Geneva, Switzerland, 1990 (second edition).

ISO 8731-1, “Banking – Approved algo- rithms for message authentication – Part 1: DEA”, International Organization for Stan- dardization, Geneva, Switzerland, 1987 (first edition; confirmed 1992).

ISO 8731-2, “Banking – Approved algo- rithms for message authentication – Part 2: Message authenticator algorithm”, Inter- national Organization for Standardization, Geneva, Switzerland, 1992 (second edition).

ISO 8732, “Banking – Key management (wholesale)”, International Organization for Standardization, Geneva, Switzerland, 1988 (first edition).

⃝c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter.

ISO 9564-1, “Banking – Personal Identifi- cation Number management and security – Part 1: PIN protection principles and tech- niques”, International Organization for Stan- dardization, Geneva, Switzerland, 1990.

ISO 9564-2, “Banking – Personal Identifica- tion Number management and security – Part 2: Approved algorithm(s) for PIN encipher- ment”, International Organization for Stan- dardization, Geneva, Switzerland, 1991.

ISO9807,“Bankingandrelatedfinancialser- vices – Requirements for message authenti- cation (retail)”, International Organization for Standardization, Geneva, Switzerland, 1991.

ISO 10126-1, “Banking – Procedures for message encipherment (wholesale) – Part 1: General principles”, International Organiza- tion for Standardization, Geneva, Switzer- land, 1991.

ISO 10126-2, “Banking – Procedures for message encipherment (wholesale) – Part 2: Algorithms”, International Organization for Standardization, Geneva, Switzerland, 1991.

ISO 10202-7, “Financial transaction cards – Security architecture of financial transaction systems using integrated circuit cards – Part 7: Key management”, draft (DIS), 1994.

ISO 11131, “Banking – Financial institution sign-on authentication”, International Organi- zation for Standardization, Geneva, Switzer- land, 1992.

ISO 11166-1, “Banking – Key management by means of asymmetric algorithms – Part 1: Principles, procedures and formats”, In- ternational Organization for Standardization, Geneva, Switzerland, 1994.

ISO 11166-2, “Banking – Key manage- ment by means of asymmetric algorithms – Part 2: Approved algorithms using the RSA cryptosystem”, International Organization for Standardization, Geneva, Switzerland, 1995.

ISO 11568-1, “Banking – Key management (retail) – Part 1: Introduction to key manage- ment”, International Organization for Stan- dardization, Geneva, Switzerland, 1994.

ISO 11568-2, “Banking – Key management (retail) – Part 2: Key management techniques for symmetric ciphers”, International Organi- zation for Standardization, Geneva, Switzer- land, 1994.

ISO 11568-3, “Banking – Key management (retail) – Part 3: Key life cycle for symmetric ciphers”, International Organization for Stan- dardization, Geneva, Switzerland, 1994.

ISO 11568-4, “Banking – Key management (retail) – Part 4: Key management techniques using public key cryptography”, draft (DIS), 1996.

ISO 11568-5, “Banking – Key management (retail) – Part 5: Key life cycle for public key cryptosystems”, draft (DIS), 1996.

ISO 11568-6, “Banking – Key management (retail) – Part 6: Key management schemes”, draft (CD), 1996.

ISO/IEC 9594-1, “Information technol- ogy – Open Systems Interconnection – The Directory: Overview of concepts, models, and services”, International Organization for Standardization, Geneva, Switzerland, 1995 (equivalent to ITU-T Rec. X.500, 1993).

ISO/IEC 9594-8, “Information technology – Open Systems Interconnection – The Di- rectory: Authentication framework”, Inter- national Organization for Standardization, Geneva, Switzerland, 1995 (equivalent to ITU-T Rec. X.509, 1993).

ISO/IEC 9796, “Information technology – Security techniques – Digital signature sch- eme giving message recovery”, International Organization for Standardization, Geneva, Switzerland, 1991 (first edition).

ISO/IEC 9797, “Information technology – Security techniques – Data integrity mech- anism using a cryptographic check function employing a block cipher algorithm”, In- ternational Organization for Standardization, Geneva, Switzerland, 1994 (second edition).

ISO/IEC 9798-1, “Information technology – Security techniques – Entity authentication mechanisms – Part 1: General model”, In- ternational Organization for Standardization, Geneva, Switzerland, 1991 (first edition).

ISO/IEC 9798-2, “Information technology – Security techniques – Entity authentication – Part 2: Mechanisms using symmetric en- cipherment algorithms”, International Organi- zation for Standardization, Geneva, Switzer- land, 1994 (first edition).

ISO/IEC 9798-3, “Information technology – Security techniques – Entity authentica- tion mechanisms – Part 3: Entity authen-

tication using a public-key algorithm”, In- ternational Organization for Standardization, Geneva, Switzerland, 1993 (first edition).

[601] ISO/IEC 9798-4, “Information technology – Security techniques – Entity authentication – Part 4: Mechanisms using a cryptographic check function”, International Organization for Standardization, Geneva, Switzerland, 1995 (first edition).

[602] ISO/IEC 9798-5, “Information technology – Security techniques – Entity authentication – Part 5: Mechanisms using zero knowledge techniques”, draft (CD), 1996.

[603] ISO/IEC 9979, “Data cryptographic tech- niques – Procedures for the registration of cryptographic algorithms”, International Organization for Standardization, Geneva, Switzerland, 1991 (first edition).

[604] ISO/IEC 10116, “Information processing – Modes of operation for an n-bit block cipher algorithm”, International Organization for Standardization, Geneva, Switzerland, 1991 (first edition).

[605] ISO/IEC 10118-1, “Information technology – Security techniques – Hash-functions – Part 1: General”, International Organization for Standardization, Geneva, Switzerland, 1994.

[606] ISO/IEC 10118-2, “Information technology – Security techniques – Hash-functions – Part 2: Hash-functions using an n-bit block cipher algorithm”, International Organization for Standardization, Geneva, Switzerland, 1994.

[607] ISO/IEC 10118-3, “Information technology – Security techniques – Hash-functions – Part 3: Dedicated hash-functions”, draft (CD), 1996.

[608] ISO/IEC 10118-4, “Information technology – Security techniques – Hash-functions – Part 4: Hash-functions using modular arithmetic”, draft (CD), 1996.

[609] ISO/IEC 10181-1, “Information technol- ogy – Open Systems Interconnection – Se- curity frameworks for open systems – Part 1: Overview”, International Organization for Standardization, Geneva, Switzerland, 1996 (equivalent to ITU-T Rec. X.810, 1995).

[610] ISO/IEC 10181-2, “Information technol- ogy – Open Systems Interconnection – Se- curity frameworks for open systems – Part 2: Authentication framework”, International Organization for Standardization, Geneva,Switzerland, 1996 (equivalent to ITU-T Rec. X.811, 1995).

ISO/IEC10181-3,“Informationtechnology – Open Systems Interconnection – Security frameworks for open systems – Part 3: Access control framework”, 1996.

ISO/IEC10181-4,“Informationtechnology – Open Systems Interconnection – Security frameworks for open systems – Part 4: Non- repudiation framework”, 1996.

ISO/IEC10181-5,“Informationtechnology – Open Systems Interconnection – Security frameworks for open systems – Part 5: Con- fidentiality framework”, 1996.

ISO/IEC10181-6,“Informationtechnology – Open Systems Interconnection – Security frameworks for open systems – Part 6: In- tegrity framework”, 1996.

ISO/IEC 10181-7, “Information technology – Open Systems Interconnection – Security frameworks for open systems – Part 7: Secu- rity audit and alarms framework”, 1996.

ISO/IEC 11770-1, “Information technology – Security techniques – Key management – Part 1: Framework”, draft (DIS), 1996.

ISO/IEC 11770-2, “Information technology – Security techniques – Key management – Part 2: Mechanisms using symmetric tech- niques”, International Organization for Stan- dardization, Geneva, Switzerland, 1996 (first edition).

ISO/IEC 11770-3, “Information technology – Security techniques – Key management – Part 3: Mechanisms using asymmetric tech- niques”, draft (DIS), 1996.

ISO/IEC13888-1,“Informationtechnology – Security techniques – Non-repudiation – Part 1: General model”, draft (CD), 1996.

ISO/IEC13888-2,“Informationtechnology – Security techniques – Non-repudiation – Part 2: Using symmetric encipherment algo- rithms”, draft (CD), 1996.

ISO/IEC13888-3,“Informationtechnology – Security techniques – Non-repudiation – Part 3: Using asymmetric techniques”, draft (CD), 1996.

ISO/IEC 14888-1, “Information technology – Security techniques – Digital signatures with appendix – Part 1: General”, draft (CD), 1996.

ISO/IEC 14888-2, “Information technology – Security techniques – Digital signatures with appendix – Part 2: Identity-based mecha- nisms”, draft (CD), 1996.

ISO/IEC 14888-3, “Information technology – Security techniques – Digital signatures with appendix – Part 3: Certificate-based mecha- nisms”, draft (CD), 1996.

M. ITO, A. SAITO, AND T. NISHIZEKI, “Se- cret sharing scheme realizing general access structure”, IEEE Global Telecommunications Conference, 99–102, 1987.

ITU-T REC. X.509 (REVISED), “The Di- rectory – Authentication framework”, Inter- national Telecommunication Union, Geneva, Switzerland, 1993 (equivalent to ISO/IEC 9594-8:1994).

ITU-T REC. X.509 (1993) TECHNICAL CORRIGENDUM 1, “The Directory – Authen- tication framework”, International Telecom- munication Union, Geneva, Switzerland, July 1995 (equivalent to Technical Corrigendum 1 to ISO/IEC 9594-8:1994).

ITU-T REC. X.509 (1993) AMENDMENT 1: CERTIFICATE EXTENSIONS, “The Directory – Authentication framework”, International Telecommunication Union, Geneva, Switzer- land, July 1995 draft for JCT1 letter ballot (equivalent to Ammendment 1 to ISO/IEC 9594-8:1994).

W.-A.JACKSON,K.M.MARTIN,ANDC.M. O’KEEFE, “Multisecret threshold schemes”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 126–135, 1994.

G. JAESCHKE, “On strong pseudoprimes to several bases”, Mathematics of Computation, 61 (1993), 915–926.

C.J.A.JANSENANDD.E.BOEKEE,“Onthe significance of the directed acyclic word graph in cryptology”, Advances in Cryptology– AUSCRYPT ’90 (LNCS 453), 318–326, 1990.

, “The shortest feedback shift register that can generate a given sequence”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 90– 99, 1990.

T. JEBELEAN, “Comparing several gcd al- gorithms”, Proceedings of the 11th Sympo- sium on Computer Arithmetic, 180–185, IEEE Press, 1993.

J. JEDWAB AND C. MITCHELL, “Minimum weight modified signed-digit representations

and fast exponentiation”, Electronics Letters, 25 (August 17, 1989), 1171–1172.

N. JEFFERIES, C. MITCHELL, AND M. WALKER, “A proposed architecture for trusted third party services”, E. Dawson and J. Golic ́, editors, Cryptography: Policy and Algorithms, International Conference, Brisbane, Queensland, Australia, July 1995 (LNCS 1029), 98–104, 1996.

H.N. JENDAL, Y.J.B. KUHN, AND J.L. MASSEY, “An information-theoretic treat- ment of homophonic substitution”, Advances in Cryptology–EUROCRYPT ’ 89 (LNCS 434), 382–394, 1990.

S.M. JENNINGS, “Multiplexed sequences: Some properties of the minimum polyno- mial”, Cryptography–Proceedings of the Workshop on Cryptography, Burg Feuerstein (LNCS 149), 189–206, 1983.

T. JOHANSSON, G. KABATIANSKII, AND B. SMEETS, “On the relation between A- codes and codes correcting independent er- rors”, Advances in Cryptology–EUROCRYPT ’ 93 (LNCS 765), 1–11, 1994.

D.B. JOHNSON, A. LE, W. MARTIN, S. MATYAS, AND J. WILKINS, “Hybrid key distribution scheme giving key record recov- ery”, IBM Technical Disclosure Bulletin, 37 (1994), 5–16.

D.B. JOHNSON AND S.M. MATYAS, “Asym- metric encryption: Evolution and enhance- ments”, CryptoBytes, 2 (Spring 1996), 1–6.

D.S. JOHNSON, “The NP-completeness col- umn: an ongoing guide”, Journal of Algo- rithms, 9 (1988), 426–444.

R.W. JONES, “Some techniques for handling encipherment keys”, ICL Technical Journal, 3 (1982), 175–188.

R.R. JUENEMAN, “Analysis of certain as- pects of output feedback mode”, Advances in Cryptology–Proceedings of Crypto 82, 99– 127, 1983.

, “A high speed manipulation detection code”, Advances in Cryptology–CRYPTO ’86 (LNCS 263), 327–346, 1987.

R.R. JUENEMAN, S.M. MATYAS, AND C.H. MEYER, “Message authentication with ma- nipulation detection codes”, Proceedings of the 1983 IEEE Symposium on Security and Privacy, 33–54, 1984.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

D. JUNGNICKEL, Finite Fields: Structure and Arithmetics, Bibliographisches Institut – Wissenschaftsverlag, Mannheim, 1993.

M. JUST, E. KRANAKIS, D. KRIZANC, AND P. VAN OORSCHOT, “On key distribution via true broadcasting”, 2nd ACM Conference on Computer and Communications Security, 81– 88, ACM Press, 1994.

D. KAHN, The Codebreakers, Macmillan Publishing Company, New York, 1967.

B.S. KALISKI JR., “A chosen message at- tack on Demytko’s elliptic curve cryptosys- tem”, Journal of Cryptology, to appear.

, “A pseudo-random bit generator based on elliptic logarithms”, Advances in Cryptology–CRYPTO ’ 86 (LNCS 263), 84– 103, 1987.

, Elliptic curves and cryptography: a pseudorandom bit generator and other tools, PhD thesis, MIT Department of Electrical En- gineering and Computer Science, 1988.

, “Anderson’s RSA trapdoor can be bro- ken”, Electronics Letters, 29 (July 22, 1993), 1387–1388.

, “The Montgomery inverse and its ap- plications”, IEEE Transactions on Comput- ers, 44 (1995), 1064–1065.

B.S. KALISKI JR., R.L. RIVEST, AND A.T. SHERMAN, “Is the Data Encryption Standard a group? (Results of cycling experiments on DES)”, Journal of Cryptology, 1 (1988), 3– 36.

B.S. KALISKI JR. AND M. ROBSHAW, “The secure use of RSA”, CryptoBytes, 1 (Autumn 1995), 7–13.

B.S. KALISKI JR. AND Y.L. YIN, “On differ- ential and linear cryptanalysis of the RC5 en- cryption algorithm”, Advances in Cryptology– CRYPTO ’95 (LNCS 963), 171–184, 1995.

E. KALTOFEN, “Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems”, Mathemat- ics of Computation, 64 (1995), 777–806.

E. KALTOFEN AND V. SHOUP, “Subquadra- tic-time factoring of polynomials over finite fields”, Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 398– 406, 1995.

J. KAM AND G. DAVIDA, “Structured de- sign of substitution-permutation encryption

networks”, IEEE Transactions on Computers, 28 (1979), 747–753.

N. KAPIDZIC AND A. DAVIDSON, “A cer- tificate management system: structure, func- tions and protocols”, Proceedings of the In- ternet Society Symposium on Network and Distributed System Security, 153–160, IEEE Computer Society Press, 1995.

A. KARATSUBA AND YU. OFMAN, “Multi- plication of multidigit numbers on automata”, Soviet Physics – Doklady, 7 (1963), 595–596.

E.D. KARNIN, J.W. GREENE, AND M.E. HELLMAN, “On secret sharing systems”, IEEE Transactions on Information Theory, 29 (1983), 35–41.

A. KEHNE, J. SCHO ̈ W A ̈ LDER, AND H. LAN- GENDO ̈ RFER, “A nonce-based protocol for multiple authentications”, Operating Systems Review, 26 (1992), 84–89.

R. KEMMERER, C. MEADOWS, AND J. MILLEN, “Three systems for cryptographic protocol analysis”, Journal of Cryptology, 7 (1994), 79–130.

S. KENT, “Encryption-based protection pro- tocols for interactive user-computer commu- nication”, MIT/LCS/TR-162 (M.Sc. thesis), MIT Laboratory for Computer Science, 1976.

, “Internet privacy enhanced mail”, Communications of the ACM, 36 (1993), 48– 60.

, “Internet security standards: past, present and future”, StandardView, 2 (1994), 78–85.

A. KERCKHOFFS, “La cryptographie mili- taire”, Journal des Sciences Militaires, 9th Se- ries (February 1883), 161–191.

I. KESSLER AND H. KRAWCZYK, “Mini- mum buffer length and clock rate for the shrinking generator cryptosystem”, IBM Re- search Report RC 19938, IBM T.J. Watson Research Center, Yorktown Heights, N.Y., 10598, U.S.A., 1995.

E. KEY, “An analysis of the structure and complexity of nonlinear binary sequence gen- erators”, IEEE Transactions on Information Theory, 22 (1976), 732–736.

J. KILIAN AND T. LEIGHTON, “Fair cryp- tosystems, revisited: A rigorous approach to key-escrow”, Advances in Cryptology– CRYPTO ’ 95 (LNCS 963), 208–221, 1995.

J. KILIAN AND P. ROGAWAY, “How to pro- tect DES against exhaustive key search”, Ad- vances in Cryptology–CRYPTO ’ 96 (LNCS 1109), 252–267, 1996.

S.-H.KIMANDC.POMERANCE,“Theprob- ability that a random probable prime is com- posite”, Mathematics of Computation, 53 (1989), 721–741.

M. KIMBERLEY, “Comparison of two statis- tical tests for keystream sequences”, Electron- ics Letters, 23 (April 9, 1987), 365–366.

A. KLAPPER, “The vulnerability of geometric sequences based on fields of odd characteris- tic”, Journal of Cryptology, 7 (1994), 33–51.

A. KLAPPER AND M. GORESKY, “Feedback shift registers, combiners with memory, and 2- adic span”, Journal of Cryptology, to appear.

, “2-Adic shift registers”, R. Ander- son, editor, Fast Software Encryption, Cam- bridge Security Workshop (LNCS 809), 174– 178, Springer-Verlag, 1994.

, “Cryptanalysis based on 2-adic ratio- nal approximation”, Advances in Cryptology– CRYPTO ’95 (LNCS 963), 262–273, 1995.

, “Large period nearly de Bruijn FCSR sequences”, Advances in Cryptology– EUROCRYPT ’ 95 (LNCS 921), 263–273, 1995.

D.V. KLEIN, “Foiling the cracker: a survey of, and improvements to, password security”, Proceedings of the 2nd USENIX UNIX Secu- rity Workshop, 5–14, 1990.

H.-J.KNOBLOCH,“Asmartcardimplemen- tation of the Fiat-Shamir identification sch- eme”, Advances in Cryptology–EUROCRYPT ’88 (LNCS 330), 87–95, 1988.

L.R. KNUDSEN, “Cryptanalysis of LOKI”,

Advances in Cryptology–ASIACRYPT ’ 91 (LNCS 739), 22–35, 1993.

, “Cryptanalysis of LOKI91”, Advances in Cryptology–AUSCRYPT ’ 92 (LNCS 718), 196–208, 1993.

, Block Ciphers – Analysis, Design and Applications, PhD thesis, Computer Science Department, Aarhus University (Denmark), 1994.

, “A key-schedule weakness in SAFER K-64”, Advances in Cryptology–CRYPTO ’ 95 (LNCS 963), 274–286, 1995.

, “Truncated and higher order differ- entials”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 196–211, Springer-Verlag, 1995.

L.R. KNUDSEN AND T. BERSON, “Trun- cated differentials of SAFER”, D. Gollmann, editor, Fast Software Encryption, Third In- ternational Workshop (LNCS 1039), 15–26, Springer-Verlag, 1996.

L.R. KNUDSEN AND X. LAI, “New attacks on all double block length hash functions of hash rate 1, including the parallel-DM”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 410–418, 1995.

L.R. KNUDSEN AND W. MEIER, “Improved differential attacks on RC5”, Advances in Cryptology–CRYPTO ’ 96 (LNCS 1109), 216– 228, 1996.

L.R. KNUDSEN AND T. PEDERSEN, “On the difficulty of software key escrow”, Advances in Cryptology–EUROCRYPT ’ 96 (LNCS 1070), 237–244, 1996.

D.E.KNUTH,TheArtofComputerProgram- ming – Fundamental Algorithms, volume 1, Addison-Wesley, Reading, Massachusetts, 2nd edition, 1973.

, The Art of Computer Programming – Seminumerical Algorithms, volume 2, Addison-Wesley, Reading, Massachusetts, 2nd edition, 1981.

, The Art of Computer Programming – Sorting and Searching, volume 3, Addison- Wesley, Reading, Massachusetts, 1973.

D.E. KNUTH AND L. TRABB PARDO, “Anal- ysis of a simple factorization algorithm”, The- oretical Computer Science, 3 (1976), 321– 348.

N.KOBLITZ,“Ellipticcurvecryptosystems”, Mathematics of Computation, 48 (1987), 203– 209.

, “Hyperelliptic cryptosystems”, Jour- nal of Cryptology, 1 (1989), 139–150.

, A Course in Number Theory and Cryp- tography, Springer-Verlag, New York, 2nd edition, 1994.

C.KOC ̧,“High-speedRSAimplementation”, Technical Report, RSA Laboratories, 1994.

, “RSA hardware implementation”, Technical Report TR-801, RSA Laboratories, 1996.

[700] C. KOC ̧, T. ACAR, AND B.S. KALISKI [714] JR., “Analyzing and comparing Montgomery multiplication algorithms”, IEEE Micro, 16

(1996), 26–33.

, “LFSR-based hashing and authentica-

[701] J.T. KOHL, “The use of encryption in Ker- beros for network authentication”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 35– 43, 1990.

[702] L.M. KOHNFELDER, “A method for certifica- tion”, MIT Laboratory for Computer Science, unpublished (essentially pp.39-43 of [703]), 1978.

[703] , Toward a practical public-key cryp- tosystem, B.Sc. thesis, MIT Department of Electrical Engineering, 1978.

[704] A. KOLMOGOROV, “Three approaches to the definition of the concept ‘quantity of infor- mation”’, Problemy Peredachi Informatsii, 1 (1965), 3–11.

[705] A.G. KONHEIM, Cryptography, A Primer, John Wiley & Sons, New York, 1981.

[706] I. KOREN, Computer Arithmetic Algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1993.

[707] V.I. KORZHIK AND A.I. TURKIN, “Crypt- analysis of McEliece’s public-key cryptosys- tem”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 68–70, 1991.

[708] K. KOYAMA, U. MAURER, T. OKAMOTO, AND S.A. VANSTONE, “New public-key sch- emes based on elliptic curves over the ring Zn”, Advances in Cryptology–CRYPTO ’91 (LNCS 576), 252–266, 1992.

[709] K. KOYAMA AND R. TERADA, “How to strengthen DES-like cryptosystems against differential cryptanalysis”, IEICE Transac- tions on Fundamentals of Electronics, Com- munications and Computer Science, E76-A (1993), 63–69.

[710] E. KRANAKIS, Primality and Cryptography, John Wiley & Sons, Stuttgart, 1986.

[711] D.W. KRAVITZ, “Digital signature algo- rithm”, U.S. Patent # 5,231,668, 27 Jul 1993.

[712] H. KRAWCZYK, “How to predict congru- ential generators”, Advances in Cryptology– CRYPTO ’89 (LNCS 435), 138–153, 1990.

[713] , “How to predict congruential genera- tors”, Journal of Algorithms, 13 (1992), 527– 545. An earlier version appeared in [712].

, “Secret sharing made short”, Ad- vances in Cryptology–CRYPTO ’ 93 (LNCS 773), 136–146, 1994.

, “The shrinking generator: Some prac- tical considerations”, R. Anderson, editor, Fast Software Encryption, Cambridge Secu- rity Workshop (LNCS 809), 45–46, Springer- Verlag, 1994.

, “New hash functions for message authentication”, Advances in Cryptology– EUROCRYPT ’ 95 (LNCS 921), 301–310, 1995.

, “SKEME: A versatile secure key ex- change mechanism for Internet”, Proceedings of the Internet Society Symposium on Net- work and Distributed System Security, 114– 127, IEEE Computer Society Press, 1996.

Y. KURITA AND M. MATSUMOTO, “Primi- tive t-nomials (t = 3,5) over GF(2) whose degree is a Mersenne exponent ≤ 44497”, Mathematics of Computation, 56 (1991), 817– 821.

K. KUROSAWA, T. ITO, AND M. TAKEUCHI, “Public key cryptosystem using a reciprocal number with the same intractability as factor- ing a large number”, Cryptologia, 12 (1988), 225–233.

K. KUROSAWA, K. OKADA, AND S. TSUJII, “Low exponent attack against elliptic curve RSA”, Advances in Cryptology–ASIACRYPT ’94 (LNCS 917), 376–383, 1995.

K. KUSUDA AND T. MATSUMOTO, “Opti- mization of time-memory trade-off cryptanal- ysis and its application to DES, FEAL-32, and Skipjack”, IEICE Transactions on Funda- mentals of Electronics, Communications and Computer Science, E79-A (1996), 35–48.

J.C. LAGARIAS, “Knapsack public key cryptosystems and diophantine approxima- tion”, Advances in Cryptology–Proceedings of Crypto 83, 3–23, 1984.

, “Pseudorandom number generators in cryptography and number theory”, C. Pomer- ance, editor, Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, 115–143, American Mathematical Society, 1990.

Advances in Cryptology–CRYPTO ’ 94

tion”,

(LNCS 839), 129–139, 1994.

X. LAI, “Condition for the nonsingularity of a feedback shift-register over a general fi- nite field”, IEEE Transactions on Information Theory, 33 (1987), 747–749.

, “On the design and security of block ciphers”, ETH Series in Information Processing, J.L. Massey (editor), vol. 1, Hartung-Gorre Verlag Konstanz, Technische Hochschule (Zurich), 1992.

X. LAI AND L.R. KNUDSEN, “Attacks on double block length hash functions”, R. An- derson, editor, Fast Software Encryption, Cambridge Security Workshop (LNCS 809), 157–165, Springer-Verlag, 1994.

X. LAI AND J.L. MASSEY, “A proposal for a new block encryption standard”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 389–404, 1991.

, “Hash functions based on block ci- phers”, Advances in Cryptology–EUROCRY- PT ’92 (LNCS 658), 55–70, 1993.

X. LAI, J.L. MASSEY, AND S. MURPHY, “Markov ciphers and differential cryptanaly- sis”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 17–38, 1991.

X. LAI, R.A. RUEPPEL, AND J. WOOL- LVEN, “A fast cryptographic checksum al- gorithm based on stream ciphers”, Advances in Cryptology–AUSCRYPT ’92 (LNCS 718), 339–348, 1993.

C.-S. LAIH, L. HARN, J.-Y. LEE, AND T. HWANG, “Dynamic threshold scheme based on the definition of cross-product in an n-dimensional linear space”, Advances in Cryptology–CRYPTO ’ 89 (LNCS 435), 286– 298, 1990.

C.-S. LAIH, F.-K. TU, AND W.-C TAI, “On the security of the Lucas function”, Informa- tion Processing Letters, 53 (1995), 243–247.

K.-Y. LAM AND T. BETH, “Timely authen- tication in distributed systems”, Y. Deswarte, G. Eizenberg, and J.-J. Quisquater, editors, Second European Symposium on Research in Computer Security – ESORICS’ 92 (LNCS 648), 293–303, Springer-Verlag, 1992.

K.-Y. LAM AND L.C.K. HUI, “Efficiency of S S (I ) square-and-multiply exponentiation algorithms”, Electronics Letters, 30 (Decem- ber 8, 1994), 2115–2116.

B.A. LAMACCHIA AND A.M. ODLYZKO, “Computation of discrete logarithms in prime

fields”, Designs, Codes and Cryptography, 1 (1991), 47–62.

, “Solving large sparse linear systems over finite fields”, Advances in Cryptology– CRYPTO ’ 90 (LNCS 537), 109–133, 1991.

L. LAMPORT, “Constructing digital signa- tures from a one-way function”, Technical re- port CSL-98, SRI International, Palo Alto, 1979.

, “Password authentication with inse- cure communication”, Communications of the ACM, 24 (1981), 770–772.

B. LAMPSON, M. ABADI, M. BURROWS, AND E. WOBBER, “Authentication in dis- tributed systems: Theory and practice”, ACM Transactions on Computer Systems, 10 (1992), 265–310.

S.K. LANGFORD AND M.E. HELLMAN, “Differential-linear cryptanalysis”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 17– 25, 1994.

P.J. LEE AND E.F. BRICKELL, “An obser- vation on the security of McEliece’s public- key cryptosystem”, Advances in Cryptology– EUROCRYPT ’ 88 (LNCS 330), 275–280, 1988.

D.H. LEHMER, “Euclid’s algorithm for large numbers”, American Mathematical Monthly, 45 (1938), 227–233.

D.H. LEHMER AND R.E. POWERS, “On fac- toring large numbers”, Bulletin of the AMS, 37 (1931), 770–776.

T. LEIGHTON AND S. MICALI, “Secret-key agreement without public-key cryptography”, Advances in Cryptology–CRYPTO ’ 93 (LNCS 773), 456–479, 1994.

A.K. LENSTRA, “Posting to sci.crypt”, April 11 1996.

, “Primality testing”, C. Pomerance, ed- itor, Cryptology and Computational Number Theory, volume 42 of Proceedings of Sym- posia in Applied Mathematics, 13–25, Amer- ican Mathematical Society, 1990.

A.K. LENSTRA AND H.W. LENSTRA JR., “Algorithms in number theory”, J. van Leeuwen, editor, Handbook of Theoretical Computer Science, 674–715, Elsevier Science Publishers, 1990.

, The Development of the Number Field Sieve, Springer-Verlag, Berlin, 1993.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

A.K. LENSTRA, H.W. LENSTRA JR., AND L. LOV A ́ SZ, “Factoring polynomials with ra- tional coefficients”, Mathematische Annalen, 261 (1982), 515–534.

A.K. LENSTRA, H.W. LENSTRA JR., M.S. MANASSE, AND J.M. POLLARD, “The fac- torization of the ninth Fermat number”, Math- ematics of Computation, 61 (1993), 319–349.

, “The number field sieve”, A.K. Lenstra and H.W. Lenstra Jr., editors, The De- velopment of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, 11–42, Springer-Verlag, 1993.

A.K. LENSTRA AND M.S. MANASSE, “Fac- toring by electronic mail”, Advances in Cryptology–EUROCRYPT ’89 (LNCS 434), 355–371, 1990.

, “Factoring with two large primes”, Mathematics of Computation, 63 (1994), 785– 798.

A.K. LENSTRA, P. WINKLER, AND Y. YA- COBI, “A key escrow system with warrant bounds”, Advances in Cryptology–CRYPTO ’95 (LNCS 963), 197–207, 1995.

H.W.LENSTRAJR.,“Factoringintegerswith elliptic curves”, Annals of Mathematics, 126 (1987), 649–673.

, “Finding isomorphisms between fi- nite fields”, Mathematics of Computation, 56 (1991), 329–347.

, “On the Chor-Rivest knapsack cryp- tosystem”, Journal of Cryptology, 3 (1991), 149–155.

H.W. LENSTRA JR. AND C. POMERANCE, “A rigorous time bound for factoring inte- gers”, Journal of the American Mathematical Society, 5 (1992), 483–516.

H.W. LENSTRA JR. AND R.J. SCHOOF, “Primitive normal bases for finite fields”, Mathematics of Computation, 48 (1987), 217– 231.

L.A. LEVIN, “One-way functions and pseu- dorandom generators”, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 363–365, 1985.

J. LEVINE, United States Cryptographic Patents 1861–1981, Cryptologia, Inc., Terre Haute, Indiana, 1983.

R. LIDL AND W.B. MU ̈ LLER, “Permuta- tion polynomials in RSA-cryptosystems”, Ad- vances in Cryptology–Proceedings of Crypto 83, 293–301, 1984.

R. LIDL AND H. NIEDERREITER, Finite Fields, Cambridge University Press, Cam- bridge, 1984.

A.LIEBL,“Authenticationindistributedsys- tems: A bibliography”, Operating Systems Review, 27 (1993), 31–41.

C.H. LIM AND P.J. LEE, “Another method for attaining security against adaptively chosen ciphertext attacks”, Advances in Cryptology–CRYPTO ’ 93 (LNCS 773), 420– 434, 1994.

, “More flexible exponentiation with precomputation”, Advances in Cryptology– CRYPTO ’94 (LNCS 839), 95–107, 1994.

, “Server (prover/signer)-aided veri- fication of identity proofs and signatures”, Advances in Cryptology–EUROCRYPT ’ 95 (LNCS 921), 64–78, 1995.

S. LIN AND D. COSTELLO, Error Con- trol Coding: Fundamentals and Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1983.

J. LIPSON, Elements of Algebra and Alge- braic Computing, Addison-Wesley, Reading, Massachusetts, 1981.

T.M.A. LOMAS, L. GONG, J.H. SALTZER, AND R.M. NEEDHAM, “Reducing risks from poorly chosen keys”, Operating Systems Re- view, 23 (Special issue), 14–18. (Pre- sented at: 12th ACM Symposium on Operat- ing Systems Principles, Litchfield Park, Ari- zona, Dec. 1989).

D.L. LONG AND A. WIGDERSON, “The dis- crete logarithm hides O(log n) bits”, SIAM Journal on Computing, 17 (1988), 363–372.

R. LOVORN, Rigorous, subexponential al- gorithms for discrete logarithms over finite fields, PhD thesis, University of Georgia, 1992.

M. LUBY, Pseudorandomness and Crypto- graphic Applications, Princeton University Press, Princeton, New Jersey, 1996.

M. LUBY AND C. RACKOFF, “Pseudo- random permutation generators and crypto- graphic composition”, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 356–363, 1986.

, “How to construct pseudorandom per- mutations from pseudorandom functions”, SIAM Journal on Computing, 17 (1988), 373– 386. An earlier version appeared in [775].

S. LUCKS, “Faster Luby-Rackoff ciphers”, D. Gollmann, editor, Fast Software Encryp- tion, Third International Workshop (LNCS 1039), 189–203, Springer-Verlag, 1996.

F.J. MACWILLIAMS AND N.J.A. SLOANE, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977 (fifth print- ing: 1986).

W. MADRYGA, “A high performance encryp- tion algorithm”, J. Finch and E. Dougall, edi- tors, Computer Security: A Global Challenge, Proceedings of the Second IFIP International Conference on Computer Security, 557–570, North-Holland, 1984.

D.P. MAHER, “Crypto backup and key es- crow”, Communications of the ACM, 39 (1996), 48–53.

W. MAO AND C. BOYD, “On the use of encryption in cryptographic protocols”, P.G. Farrell, editor, Codes and Cyphers: Cryptog- raphy and Coding IV, 251–262, Institute of Mathematics & Its Applications (IMA), 1995.

G. MARSAGLIA, “A current view of random number generation”, L. Billard, editor, Com- puter Science and Statistics: Proceedings of the Sixteenth Symposium on the Interface, 3– 10, North-Holland, 1985.

P. MARTIN-LO ̈ F, “The definition of ran- dom sequences”, Information and Control, 9 (1966), 602–619.

J.L. MASSEY, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Infor- mation Theory, 15 (1969), 122–127.

, “An introduction to contemporary cryptology”, Proceedings of the IEEE, 76 (1988), 533–549.

, “Contemporary cryptology: An intro- duction”, G.J. Simmons, editor, Contempo- rary Cryptology: The Science of Information Integrity, 1–39, IEEE Press, 1992. An earlier version appeared in [785].

, “SAFER K-64: A byte-oriented block-ciphering algorithm”, R. Anderson, editor, Fast Software Encryption, Cam- bridge Security Workshop (LNCS 809), 1–17, Springer-Verlag, 1994.

, “SAFER K-64: One year later”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 212–241, Springer-Verlag, 1995.

J.L. MASSEY AND I. INGEMARSSON, “The Rip Van Winkle cipher – A simple and prov- ably computationally secure cipher with a fi- nite key”, IEEE International Symposium on Information Theory (Abstracts), p.146, 1985.

J.L. MASSEY AND X. LAI, “Device for con- verting a digital block and the use thereof”, European Patent # 482,154, 29 Apr 1992.

, “Device for the conversion of a dig- ital block and use of same”, U.S. Patent # 5,214,703, 25 May 1993.

J.L. MASSEY AND J.K. OMURA, “Method and apparatus for maintaining the privacy of digital messages conveyed by public transmis- sion”, U.S. Patent # 4,567,600, 28 Jan 1986.

J.L. MASSEY AND R.A. RUEPPEL, “Linear ciphers and random sequence generators with multiple clocks”, Advances in Cryptology– Proceedings of EUROCRYPT 84 (LNCS 209), 74–87, 1985.

J.L. MASSEY AND S. SERCONEK, “A Fourier transform approach to the linear com- plexity of nonlinearly filtered sequences”, Ad- vances in Cryptology–CRYPTO ’ 94 (LNCS 839), 332–340, 1994.

M. MATSUI, “The first experimental crypt- analysis of the Data Encryption Standard”, Advances in Cryptology–CRYPTO ’ 94 (LNCS 839), 1–11, 1994.

, “Linear cryptanalysis method for DES cipher”, Advances in Cryptology– EUROCRYPT ’ 93 (LNCS 765), 386–397, 1994.

, “On correlation between the or- der of S-boxes and the strength of DES”, Advances in Cryptology–EUROCRYPT ’ 94 (LNCS 950), 366–375, 1995.

M. MATSUI AND A. YAMAGISHI, “A new method for known plaintext attack of FEAL cipher”, Advances in Cryptology– EUROCRYPT ’ 92 (LNCS 658), 81–91, 1993.

T. MATSUMOTO AND H. IMAI, “On the key predistribution system: A practical solution to the key distribution problem”, Advances in Cryptology–CRYPTO ’ 87 (LNCS 293), 185– 193, 1988.

T. MATSUMOTO, Y. TAKASHIMA, AND H. IMAI, “On seeking smart public-key- distribution systems”, The Transactions of the IECE of Japan, E69 (1986), 99–106.

S.M. MATYAS, “Digital signatures – an overview”, Computer Networks, 3 (1979), 87–94.

, “Key handling with control vectors”, IBM Systems Journal, 30 (1991), 151–174.

, “Key processing with control vec- tors”, Journal of Cryptology, 3 (1991), 113– 136.

S.M. MATYAS AND C.H. MEYER, “Gener- ation, distribution, and installation of cryp- tographic keys”, IBM Systems Journal, 17 (1978), 126–137.

S.M. MATYAS, C.H. MEYER, AND J. OS- EAS, “Generating strong one-way functions with cryptographic algorithm”, IBM Techni- cal Disclosure Bulletin, 27 (1985), 5658– 5659.

S.M. MATYAS, C.H.W. MEYER, AND B.O. BRACHTL, “Controlled use of cryptographic keys via generating station established control values”, U.S. Patent # 4,850,017, 18 Jul 1989.

U. MAURER, “Fast generation of secure RSA-moduli with almost maximal diversity”, Advances in Cryptology–EUROCRYPT ’ 89 (LNCS 434), 636–647, 1990.

, “New approaches to the design of self- synchronizing stream ciphers”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 458–471, 1991.

, “A provably-secure strongly-random- ized cipher”, Advances in Cryptology–EURO- CRYPT ’90 (LNCS 473), 361–373, 1991.

, “A universal statistical test for ran- dom bit generators”, Advances in Cryptology– CRYPTO ’90 (LNCS 537), 409–420, 1991.

, “Conditionally-perfect secrecy and a provably-secure randomized cipher”, Journal of Cryptology, 5 (1992), 53–66. An earlier version appeared in [809].

, “Some number-theoretic conjectures and their relation to the generation of crypto- graphic primes”, C. Mitchell, editor, Cryptog- raphy and Coding II, volume 33 of Institute of Mathematics & Its Applications (IMA), 173– 191, Clarendon Press, 1992.

, “A universal statistical test for ran- dom bit generators”, Journal of Cryptology, 5 (1992), 89–105. An earlier version appeared in [810].

, “Factoring with an oracle”, Advances in Cryptology–EUROCRYPT ’ 92 (LNCS 658), 429–436, 1993.

, “Secret key agreement by public dis- cussion from common information”, IEEE Transactions on Information Theory, 39 (1993), 733–742.

, “A simplified and generalized treat- ment of Luby-Rackoff pseudorandom permu- tation generators”, Advances in Cryptology– EUROCRYPT ’ 92 (LNCS 658), 239–255, 1993.

, “Towards the equivalence of break- ing the Diffie-Hellman protocol and com- puting discrete logarithms”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 271– 281, 1994.

, “Fast generation of prime numbers and secure public-key cryptographic parameters”, Journal of Cryptology, 8 (1995), 123–155. An earlier version appeared in [807].

, “The role of information theory in cryptography”, P.G. Farrell, editor, Codes and Cyphers: Cryptography and Coding IV, 49– 71, Institute of Mathematics & Its Applica- tions (IMA), 1995.

U. MAURER AND J.L. MASSEY, “Per- fect local randomness in pseudo-random se- quences”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 100–112, 1990.

, “Local randomness in pseudorandom sequences”, Journal of Cryptology, 4 (1991), 135–149. An earlier version appeared in [820].

, “Cascade ciphers: The importance of being first”, Journal of Cryptology, 6 (1993), 55–61.

U. MAURER AND Y. YACOBI, “Non- interactive public-key cryptography”, Ad- vances in Cryptology–EUROCRYPT ’ 91 (LNCS 547), 498–507, 1991.

, “A remark on a non-interactive public-key distribution system”, Advances in Cryptology–EUROCRYPT ’92 (LNCS 658), 458–460, 1993.

K.S. MCCURLEY, “A key distribution sys- tem equivalent to factoring”, Journal of Cryp- tology, 1 (1988), 95–105.

, “Cryptographic key distribution and computation in class groups”, R.A. Mollin, editor, Number Theory and Applications, 459–479, Kluwer Academic Publishers, 1989.

, “The discrete logarithm problem”, C. Pomerance, editor, Cryptology and Com- putational Number Theory, volume 42 of Pro- ceedings of Symposia in Applied Mathemat- ics, 49–74, American Mathematical Society, 1990.

R.J. MCELIECE, “A public-key cryptosys- tem based on algebraic coding theory”, DSN progress report #42-44, Jet Propulsion Labo- ratory, Pasadena, California, 1978.

, The Theory of Information and Cod- ing: A Mathematical Framework for Commu- nication, Cambridge University Press, Cam- bridge, 1984.

, Finite Fields for Computer Scientists and Engineeers, Kluwer Academic Publish- ers, Boston, 1987.

C.A. MEADOWS, “Formal verification of cryptographic protocols: a survey”, Advances in Cryptology–ASIACRYPT ’94 (LNCS 917), 133–150, 1995.

W. MEIER, “On the security of the IDEA block cipher”, Advances in Cryptology– EUROCRYPT ’ 93 (LNCS 765), 371–385, 1994.

W. MEIER AND O. STAFFELBACH, “Fast correlation attacks on stream ciphers”, Ad- vances in Cryptology–EUROCRYPT ’ 88 (LNCS 330), 301–314, 1988.

, “Fast correlation attacks on certain stream ciphers”, Journal of Cryptology, 1 (1989), 159–176. An earlier version appeared in [833].

, “Analysis of pseudo random se- quences generated by cellular automata”, Advances in Cryptology–EUROCRYPT ’ 91 (LNCS 547), 186–199, 1991.

, “Correlation properties of combiners with memory in stream ciphers”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 204–213, 1991.

, “Correlation properties of combiners with memory in stream ciphers”, Journal of Cryptology, 5 (1992), 67–86. An earlier ver- sion appeared in [836].

, “The self-shrinking generator”, Ad- vances in Cryptology–EUROCRYPT ’ 94 (LNCS 950), 205–214, 1995.

S. MENDES AND C. HUITEMA, “A new ap- proach to the X.509 framework: allowing a global authentication infrastructure without a global trust model”, Proceedings of the In- ternet Society Symposium on Network and Distributed System Security, 172–189, IEEE Computer Society Press, 1995.

A. MENEZES, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston, 1993.

A. MENEZES, I. BLAKE, X. GAO, R. MUL- LIN, S. VANSTONE, AND T. YAGHOOBIAN, Applications of Finite Fields, Kluwer Aca- demic Publishers, Boston, 1993.

A. MENEZES, T. OKAMOTO, AND S. VAN- STONE, “Reducing elliptic curve logarithms to logarithms in a finite field”, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 80–89, 1991.

, “Reducing elliptic curve logarithms to logarithms in a finite field”, IEEE Trans- actions on Information Theory, 39 (1993), 1639–1646. An earlier version appeared in [842].

A. MENEZES, M. QU, AND S. VANSTONE, “Some new key agreement protocols provid- ing implicit authentication”, workshop record, 2nd Workshop on Selected Areas in Cryptog- raphy (SAC’95), Ottawa, Canada, May 18–19 1995.

R. MENICOCCI, “Cryptanalysis of a two- stage Gollmann cascade generator”, W. Wol- fowicz, editor, Proceedings of the 3rd Sym- posium on State and Progress of Research in Cryptography, Rome, Italy, 62–69, 1993.

R.C.MERKLE,“Digitalsignaturesystemand method based on a conventional encryption function”, U.S. Patent # 4,881,264, 14 Nov 1989.

, “Method and apparatus for data en- cryption”, U.S. Patent # 5,003,597, 26 Mar 1991.

, “Method of providing digital signa- tures”, U.S. Patent # 4,309,569, 5 Jan 1982.

, “Secure communications over inse- cure channels”, Communications of the ACM, 21 (1978), 294–299.

, Secrecy, Authentication, and Public Key Systems, UMI Research Press, Ann Ar- bor, Michigan, 1979.

, “Secrecy, authentication, and pub- lic key systems”, Technical Report No.1979- 1, Information Systems Laboratory, Stanford University, Palo Alto, California, 1979. Also available as [850].

, “Protocols for public key cryptosys- tems”, Proceedings of the 1980 IEEE Sympo- sium on Security and Privacy, 122–134, 1980.

, “A certified digital signature”, Ad- vances in Cryptology–CRYPTO ’89 (LNCS 435), 218–238, 1990.

, “A fast software one-way hash func- tion”, Journal of Cryptology, 3 (1990), 43–58.

, “One way hash functions and DES”,

Advances in Cryptology–CRYPTO ’ 89 (LNCS 435), 428–446, 1990.

, “Fast software encryption functions”,

Advances in Cryptology–CRYPTO ’90 (LNCS 537), 476–501, 1991.

R.C. MERKLE AND M.E. HELLMAN, “Hid- ing information and signatures in trapdoor knapsacks”, IEEE Transactions on Informa- tion Theory, 24 (1978), 525–530.

, “On the security of multiple en- cryption”, Communications of the ACM, 24 (1981), 465–467.

C.H. MEYER AND S.M. MATYAS, Cryptog- raphy: A New Dimension in Computer Data Security, John Wiley & Sons, New York, 1982 (third printing).

C.H. MEYER AND M. SCHILLING, “Se- cure program load with manipulation detec- tion code”, Proceedings of the 6th Worldwide Congress on Computer and Communications Security and Protection (SECURICOM’88), 111–130, 1988.

S. MICALI, “Fair cryptosystems and methods of use”, U.S. Patent # 5,276,737, 4 Jan 1994.

, “Fair cryptosystems and methods of use”, U.S. Patent # 5,315,658, 24 May 1994 (continuation-in-part of 5,276,737).

, “Fair public-key cryptosystems”, Ad- vances in Cryptology–CRYPTO ’92 (LNCS 740), 113–138, 1993.

S. MICALI, O. GOLDREICH, AND S. EVEN, “On-line/off-line digital signing”, U.S. Patent # 5,016,274, 14 May 1991.

S. MICALI, C. RACKOFF, AND B. SLOAN, “The notion of security for probabilistic cryp- tosystems”, SIAM Journal on Computing, 17 (1988), 412–426.

S. MICALI AND C.P. SCHNORR, “Efficient, perfect random number generators”, Ad- vances in Cryptology–CRYPTO ’ 88 (LNCS 403), 173–198, 1990.

, “Efficient, perfect polynomial random number generators”, Journal of Cryptology, 3 (1991), 157–172. An earlier version appeared in [866].

S. MICALI AND A. SHAMIR, “An improve- ment of the Fiat-Shamir identification and signature scheme”, Advances in Cryptology– CRYPTO ’88 (LNCS 403), 244–247, 1990.

S. MICALI AND R. SIDNEY, “A simple method for generating and sharing pseudo- random functions, with applications to Clipper-like key escrow systems”, Advances in Cryptology–CRYPTO ’ 95 (LNCS 963), 185–196, 1995.

P. MIHAILESCU, “Fast generation of provable primes using search in arithmetic progres- sions”, Advances in Cryptology–CRYPTO ’ 94 (LNCS 839), 282–293, 1994.

M.J. MIHALJEVIC ́ , “A security examination of the self-shrinking generator”, presentation at 5th IMA Conference on Cryptography and Coding, Cirencester, U.K., December 1995.

, “An approach to the initial state re- construction of a clock-controlled shift regis- ter based on a novel distance measure”, Ad- vances in Cryptology–AUSCRYPT ’92 (LNCS 718), 349–356, 1993.

, “A correlation attack on the bi- nary sequence generators with time-varying output function”, Advances in Cryptology– ASIACRYPT ’ 94 (LNCS 917), 67–79, 1995.

M.J. MIHALJEVIC ́ AND J.D. GOLIC ́, “A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence”, Advances in Cryptology– AUSCRYPT ’90 (LNCS 453), 165–175, 1990.

, “Convergence of a Bayesian iterative error-correction procedure on a noisy shift register sequence”, Advances in Cryptology– EUROCRYPT ’ 92 (LNCS 658), 124–137, 1993.

G.L. MILLER, “Riemann’s hypothesis and tests for primality”, Journal of Computer and System Sciences, 13 (1976), 300–317.

S.P. MILLER, B.C. NEUMAN, J.I. SCHILL- ER, AND J.H. SALTZER, “Kerberos authen- tication and authorization system”, Section E.2.1 of Project Athena Technical Plan, MIT, Cambridge, Massachusetts, 1987.

V.S. MILLER, “Use of elliptic curves in cryp- tography”, Advances in Cryptology–CRYPTO ’ 85 (LNCS 218), 417–426, 1986.

C. MITCHELL, “A storage complexity based analogue of Maurer key establishment using public channels”, C. Boyd, editor, Cryptog- raphy and Coding, 5th IMA Conference, Pro- ceedings, 84–93, Institute of Mathematics & Its Applications (IMA), 1995.

, “Limitations of challenge-response entity authentication”, Electronics Letters, 25 (August 17, 1989), 1195–1196.

C. MITCHELL AND F. PIPER, “Key storage in secure networks”, Discrete Applied Math- ematics, 21 (1988), 215–228.

C. MITCHELL, F. PIPER, AND P. WILD, “Digital signatures”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information Integrity, 325–378, IEEE Press, 1992.

A. MITROPOULOS AND H. MEIJER, “Zero knowledge proofs – a survey”, Technical Re- port No. 90-IR-05, Queen’s University at Kingston, Kingston, Ontario, Canada, 1990.

S. MIYAGUCHI, “The FEAL cipher family”,

Advances in Cryptology–CRYPTO ’90 (LNCS 537), 627–638, 1991.

S. MIYAGUCHI, S. KURIHARA, K. OHTA, AND H. MORITA, “Expansion of FEAL ci- pher”, NTT Review, 2 (1990), 117–127.

S. MIYAGUCHI, K. OHTA, AND M. IWATA, “128-bit hash function (N-hash)”, NTT Re- view, 2 (1990), 128–132.

S. MIYAGUCHI, A. SHIRAISHI, AND A. SHIMIZU, “Fast data encipherment al- gorithm FEAL-8”, Review of the Electrical Communications Laboratories, 36 (1988), 433–437.

A. MIYAJI AND M. TATEBAYASHI, “Public key cryptosystem with an elliptic curve”, U.S. Patent # 5,272,755, 21 Dec 1993.

, “Method of privacy communica- tion using elliptic curves”, U.S. Patent # 5,351,297, 27 Sep 1994 (continuation-in-part of 5,272,755).

S.B. MOHAN AND B.S. ADIGA, “Fast al- gorithms for implementing RSA public key cryptosystem”, Electronics Letters, 21 (Au- gust 15, 1985), 761.

R. MOLVA, G. TSUDIK, E. VAN HER- REWEGHEN, AND S. ZATTI, “KryptoKnight authentication and key distribution sys- tem”, Y. Deswarte, G. Eizenberg, and J.-J. Quisquater, editors, Second European Sympo- sium on Research in Computer Security – ES- ORICS’92 (LNCS 648), 155–174, Springer- Verlag, 1992.

L. MONIER, “Evaluation and comparison of two efficient probabilistic primality testing al- gorithms”, Theoretical Computer Science, 12 (1980), 97–108.

P. MONTGOMERY, “Modular multiplication without trial division”, Mathematics of Com- putation, 44 (1985), 519–521.

, “Speeding the Pollard and elliptic curve methods of factorization”, Mathematics of Computation, 48 (1987), 243–264.

P. MONTGOMERY AND R. SILVERMAN, “An FFT extension to the P − 1 factoring al- gorithm”, Mathematics of Computation, 54 (1990), 839–854.

P.L.MONTGOMERY,“AblockLanczosalgo- rithm for finding dependencies over GF (2)”, Advances in Cryptology–EUROCRYPT ’95 (LNCS 921), 106–120, 1995.

A.M. MOOD, “The distribution theory of runs”, The Annals of Mathematical Statistics, 11 (1940), 367–392.

J.H.MOORE,“Protocolfailuresincryptosys- tems”, Proceedings of the IEEE, 76 (1988), 594–602.

, “Protocol failures in cryptosystems”, G.J. Simmons, editor, Contemporary Cryp- tology: The Science of Information Integrity, 541–558, IEEE Press, 1992. Appeared earlier as [898].

J.H. MOORE AND G.J. SIMMONS, “Cy- cle structure of the DES for keys having palindromic (or antipalindromic) sequences of round keys”, IEEE Transactions on Software Engineering, 13 (1987), 262–273. An earlier version appeared in [901].

, “Cycle structure of the DES with weak and semi-weak keys”, Advances in Cryptology–CRYPTO ’ 86 (LNCS 263), 9–32, 1987.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

[902] F. MORAIN, “Distributed primality prov- ing and the primality of (23539 + 1)/3”, Advances in Cryptology–EUROCRYPT ’ 90 (LNCS 473), 110–123, 1991.

[903] , “Prime values of partition numbers and the primality of p1840926”, LIX Re- search Report LIX/RR/92/11, Laboratoire d’ Informatique de l’ Ecole P olytechnique, France, June 1992.

[904] F. MORAIN AND J. OLIVOS, “Speeding up the computations on an elliptic curve using addition-subtraction chains”, Theoretical In- formatics and Applications, 24 (1990), 531– 543.

[905] I.H. MORGAN AND G.L. MULLEN, “Prim- itive normal polynomials over finite fields”, Mathematics of Computation, 63 (1994), 759– 765.

[906] R. MORRIS, “The Hagelin cipher machine (M-209), Reconstruction of the internal set- tings”, Cryptologia, 2 (1978), 267–278.

[907] R. MORRIS AND K. THOMPSON, “Password security: a case history”, Communications of the ACM, 22 (1979), 594–597.

[908] M.A. MORRISON AND J. BRILLHART, “A method of factoring and the factorization of F7 ”, Mathematics of Computation, 29 (1975), 183–205.

[909] W.B. MU ̈ LLER AND R. NO ̈ BAUER, “Crypt- analysis of the Dickson-scheme”, Advances in Cryptology–EUROCRYPT ’85 (LNCS 219), 50–61, 1986.

[910] W.B. MU ̈ LLER AND W. NO ̈ BAUER, “Some remarks on public-key cryptosystems”, Studia Scientiarum Mathematicarum Hungarica, 16 (1981), 71–76.

[911] R. MULLIN, I. ONYSZCHUK, S. VANSTONE, AND R. WILSON, “Optimal normal bases in GF (pn)”, Discrete Applied Mathematics, 22 (1988/89), 149–161.

[912] S. MUND, “Ziv-Lempel complexity for peri- odic sequences and its cryptographic applica- tion”, Advances in Cryptology–EUROCRYPT ’91 (LNCS 547), 114–126, 1991.

[913] S. MURPHY, “The cryptanalysis of FEAL-4 with 20 chosen plaintexts”, Journal of Cryp- tology, 2 (1990), 145–154.

[914] D. NACCACHE, “Can O.S.S. be repaired? – proposal for a new practical signature sch- eme”, Advances in Cryptology–EUROCRYPT ’ 93 (LNCS 765), 233–239, 1994.

D. NACCACHE, D. M’RA ̈IHI, AND D. RAP- HAELI, “Can Montgomery parasites be avoided? A design methodology based on key and cryptosystem modifications”, Designs, Codes and Cryptography, 5 (1995), 73–80.

D. NACCACHE, D. M’RA ̈IHI, S. VAU- DENAY, AND D. RAPHAELI, “Can D.S.A. be improved? Complexity trade-offs with the digital signature standard”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 77–85, 1995.

D. NACCACHE AND H. M’SILTI, “A new modulo computation algorithm”, Recherche Ope ́ rationnelle – Operations Research (RAIRO-OR), 24 (1990), 307–313.

K. NAGASAKA, J.-S. SHIUE, AND C.-W. HO, “A fast algorithm of the Chinese remain- der theorem and its application to Fibonacci number”, G.E. Bergum, A.N. Philippou, and A.F. Horadam, editors, Applications of Fi- bonacci Numbers, Proceedings of the Fourth International Conference on Fibonacci Num- bers and their Applications, 241–246, Kluwer Academic Publishers, 1991.

M. NAOR AND A. SHAMIR, “Visual cryptography”, Advances in Cryptology– EUROCRYPT ’ 94 (LNCS 950), 1–12, 1995.

M. NAOR AND M. YUNG, “Universal one- way hash functions and their cryptographic applications”, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 33–43, 1989.

, “Public-key cryptosystems provably secure against chosen ciphertext attacks”, Proceedings of the 22nd Annual ACM Sym- posium on Theory of Computing, 427–437, 1990.

J. NECHVATAL, “Public key cryptography”, G.J. Simmons, editor, Contemporary Cryp- tology: The Science of Information Integrity, 177–288, IEEE Press, 1992.

R.M. NEEDHAM AND M.D. SCHROEDER, “Using encryption for authentication in large networks of computers”, Communications of the ACM, 21 (1978), 993–999.

, “Authentication revisited”, Operating Systems Review, 21 (1987), 7.

B.C. NEUMAN AND S.G. STUBBLEBINE,“A note on the use of timestamps as nonces”, Op- erating Systems Review, 27 (1993), 10–14.

B.C. NEUMAN AND T. TS’O, “Kerberos: an authentication service for computer net- works”, IEEE Communications Magazine, 32 (September 1994), 33–38.

H. NIEDERREITER, “The probabilistic the- ory of linear complexity”, Advances in Cryptology–EUROCRYPT ’88 (LNCS 330), 191–209, 1988.

, “A combinatorial approach to proba- bilistic results on the linear-complexity profile of random sequences”, Journal of Cryptology, 2 (1990), 105–112.

, “Keystream sequences with a good linear complexity profile for every starting point”, Advances in Cryptology– EUROCRYPT ’ 89 (LNCS 434), 523–532, 1990.

, “The linear complexity profile and the jump complexity of keystream sequences”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 174–188, 1991.

K. NISHIMURA AND M. SIBUYA, “Probabil- ity to meet in the middle”, Journal of Cryptol- ogy, 2 (1990), 13–22.

I.M. NIVEN AND H.S. ZUCKERMAN, An In- troduction to the Theory of Numbers, John Wi- ley & Sons, New York, 4th edition, 1980.

M.J. NORRIS AND G.J. SIMMONS, “Algo- rithms for high-speed modular arithmetic”, Congressus Numerantium, 31 (1981), 153– 163.

G. NORTON, “Extending the binary gcd al- gorithm”, J. Calmet, editor, Algebraic Algo- rithms and Error-Correcting Codes, 3rd Inter- national Conference, AAECC-3 (LNCS 229), 363–372, Springer-Verlag, 1986.

K. NYBERG, “On one-pass authenticated key establishment schemes”, workshop record, 2nd Workshop on Selected Areas in Cryptog- raphy (SAC’95), Ottawa, Canada, May 18–19 1995.

K. NYBERG AND R. RUEPPEL, “A new sig- nature scheme based on the DSA giving mes- sage recovery”, 1st ACM Conference on Com- puter and Communications Security, 58–61, ACM Press, 1993.

, “Weaknesses in some recent key agreement protocols”, Electronics Letters, 30 (January 6, 1994), 26–27.

, “Message recovery for signature sch- emes based on the discrete logarithm prob- lem”, Designs, Codes and Cryptography, 7 (1996), 61–81.

A.M. ODLYZKO, “Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir’s fast signature scheme”, IEEE Transactions on Information Theory, 30 (1984), 594–601.

, “Discrete logarithms in finite fields and their cryptographic significance”, Ad- vances in Cryptology–Proceedings of EURO- CRYPT 84 (LNCS 209), 224–314, 1985.

, “The rise and fall of knapsack cryp- tosystems”, C. Pomerance, editor, Cryptol- ogy and Computational Number Theory, vol- ume 42 of Proceedings of Symposia in Applied Mathematics, 75–88, American Mathematical Society, 1990.

, “Discrete logarithms and smooth poly- nomials”, G.L. Mullen and P.J-S. Shiue, ed- itors, Finite Fields: Theory, Applications, and Algorithms, volume 168 of Contemporary Mathematics, 269–278, American Mathemat- ical Society, 1994.

K. OHTA AND K. AOKI, “Linear cryptanaly- sis of the Fast Data Encipherment Algorithm”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 12–16, 1994.

K. OHTA AND T. OKAMOTO, “Practical ex- tension of Fiat-Shamir scheme”, Electronics Letters, 24 (July 21, 1988), 955–956.

, “A modification of the Fiat-Shamir scheme”, Advances in Cryptology–CRYPTO ’88 (LNCS 403), 232–243, 1990.

E. OKAMOTO AND K. TANAKA, “Key dis- tribution system based on identification infor- mation”, IEEE Journal on Selected Areas in Communications, 7 (1989), 481–485.

T. OKAMOTO, “A single public-key authen- tication scheme for multiple users”, Systems and Computers in Japan, 18 (1987), 14–24. Translated from Denshi Tsushin Gakkai Ron- bunshi vol. 69-D no.10, October 1986, 1481– 1489.

, “A fast signature scheme based on congruential polynomial operations”, IEEE Transactions on Information Theory, 36 (1990), 47–53.

, “Provably secure and practical identi- fication schemes and corresponding signature

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

schemes”, Advances in Cryptology–CRYPTO ’ 92 (LNCS 740), 31–53, 1993.

, “Designated confirmer signatures and public-key encryption are equivalent”, Ad- vances in Cryptology–CRYPTO ’ 94 (LNCS 839), 61–74, 1994.

, “An efficient divisible electronic cash scheme”, Advances in Cryptology–CRYPTO ’ 95 (LNCS 963), 438–451, 1995.

T. OKAMOTO, S. MIYAGUCHI, A. SHI- RAISHI, AND T. KAW AOKA, “Signed doc- ument transmission system”, U.S. Patent # 4,625,076, 25 Nov 1986.

T. OKAMOTO AND A. SHIRAISHI, “A fast signature scheme based on quadratic inequal- ities”, Proceedings of the 1985 IEEE Sympo- sium on Security and Privacy, 123–132, 1985.

T. OKAMOTO, A. SHIRAISHI, AND T. KAW- AOKA, “Secure user authentication without password files”, Technical Report NI83-92, I.E.C.E., Japan, January 1984. In Japanese.

J. OLIVOS, “On vectorial addition chains”, Journal of Algorithms, 2 (1981), 13–21.

J.K. OMURA AND J.L. MASSEY, “Compu- tational method and apparatus for finite field arithmetic”, U.S. Patent # 4,587,627, 6 May 1986.

H. ONG AND C.P. SCHNORR, “Fast signa- ture generation with a Fiat Shamir-like sch- eme”, Advances in Cryptology–EUROCRYPT ’90 (LNCS 473), 432–440, 1991.

H. ONG, C.P. SCHNORR, AND A. SHAMIR, “An efficient signature scheme based on quadratic equations”, Proceedings of the 16th Annual ACM Symposium on Theory of Com- puting, 208–216, 1984.

I.M. ONYSZCHUK, R.C. MULLIN, AND S.A. VANSTONE, “Computational method and apparatus for finite field multiplication”, U.S. Patent # 4,745,568, 17 May 1988.

G. ORTON, “A multiple-iterated trapdoor for dense compact knapsacks”, Advances in Cryptology–EUROCRYPT ’94 (LNCS 950), 112–130, 1995.

D. OTWAY AND O. REES, “Efficient and timely mutual authentication”, Operating Sys- tems Review, 21 (1987), 8–10.

J.C.PAILLE`SANDM.GIRAULT,“CRIPT:A public-key based solution for secure data com- munications”, Proceedings of the 7th World-wide Congress on Computer and Commu- nications Security and Protection (SECURI- COM’89), 171–185, 1989.

C.H. PAPADIMITRIOU, Computational Com- plexity, Addison-Wesley, Reading, Mas- sachusetts, 1994.

S.-J. PARK, S.-J. LEE, AND S.-C. GOH, “On the security of the Gollmann cascades”, Advances in Cryptology–CRYPTO ’ 95 (LNCS 963), 148–156, 1995.

J. PATARIN, “Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms”, Advances in Cryptology–EUROCRYPT ’96 (LNCS 1070), 33–48, 1996.

J. PATARIN AND P. CHAUVAUD, “Improved algorithms for the permuted kernel problem”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 391–402, 1994.

W. PENZHORN AND G. KU ̈HN, “Computa- tion of low-weight parity checks for corre- lation attacks on stream ciphers”, C. Boyd, editor, Cryptography and Coding, 5th IMA Conference, Proceedings, 74–83, Institute of Mathematics & Its Applications (IMA), 1995.

R. PERALTA, “Simultaneous security of bits in the discrete log”, Advances in Cryptology– EUROCRYPT ’85 (LNCS 219), 62–72, 1986.

R. PERALTA AND V. SHOUP, “Primality test- ing with fewer random bits”, Computational Complexity, 3 (1993), 355–367.

A. PFITZMANN AND R. ASSMANN, “More efficient software implementations of (gen- eralized) DES”, Computers & Security, 12 (1993), 477–500.

B. PFITZMANN AND M. WAIDNER, “Fail- stop signatures and their applications”, Pro- ceedings of the 9th Worldwide Congress on Computer and Communications Security and Protection (SECURICOM’91), 145–160, 1991.

, “Formal aspects of fail-stop signa- tures”, Interner Bericht 22/90, Universita ̈ t Karlsruhe, Germany, December 1990.

S.J.D. PHOENIX AND P.D. TOWNSEND, “Quantum cryptography: protecting our fu- ture networks with quantum mechanics”, C. Boyd, editor, Cryptography and Coding, 5th IMA Conference, Proceedings, 112–131, Institute of Mathematics & Its Applications (IMA), 1995.

R. PINCH, “The Carmichael numbers up to 1015 ”, Mathematics of Computation, 61 (1993), 381–391.

, “Some primality testing algorithms”,

Notices of the American Mathematical Soci- ety, 40 (1993), 1203–1210.

, “Extending the Ha ̊ stad attack to LUC”, Electronics Letters, 31 (October 12, 1995), 1827–1828.

, “Extending the Wiener attack to RSA- type cryptosystems”, Electronics Letters, 31 (September 28, 1995), 1736–1738.

V.PLESS,“Encryptionschemesforcomputer confidentiality”, IEEE Transactions on Com- puters, 26 (1977), 1133–1136.

J.B. PLUMSTEAD, “Inferring a sequence gen- erated by a linear congruence”, Proceedings of the IEEE 23rd Annual Symposium on Foun- dations of Computer Science, 153–159, 1982.

, “Inferring a sequence produced by a linear congruence”, Advances in Cryptology– Proceedings of Crypto 82, 317–319, 1983.

H.C. POCKLINGTON, “The determination of the prime or composite nature of large num- bers by Fermat’s theorem”, Proceedings of the Cambridge Philosophical Society, 18 (1914), 29–30.

S.C.POHLIGANDM.E.HELLMAN,“Anim- proved algorithm for computing logarithms over GF(p) and its cryptographic signifi- cance”, IEEE Transactions on Information Theory, 24 (1978), 106–110.

D. POINTCHEVAL, “A new identification scheme based on the perceptrons problem”, Advances in Cryptology–EUROCRYPT ’95 (LNCS 921), 319–328, 1995.

J.M. POLLARD, “Theorems on factorization and primality testing”, Proceedings of the Cambridge Philosophical Society, 76 (1974), 521–528.

, “A Monte Carlo method for factoriza- tion”, BIT, 15 (1975), 331–334.

, “Monte Carlo methods for index com- putation (mod p)”, Mathematics of Compu- tation, 32 (1978), 918–924.

, “Factoring with cubic integers”, A.K. Lenstra and H.W. Lenstra Jr., editors, The De- velopment of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, 4–10, Springer-Verlag, 1993.

J.M. POLLARD AND C. SCHNORR, “An effi- cient solution of the congruence x2 + ky2 = m (mod n)”, IEEE Transactions on Infor- mation Theory, 33 (1987), 702–709.

C. POMERANCE, “Analysis and comparison of some integer factoring algorithms”, H.W. Lenstra Jr. and R. Tijdeman, editors, Compu- tational Methods in Number Theory, Part 1, 89–139, Mathematisch Centrum, 1982.

, “The quadratic sieve factoring algo- rithm”, Advances in Cryptology–Proceedings of EUROCRYPT 84 (LNCS 209), 169–182, 1985.

, “Fast, rigorous factorization and dis- crete logarithm algorithms”, Discrete Algo- rithms and Complexity, 119–143, Academic Press, 1987.

, “Very short primality proofs”, Mathe- matics of Computation, 48 (1987), 315–322.

, editor, Cryptology and Computational Number Theory, American Mathematical So- ciety, Providence, Rhode Island, 1990.

, “Factoring”, C. Pomerance, editor,

Cryptology and Computational Number The- ory, volume 42 of Proceedings of Symposia in Applied Mathematics, 27–47, American Mathematical Society, 1990.

, “The number field sieve”, W. Gautsc- hi, editor, Mathematics of Computation, 1943- 1993: A Half-Century of Computation Math- ematics, volume 48 of Proceedings of Sym- posia in Applied Mathematics, 465–480, American Mathematical Society, 1994.

C. POMERANCE, J.L. SELFRIDGE, AND S.S. WAGSTAFF JR., “The pseudoprimes to 25 · 109”, Mathematics of Computation, 35 (1980), 1003–1026.

C. POMERANCE AND J. SORENSON, “Count- ing the integers factorable via cyclotomic methods”, Journal of Algorithms, 19 (1995), 250–265.

G.J. POPEK AND C.S. KLINE, “Encryption and secure computer networks”, ACM Com- puting Surveys, 11 (1979), 331–356.

E. PRANGE, “An algorism for factoring xn − 1 over a finite field”, AFCRC-TN-59-775, Air Force Cambridge Research Center, 1959.

V.R. PRATT, “Every prime has a succinct certificate”, SIAM Journal on Computing, 4 (1975), 214–220.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

B. PRENEEL, “Standardization of crypto- graphic techniques”, B. Preneel, R. Govaerts, and J. Vandewalle, editors, Computer Secu- rity and Industrial Cryptography: State of the Art and Evolution (LNCS 741), 162–173, Springer-Verlag, 1993.

, “Cryptographic hash functions”, Eu- ropean Transactions on Telecommunications, 5 (1994), 431–448.

, Analysis and design of cryptographic hash functions, PhD thesis, Katholieke Uni- versiteit Leuven (Belgium), Jan. 1993.

, Cryptographic Hash Functions, Kluwer Academic Publishers, Boston, (to ap- pear). Updated and expanded from [1003].

B. PRENEEL, R. GOVAERTS, AND J. VAN- DEWALLE, “Differential cryptanalysis of hash functions based on block ciphers”, 1st ACM Conference on Computer and Communica- tions Security, 183–188, ACM Press, 1993.

, “Information authentication: Hash functions and digital signatures”, B. Preneel, R. Govaerts, and J. Vandewalle, editors, Com- puter Security and Industrial Cryptography: State of the Art and Evolution (LNCS 741), 87–131, Springer-Verlag, 1993.

, “Hash functions based on block ci- phers: A synthetic approach”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 368– 378, 1994.

B. PRENEEL, M. NUTTIN, V. RIJMEN, AND J. BUELENS, “Cryptanalysis of the CFB mode of the DES with a reduced number of rounds”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 212–223, 1994.

B. PRENEEL AND P. VAN OORSCHOT, “MDx-MAC and building fast MACs from hash functions”, Advances in Cryptology– CRYPTO ’95 (LNCS 963), 1–14, 1995.

, “On the security of two MAC algorithms”, Advances in Cryptology– EUROCRYPT ’ 96 (LNCS 1070), 19–32, 1996.

N. PROCTOR, “A self-synchronizing cas- caded cipher system with dynamic control of error propagation”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 174–190, 1985.

G.B. PURDY, “A high security log-in pro- cedure”, Communications of the ACM, 17 (1974), 442–445.

M. QU AND S.A. VANSTONE, “The knap- sack problem in cryptography”, Contempo- rary Mathematics, 168 (1994), 291–308.

K. QUINN, “Some constructions for key dis- tribution patterns”, Designs, Codes and Cryp- tography, 4 (1994), 177–191.

J.-J. QUISQUATER, “A digital signature sch- eme with extended recovery”, preprint, 1995.

J.-J. QUISQUATER AND C. COUVREUR, “Fast decipherment algorithm for RSA public- key cryptosystem”, Electronics Letters, 18 (October 14, 1982), 905–907.

J.-J. QUISQUATER AND J.-P. DELESCAILLE, “How easy is collision search? Applica- tion to DES”, Advances in Cryptology– EUROCRYPT ’ 89 (LNCS 434), 429–434, 1990.

, “How easy is collision search. New re- sults and applications to DES”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 408– 413, 1990.

J.-J. QUISQUATER AND M. GIRAULT, “2n-bit hash-functions using n-bit symmet- ric block cipher algorithms”, Advances in Cryptology–EUROCRYPT ’89 (LNCS 434), 102–109, 1990.

J.-J. QUISQUATER, L. GUILLOU, AND T. BERSON, “How to explain zero-knowledge protocols to your children”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 628– 631, 1990.

M.O. RABIN, “Probabilistic algorithms”, J.F. Traub, editor, Algorithms and Complexity, 21–40, Academic Press, 1976.

, “Digitalized signatures”, R. DeMillo, D. Dobkin, A. Jones, and R. Lipton, editors, Foundations of Secure Computation, 155– 168, Academic Press, 1978.

, “Digitalized signatures and public- key functions as intractable as factorization”, MIT/LCS/TR-212, MIT Laboratory for Com- puter Science, 1979.

, “Probabilistic algorithm for testing primality”, Journal of Number Theory, 12 (1980), 128–138.

, “Probabilistic algorithms in finite fields”, SIAM Journal on Computing, 9 (1980), 273–280.

, “Fingerprinting by random polynomi- als”, TR-15-81, Center for Research in Com- puting Technology, Harvard University, 1981.

[1027] , “Efficient dispersal of information for security, load balancing, and fault tolerance”, Journal of the Association for Computing Ma- chinery, 36 (1989), 335–348.

[1028] T. RABIN AND M. BEN-OR, “Verifiable se- cret sharing and multiparty protocols with honest majority”, Proceedings of the 21st An- nual ACM Symposium on Theory of Comput- ing, 73–85, 1989.

[1029] C. RACKOFF AND D.R. SIMON, “Non- interactive zero-knowledge proof of knowl- edge and chosen ciphertext attack”, Advances

in Cryptology–CRYPTO ’ 91 (LNCS 576), 433–444, 1992.

[1030] G. RAWLINS, Compared to What? An Intro- duction to the Analysis of Algorithms, Com- puter Science Press, New York, 1992.

[1031] G. REITWIESNER, “Binary arithmetic”, Ad- vances in Computers, 1 (1960), 231–308.

[1032] T.RENJI,“Onfiniteautomatonone-keycryp- tosystems”, R. Anderson, editor, Fast Soft- ware Encryption, Cambridge Security Work- shop (LNCS 809), 135–148, Springer-Verlag, 1994.

[1033] RFC 1319, “The MD2 message-digest algo- rithm”, Internet Request for Comments 1319, B. Kaliski, April 1992 (updates RFC 1115, August 1989, J. Linn).

[1034] RFC 1320, “The MD4 message-digest algo- rithm”, Internet Request for Comments 1320, R.L. Rivest, April 1992 (obsoletes RFC 1186, October 1990, R. Rivest).

[1035] RFC 1321, “The MD5 message-digest algo- rithm”, Internet Request for Comments 1321, R.L. Rivest, April 1992 (presented at Rump Session of Crypto’91).

[1036] RFC 1421, “Privacy enhancement for Inter- net electronic mail – Part I: Message encryp- tion and authentication procedures”, Internet Request for Comments 1421, J. Linn, Febru- ary 1993 (obsoletes RFC 1113 – September 1989; RFC 1040 – January 1988; and RFC 989 – February 1987, J. Linn).

[1037] RFC 1422, “Privacy enhancement for Inter- net electronic mail – Part II: Certificate-based key management”, Internet Request for Com- ments 1422, S. Kent, February 1993 (obso- letes RFC 1114, August 1989, S. Kent and J. Linn).

[1038] RFC 1423, “Privacy enhancement for In- ternet electronic mail – Part III: Algorithms,

modes, and identifiers”, Internet Request for Comments 1423, D. Balenson, February 1993 (obsoletes RFC 1115, September 1989, J. Linn).

[1039] RFC 1424, “Privacy enhancement for Inter- net electronic mail – Part IV: Key certifica- tion and related services”, Internet Request for Comments 1424, B. Kaliski, February 1993.

[1040] RFC1508,“Genericsecurityserviceapplica- tion program interface”, Internet Request for Comments 1508, J. Linn, September 1993.

[1041] RFC 1510, “The Kerberos network authen- tication service (V5)”, Internet Request for Comments 1510, J. Kohl and C. Neuman, September 1993.

[1042] RFC 1521, “MIME (Multipurpose Internet Mail Extensions) Part One: Mechanisms for specifying and describing the format of In- ternet message bodies”, Internet Request for Comments 1521, N. Borenstein and N. Freed, September 1993 (obsoletes RFC 1341).

[1043] RFC 1750, “Randomness requirements for security”, Internet Request for Comments 1750, D. Eastlake, S. Crocker and J. Schiller, December 1994.

[1044] RFC 1828, “IP authentication using keyed MD5”, Internet Request for Comments 1828, P. Metzger and W. Simpson, August 1995.

[1045] RFC 1847, “Security multiparts for MIME: Multipart/signed and multipart/encrypted”, Internet Request for Comments 1847, J. Galvin, S. Murphy, S. Crocker and N. Freed, October 1995.

[1046] RFC 1848, “MIME object security services”, Internet Request for Comments 1848, S. Crocker, N. Freed, J. Galvin and S. Murphy, October 1995.

[1047] RFC 1938, “A one-time password system”, Internet Request for Comments 1938, N. Haller and C. Metz, May 1996.

[1048] V. RIJMEN, J. DAEMEN, B. PRENEEL, A. BOSSELAERS, AND E. DE WIN, “The cipher SHARK”, D. Gollmann, editor, Fast Software Encryption, Third International Workshop (LNCS 1039), 99–111, Springer- Verlag, 1996.

[1049] V. RIJMEN AND B. PRENEEL, “On weak- nesses of non-surjective round functions”, presented at the 2nd Workshop on Selected Areas in Cryptography (SAC’95), Ottawa, Canada, May 18–19 1995.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

, “Improved characteristics for differ- ential cryptanalysis of hash functions based on block ciphers”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 242–248, Springer- Verlag, 1995.

R.L. RIVEST, “Are ‘strong’ primes needed for RSA?”, unpublished manuscript, 1991.

, “Remarks on a proposed cryptana- lytic attack on the M.I.T. public-key cryp- tosystem”, Cryptologia, 2 (1978), 62–65.

, “Statistical analysis of the Hagelin cryptograph”, Cryptologia, 5 (1981), 27–32.

, “Cryptography”, J. van Leeuwen, ed- itor, Handbook of Theoretical Computer Sci- ence, 719–755, Elsevier Science Publishers, 1990.

, “The MD4 message digest algorithm”,

Advances in Cryptology–CRYPTO ’90 (LNCS 537), 303–311, 1991.

, “The RC5 encryption algorithm”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 86–96, Springer-Verlag, 1995.

R.L. RIVEST AND A. SHAMIR, “How to ex- pose an eavesdropper”, Communications of the ACM, 27 (1984), 393–395.

, “Efficient factoring based on par- tial information”, Advances in Cryptology– EUROCRYPT ’85 (LNCS 219), 31–34, 1986.

R.L. RIVEST, A. SHAMIR, AND L.M. ADLEMAN, “Cryptographic communications system and method”, U.S. Patent # 4,405,829, 20 Sep 1983.

, “A method for obtaining digital signa- tures and public-key cryptosystems”, Commu- nications of the ACM, 21 (1978), 120–126.

R.L. RIVEST AND A.T. SHERMAN, “Ran- domized encryption techniques”, Advances in Cryptology–Proceedings of Crypto 82, 145– 163, 1983.

M.J.B. ROBSHAW, “On evaluating the linear complexity of a sequence of least period 2n”, Designs, Codes and Cryptography, 4 (1994), 263–269.

, “Stream ciphers”, Technical Report TR-701 (version 2.0), RSA Laboratories, 1995.

M. ROE, “How to reverse engineer an EES device”, B. Preneel, editor, Fast Software

Encryption, Second International Workshop (LNCS 1008), 305–328, Springer-Verlag, 1995.

[1065] P. ROGAWAY, “Bucket hashing and its ap- plication to fast message authentication”, Ad- vances in Cryptology–CRYPTO ’95 (LNCS 963), 29–42, 1995.

[1066] P. ROGAWAY AND D. COPPERSMITH, “A software-optimized encryption algorithm”, R. Anderson, editor, Fast Software Encryp- tion, Cambridge Security Workshop (LNCS 809), 56–63, Springer-Verlag, 1994.

[1067] N. ROGIER AND P. CHAUVAUD, “The com- pression function of MD2 is not collision free”, workshop record, 2nd Workshop on Se- lected Areas in Cryptography (SAC’95), Ot- tawa, Canada, May 18–19 1995.

[1068] J. ROMPEL, “One-way functions are neces- sary and sufficient for secure signatures”, Pro- ceedings of the 22nd Annual ACM Symposium on Theory of Computing, 387–394, 1990.

[1069] K.H. ROSEN, Elementary Number Theory and its Applications, Addison-Wesley, Read- ing, Massachusetts, 3rd edition, 1992.

[1070] J. ROSSER AND L. SCHOENFELD, “Approx- imate formulas for some functions of prime numbers”, Illinois Journal of Mathematics, 6 (1962), 64–94.

[1071] RSA LABORATORIES, “The Public-Key Cryptography Standards – PKCS #11: Cryp- tographic token interface standard”, RSA Data Security Inc., Redwood City, California, April 28 1995.

[1072] , “The Public-Key Cryptography Stan- dards (PKCS)”, RSA Data Security Inc., Red- wood City, California, November 1993 Re- lease.

[1073] A.D. RUBIN AND P. HONEYMAN, “Formal methods for the analysis of authentication pro- tocols”, CITI Technical Report 93-7, Infor- mation Technology Division, University of Michigan, 1993.

[1074] F. RUBIN, “Decrypting a stream cipher based on J-K flip-flops”, IEEE Transactions on Computers, 28 (1979), 483–487.

[1075] R.A. RUEPPEL, Analysis and Design of Stream Ciphers, Springer-Verlag, Berlin, 1986.

[1076] , “Correlation immunity and the sum- mation generator”, Advances in Cryptology– CRYPTO ’ 85 (LNCS 218), 260–272, 1986.

, “Linear complexity and random se- quences”, Advances in Cryptology–EURO- CRYPT ’ 85 (LNCS 219), 167–188, 1986.

, “Key agreements based on func- tion composition”, Advances in Cryptology– EUROCRYPT ’88 (LNCS 330), 3–10, 1988.

, “On the security of Schnorr’s pseudo random generator”, Advances in Cryptology– EUROCRYPT ’ 89 (LNCS 434), 423–428, 1990.

, “A formal approach to security architectures”, Advances in Cryptology– EUROCRYPT ’ 91 (LNCS 547), 387–398, 1991.

, “Stream ciphers”, G.J. Simmons, ed- itor, Contemporary Cryptology: The Science of Information Integrity, 65–134, IEEE Press, 1992.

, “Criticism of ISO CD 11166 banking — key management by means of asymmet- ric algorithms”, W. Wolfowicz, editor, Pro- ceedings of the 3rd Symposium on State and Progress of Research in Cryptography, Rome, Italy, 191–198, 1993.

R.A. RUEPPEL, A. LENSTRA, M. SMID, K. MCCURLEY, Y. DESMEDT, A. ODLYZKO, AND P. LANDROCK, “The Eurocrypt ’92 con- troversial issue: trapdoor primes and mod- uli”, Advances in Cryptology–EUROCRYPT ’92 (LNCS 658), 194–199, 1993.

R.A. RUEPPEL AND J.L. MASSEY, “The knapsack as a non-linear function”, IEEE In- ternational Symposium on Information The- ory (Abstracts), p.46, 1985.

R.A. RUEPPEL AND O.J. STAFFELBACH, “Products of linear recurring sequences with maximum complexity”, IEEE Transactions on Information Theory, 33 (1987), 124–131.

R.A. RUEPPEL AND P.C. VAN OORSCHOT, “Modern key agreement techniques”, Com- puter Communications, 17 (1994), 458–465.

A. RUSSELL, “Necessary and sufficient con- ditions for collision-free hashing”, Advances in Cryptology–CRYPTO ’ 92 (LNCS 740), 433–441, 1993.

, “Necessary and sufficient conditions for collision-free hashing”, Journal of Cryp- tology, 8 (1995), 87–99. An earlier version appeared in [1087].

A . S A L O M A A , Public-key Cryptography, Springer-Verlag, Berlin, 1990.

[1090] M. SANTHA AND U.V. VAZIRANI, “Gener- ating quasi-random sequences from slightly- random sources”, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Science, 434–440, 1984.

[1091] , “Generating quasi-random sequences from semi-random sources”, Journal of Com- puter and System Sciences, 33 (1986), 75–87. An earlier version appeared in [1090].

[1092] O.SCHIROKAUER,“Discretelogarithmsand local units”, Philosophical Transactions of the Royal Society of London A, 345 (1993), 409– 423.

[1093] B. SCHNEIER, “Description of a new variable-length key, 64-bit block cipher (Blowfish)”, R. Anderson, editor, Fast Soft- ware Encryption, Cambridge Security Work- shop (LNCS 809), 191–204, Springer-Verlag, 1994.

[1094] , Applied Cryptography: Protocols, Al- gorithms, and Source Code in C, John Wiley & Sons, New York, 2nd edition, 1996.

[1095] C.P.SCHNORR,“Methodforidentifyingsub- scribers and for generating and verifying elec- tronic signatures in a data exchange system”, U.S. Patent # 4,995,082, 19 Feb 1991.

[1096] , “On the construction of random num- ber generators and random function genera- tors”, Advances in Cryptology–EUROCRYPT ’88 (LNCS 330), 225–232, 1988.

[1097] , “Efficient identification and signatures for smart cards”, Advances in Cryptology– CRYPTO ’89 (LNCS 435), 239–252, 1990.

[1098] , “Efficient signature generation by smart cards”, Journal of Cryptology, 4 (1991), 161–174.

[1099] C.P. SCHNORR AND M. EUCHNER, “Lat- tice basis reduction: Improved practical al- gorithms and solving subset sum problems”, L. Budach, editor, Fundamentals of Compu- tation Theory (LNCS 529), 68–85, Springer- Verlag, 1991.

[1100] C.P. SCHNORR AND H.H. HO ̈RNER, “At- tacking the Chor-Rivest cryptosystem by improved lattice reduction”, Advances in Cryptology–EUROCRYPT ’95 (LNCS 921), 1–12, 1995.

[1101] A. SCHO ̈NHAGE, “A lower bound for the length of addition chains”, Theoretical Com- puter Science, 1 (1975), 1–12.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

A.W. SCHRIFT AND A. SHAMIR, “On the universality of the next bit test”, Advances in Cryptology–CRYPTO ’ 90 (LNCS 537), 394– 408, 1991.

, “Universal tests for nonuniform dis- tributions”, Journal of Cryptology, 6 (1993), 119–133. An earlier version appeared in [1102].

F. SCHWENK AND J. EISFELD, “Public key encryption and signature schemes based on polynomials over Zn ”, Advances in Cryptology–EUROCRYPT ’96 (LNCS 1070), 60–71, 1996.

R. SEDGEWICK, Algorithms, Addison- Wesley, Reading, Massachusetts, 2nd edition, 1988.

R. SEDGEWICK, T.G. SZYMANSKI, AND A.C. YAO, “The complexity of finding cycles in periodic functions”, SIAM Journal on Com- puting, 11 (1982), 376–390.

E.S. SELMER, “Linear recurrence relations over finite fields”, Department of Mathemat- ics, University of Bergen, Norway, 1966.

J. SHALLIT, “On the worst case of three al- gorithms for computing the Jacobi symbol”, Journal of Symbolic Computation, 10 (1990), 593–610.

A. SHAMIR, “A fast signature scheme”, MIT/LCS/TM-107, MIT Laboratory for Com- puter Science, 1978.

, “How to share a secret”, Communica- tions of the ACM, 22 (1979), 612–613.

, “On the generation of cryptograph- ically strong pseudo-random sequences”, S. Even and O. Kariv, editors, Automata, Lan- guages, and Programming, 8th Colloquium (LNCS 115), 544–550, Springer-Verlag, 1981.

, “On the generation of cryptographi- cally strong pseudorandom sequences”, ACM Transactions on Computer Systems, 1 (1983), 38–44. An earlier version appeared in [1111].

, “A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem”, Advances in Cryptology– Proceedings of Crypto 82, 279–288, 1983.

, “A polynomial-time algorithm for breaking the basic Merkle-Hellman cryp- tosystem”, IEEE Transactions on Information Theory, 30 (1984), 699–704. An earlier ver- sion appeared in [1113].

, “Identity-based cryptosystems and signature schemes”, Advances in Cryptology– Proceedings of CRYPTO 84 (LNCS 196), 47– 53, 1985.

, “An efficient identification scheme based on permuted kernels”, Advances in Cryptology–CRYPTO ’ 89 (LNCS 435), 606– 609, 1990.

, “RSA for paranoids”, CryptoBytes, 1 (Autumn 1995), 1–4.

A. SHAMIR AND A. FIAT, “Method, appa- ratus and article for identification and signa- ture”, U.S. Patent # 4,748,668, 31 May 1988.

M.SHANDANDJ.VUILLEMIN,“Fastimple- mentations of RSA cryptography”, Proceed- ings of the 11th IEEE Symposium on Com- puter Arithmetic, 252–259, 1993.

C.E. SHANNON, “A mathematical theory of communication”, Bell System Technical Jour- nal, 27 (1948), 379–423, 623–656.

, “Communication theory of secrecy systems”, Bell System Technical Journal, 28 (1949), 656–715.

, “Prediction and entropy of printed English”, Bell System Technical Journal, 30 (1951), 50–64.

J. SHAWE-TAYLOR, “Generating strong primes”, Electronics Letters, 22 (July 31, 1986), 875–877.

S.SHEPHERD,“Ahighspeedsoftwareimple- mentation of the Data Encryption Standard”, Computers & Security, 14 (1995), 349–357.

A. SHIMIZU AND S. MIYAGUCHI, “Data randomization equipment”, U.S. Patent # 4,850,019, 18 Jul 1989.

, “Fast data encipherment algo- rithm FEAL”, Advances in Cryptology– EUROCRYPT ’ 87 (LNCS 304), 267–278, 1988.

Z . S H M U E L Y , “Composite Diffie-Hellman public-key generating systems are hard to break”, Technical Report #356, TECHNION – Israel Institute of Technology, Computer Science Department, 1985.

P.W. SHOR, “Algorithms for quantum com- putation: discrete logarithms and factoring”, Proceedings of the IEEE 35th Annual Sym- posium on Foundations of Computer Science, 124–134, 1994.

V. SHOUP, “New algorithms for finding irre- ducible polynomials over finite fields”, Math- ematics of Computation, 54 (1990), 435–447.

, “Searching for primitive roots in fi- nite fields”, Mathematics of Computation, 58 (1992), 369–380.

, “Fast construction of irreducible poly- nomials over finite fields”, Journal of Sym- bolic Computation, 17 (1994), 371–391.

T. SIEGENTHALER, “Correlation-immunity of nonlinear combining functions for crypto- graphic applications”, IEEE Transactions on Information Theory, 30 (1984), 776–780.

, “Decrypting a class of stream ciphers using ciphertext only”, IEEE Transactions on Computers, 34 (1985), 81–85.

, “Cryptanalysts representation of non- linearly filtered ML-sequences”, Advances in Cryptology–EUROCRYPT ’85 (LNCS 219), 103–110, 1986.

R.D.SILVERMAN,“Themultiplepolynomial quadratic sieve”, Mathematics of Computa- tion, 48 (1987), 329–339.

R.D. SILVERMAN AND S.S. WAGSTAFF JR., “A practical analysis of the elliptic curve fac- toring algorithm”, Mathematics of Computa- tion, 61 (1993), 445–462.

G.J. SIMMONS, “A “weak” privacy protocol using the RSA crypto algorithm”, Cryptolo- gia, 7 (1983), 180–182.

, “Authentication theory/coding the- ory”, Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 411–431, 1985.

, “The subliminal channel and dig- ital signatures”, Advances in Cryptology– Proceedings of EUROCRYPT 84 (LNCS 209), 364–378, 1985.

, “A secure subliminal channel (?)”, Ad- vances in Cryptology–CRYPTO ’85 (LNCS 218), 33–41, 1986.

, “How to (really) share a secret”, Ad- vances in Cryptology–CRYPTO ’ 88 (LNCS 403), 390–448, 1990.

, “Prepositioned shared secret and/or shared control schemes”, Advances in Cryptology–EUROCRYPT ’ 89 (LNCS 434), 436–467, 1990.

, “Contemporary cryptology: a fore- word”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information In- tegrity, vii–xv, IEEE Press, 1992.

, “A survey of information authentica- tion”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information In- tegrity, 379–419, IEEE Press, 1992.

, “An introduction to shared secret and/or shared control schemes and their appli- cation”, G.J. Simmons, editor, Contemporary Cryptology: The Science of Information In- tegrity, 441–497, IEEE Press, 1992.

, “How to insure that data acquired to verify treaty compliance are trustworthy”, G.J. Simmons, editor, Contemporary Cryp- tology: The Science of Information Integrity, 615–630, IEEE Press, 1992.

, “The subliminal channels in the U.S. Digital Signature Algorithm (DSA)”, W. Wol- fowicz, editor, Proceedings of the 3rd Sym- posium on State and Progress of Research in Cryptography, Rome, Italy, 35–54, 1993.

, “Proof of soundness (integrity) of cryptographic protocols”, Journal of Cryptol- ogy, 7 (1994), 69–77.

, “Subliminal communication is easy using the DSA”, Advances in Cryptology– EUROCRYPT ’ 93 (LNCS 765), 218–232, 1994.

, “Protocols that ensure fairness”, P.G. Farrell, editor, Codes and Cyphers: Cryptog- raphy and Coding IV, 383–394, Institute of Mathematics & Its Applications (IMA), 1995.

G.J.SIMMONSANDM.J.NORRIS,“Prelimi- nary comments on the M.I.T. public-key cryp- tosystem”, Cryptologia, 1 (1977), 406–414.

A. SINKOV, Elementary Cryptanalysis: A Mathematical Approach, Random House, New York, 1968.

M.E. SMID, “Integrating the Data Encryp- tion Standard into computer networks”, IEEE Transactions on Communications, 29 (1981), 762–772.

M.E. SMID AND D.K. BRANSTAD, “Crypto- graphic key notarization methods and appara- tus”, U.S. Patent # 4,386,233, 31 May 1983.

, “The Data Encryption Standard: Past and future”, Proceedings of the IEEE, 76 (1988), 550–559.

, “The Data Encryption Standard: Past and future”, G.J. Simmons, editor, Contempo- rary Cryptology: The Science of Information Integrity, 43–64, IEEE Press, 1992. Appeared earlier as [1155].

, “Response to comments on the NIST proposed digital signature standard”, Ad- vances in Cryptology–CRYPTO ’ 92 (LNCS 740), 76–88, 1993.

D.R. SMITH AND J.T. PALMER, “Univer- sal fixed messages and the Rivest-Shamir- Adleman cryptosystem”, Mathematika, 26 (1979), 44–52.

J.L. SMITH, “Recirculating block ci- pher cryptographic system”, U.S. Patent # 3,796,830, 12 Mar 1974.

, “The design of Lucifer: A cryp- tographic device for data communications”, IBM Research Report RC 3326, IBM T.J. Watson Research Center, Yorktown Heights, N.Y., 10598, U.S.A., Apr. 15 1971.

P. SMITH AND M. LENNON, “LUC: A new public key system”, E. Dougall, editor, Pro- ceedings of the IFIP TC11 Ninth International Conference on Information Security, IFIP/Sec 93, 103–117, North-Holland, 1993.

P. SMITH AND C. SKINNER, “A public-key cryptosystem and a digital signature system based on the Lucas function analogue to dis- crete logarithms”, Advances in Cryptology– ASIACRYPT ’94 (LNCS 917), 357–364, 1995.

R. SOLOVAY AND V. STRASSEN, “A fast Monte-Carlo test for primality”, SIAM Jour- nal on Computing, 6 (1977), 84–85. Erratum in ibid, 7 (1978), 118.

J. SORENSON, “Two fast gcd algorithms”, Journal of Algorithms, 16 (1994), 110–144.

A. SORKIN, “Lucifer, a cryptographic algo- rithm”, Cryptologia, 8 (1984), 22–35.

M. STADLER, J.-M. PIVETEAU, AND J. CA- MENISCH, “Fair blind signatures”, Advances in Cryptology–EUROCRYPT ’ 95 (LNCS 921), 209–219, 1995.

O. STAFFELBACH AND W. MEIER, “Cryp- tographic significance of the carry for ci- phers based on integer addition”, Advances in Cryptology–CRYPTO ’90 (LNCS 537), 601– 614, 1991.

W. STAHNKE, “Primitive binary polynomi- als”, Mathematics of Computation, 27 (1973), 977–980.

D.G. STEER, L. STRAWCZYNSKI, W. DIFF- IE, AND M. WIENER, “A secure audio tele- conference system”, Advances in Cryptology– CRYPTO ’ 88 (LNCS 403), 520–528, 1990.

J. STEIN, “Computational problems associ- ated with Racah algebra”, Journal of Compu- tational Physics, 1 (1967), 397–405.

J.G. STEINER, C. NEUMAN, AND J.I. SCHILLER, “Kerberos: an authentication ser- vice for open network systems”, Proceedings of the Winter 1988 Usenix Conference, 191– 201, 1988.

M. STEINER, G. TSUDIK, AND M. WAID- NER, “Refinement and extension of encrypted key exchange”, Operating Systems Review, 29:3 (1995), 22–30.

J. STERN, “Secret linear congruential gener- ators are not cryptographically secure”, Pro- ceedings of the IEEE 28th Annual Symposium on Foundations of Computer Science, 421– 426, 1987.

, “An alternative to the Fiat-Shamir pro- tocol”, Advances in Cryptology–EUROCRY- PT ’89 (LNCS 434), 173–180, 1990.

, “Designing identification schemes with keys of short size”, Advances in Cryptology–CRYPTO ’94 (LNCS 839), 164– 173, 1994.

, “A new identification scheme based on syndrome decoding”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 13– 21, 1994.

D.R. STINSON, “An explication of secret sharing schemes”, Designs, Codes and Cryp- tography, 2 (1992), 357–390.

, Cryptography: Theory and Practice, CRC Press, Boca Raton, Florida, 1995.

S.G. STUBBLEBINE AND V.D. GLIGOR, “On message integrity in cryptographic protocols”, Proceedings of the 1992 IEEE Computer So- ciety Symposium on Research in Security and Privacy, 85–104, 1992.

D.J.SYKES,“Themanagementofencryption keys”, D.K. Branstad, editor, Computer secu- rity and the Data Encryption Standard, 46–53, NBS Special Publication 500-27, U.S. Depart- ment of Commerce, National Bureau of Stan- dards, Washington, D.C., 1977.

P. SYVERSON, “Knowledge, belief and se- mantics in the analysis of cryptographic proto- cols”, Journal of Computer Security, 1 (1992), 317–334.

, “A taxonomy of replay attacks”, Pro- ceedings of the Computer Security Founda- tions Workshop VII (CSFW 1994), 187–191, IEEE Computer Society Press, 1994.

P. SYVERSON AND P. VAN OORSCHOT, “On unifying some cryptographic protocol logics”, Proceedings of the 1994 IEEE Computer So- ciety Symposium on Research in Security and Privacy, 14–28, 1994.

K. TANAKA AND E. OKAMOTO, “Key dis- tribution using id-related information direc- tory suitable for mail systems”, Proceedings of the 8th Worldwide Congress on Computer and Communications Security and Protection (SECURICOM’90), 115–122, 1990.

A. TARAH AND C. HUITEMA, “Associating metrics to certification paths”, Y. Deswarte, G. Eizenberg, and J.-J. Quisquater, editors, Second European Symposium on Research in Computer Security – ESORICS’92 (LNCS 648), 175–189, Springer-Verlag, 1992.

J.J. TARDO AND K. ALAGAPPAN, “SPX: Global authentication using public key certifi- cates”, Proceedings of the IEEE Symposium on Research in Security and Privacy, 232– 244, 1991.

A. TARDY-CORFDIR AND H. GILBERT, “A known plaintext attack of FEAL-4 and FEAL- 6”, Advances in Cryptology–CRYPTO ’ 91 (LNCS 576), 172–182, 1992.

M. TATEBAYASHI, N. MATSUZAKI, AND D.B. NEWMAN JR., “Key distribution pro- tocol for digital mobile communication sys- tems”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 324–334, 1990.

R. TAYLOR, “An integrity check value al- gorithm for stream ciphers”, Advances in Cryptology–CRYPTO ’93 (LNCS 773), 40– 48, 1994.

J.A. THIONG LY, “A serial version of the Pohlig-Hellman algorithm for computing dis- crete logarithms”, Applicable Algebra in En- gineering, Communication and Computing, 4 (1993), 77–80.

J. THOMPSON, “S/MIME message specifica- tion – PKCS security services for MIME”, RSA Data Security Inc., Aug. 29 1995, http://www.rsa.com/.

T. TOKITA, T. SORIMACHI, AND M. MAT- SUI, “Linear cryptanalysis of LOKI and s2DES”, Advances in Cryptology–ASIACRY- PT ’94 (LNCS 917), 293–303, 1995.

, “On applicability of linear cryptanal- ysis to DES-like cryptosystems – LOKI89, LOKI91 and s2 DES”, IEICE Transactions on Fundamentals of Electronics, Communica- tions and Computer Science, E78-A (1995), 1148–1153. An earlier version appeared in [1192].

M. TOMPA AND H. WOLL, “Random self- reducibility and zero-knowledge interactive proofs of possession of information”, Pro- ceedings of the IEEE 28th Annual Symposium on Foundations of Computer Science, 472– 482, 1987.

, “How to share a secret with cheaters”, Journal of Cryptology, 1 (1988), 133–138.

G. TSUDIK, “Message authentication with one-way hash functions”, Computer Commu- nication Review, 22 (1992), 29–38.

S. TSUJII AND J. CHAO, “A new ID- based key sharing system”, Advances in Cryptology–CRYPTO ’91 (LNCS 576), 288– 299, 1992.

W. TUCHMAN, “Integrated system design”, D.K. Branstad, editor, Computer security and the Data Encryption Standard, 94–96, NBS Special Publication 500-27, U.S. Department of Commerce, National Bureau of Standards, Washington, D.C., 1977.

, “Hellman presents no shortcut solu- tions to the DES”, IEEE Spectrum, 16 (1979), 40–41.

J. VAN DE GRAAF AND R. PERALTA,“A sim- ple and secure way to show the validity of your public key”, Advances in Cryptology– CRYPTO ’87 (LNCS 293), 128–134, 1988.

E. VAN HEIJST AND T.P. PEDERSEN, “How to make efficient fail-stop signatures”, Ad- vances in Cryptology–EUROCRYPT ’ 92 (LNCS 658), 366–377, 1993.

E. VAN HEIJST, T.P. PEDERSEN, AND B. PFITZMANN, “New constructions of fail- stop signatures and lower bounds”, Advances in Cryptology–CRYPTO ’92 (LNCS 740), 15– 30, 1993.

P. VAN OORSCHOT, “A comparison of prac- tical public key cryptosystems based on in- teger factorization and discrete logarithms”, G.J. Simmons, editor, Contemporary Cryp- tology: The Science of Information Integrity, 289–322, IEEE Press, 1992.

, “Extending cryptographic logics of belief to key agreement protocols”, 1st ACM Conference on Computer and Communica- tions Security, 232–243, ACM Press, 1993.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

, “An alternate explanation of two BAN-logic “failures””, Advances in Crypto- logy–EUROCRYPT ’ 93 (LNCS 765), 443– 447, 1994.

P. VAN OORSCHOT AND M. WIENER, “A known-plaintext attack on two-key triple encryption”, Advances in Cryptology– EUROCRYPT ’ 90 (LNCS 473), 318–325, 1991.

, “Parallel collision search with appli- cations to hash functions and discrete log- arithms”, 2nd ACM Conference on Com- puter and Communications Security, 210– 218, ACM Press, 1994.

, “Improving implementable meet-in- the-middle attacks by orders of magnitude”, Advances in Cryptology–CRYPTO ’ 96 (LNCS 1109), 229–236, 1996.

, “On Diffie-Hellman key agree- ment with short exponents”, Advances in Cryptology–EUROCRYPT ’ 96 (LNCS 1070), 332–343, 1996.

H.C.A. VAN TILBORG, An Introduction to Cryptology, Kluwer Academic Publishers, Boston, 1988.

, “Authentication codes: an area where coding and cryptology meet”, C. Boyd, edi- tor, Cryptography and Coding, 5th IMA Con- ference, Proceedings, 169–183, Institute of Mathematics & Its Applications (IMA), 1995.

J. VAN TILBURG, “On the McEliece public- key cryptosystem”, Advances in Cryptology– CRYPTO ’88 (LNCS 403), 119–131, 1990.

S.A. VANSTONE AND R.J. ZUCCHERATO, “Elliptic curve cryptosystems using curves of smooth order over the ring Zn”, IEEE Trans- actions on Information Theory, to appear.

, “Short RSA keys and their genera- tion”, Journal of Cryptology, 8 (1995), 101– 114.

S. VAUDENAY, “On the need for multipermu- tations: Cryptanalysis of MD4 and SAFER”, B. Preneel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 286–297, Springer-Verlag, 1995.

, “On the weak keys of Blowfish”, D. Gollmann, editor, Fast Software Encryp- tion, Third International Workshop (LNCS 1039), 27–32, Springer-Verlag, 1996.

U.V. VAZIRANI, “Towards a strong com- munication complexity theory, or generating

quasi-random sequences from two communi- cating slightly-random sources”, Proceedings of the 17th Annual ACM Symposium on The- ory of Computing, 366–378, 1985.

U.V. VAZIRANI AND V.V. VAZIRANI, “Effi- cient and secure pseudo-random number gen- eration”, Proceedings of the IEEE 25th An- nual Symposium on Foundations of Computer Science, 458–463, 1984. This paper also ap- peared in [1219].

, “Efficient and secure pseudo- random number generation”, Advances in Cryptology–Proceedings of CRYPTO 84 (LNCS 196), 193–202, 1985.

K. VEDDER, “Security aspects of mobile communications”, B. Preneel, R. Govaerts, and J. Vandewalle, editors, Computer Secu- rity and Industrial Cryptography: State of the Art and Evolution (LNCS 741), 193–210, Springer-Verlag, 1993.

G.S. VERNAM, “Secret signaling system”, U.S. Patent # 1,310,719, 22 Jul 1919.

, “Cipher printing telegraph systems for secret wire and radio telegraphic communica- tions”, Journal of the American Institute for Electrical Engineers, 55 (1926), 109–115.

J. VON NEUMANN, “Various techniques used in connection with random digits”, Applied Mathematics Series, U.S. National Bureau of Standards, 12 (1951), 36–38.

J. VON ZUR GATHEN AND V. SHOUP, “Com- puting Frobenius maps and factoring polyno- mials”, Computational Complexity, 2 (1992), 187–224.

V.L. VOYDOCK AND S.T. KENT, “Security mechanisms in high-level network protocols”, Computing Surveys, 15 (1983), 135–171.

D. WACKERLY, W. MENDENHALL III, AND R. SCHEAFFER, Mathematical Statistics with Applications, Duxbury Press, Belmont, Cali- fornia, 5th edition, 1996.

M. WAIDNER AND B. PFITZMANN, “The dining cryptographers in the disco: Uncon- ditional sender and recipient untraceability with computationally secure serviceability”, Advances in Cryptology–EUROCRYPT ’ 89 (LNCS 434), 690, 1990.

C.P. WALDVOGEL AND J.L. MASSEY, “The probability distribution of the Diffie-Hellman key”, Advances in Cryptology–AUSCRYPT ’ 92 (LNCS 718), 492–504, 1993.

S.T. WALKER, S.B. LIPNER, C.M. ELLI- SON, AND D.M. BALENSON, “Commercial key recovery”, Communications of the ACM, 39 (1996), 41–47.

C.D. WALTER, “Faster modular multipli- cation by operand scaling”, Advances in Cryptology–CRYPTO ’91 (LNCS 576), 313– 323, 1992.

P.C. WAYNER, “Content-addressable search engines and DES-like systems”, Advances in Cryptology–CRYPTO ’ 92 (LNCS 740), 575– 586, 1993.

D. WEBER, “An implementation of the gen- eral number field sieve to compute discrete logarithms mod p”, Advances in Cryptology– EUROCRYPT ’95 (LNCS 921), 95–105, 1995.

A.F. WEBSTER AND S.E. TAVARES, “On the design of S-boxes”, Advances in Cryptology– CRYPTO ’85 (LNCS 218), 523–534, 1986.

M.N. WEGMAN AND J.L. CARTER, “New hash functions and their use in authentication and set equality”, Journal of Computer and System Sciences, 22 (1981), 265–279.

D. WELSH, Codes and Cryptography, Clarendon Press, Oxford, 1988.

A.E. WESTERN AND J.C.P. MILLER, Ta- bles of Indices and Primitive Roots, volume 9, Royal Society Mathematical Tables, Cam- bridge University Press, 1968.

D.J. WHEELER, “A bulk data encryption al- gorithm”, R. Anderson, editor, Fast Software Encryption, Cambridge Security Workshop (LNCS 809), 127–134, Springer-Verlag, 1994.

D.J. WHEELER AND R.M. NEEDHAM, “TEA, a tiny encryption algorithm”, B. Pre- neel, editor, Fast Software Encryption, Second International Workshop (LNCS 1008), 363– 366, Springer-Verlag, 1995.

D.H. WIEDEMANN, “Solving sparse linear equations over finite fields”, IEEE Transac- tions on Information Theory, 32 (1986), 54– 62.

M.J. WIENER, “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on In- formation Theory, 36 (1990), 553–558.

, “Efficient DES key search”, Technical Report TR-244, School of Computer Science, Carleton University, Ottawa, 1994. Presented at Crypto ’93 rump session.

S. WIESNER, “Conjugate coding”, SIGACT News, 15 (1983), 78–88. Original manuscript (circa 1970).

H.S. WILF, “Backtrack: An O(1) expected time algorithm for the graph coloring prob- lem”, Information Processing Letters, 18 (1984), 119–121.

M.V. WILKES, Time-Sharing Computer Sys- tems, American Elsevier Pub. Co., New York, 3rd edition, 1975.

F. WILLEMS, “Universal data compression and repetition times”, IEEE Transactions on Information Theory, 35 (1989), 54–58.

H.C. WILLIAMS, “A modification of the RSA public-key encryption procedure”, IEEE Transactions on Information Theory, 26 (1980), 726–729.

, “A p + 1 method of factoring”, Math- ematics of Computation, 39 (1982), 225–234.

, “Some public-key crypto-functions as intractable as factorization”, Cryptologia, 9 (1985), 223–237.

H.C.WILLIAMSANDB.SCHMID,“Somere- marks concerning the M.I.T. public-key cryp- tosystem”, BIT, 19 (1979), 525–538.

R.S. WINTERNITZ, “A secure one-way hash function built from DES”, Proceedings of the 1984 IEEE Symposium on Security and Pri- vacy, 88–90, 1984.

S. WOLFRAM, “Cryptography with cellular automata”, Advances in Cryptology–CRYPTO ’ 85 (LNCS 218), 429–432, 1986.

, “Random sequence generation by cel- lular automata”, Advances in Applied Mathe- matics, 7 (1986), 123–169.

H . W O L L , “Reductions among number the- oretic problems”, Information and Computa- tion, 72 (1987), 167–179.

A.D. WYNER, “The wire-tap channel”, Bell System Technical Journal, 54 (1975), 1355– 1387.

Y. YACOBI, “A key distribution “paradox””,

Advances in Cryptology–CRYPTO ’90 (LNCS 537), 268–273, 1991.

Y. YACOBI AND Z. SHMUELY, “On key dis- tribution systems”, Advances in Cryptology– CRYPTO ’89 (LNCS 435), 344–355, 1990.

A.C. YAO, “On the evaluation of powers”, SIAM Journal on Computing, 5 (1976), 100– 103.

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

, “Theory and applications of trapdoor functions”, Proceedings of the IEEE 23rd An- nual Symposium on Foundations of Computer Science, 80–91, 1982.

S.-M. YEN AND C.-S. LAIH, “New digi- tal signature scheme based on discrete log- arithm”, Electronics Letters, 29 (June 10, 1993), 1120–1121.

C. YUEN, “Testing random number genera- tors by Walsh transform”, IEEE Transactions on Computers, 26 (1977), 329–333.

D. YUN, “Fast algorithm for rational function integration”, Information Processing 77: Pro- ceedings of IFIP Congress 77, 493–498, 1977. G. YUVAL, “How to swindle Rabin”, Cryp- tologia, 3 (1979), 187–190.

K. ZENG AND M. HUANG, “On the lin- ear syndrome method in cryptanalysis”, Ad- vances in Cryptology–CRYPTO ’88 (LNCS 403), 469–478, 1990.

K. ZENG, C.-H. YANG, AND T.R.N. RAO, “On the linear consistency test (LCT) in cryptanalysis with applications”, Advances in Cryptology–CRYPTO ’89 (LNCS 435), 164– 174, 1990.

, “An improved linear syndrome algo- rithm in cryptanalysis with applications”, Ad- vances in Cryptology–CRYPTO ’ 90 (LNCS 537), 34–47, 1991.

K. ZENG, C.-H. YANG, D.-Y WEI, AND T.R.N. RAO, “Pseudorandom bit generators in stream-cipher cryptography”, Computer, 24 (1991), 8–17.

C. ZHANG, “An improved binary algorithm for RSA”, Computers and Mathematics with Applications, 25:6 (1993), 15–24.

Y. ZHENG, J. PIEPRZYK, AND J. SEBERRY, “HAVAL – a one-way hashing algorithm with variable length of output”, Advances in Cryptology–AUSCRYPT ’ 92 (LNCS 718), 83– 104, 1993.

Y. ZHENG AND J. SEBERRY, “Immunizing public key cryptosystems against chosen ci- phertext attacks”, IEEE Journal on Selected Areas in Communications, 11 (1993), 715– 724.

N. ZIERLER, “Primitive trinomials whose de- gree is a Mersenne exponent”, Information and Control, 15 (1969), 67–69.

N. ZIERLER AND J. BRILLHART, “On prim- itive trinomials (mod 2)”, Information and Control, 13 (1968), 541–554.

P.R. ZIMMERMANN, The Official PGP User’s Guide, MIT Press, Cambridge, Mas- sachusetts, 1995 (second printing).

J. ZIV AND A. LEMPEL, “On the complexity of finite sequences”, IEEE Transactions on In- formation Theory, 22 (1976), 75–81.

M. Zˇ IVKOVIC ́ , “An algorithm for the initial state reconstruction of the clock-controlled shift register”, IEEE Transactions on Infor- mation Theory, 37 (1991), 1488–1490.

, “A table of primitive binary polynomi- als”, Mathematics of Computation, 62 (1994), 385–386.

, “Table of primitive binary polyno- mials. II”, Mathematics of Computation, 63 (1994), 301–306.

### Appendix A: References (Informative) on [6] Recommendation for Key Derivation Using Pseudorandom Functions (Revised)

[1] NIST SP 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, May 2006.

[2] NIST SP 800-56B, Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography, expected to be published in 2008.

[3] IETF RFC 5216, The EAP-TLS Authentication Protocol, March 2008.

[4] Y. Dodis, R. Gennaro, J. Håstad, H. Krawczyk, and T. Rabin, Randomness Extraction and Key derivation Using the CBC, Cascade, and HMAC Modes, Crypto’04, LNCS 3152, pp. 494-510. Springer Verlag, 2004.

[5]NIST SP 800-90, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, March 2007.

[6] FIPS 180-3, Secure Hash Standard, Revision expected to be published in 2008.

[7] NIST SP 800-38B, Recommendation for Block Cipher Modes of Operation – The CMAC Mode for Authentication, May 2005.

[8] FIPS 198-1, The Keyed-Hash Message Authentication Code (HMAC), Revision expected to be published in 2008.

[9] O.Goldreich, S. Goldwasser and S. Micali, “How to construct pseudorandom functions”, Journal of the ACM, Vol. 33, No. 4, pp. 210-217, (1986).

[10] C. Adams, G. Kramer, S. Mister, and R. Zuccherato “On the Security of Key Derivation Functions”, Information Security, LNCS 3225, pp. 134-145, Springer Verlag, 2004.

### [7] BSI: A proposal for: Functionality classes and evaluation methodology for true (physical)random number generators, Version 3.1

### [8] BSI: Application Notes and Interpretation of the Scheme (AIS) http://www.bsi.bund.de/zertifiz/zert/interpr/ais20e.pdf

### [9] Trusted Computing Group https://www.trustedcomputinggroup.org/

# 考察

関連文書との整合性を順次確認。

参考文献の参考文献

### 最後までおよみいただきありがとうございました。

いいね 💚、フォローをお願いします。

#### Thank you very much for reading to the last sentence.

Please press the like icon 💚 and follow me for your happy life.