Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes

DOI10.1007/3-540-68697-5_11zbMath1329.94054OpenAlexW1580599221MaRDI QIDQ3452347

Ramarathnam Venkatesan, Dan Boneh

Publication date: 11 November 2015

Published in: Advances in Cryptology — CRYPTO ’96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-68697-5_11

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (53)

(EC)DSA lattice attacks based on Coppersmith's method ⋮ Evaluating the Cache Side Channel Attacks Against ECDSA ⋮ Secret sets and applications ⋮ A Tale of Three Signatures: Practical Attack of ECDSA with wNAF ⋮ Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes ⋮ Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm ⋮ Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation ⋮ Attacking ECDSA leaking discrete bits with a more efficient lattice ⋮ Integer LWE with non-subgaussian error and related attacks ⋮ Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator ⋮ A hidden number problem in small subgroups ⋮ RSA and Elliptic Curve Least Significant Bit Security ⋮ The Multivariate Hidden Number Problem ⋮ Finding shortest lattice vectors faster using quantum search ⋮ The security of all private-key bits in isogeny-based schemes ⋮ Generalized attack on ECDSA: known bits in arbitrary positions ⋮ All shall FA-LLL: breaking CT-RSA 2022 and CHES 2022 infective countermeasures with lattice-based fault attacks ⋮ On the bit security of the weak Diffie-Hellman problem ⋮ Characterizing overstretched NTRU attacks ⋮ The hidden number problem with small unknown multipliers: cryptanalyzing MEGA in six queries and other applications ⋮ Analysis of hidden number problem with hidden multiplier ⋮ Handle the traces: revisiting the attack on ECDSA with EHNP ⋮ Protecting the most significant bits in scalar multiplication algorithms ⋮ On the modular inversion hidden number problem ⋮ On the Security of Supersingular Isogeny Cryptosystems ⋮ Improving bounds on elliptic curve hidden number problem for ECDH key exchange ⋮ Differential fault attack on Montgomery ladder and in the presence of scalar randomization ⋮ The curious case of the half-half Bitcoin ECDSA nonces ⋮ Security of polynomial transformations of the Diffie-Hellman key. ⋮ Limits of a conjecture on a leakage-resilient cryptosystem ⋮ Security of the most significant bits of the Shamir message passing scheme ⋮ On the statistical properties of Diffie-Hellman distributions ⋮ On the Bit Security of Elliptic Curve Diffie–Hellman ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Toward an Easy-to-Understand Structure for Achieving Chosen Ciphertext Security from the Decisional Diffie-Hellman Assumption ⋮ The Geometry of Provable Security: Some Proofs of Security in Which Lattices Make a Surprise Appearance ⋮ Koblitz curve cryptosystems ⋮ Efficient Chosen Ciphertext Secure Public Key Encryption under the Computational Diffie-Hellman Assumption ⋮ The Hidden Root Problem ⋮ Noisy polynomial interpolation modulo prime powers ⋮ Safe-Errors on SPA Protected Implementations with the Atomicity Technique ⋮ Cryptanalysis of elliptic curve hidden number problem from PKC 2017 ⋮ Bit Security of the CDH Problems over Finite Fields ⋮ Optimal Randomness Extraction from a Diffie-Hellman Element ⋮ Minicrypt primitives with algebraic structure and applications ⋮ Security of hedged Fiat-Shamir signatures under fault attacks ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Toward Compact Public Key Encryption Based on CDH Assumption via Extended Twin DH Assumption ⋮ On the complexity of the discrete logarithm and Diffie-Hellman problems ⋮ Noisy Chinese remaindering in the Lee norm ⋮ RSA key recovery from digit equivalence information ⋮ Security of most significant bits of \(g^{x^{2}}\). ⋮ Close values of shifted modular inversions and the decisional modular inversion hidden number problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Lovász' lattice reduction and the nearest lattice point problem
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Generating EIGamal Signatures Without Knowing the Secret Key
• Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
• A public key cryptosystem and a signature scheme based on discrete logarithms
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
• Reconstructing Truncated Integer Variables Satisfying Linear Congruences
• New directions in cryptography
• Block Reduced Lattice Bases and Successive Minima

This page was built for publication: Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes