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

jQcmQRYFpfptBannerEnd 

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


You mean the lower-bound proofs on (iirc) unstructured lattices? 

Let me hide my ignorance and the lack of NI behind AI 😊. But basically – no, not only unstructured (and “conditional”, not “unconditional lower bounds”): 


1. What the proofs say 


* Scheme security reduction. Kyber’s IND-CCA KEM security is proven via a sequence of games to the hardness of Module-LWE/Module-SIS in the (quantum) random-oracle model. This means: a Kyber break ⇒ MLWE/MSIS solver. It does not prove a runtime lower bound; it ties security to assumptions believed hard. 

cryptojedi.org+1 <_blank> 


* Hardness of the assumptions. 

i. LWE: Regev showed (quantum) worst-case→average-case: solving average-case LWE would let you solve worst-case GapSVP/SIVP on arbitrary lattices. Later work gave classical reductions for LWE under modulus/dimension trade-offs. 
NYU Courant+1 <_blank> 
ii. Ring-/Module-LWE: Analogous reductions exist, but now the worst-case problems live on ideal/module lattices (structured objects). These reductions are typically quantum; getting fully classical, equally strong reductions remains a major open problem. 
NYU Courant+2EECS Department+2 <_blank> 

1. Unstructured vs. structured 


* Unstructured: Standard LWE’s reductions target arbitrary lattices. Good for “minimal assumptions,” but raw LWE is less efficient. 

NYU Courant <_blank> 


* Structured (ideal/module): Ring-/Module-LWE bring speed and compactness (used in practice), with reductions to worst-case problems restricted to ideal/module lattices. Security therefore relies on the hardness of these structured worst-case problems—not the full class of arbitrary lattices. (Module-LWE interpolates between ring and standard LWE as the module rank grows.) 

NYU Courant+1 <_blank> 

1. What we don’t have 


* No unconditional lower bounds (e.g., “any attack needs 2^Ω(n) time”). Instead, parameter choices blend these reductions with concrete attack cost models (BKZ/sieving, etc.). The reductions themselves don’t give such lower bounds. 

ENS Di <_blank> 

1. Kyber specifically 


* Kyber (ML-KEM) bases its CCA security on Module-LWE/Module-SIS over a polynomial ring; parameter sets correspond to different security levels. The proof is reductionist; the underlying hardness evidence comes from the (structured) worst-case→average-case theory for Ring/Module-LWE. 


Either one of us could dig deeper, pull the references 





On Wed, Nov 5, 2025, 10:55 AM Blumenthal, Uri - 0553 - MITLL <[email protected] <mailto:[email protected]>> wrote: 

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 value before 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 <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 – helping at 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] <mailto:[email protected]>
To unsubscribe send an email to [email protected] <mailto:[email protected]>

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