[Pqc] Re: [EXT] Re: [saag] Re: Re: [SAAG] A New Theory on Post-quantum Migration

Thanks for the literature info.

>Those "specific algorithms" are based on the discussed and studied mathematical problems. E.g., Kyber and Dilithium are cases of Lattice-based crypto, which, as I pointed out above, has been studied since 1996 at least.

Yes, cryto algorithms are based on or related to hard problems. However, they are still not the same. Otherwise, one may claim that RSA has been studied for nearly 400 years, as Fermat's little theorem was stated by Pierre de Fermat in 1640. https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Or even longer, if tracing back to the history of integer factorization.

>They have their professional opinion, I have mine.

Yes, true. I respect.

>I also described in details (and more than once) the logic of why hybrids are not helpful, if your data needs to outlast CRQC. (And if the lifetime of protection for your data is short enough - no point bothering with PQ at all.)

Half true, in my opinion. The real.question is: how 'short' do you mean?

The life time of users' data could be a few minutes, a few days, a few months, a few years, more than 10 years, several decades, and even longer. Also, we do not know when CRQCs will come. In these cases, how do you suggest customers?

As my presentation slides explains, compared to pure PQ migration, the hybrid solution may further reduce risks.

Guilin

发件人：Blumenthal, Uri - 0553 - MITLL <[email protected]<mailto:[email protected]>>
收件人：Wang Guilin <[email protected]<mailto:[email protected]>>;SIDDESH PAWAR <[email protected]<mailto:[email protected]>>;[email protected] <[email protected]<mailto:[email protected]>>;[email protected] <[email protected]<mailto:[email protected]>>
时 间：2025-11-05 21:39:35
主 题：Re: [Pqc] Re: [EXT] Re: [saag] Re: Re: [SAAG] A New Theory on Post-quantum Migration




In my understanding, that planning is a mistake – a combination of overestimating the risk of Lattice-based crypto failure (has been studied for about 30 years, compared to about 50 years of ECC crypto studies), and underestimating the likelihood/speed of CRQC arrival.



30 years of studying Lattice-based crypto failure? Not sure which the first literature is in this area, in your viewpoint.  As I know, the concept of LWE is proposed in [1], in 2005. Up to now, 20 years.

Literature search points at Miklós Ajtai<https://en.wikipedia.org/wiki/Mikl%C3%B3s_Ajtai>, 1996: https://dl.acm.org/doi/10.1145/237814.237838 (my former colleague, BTW 😉 - IBM Research, Almaden/San Jose). Security proofs - same year (Cynthia Dwork:https://eccc.weizmann.ac.il/report/1996/065/ - correction of https://eccc.weizmann.ac.il/report/1996/065/download).

Check Wiki https://en.wikipedia.org/wiki/Lattice-based_cryptography:

In 1996,Miklós Ajtai<https://en.wikipedia.org/wiki/Mikl%C3%B3s_Ajtai> introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems,[3]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-:1-3> andCynthia Dwork<https://en.wikipedia.org/wiki/Cynthia_Dwork> showed that a certain average-case lattice problem, known as short integer solutions<https://en.wikipedia.org/wiki/Short_integer_solution_problem> (SIS), is at least as hard to solve as a worst-case<https://en.wikipedia.org/wiki/Worst-case_complexity> lattice problem.[4]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-4> She then showed a cryptographic hash function<https://en.wikipedia.org/wiki/Cryptographic_hash_function> whose security is equivalent to the computational hardness of SIS.

In 1998,Jeffrey Hoffstein<https://en.wikipedia.org/wiki/Jeffrey_Hoffstein>, Jill Pipher<https://en.wikipedia.org/wiki/Jill_Pipher>, and Joseph H. Silverman<https://en.wikipedia.org/wiki/Joseph_H._Silverman> introduced a lattice-based public-key encryption<https://en.wikipedia.org/wiki/Public-key_cryptography> scheme, known as NTRU<https://en.wikipedia.org/wiki/NTRUEncrypt>.[5]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-5> However, their scheme is not known to be at least as hard as solving a worst-case lattice problem.

The first lattice-based public-key encryption schemewhose security was proven under worst-case hardness assumptions was introduced byOded Regev<https://en.wikipedia.org/wiki/Oded_Regev_(computer_scientist)> in 2005,[6]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-:2-6> together with the learning with errors<https://en.wikipedia.org/wiki/Learning_with_errors> problem (LWE). Since then, much follow-up work has focused on improving Regev's security proof[7]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-:3-7>[8]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-8> and improving the efficiency of the original scheme.[9]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-:4-9>[10]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-:0-10>[11]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-11>[12]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-12> Much more work has been devoted to constructing additional cryptographic primitives based on LWE and related problems. For example, in 2009,Craig Gentry<https://en.wikipedia.org/wiki/Craig_Gentry_(computer_scientist)> introduced the first fully homomorphic encryption<https://en.wikipedia.org/wiki/Homomorphic_encryption> scheme, which was based on a lattice problem.[13]<https://en.wikipedia.org/wiki/Lattice-based_cryptography#cite_note-:5-13>

"The" NTRU above was submitted to the NIST PQC and lost to Kyber (several reasons).

Also, in this thread, it seems more relevant to just discuss specific algorithms, rather than the history of an area or a sub-area. In this case, please note that both Dilithium and Kyber were published in 2017 [2, 3].

Those "specific algorithms" are based on the discussed and studied mathematical problems. E.g., Kyber and Dilithium are cases of Lattice-based crypto, which, as I pointed out above, has been studied since 1996 at least.


PS, as a bonus, notice that the design team of Dilithium give the following message on the home page of Dilithium athttps://pq-crystals.org/dilithium/:


" For users who are interested in using Dilithium, we recommend the following:

  *   Use Dilithium in a so-calledhybrid mode in combination with an established "pre-quantum" signature scheme. "

They have their professional opinion, I have mine. I also described in details (and more than once) the logic of why hybrids are not helpful, if your data needs to outlast CRQC. (And if the lifetime of protection for your data is short enough - no point bothering with PQ at all.)


[1] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. ACM Press, May 2005
[2] CRYSTALS -- Dilithium: Digital Signatures from Module Lattices.https://eprint.iacr.org/2017/633; IACR TCHES, 2018(1):238–268
[3] CRYSTALS -- Kyber: a CCA-secure module-lattice-based KEM.https://eprint.iacr.org/2017/634; EuroS&P 2018: 353-367

Guilin

________________________________
From: Blumenthal, Uri - 0553 - MITLL <[email protected]<mailto:[email protected]>>
Sent: Wednesday, November 5, 2025 11:52 PM
To: SIDDESH PAWAR; [email protected]<mailto:[email protected]>; [email protected]<mailto:[email protected]>
Subject: [Pqc] Re: [EXT] Re: [saag] Re: Re: [SAAG] A New Theory on Post-quantum Migration

ZjQcmQRYFpfptBannerEnd

My take,

If ECC is anyhow prone to Quantum attack and also the part of implementation is old and received by the attackers, then why are we planning traditional crypt+ pqc (NIST approved).



In my understanding, that planning is a mistake – a combination of overestimating the risk of Lattice-based crypto failure (has been studied for about 30 years, compared to about 50 years of ECC crypto studies), and underestimating the likelihood/speed of CRQC arrival.



Their hope basically is that the protected data will lose all valuebefore CRQC arrives, and maybe the QC part will hold.



Instead we should focus on rapid migration techniques for the infra collaborating with big players like DigiCert, checkpoint, hp, for the pure pqc migration.

Design and Evaluation of StrongVPN, a Pure Post-Quantum VPN Architecture<https://www.techrxiv.org/users/978467/articles/1345362-design-and-evaluation-of-strongvpn-a-pure-post-quantum-vpn-architecture>



IMHO, that is correct.



https://www.techrxiv.org/users/978467/articles/1345362-design-and-evaluation-of-strongvpn-a-pure-post-quantum-vpn-architecture

I totally understand that the proven technology is more convincing to the industry then the future evolution.
Even if we are considering the migration techniques, do we have any plan under discussion so far.

I’ll also add that Lattice-based crypto (Kyber, NTRU) has formal proofs, while ECC crypto does not.😉




________________________________

From: Blumenthal, Uri - 0553 - MITLL <[email protected]<mailto:[email protected]>>
Sent: 04 November 2025 19:54
To: [email protected]<mailto:[email protected]> <[email protected]<mailto:[email protected]>>; [email protected]<mailto:[email protected]> <[email protected]<mailto:[email protected]>>
Subject: [Pqc] Re: [EXT] Re: [saag] Re: Re: [SAAG] A New Theory on Post-quantum Migration

My take.



Does this mean ECC+PQ can be declared insecure on the basis of, e.g.,
declaring that small code size is a "security property" and that ECC+PQ
is more code than just PQ? The only good cipher is the null cipher?



Yes, it can. An extra attack surface is an extra attack surface.

Here's an example. There's a problem right now of attackers recording
data to decrypt with future quantum computers.



In that case, ECC part is irrelevant – helpingat best only until CRQC.



There are protocols such
as TLS responding to this by rolling out ECC+PQ concatenation:

  * Maybe the PQ part holds up. If so, big step forward!
  * Maybe the PQ part ends up as another disaster. If so, at least
     ECC+PQ isn't worse than current normal usage of ECC.



If the data sensitivity persists through the appearance of CRQC – which is the main purpose of the governments driving PQC rollout – then ECC+PQ is exactly as secure as PQ alone, not counting for implementation bugs that could make it worse.

Skipping the ECC part would fail horribly on the second point.



Not at all. It might only help for “short-lived” data. If that’s all you care for – then ECC+PQ (or ECC alone) would work fine for you. Otherwise – it’s a waste of time and resources to even argue about it.

-- 
Pqc mailing list -- [email protected]
To unsubscribe send an email to [email protected]