[HN Gopher] Lattices vs. Cranks
       ___________________________________________________________________
        
       Lattices vs. Cranks
        
       Author : todsacerdoti
       Score  : 34 points
       Date   : 2024-02-24 23:54 UTC (23 hours ago)
        
 (HTM) web link (keymaterial.net)
 (TXT) w3m dump (keymaterial.net)
        
       | petermcneeley wrote:
       | I think this post is about how it is easy to find "a" if you have
       | the value alpha=frac(sqrt(a)). Someone somewhere on twitter was
       | using this for a crypto idea but no link was provided to the post
       | or documentation.
        
       | o11c wrote:
       | Hm, does this kind of approach also work for the "recover the
       | algebraic expression that generated an approximated float"
       | problem?
        
         | chrispeel wrote:
         | If by "this kind of approach" you mean lattice tools, then I
         | think the answer is yes. See the link below for an example in
         | the Wikipedia page on the LLL. Also the second link may be
         | helpful
         | 
         | https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...
         | 
         | https://eprint.iacr.org/2023/032.pdf
        
       | LegionMammal978 wrote:
       | If I'm thinking of the same 'crank' that the author is, I believe
       | that the main conteibution he claims is a novel way to compute
       | very distant parts of the keystream without having to work
       | through the preceding digits with Newton's method. But this
       | author dismisses it as even slower than Newton's method, and
       | susceptible to brute force in any case. That would be a shame,
       | since I was drawn to the work of this 'crank' a while back in
       | trying to approximate algebraic numbers using sublinear memory.
        
         | SAI_Peregrinus wrote:
         | If you want a CSPRNG where you can get very distant parts of
         | the keystream just use a stream cipher like ChaCha20's
         | keystream or AES-CTR-DRBG. Set the counter to the place in the
         | keystream you desire!
        
       | shoo wrote:
       | Readers who enjoyed lattices vs cranks may also enjoy:
       | 
       | 1/2 Building Lattice Reduction (LLL) Intuition (2017 blog post):
       | https://kel.bz/post/lll/ 2017 HN thread
       | https://news.ycombinator.com/item?id=14847560
       | 
       | 2/2 the cryptopals crypto challenges: https://cryptopals.com/
       | 2014 HN thread https://news.ycombinator.com/item?id=8166064
       | 
       | Cryptopals problem 62 "Key-Recovery Attacks on ECDSA with Biased
       | Nonces" from set 8 "abstract algebra" applies the Lenstra-
       | Lenstra-Lovasz (LLL) algorithm:
       | https://cryptopals.com/sets/8/challenges/62.txt
        
       ___________________________________________________________________
       (page generated 2024-02-25 23:01 UTC)