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

DOI10.1016/0022-0000(93)90038-XMaRDI QIDQ1317484zbMATH OpenWikidataFDO

Authors A. W. Schrift, A. Sharmir, Johan Hastad

Publication date 30 June 1994

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

Full work available at URL https://doi.org/10.1016/0022-0000(93)90038-X

zbMATH Keywords

Blum integerefficient pseudorandom bit generatorsmultibit commitment schemesone-way functionprobability distributions

Mathematics Subject Classification ID

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

Recommendations

• Simultaneous Security of Bits in the Discrete Log
• The Discrete Logarithm Hides $O(\log n)$ Bits
• The security of all RSA and discrete log bits
• scientific article; zbMATH DE number 1302855
• scientific article; zbMATH DE number 1759796

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A Simple Unpredictable Pseudo-Random Number Generator
• An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
• Efficient cryptographic schemes provably as secure as subset sum
• Efficient Factoring Based on Partial Information
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 503265 (Why is no real title available?)
• scientific article; zbMATH DE number 4187086 (Why is no real title available?)
• Probabilistic encryption
• The Differences between Consecutive Primes

Cited in

(11)

• Synthesizers and their application to the parallel construction of pseudo-random functions
• On the security of modular exponentiation with application to the construction of pseudorandom generators
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• Non-malleable functions and their applications
• A new cryptosystem using generalized Mersenne primes
• On completely factoring any integer efficiently in a single run of an order-finding algorithm
• All bits in ax + b p are hard
• Paillier's trapdoor function hides \(\Theta(n)\) bits
• The Discrete Logarithm Hides $O(\log n)$ Bits
• Quantum attacks on pseudorandom generators
• A Kilobit Hidden SNFS Discrete Logarithm Computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1317484)