Advances in Cryptology

1. Front Matter

   Pages I-IX

   PDF

2. Public Key Cryptosystems and Signatures

   1. A Prototype Encryption System Using Public Key

      • S C Serpell, C B Brookson, B L Clark

      Pages 3-9

   2. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms

      • Taher ElGamal

      Pages 10-18

   3. A Public-Key Cryptosystem Based on the Word Problem

      • Neal R. Wagner, Marianne R. Magyarik

      Pages 19-36

   4. Efficient Signature Schemes Based on Polynomial Equations (preliminary version)

      • H. Ong, C. P. Schnorr, A. Shamir

      Pages 37-46

   5. Identity-Based Cryptosystems and Signature Schemes

      • Adi Shamir

      Pages 47-53

   6. A Knapsack Type Public Key Cryptosystem Based On Arithmetic in Finite Fields (preliminary draft)

      • Benny Chor, Ronald L. Rivest

      Pages 54-65

   7. Some Public-Key Crypto-Functions as Intractable as Factorization

      • H. C. Williams

      Pages 66-70

3. Cryptosystems and Other Hard Problems

   1. Computing Logarithms in GF (2n)

      • I. F. Blake, R. C. Mullin, S. A. Vanstone

      Pages 73-82

   2. Wyner’s Analog Encryption Scheme: Results of a Simulation

      • Burt S. Kaliski

      Pages 83-94

   3. On Rotation Group and Encryption of Analog Signals

      • Su-shing Chen

      Pages 95-100

   4. The History of Book Ciphers

      • Albert C. Leighton, Stephen M. Matyas

      Pages 101-113

   5. An Update on Factorization at Sandia National Laboratories

      • J. A. Davis, D. B. Holdridge

      Pages 114-114

   6. An LSI Digital Encryption Processor (DEP)

      • R. C. Fairfield, A. Matusevich, J. Plany

      Pages 115-143

   7. Efficient hardware and software implementations for the DES

      • Marc Davio, Yvo Desmedt, Jo Goubert, Frank Hoornaert, Jean-Jacques Quisquater

      Pages 144-146

   8. Efficient hardware implementation of the DES

      • Frank Hoornaert, Jo Goubert, Yvo Desmedt

      Pages 147-173

   9. A Self-Synchronizing Cascaded Cipher System with Dynamic Control of Error Propagation

      • Norman Proctor

      Pages 174-190

4. Randomness and Its Concomitants

   1. Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)

      • Umesh V. Vazirani, Vijay V. Vazirani

      Pages 193-202

   2. An LSI Random Number Generator (RNG)

      • R. C. Fairfield, R. L. Mortenson, K. B. Coulthart

      Pages 203-230

   3. Generalized Linear Threshold Scheme

      • S. C. Kothari

      Pages 231-241

Recently, there has been a lot of interest in provably "good" pseudo-random number generators [lo, 4, 14, 31. These cryptographically secure generators are "good" in the sense that they pass all probabilistic polynomial time statistical tests. However, despite these nice properties, the secure generators known so far suffer from the han- cap of being inefiicient; the most efiicient of these take n2 steps (one modular multip- cation, n being the length of the seed) to generate one bit. Pseudc-random number g- erators that are currently used in practice output n bits per multiplication (n2 steps). An important open problem was to output even two bits on each multiplication in a cryptographically secure way. This problem was stated by Blum, Blum & Shub [3] in the context of their z2 mod N generator. They further ask: how many bits can be o- put per multiplication, maintaining cryptographic security? In this paper we state a simple condition, the XOR-Condition and show that any generator satisfying this condition can output logn bits on each multiplication. We show that the XOR-Condition is satisfied by the lop least significant bits of the z2-mod N generator. The security of the z2 mod N generator was based on Quadratic Residu- ity [3]. This generator is an example of a Trapdoor Generator [13], and its trapdoor properties have been used in protocol design. We strengthen the security of this gene- tor by proving it as hard as factoring.

• Computer
• Hardware
• algorithms
• calculus
• coding theory
• complexity
• cryptography
• cryptology
• information theory

• Department of Mathematics, Texas A&M University, College Station, USA

  George Robert Blakley

• Center for Mathematics and Computer Science (CWI), Amsterdam, The Netherlands

  David Chaum

Policies and ethics