5 ms·
Lattices vs. Cranks
- petermcneeley 3y agoI 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 3y agoHm, does this kind of approach also work for the "recover the algebraic expression that generated an approximated float" problem?
- chrispeel 3y agoIf 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%93Lov%C3%A1sz_lattice_basis_reduction_algorithm#Applications https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%... https://eprint.iacr.org/2023/032.pdf https://eprint.iacr.org/2023/032.pdf
- LegionMammal978 3y agoIf 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 3y agoIf 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!
- LegionMammal978 3y agoOf course, the 'crank' here is looking for a cipher with an easy-to-understand keystream; but my own goal was always to efficiently compute the digits of numbers for their particular algebraic properties, to an arbitrary distance. Though it looks like there really might not be any alternative to Newton's method (or similar) for many of them.
- shoo 3y agoReaders who enjoyed lattices vs cranks may also enjoy: 1/2 Building Lattice Reduction (LLL) Intuition (2017 blog post): https://kel.bz/post/lll/ https://kel.bz/post/lll/ 2017 HN thread https://news.ycombinator.com/item?id=14847560 https://news.ycombinator.com/item?id=14847560 2/2 the cryptopals crypto challenges: https://cryptopals.com/ https://cryptopals.com/ 2014 HN thread https://news.ycombinator.com/item?id=8166064 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–Lovász (LLL) algorithm: https://cryptopals.com/sets/8/challenges/62.txt https://cryptopals.com/sets/8/challenges/62.txt
- daedalus2027 3y agoAlso https://github.com/daedalus/BreakingECDSAwithLLL https://github.com/daedalus/BreakingECDSAwithLLL