Re:Enough Polynomials and Linear Algebra to Implement Kyber
by dotancohen on Tuesday November 07, 2023 @08:12PM
(#38185477)
> Note that the inner product of the Barrett reduction is 37 bits, so you need a uint64 intermediate value. Ask me how I know!
Without even addressing the excellent content of this article, the expression "ask me how I know" is a sign of someone with experience in a field, any field. Sort of a shibboleth for intimacy with the subject matter. This man has fought a battle and felt pain.
Re:Enough Polynomials and Linear Algebra to Implement Kyber
by loxias on Tuesday November 07, 2023 @11:35PM
(#38186843)
Amen to that! This matches my lived experience. Every time I share a surprising or specific technical detail like that, inside I'm hoping, begging, someone will ask me how I know, so I can recall and share the tale of the months of my time, and, honestly, my cleverness expended to win that knowledge.
(Also I don't know why you're downvoted?)
Anyway, great article. I didn't know division wasn't constant time, but ew, division, old busted. cool cats multiply by a constant and shift. :)
Re:Enough Polynomials and Linear Algebra to Implement Kyber
by coppsilgold on Wednesday November 08, 2023 @12:17AM
(#38187075)
SPHINCS+ is an elaborate scheme building up on very simple blocks. It's all down to cryptographic hashes, there is no other security assumption involved.
There is a good talk given out by a NIST guy that starts from the simplest one time hash signature construction and builds up to XMSS/SPHINCS: <https://www.youtube.com/watch?v=jiU0ICoiPI0>
TLDR; SPHINCS+ is a hypertree of Merkle trees where leafs of Merkle trees are used to sign Merkle roots of other Merkle trees. Leafs of the hypertree (final layer of Merkle trees) are used to sign messages. Paths through the hypertree need only be constructed on demand through the use of a PRF - paths through the hypertree consist of entire merkle trees. This means the secret key is just a seed to a CSPRNG. A hypertree is required because Merkle roots are parts of the public key and public signature and can only be determined through computation, if the Merkle tree is too big you will never compute any root.
Re:Enough Polynomials and Linear Algebra to Implement Kyber
by loxias on Wednesday November 08, 2023 @03:09AM
(#38187870)
> SPHINCS+ is a hypertree of Merkle trees where leafs of Merkle trees are used to sign Merkle roots of other Merkle trees. Leafs of the hypertree (final layer of Merkle trees) are used to sign messages.
> Paths through the hypertree need only be constructed on demand through the use of a PRF - computing paths through the hypertree requires computing entire Merkle trees. The private key is just a secret key to a PRF.
Wow, thank you so much. Such a perfect match between exactly what I didn't know described in terms I do. "Cool. Now I could write a high performant SPHINCS+ c++ impl, if i ever wanted to or thought it was cool" :D
Edit: I love it when stuff like that happens, it's the reason I still bother to read the comments on this website.
I/we've all got our own unique decades of experience and collection of earned wisdom, and sometimes substantial technological progress happens when the right people get the right "holes in understanding" filled at the right time.
Re:Enough Polynomials and Linear Algebra to Implement Kyber
by rjeli on Wednesday November 08, 2023 @03:20AM
(#38187929)
Not sure why the NTT is treated as a completely opaque transform. It’s simply the algebraic equivalent of the Fourier transform (and it’s implemented with almost exactly the same algorithms). So you are transforming between the polynomial coefficients and its evaluations on a domain.
(Also I don't know why you're downvoted?)
Anyway, great article. I didn't know division wasn't constant time, but ew, division, old busted. cool cats multiply by a constant and shift. :)
There is a good talk given out by a NIST guy that starts from the simplest one time hash signature construction and builds up to XMSS/SPHINCS: <https://www.youtube.com/watch?v=jiU0ICoiPI0>
TLDR; SPHINCS+ is a hypertree of Merkle trees where leafs of Merkle trees are used to sign Merkle roots of other Merkle trees. Leafs of the hypertree (final layer of Merkle trees) are used to sign messages. Paths through the hypertree need only be constructed on demand through the use of a PRF - paths through the hypertree consist of entire merkle trees. This means the secret key is just a seed to a CSPRNG. A hypertree is required because Merkle roots are parts of the public key and public signature and can only be determined through computation, if the Merkle tree is too big you will never compute any root.
> Paths through the hypertree need only be constructed on demand through the use of a PRF - computing paths through the hypertree requires computing entire Merkle trees. The private key is just a secret key to a PRF.
Wow, thank you so much. Such a perfect match between exactly what I didn't know described in terms I do. "Cool. Now I could write a high performant SPHINCS+ c++ impl, if i ever wanted to or thought it was cool" :D
Edit: I love it when stuff like that happens, it's the reason I still bother to read the comments on this website.
I/we've all got our own unique decades of experience and collection of earned wisdom, and sometimes substantial technological progress happens when the right people get the right "holes in understanding" filled at the right time.