What Every Programmer Needs to Know about Quantum Safe Cryptography and Hidden Number Problems

We code the 1996 paper that introduced the Hidden Number Problem as well as the 2020 paper that improves on the LLL solution.We help programmers learn to turn advanced math papers into C and Python code. Sub for moreThis is part of our series on Practical Index Calculus for Computer Programmers.Part 1: Discrete Logarithms and the Index Calculus Solution.Part 2: Solving Pell Equations with Index Calculus and Algebraic Numbers.Part 3: Solving Index Calculus Equations over Integers and Finite Fields.Part 4.1 : Pollard Kangaroo when Index Calculus Fails.Part 4.2 : Pohlig-Hellman Attack.Part 5 : Smart Attack on Anomalous Curves.Part 6: Hacking Dormant Bitcoin Wallets in C.Part 7: Lattice Based Attacks on Discrete Logarithms.The 2001 paper Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes (Boneh & Venkatesan, 2001)1 attempts to answer the question: is it easier to calculate just a few bits of a secret key than the entire secret?Along the way, this paper introduces the hidden number problem: the challenge of recovering a secret hidden number given partial knowledge of its linear relations (Surin & Cohney, 2023)2.As it turns out, this problem is difficult even for quantum computers. So hidden number problems are at the heart of post-quantum cryptography.Integer Discrete Logarithm ProblemThe Integer Discrete Logarithm Problem is the challenge of finding an integer x satisfying (Howell, 1998)3:The equation above states: there exists a primitive root (g) raised to an exponent (x) that gives us a target (y).Finding x is difficult and researchers call this the integer discrete logarithm problem (Integer DLP). (Boneh & Venkatesan, 1996) explore the complexity of extracting partial info about the secret key in an integer DLP.Here’s their conclusion: for a prime number p, the first √(log p) are as hard to compute as the entire key.In practice, this implies that the anything after the first 32 bits of a 1024 bit prime are difficult to compute.Along the way, the authors introduce ‘The Hidden Number Problem’ to prove their thesis.In a regular integer discrete logarithm problem, we attempt to find a secret key x as shown below:Say we gain extra information about x from a cache leak, a timing attack or other side channel (Zhou & Feng, 2005)4.(Boneh & Venkatesan, 1996) reformulate the integer DLP to incorporate these side channel information leaks as:They call this reformulation the Hidden Number Problem (HNP).Hidden Number Problem (HNP) statement: we can recover x by finding multiples of the secret key (ti⋅x) alongside the most significant bits of the result (ai), even when the error term (β) is unkown.NoteThis attack is not possible in a typical DLP. Hidden number problems emanate from information leaks in sidechannel attacks (Chao Sun et al., 2021)5.HNP suggests that knowing multiples of our secret key (x) by known numbers (ti) and the most significant bits of the result (a) permit us recover the secret key all while ignoring the error term (β).(Boneh & Venkatesan, 1996) prove that small error terms are in fact the shortest vectors in the lattice corresponding to the reformulated integer DLP with side channel information.(Boneh & Venkatesan, 1996) construct a matrix of the form below and use LLL reduction to find the shortest basis vectors:whereThe authors prove that finding the shortest basis vectors for this integer lattice provides a solution to the DLP. (Benger, 2014) includes a terms in the lattice to improve solution search. We shall work with the improved lattice:We follow the numerical example in (Surin & Cohney, 2023). Say we want to solve:Suppose we encounter a side channel that leaks info in the form:Such a leak would resemble:where the Betas are small but unknown. For maximum clarity, these are the actual unknown betas.Now we can construct our lattice:Running LLL on this basis gives us the reduced basis:(Boneh & Venkatesan, 1996) proved that the shortest vector always contains our noise terms:Our second basis vector gives us the result so we take the second basis vector to find:Indeed, 309 is our secret key! It worked.Main takeaway from this section:We wouldn’t have information on the small betas but I revealed them earlier:Observe that the correct noise terms occur in the LLL reduction as stated in (Boneh & Venkatesan, 1996):Joseph Surin offers a Sage implementation on GitHub.We simply create the matrix and call LLL on it. It’s about 20 lines of Sage/Python code.and we test our small example to see if it works:Yes, it does. The previous example is from a side channel attack observed modulo p. HNP works everywhere information leaks.We experience one extreme setback in our approach: the LLL algorithm fails to recover secret keys when our error betas are 1 or 2 bits close to our field modulo.Researchers call this the Lattice Barrier problem.The Lattice Barrier occurs when our target vector may not be the shortest in our basis and the paper (Albrecht & Heninger, 2020)6 demonstrates ways to overcome the challenge.We start from this code. q is the largest prime factor of the secp field characteristic primesecretKey is a 135 bit target similar (somewhat) to the bitcoin puzzles.errorMaxExponent is 233 bits.multiplierMaxExponent is 98 bits.So we expect our HNP to be correct upto 135 bits since (135 + 98=233)We can preprocess our HNP inputs to increase our gains. There are 3 known approaches:(Albrecht & Heninger, 2020) assert that lattice reduction works for both positive and negative integers, so we can shift our Betas from [0,β ] to the range [-β/2,β/2] and this permits us save an entire bit.This idea is called Recentering and was introduced in (Nguyen & Shparlinski, 2002)7.The easiest way to recenter is by subtracting half our maximum beta from our observed c values:Reecntering works wonders. The red annotation shows we can work with a higher multiplier and get even better predictions.Simple recentering increases our prediction accuracy from 0.5 bits to about 8 bits. We correctly predict an entire byte!We can adapt our matrix to handle Betas much smaller than our overall error bound. We do this by normalizing each column in the lattic by MaxError / CustomError (Benger et al., 2014)8.Practically this resembles:Storing each observation’s error bound and rescaling each observation by its specific half-error bound.Rewriting our HNP such that each column is scaled by a constant factorFind the maximum scaling bound and a scaling term (Max Bound / Current Bound)This change provides stability since the lattice vectors are bounded better.(Albrecht & Heninger, 2020) provide the algorithm below to eliminate the secret key from our lattice basis:Eliminating the secret key from our basis :Reduces lattice dimension by 1.Lattice complexity grows exponentially with dimension. Reducing dimension by 1 reduces solving time in large systems by a looot.Our target vector becomes the true shortest vector.The first row (the one that had the error bound) was the actual shortest vector. It had lots of zeros and a single B entry.This first row disappears in our new lattice. So our target becomes the true short vector.where In code, we write a transformation function to obtain the new variables:Then the new lattice needs us decrease m by 1 and replace B/p with 1:We search for the target vector (k₁ - B, k₂ - B, ..., k_{m-1} - B, k₀ - B, w) and recover our secret keyOur secret key is the smallest alpha value so we search for it like this:As expected, our shortest vector is close to our target:These are my personal notes. Don’t quote meWe encountered the complex number identity below when we coded the Gaussian Integers paper. where ω is one of the three possible cube roots of unity modulo p.Note thatthat is, the correct T,V and ω values should equal 0 mod p.We rewrite our identity as a complex HNP of the form:whered - unknown secret key.V(c+dω) - unknown noise term.T - known random multiplier for secret key.cV - known observation.In this form, c changes while d remains constant.We can attempt to keep the noise term constant across equations. How?Next, we write a function that provided T and P, finds V like in the Gaussian integers paper using the known relation:We reformulate it as a quadratic:Thus our V values are:Replacing T and V in the quadratic permits us solve for T given p.Boneh, D., & Venkatesan, R. (1996). Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. In: Koblitz, N. (eds) Advances in Cryptology — CRYPTO ’96. CRYPTO 1996. Lecture Notes in Computer Science, vol 1109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68697-5_11Surin, J., & Cohney, S. (2023). A Gentle Tutorial for Lattice-Based Cryptanalysis. University of Melbourne. Cryptology ePrint Archive. PDF Link.Howell, S,. J,. (1998).

The Index Calculus Algorithm for Discrete Logarithms.

Clemson University Masters Thesis.Zhou, Y., & Feng, D. (2005). Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing. IACR Cryptol. ePrint Arch., 2005, 388. PDF Link.Chao Sun et al. (2021). Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage. In: IACR Transactions on Cryptographic Hardware and Embedded Systems (Nov. 2021),pp. 391–413. url: https://doi.org/10.46586/tches.v2022.i1.391-413.Albrecht, M.R., & Heninger, N. (2020).

On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem. IACR Cryptology ePrint Archive.Nguyen, P., & Shparlinski, I. (2002). The Insecurity of the Digital Signature Algorithm with Partially Known Nonces . J. Cryptology 15, 151–176. https://doi.org/10.1007/s00145-002-0021-3Benger, N., van de Pol, J., Smart, N.P., Yarom, Y. (2014). “Ooh Aah... Just a Little Bit” : A Small Amount of Side Channel Can Go a Long Way. In: Batina, L., Robshaw, M. (eds) Cryptographic Hardware and Embedded Systems – CHES 2014. CHES 2014. Lecture Notes in Computer Science, vol 8731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44709-3_5