The discrete logarithm modulo a composite hides \(O(n)\) bits

DOI10.1016/0022-0000(93)90038-XzbMath0790.94013WikidataQ56959146 ScholiaQ56959146MaRDI QIDQ1317484

A. W. Schrift, A. Sharmir, Johan T. Håstad

Publication date: 30 June 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

probability distributionsone-way functionBlum integerefficient pseudorandom bit generatorsmultibit commitment schemes

Mathematics Subject Classification ID

Cryptography (94A60) Random number generation in numerical analysis (65C10)

Related Items (8)

Non-malleable functions and their applications ⋮ All Bits in ax + b mod p are Hard ⋮ Paillier's trapdoor function hides \(\Theta(n)\) bits ⋮ On completely factoring any integer efficiently in a single run of an order-finding algorithm ⋮ Quantum attacks on pseudorandom generators ⋮ Quantum algorithms for computing general discrete logarithms and orders with tradeoffs ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ A new cryptosystem using generalized Mersenne primes

Cites Work

• Probabilistic encryption
• Efficient cryptographic schemes provably as secure as subset sum
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Efficient Factoring Based on Partial Information
• A Simple Unpredictable Pseudo-Random Number Generator
• An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
• A method for obtaining digital signatures and public-key cryptosystems
• The Differences between Consecutive Primes
• Unnamed Item
• Unnamed Item

This page was built for publication: The discrete logarithm modulo a composite hides \(O(n)\) bits