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.
Author(s): S C Serpell, C B Brookson, B L Clark (auth.), George Robert Blakley, David Chaum (eds.)
Series: Lecture Notes in Computer Science 196
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1985
Language: English
Pages: 496
Tags: Coding and Information Theory; Data Encryption
A Prototype Encryption System Using Public Key....Pages 3-9
A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms....Pages 10-18
A Public-Key Cryptosystem Based on the Word Problem....Pages 19-36
Efficient Signature Schemes Based on Polynomial Equations (preliminary version)....Pages 37-46
Identity-Based Cryptosystems and Signature Schemes....Pages 47-53
A Knapsack Type Public Key Cryptosystem Based On Arithmetic in Finite Fields (preliminary draft)....Pages 54-65
Some Public-Key Crypto-Functions as Intractable as Factorization....Pages 66-70
Computing Logarithms in GF (2 n )....Pages 73-82
Wyner’s Analog Encryption Scheme: Results of a Simulation....Pages 83-94
On Rotation Group and Encryption of Analog Signals....Pages 95-100
The History of Book Ciphers....Pages 101-113
An Update on Factorization at Sandia National Laboratories....Pages 114-114
An LSI Digital Encryption Processor (DEP)....Pages 115-143
Efficient hardware and software implementations for the DES....Pages 144-146
Efficient hardware implementation of the DES....Pages 147-173
A Self-Synchronizing Cascaded Cipher System with Dynamic Control of Error Propagation....Pages 174-190
Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)....Pages 193-202
An LSI Random Number Generator (RNG)....Pages 203-230
Generalized Linear Threshold Scheme....Pages 231-241
Security of Ramp Schemes....Pages 242-268
A Fast Pseudo Random Permutation Generator With Applications to Cryptology....Pages 269-275
On the Cryptographic Applications of Random Functions (Extended Abstract)....Pages 276-288
An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information....Pages 289-299
Information Theory without the Finiteness Assumption, I: Cryptosystems as Group-Theoretic Objects....Pages 303-313
Cryptanalysis of Adfgvx Encipherment Systems....Pages 314-338
Breaking Iterated Knapsacks....Pages 339-341
Dependence of output on input in DES: Small avalanche characteristics....Pages 342-358
Des has no Per Round Linear Factors....Pages 359-376
A Message Authenticator Algorithm Suitable for a Mainframe Computer....Pages 377-389
Key Management for Secure Electronic Funds Transfer in a Retail Environment....Pages 393-400
Authentication Theory/Coding Theory....Pages 401-410
New Secret Codes Can Prevent a Computerized Big Brother....Pages 411-431
Fair Exchange of Secrets (extended abstract)....Pages 432-433
Cryptoprotocols: Subscription to a Public Key, The Secret Blocking and The Multi-Player Mental Poker Game (extended abstract)....Pages 434-438
Poker Protocols....Pages 439-453
A “Paradoxical” Solution to The Signature Problem....Pages 454-464
Sequence Complexity as a Test for Cryptographic Systems....Pages 467-467
An Update on Quantum Cryptography....Pages 468-474
How to Keep a Secret Alive....Pages 475-480
....Pages 481-485
