17 ms·

Dan Bernstein (look him up, you already use a lot of his cryptography) recommends Streamlined NTRU Prime. https://libntruprime.cr.yp.to/ https://libntruprime.c

Dan Bernstein (look him up, you already use a lot of his cryptography) recommends Streamlined NTRU Prime. https://libntruprime.cr.yp.to/ https://libntruprime.cr.yp.to/

tptacek 2y ago
Which other cryptographers agree with him about this?
- alphazard 2y ago
  He has repeatedly collaborated with Tanja Lange who is also credited as working on the original NTRU Prime design. The other collaborators (all respected cryptographers) presumably think the scheme is sound as well. The developers of OpenSSH agree enough to use this scheme in OpenSSH. DJB is high profile enough that all of his stuff gets a lot of cryptanalysis from experts. This isn't a rando proposing a scheme that no one can follow, and no one can be bothered to review. He consistently designs cryptographic systems which perform better and are less error prone to implement than systems designed by committees of people.
  - tptacek 2y ago
    CRYSTALS-Kyber had the same team structure; neither was more "designed by a committee" than the other. Can you articulate what would make Bernstein's team more credible than the Kyber team? I promise you, CRYSTALS-Kyber does not lack for expert analysis. I ask all this because there's a pretty big "Schneier Facts" vibe to anything that involves Bernstein, and because I don't think you'll find many cryptographers --- probably even including on the NTRU Prime team --- that would sign off on his critique of Kyber and the NIST process. I could be wrong, but if I am, could you tell me how?
    - notfed 2y ago
      Also, CRYSTALS-Kyber was a finalist in NIST's PQCrypto competition: https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 https://csrc.nist.gov/Projects/post-quantum-cryptography/sel...
      - tptacek 2y ago
        Well, right, the subtext here is Bernstein's rejection of that result.
        throw0101d 2y ago
        > […] Bernstein's rejection of that result. Some previous discussion on this from 2022 and 2023: * https://news.ycombinator.com/item?id=32360533 https://news.ycombinator.com/item?id=32360533 * https://news.ycombinator.com/item?id=37756656 https://news.ycombinator.com/item?id=37756656
  - throw0101d 2y ago
    > The developers of OpenSSH agree enough to use this scheme in OpenSSH. Or simply because it was the most convenient algorithm at the time (2022). There may also be regulated industries where Officially Approved™ algorithms need to be used, and if you're not on the list you're not going to be enabled, so if the developers of OpenSSH want to protect their users in those situations, then they're going to have to offer something on the list (even if it's not enable by default, or further down the preference ranking in the default settings). * https://ubuntu.com/blog/ubuntu-22-04-fips-140-3-modules-available-for-preview https://ubuntu.com/blog/ubuntu-22-04-fips-140-3-modules-avai... * https://www.stigviewer.com/stig/canonical_ubuntu_22.04_lts/2024-05-30/finding/V-260533 https://www.stigviewer.com/stig/canonical_ubuntu_22.04_lts/2... * https://www.stigviewer.com/stig/red_hat_enterprise_linux_9/2023-09-13/finding/V-257991 https://www.stigviewer.com/stig/red_hat_enterprise_linux_9/2... * https://support.apple.com/en-ca/guide/certifications/apc35eb3dc4fa/web https://support.apple.com/en-ca/guide/certifications/apc35eb...
  - less_less 2y ago
    > DJB is high profile enough that all of his stuff gets a lot of cryptanalysis from experts. This isn't a rando proposing a scheme that no one can follow, and no one can be bothered to review. He consistently designs cryptographic systems which perform better and are less error prone to implement than systems designed by committees of people. So in my opinion, NTRU Prime is a good cryptosystem. But it's not particularly better than Kyber: each has small advantages and disadvantages, and both got a ton of expert review (Kyber even more than NTRU Prime), and they will probably stand or fall together depending on improvements in lattice cryptanalysis. I also don't think Kyber suffers from design-by-committee. There are a zillion small choices to make in these lattice schemes, and while some choices are definitely wrong, both the NTRU Prime and Kyber teams made reasonable ones. The same goes for SABER and regular NTRU.
  - dadrian 2y ago
    DJB and Tanya operate as a unit. Saying Lange agrees with DJB is like citing Clark as support of Lewis.
notfed 2y ago
Not too surprising as he is the author (giggle emoji) But really, there are very few "trustworthy" PQCrypto algorithms/implementations and he is the author of more than one of those.
ilove196884 2y ago
I wonder what he thinks about FALCON considering it's a rival to his submission based on NTRU but is on path to standardization but NTRUPrime isn't.
- less_less 2y ago
  DJB's signature proposal is SPHINCS+, which is standardized in FIPS 205 as SLH-DSA. NTRUPrime is a KEM, so it doesn't really compete with FALCON. Personally I think that FALCON is brilliant, but it is very difficult to securely implement or even precisely define, due to heavy use of floating-point arithmetic in the signing routine. I don't want to put words in DJB's mouth, but if you share his concern for ease of secure implementation, ease of auditing and side-channel protection, then you may prefer SPHINCS+ or, if the performance of SPHINCS+ is not acceptable in your workload, possibly Dilithium. Of course, if signature size is make-or-break, then of the choices currently slated for standardization, FALCON has the smallest signatures. But it is possible that the new signature onramp will change that in a few years -- if you can be confident in the security of whatever is chosen within so short a time.
deknos 2y ago
I think this is also in https://libpqcrypto.org/ https://libpqcrypto.org/ which has much more cryptographic primitives :) and has also the stuff from nist.
jonathanstrange 2y ago
I find this particular NIST process confusing. ML-KEM 1024 for key encapsulation is FIPS 203 certified, so I take it that it is the right choice for key encapsulation? But there are FIPS 204 and 205 standards for digital signatures, apparently soon to be complemented by FIPS 206 based on FALCON. Which one should be used? Has NIST stopped to recommend one winner and opted for several. Or, do these have different purposes?
- less_less 2y ago
  SLH-DSA aka SPHINCS+ is the most conservative choice (i.e. they are all secure against currently-known attacks, but SLH-DSA is less likely to be broken later), but it is slow (at least several milliseconds to sign) and produces large sigs (>= 7.8kB). This means that it may not be suitable for all applications. Dilithium is faster but less conservative, harder to implement securely, and produces medium sigs. FALCON is even harder to implement securely, faster to verify and produces smaller sigs, though still much larger than classical systems. IMHO this choice was questionable, in that its advantages overlap too heavily with Dilithium to be worth another standard, but NIST apparently felt otherwise.
  - jonathanstrange 2y ago
    Thank you! That clarifies it. The length of the signatures indeed seems to be a problem. I'm currently investigating ways to implement secure group chat (like adapting MLS to use PQC).

Dan Bernstein (look him up, you already use a lot of his cryptography) recommends Streamlined NTRU Prime. https://libntruprime.cr.yp.to/ https://libntruprime.cr.yp.to/

tptacek 2y ago

Which other cryptographers agree with him about this?

alphazard 2y ago
He has repeatedly collaborated with Tanja Lange who is also credited as working on the original NTRU Prime design. The other collaborators (all respected cryptographers) presumably think the scheme is sound as well. The developers of OpenSSH agree enough to use this scheme in OpenSSH. DJB is high profile enough that all of his stuff gets a lot of cryptanalysis from experts. This isn't a rando proposing a scheme that no one can follow, and no one can be bothered to review. He consistently designs cryptographic systems which perform better and are less error prone to implement than systems designed by committees of people.
- tptacek 2y ago
  CRYSTALS-Kyber had the same team structure; neither was more "designed by a committee" than the other. Can you articulate what would make Bernstein's team more credible than the Kyber team? I promise you, CRYSTALS-Kyber does not lack for expert analysis. I ask all this because there's a pretty big "Schneier Facts" vibe to anything that involves Bernstein, and because I don't think you'll find many cryptographers --- probably even including on the NTRU Prime team --- that would sign off on his critique of Kyber and the NIST process. I could be wrong, but if I am, could you tell me how?
  - notfed 2y ago
    Also, CRYSTALS-Kyber was a finalist in NIST's PQCrypto competition: https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 https://csrc.nist.gov/Projects/post-quantum-cryptography/sel...
    - tptacek 2y ago
      Well, right, the subtext here is Bernstein's rejection of that result.
      - throw0101d 2y ago
        > […] Bernstein's rejection of that result. Some previous discussion on this from 2022 and 2023: * https://news.ycombinator.com/item?id=32360533 https://news.ycombinator.com/item?id=32360533 * https://news.ycombinator.com/item?id=37756656 https://news.ycombinator.com/item?id=37756656
- throw0101d 2y ago
  > The developers of OpenSSH agree enough to use this scheme in OpenSSH. Or simply because it was the most convenient algorithm at the time (2022). There may also be regulated industries where Officially Approved™ algorithms need to be used, and if you're not on the list you're not going to be enabled, so if the developers of OpenSSH want to protect their users in those situations, then they're going to have to offer something on the list (even if it's not enable by default, or further down the preference ranking in the default settings). * https://ubuntu.com/blog/ubuntu-22-04-fips-140-3-modules-available-for-preview https://ubuntu.com/blog/ubuntu-22-04-fips-140-3-modules-avai... * https://www.stigviewer.com/stig/canonical_ubuntu_22.04_lts/2024-05-30/finding/V-260533 https://www.stigviewer.com/stig/canonical_ubuntu_22.04_lts/2... * https://www.stigviewer.com/stig/red_hat_enterprise_linux_9/2023-09-13/finding/V-257991 https://www.stigviewer.com/stig/red_hat_enterprise_linux_9/2... * https://support.apple.com/en-ca/guide/certifications/apc35eb3dc4fa/web https://support.apple.com/en-ca/guide/certifications/apc35eb...
- less_less 2y ago
  > DJB is high profile enough that all of his stuff gets a lot of cryptanalysis from experts. This isn't a rando proposing a scheme that no one can follow, and no one can be bothered to review. He consistently designs cryptographic systems which perform better and are less error prone to implement than systems designed by committees of people. So in my opinion, NTRU Prime is a good cryptosystem. But it's not particularly better than Kyber: each has small advantages and disadvantages, and both got a ton of expert review (Kyber even more than NTRU Prime), and they will probably stand or fall together depending on improvements in lattice cryptanalysis. I also don't think Kyber suffers from design-by-committee. There are a zillion small choices to make in these lattice schemes, and while some choices are definitely wrong, both the NTRU Prime and Kyber teams made reasonable ones. The same goes for SABER and regular NTRU.
- dadrian 2y ago
  DJB and Tanya operate as a unit. Saying Lange agrees with DJB is like citing Clark as support of Lewis.

notfed 2y ago

Not too surprising as he is the author (giggle emoji) But really, there are very few "trustworthy" PQCrypto algorithms/implementations and he is the author of more than one of those.

ilove196884 2y ago

I wonder what he thinks about FALCON considering it's a rival to his submission based on NTRU but is on path to standardization but NTRUPrime isn't.

less_less 2y ago
DJB's signature proposal is SPHINCS+, which is standardized in FIPS 205 as SLH-DSA. NTRUPrime is a KEM, so it doesn't really compete with FALCON. Personally I think that FALCON is brilliant, but it is very difficult to securely implement or even precisely define, due to heavy use of floating-point arithmetic in the signing routine. I don't want to put words in DJB's mouth, but if you share his concern for ease of secure implementation, ease of auditing and side-channel protection, then you may prefer SPHINCS+ or, if the performance of SPHINCS+ is not acceptable in your workload, possibly Dilithium. Of course, if signature size is make-or-break, then of the choices currently slated for standardization, FALCON has the smallest signatures. But it is possible that the new signature onramp will change that in a few years -- if you can be confident in the security of whatever is chosen within so short a time.

deknos 2y ago

I think this is also in https://libpqcrypto.org/ https://libpqcrypto.org/ which has much more cryptographic primitives :) and has also the stuff from nist.

jonathanstrange 2y ago

I find this particular NIST process confusing. ML-KEM 1024 for key encapsulation is FIPS 203 certified, so I take it that it is the right choice for key encapsulation? But there are FIPS 204 and 205 standards for digital signatures, apparently soon to be complemented by FIPS 206 based on FALCON. Which one should be used? Has NIST stopped to recommend one winner and opted for several. Or, do these have different purposes?

less_less 2y ago
SLH-DSA aka SPHINCS+ is the most conservative choice (i.e. they are all secure against currently-known attacks, but SLH-DSA is less likely to be broken later), but it is slow (at least several milliseconds to sign) and produces large sigs (>= 7.8kB). This means that it may not be suitable for all applications. Dilithium is faster but less conservative, harder to implement securely, and produces medium sigs. FALCON is even harder to implement securely, faster to verify and produces smaller sigs, though still much larger than classical systems. IMHO this choice was questionable, in that its advantages overlap too heavily with Dilithium to be worth another standard, but NIST apparently felt otherwise.
- jonathanstrange 2y ago
  Thank you! That clarifies it. The length of the signatures indeed seems to be a problem. I'm currently investigating ways to implement secure group chat (like adapting MLS to use PQC).