[Pqc] Re: [EXTERNAL] Re: Review of PQC for Engineers

["Hale, Britta (CIV)" <[e-mail]>]

I think it may help to have some clarity in the WG about the layers of construction of these schemes so as to categorize pieces accordingly.

Lattice-based, coding-based, hash-based, etc. are references that point to the types of hardness of assumptions an algorithm is built on (e.g., lattice-based hardness assumptions, hardness of decoding a random linear code, the one-way properties of hashes, etc.). These categories point explicitly to the types of assumptions needed for security of a scheme.

In contrast, a "ZK-hardness assumption" is not a thing. ZKPs are middle steps or general-purpose algorithms only, or could be considered a construction strategy for a scheme. They do not tell us about the underlying hardness of it though (up to the point where we might deduce the actual assumptions used to create the ZKP). This is because ZKPs are themselves based on classes of hardness assumptions, such as the hardness of deciding quadratic residues modulo a composite, hardness of DLP, etc. (Unsurprisingly, these types of hardness assumptions show up in other things, Diffie-Hellmann being an example of a DLP-based scheme.) PICNIC had a ZKP which was based on the hardness of one-way functions, which is the actual way it should be categorized. If it had instead used a ZKP that was based on e.g., DLP, then it would not have even begun to be considered for PQ-resistance. In this is it easy to see how ZKP provides the construction strategy but is not the underlying hardness problem on which security is based.

Ergo, general-purpose ZKP or ZKPs as a construction step to signatures is a moot distinction when it comes to saying that a scheme is "based" on a type of hardness approach. Schemes are based on hardness assumptions or classes thereof, and ZKP is simply not one. Thus we have some confusion/mixing in this threat regarding classifications as well as decision points: namely whether to classify using the categories of "PQ, traditional, fancy", where 'fancy' is a fun name for new approaches using either quantum-resistant or non-quantum resistant hardness assumptions, or to classify by hardness category-based approaches.

It sounds like everyone is generally trending towards not including ZKP as this time, so I am adding this note as a more forward-looking reference. Understanding how ZKP sits with respect to core cryptographic hardness assumptions is important when it comes to how engineers may interpret this (or a future) document. If someone does not understand that ZKP is not the basis for hardness of an algorithm but rather a construction strategy, and instead reads it to be 'fancy'/futuristic crypto, there is risk of them interpreting it as a post-quantum approach when it really could be using a PQ or non-PQ hardness basis. We should not underestimate the potential for drafts to be misinterpreted, and it is worth being very explicit about such things if including them and avoid wording that can be misleading.

Britta


On 7/26/24, 6:33 AM, "Sofia Celi" <[e-mail] <mailto:[e-mail]>> wrote:


NPS WARNING: *external sender* verify before acting.




Hi, all,


Not speaking as a chair.


I agree with Thom. The post-quantum schemes currently in standarization
by NIST do not include standarizing general-purpose ZKP or complex ZKP;
but many signature algorithms are based on the same ideas as building a
ZKP, and, as Thom notes, some of the PQC ones proposed are internally
based on self-knowledge proofs. For the time being, I agree that it is
best to keep out general ZKP from the document.


However, general ZKP does seem of interest to some protocols of the
IETF. The one that comes immediately to my mind is Privacy Pass, as the
internal VOPRF does use a ZKP. There has been some advancements on how
to build general-ZKP from lattices and others, but for the time being,
research is still busy on this front.


Thank you,


On 25/07/2024 21:08, Thom Wiggers wrote:
> Hi all,
>
> I think that Mike, through Picnic, wanted to mention general purpose
> signature schemes that are *internally* based on zero-knowledge proofs.
> Picnic was broken, but in the NIST call for additional post-quantum
> signature schemes there are many proposals based on MPC-in-the-head and
> other “fancy crypto” constructions internally.
>
> In very real ways, any signature scheme can of course be viewed as a
> zero-knowledge proof of knowledge of the private key. Dilithium is also
> based on the Fiat-Shamir construction, which also transforms a proof of
> knowledge to digital signature scheme.
>
> So while I agree that ZKPs and other “fancy crypto" probably don’t have
> a place in this engineering-focused document, we shouldn’t confuse
> general-purpose ZKP with these ways of constructing signature schemes.
> Now, whether these “inside the black box" details are relevant to the
> document is a separate question, but the same argument can be applied to
> describing lattice details.
>
> Cheers,
>
> Thom
>
>> Op 25 jul 2024, om 21:59 heeft Tim Hollebeek
>> <tim.hollebeek=[e-mail] <mailto:[e-mail]>> het volgende geschreven:
>>
>> I would leave out ZKP entirely. It’s a fun topic (one of my
>> favorites), but IMO totally unnecessary and distracting when trying to
>> get up to speed on basic PQC issues.
>> We do have to watch for scope creep, and I think trying to keep it
>> somewhere near the current scope is smart, or we won’t be done for a
>> few more years.
>> In particular, I also think trying to agree on definitions for terms
>> the industry has struggled to define for years is probably a non-goal
>> from my point of view.
>> Remember, we need to publish RFCs, not just start them and work on them!
>> -Tim
>> *From:*Mike Ounsworth <[e-mail] <mailto:[e-mail]>>
>> *Sent:*Wednesday, July 24, 2024 4:27 PM
>> *To:*Deirdre Connolly <[e-mail] <mailto:[e-mail]>>; Mike Ounsworth
>> <Mike.Ounsworth=[e-mail] <mailto:[e-mail]>>
>> *Cc:*[e-mail] <mailto:[e-mail]>; tirumal reddy <[e-mail] <mailto:[e-mail]>>; Aritra Banerjee
>> (Nokia) <[e-mail] <mailto:[e-mail]>>; Tim Hollebeek
>> <[e-mail] <mailto:[e-mail]>>
>> *Subject:*RE: [EXTERNAL] [Pqc] Re: Review of PQC for Engineers
>> Fair enough to not mention Picnic.
>>
>> Do you feel that the whole category of ZKP should or should not be
>> mentioned? Is there another example to cite, or just have the
>> descriptive text with no example?
>> ---
>> *Mike*Ounsworth
>> *From:*Deirdre Connolly <[e-mail] <mailto:[e-mail]>
>> <mailto:[e-mail] <mailto:[e-mail]>>>
>> *Sent:*Wednesday, July 24, 2024 6:17 PM
>> *To:*Mike Ounsworth <Mike.Ounsworth=[e-mail] <mailto:[e-mail]>
>> <mailto:Mike.Ounsworth=[e-mail] <mailto:[e-mail]>>>
>> *Cc:*[e-mail] <mailto:[e-mail]> <mailto:[e-mail] <mailto:[e-mail]>>; tirumal reddy
>> <[e-mail] <mailto:[e-mail]> <mailto:[e-mail] <mailto:[e-mail]>>>; Aritra Banerjee
>> (Nokia) <[e-mail] <mailto:[e-mail]>
>> <mailto:[e-mail] <mailto:[e-mail]>>>; Tim Hollebeek
>> <[e-mail] <mailto:[e-mail]> <mailto:[e-mail] <mailto:[e-mail]>>>
>> *Subject:*[EXTERNAL] [Pqc] Re: Review of PQC for Engineers
>> Suggested the mention be removed on GitHub On Wed, Jul 24, 2024 at 4:
>> 15 PM Deirdre Connolly <durumcrustulum@ gmail. com> wrote: > I added
>> a section, under the types of cryptography, about “symmetric-based
>> public key cryptography” so that
>> Suggested the mention be removed onGitHub
>> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/pull/50/files <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/pull/50/files>*r1690570148__%3BIw!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQGKiZdR_g%24&data=05%7C02%7Cbritta.hale%40nps.edu%7C25840bd000f3498e34cf08dcad779416%7C6d936231a51740ea9199f7578963378e%7C0%7C0%7C638575976334038860%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=ilZS36AS%2Bb%2FwMoy40HjVJsiGLu9VdSyMkIDRwvcv9os%3D&reserved=0>
>> On Wed, Jul 24, 2024 at 4:15 PM Deirdre Connolly
>> <[e-mail] <mailto:[e-mail]> <mailto:[e-mail] <mailto:[e-mail]>>> wrote:
>>
>> > I added a section, under the types of cryptography, about
>> “symmetric-based public key cryptography” so that we at least
>> mention zero-knowledge cryptography and the PICNIC NIST candidate.
>>
>> Picnic wasbroken
>> <https://urldefense.com/v3/__https:/groups.google.com/a/list.nist.gov/g/pqc-forum/c/r7DvnGGSp5s/m/lhlpV3BKBAAJ__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQHLLWru0Q$>via <https://urldefense.com/v3/__https:/groups.google.com/a/list.nist.gov/g/pqc-forum/c/r7DvnGGSp5s/m/lhlpV3BKBAAJ__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQHLLWru0Q$> an attack on its block cipher LowMC. It isno longer a NIST candidate <https://urldefense.com/v3/__https:/csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQGWnfjDZw$> <https://urldefense.com/v3/__https:/csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQGWnfjDZw$;>.
>> On Tue, Jul 23, 2024 at 9:41 PM Mike Ounsworth
>> <Mike.Ounsworth=[e-mail] <mailto:[e-mail]>
>> <mailto:[e-mail] <mailto:[e-mail]>>> wrote:
>>
>> I think this document is great. Ready for WGLC.
>> Procedural question: this document refers to a whole ton of
>> internet drafts. How is that gonna work when it hits RFC Editor?
>> I’ve made a BUNCH of comments; it got enough that I decided to
>> just do a pull request:
>> https://github.com/tireddy2/pqc-for-engineers/pull/50 <https://github.com/tireddy2/pqc-for-engineers/pull/50>
>> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/pull/50__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQE-b4KHJw$> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/pull/50__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQE-b4KHJw$;>
>> I’ll note here the ones that I think the WG would care about.
>> Introduction
>> I would like to propose definitions for “quantum resistant”
>> and “quantum ready”.
>> A “quantum ready” system is one that is capable of interacting
>> with peers using post-quantum cryptographic protocols.
>> A “quantum resistant” or “quantum secure” is a system which is
>> fully upgraded to use post-quantum cryptography for all
>> internal security functions.
>> To illustrate the difference, consider a device which supports
>> PQC TLS ciphersuites, but whose firmware and secure-boot
>> system uses only traditional cryptography. Such a system would
>> be considered quantum ready but not quantum secure.
>> This one I did not put in my PR because I’m not sure con
>> controversial it is. I have created this as a github issue:
>> https://github.com/tireddy2/pqc-for-engineers/issues/49 <https://github.com/tireddy2/pqc-for-engineers/issues/49>
>> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/issues/49__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQHz6wdmGA$> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/issues/49__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQHz6wdmGA$;>
>> We should have a section on quantum side-channel attacks. I am
>> not an expert on this. I have written something in a pull
>> request, but it should be reviewed.
>> I added a section getting people to think about various
>> factors that can contribute to the migration time “y”.
>> I added a section, under the types of cryptography, about
>> “symmetric-based public key cryptography” so that we at least
>> mention zero-knowledge cryptography and the PICNIC NIST candidate.
>> Does kemEncaps(pk) return (ss, ct) or (ct, ss)?
>> I’ve recently had some debate about this. I don’t know if
>> anywhere there is an authoritative definition of the KEM API.
>> The NIST PQC competition C API is (ct, ss), however FIPS 203
>> and RFC9180 are (ss, ct). I have updated the draft to the latter.
>> “Post-Quantum KEMs are inherently interactive Key Exchange
>> (KE) protocols because they involve back-and-forth
>> communication to negotiate and establish a shared secret key.”
>> I think that’s actually incorrect; and contradicts the
>> previous paragraph which says “When using Key Encapsulation
>> Mechanisms (KEMs) as the underlying primitive, a flow may be
>> non-interactive or authenticated, but not both.” There were a
>> few other issues with this section, so I re-worked it, and
>> consequently it’s much shorter now😊
>> I updated the discussion of KEM Combiners to reflect recent
>> developments.
>> You had a short description of IND-CCA. I also added a section
>> on Binding.
>> Added a reference to the Hale-Connolly non-separability work.
>>
>> I made plenty of other minor and minor-ish changes in my PR.
>> https://github.com/tireddy2/pqc-for-engineers/pull/50 <https://github.com/tireddy2/pqc-for-engineers/pull/50>
>> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/pull/50__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQE-b4KHJw$> <https://urldefense.com/v3/__https:/github.com/tireddy2/pqc-for-engineers/pull/50__;!!FJ-Y8qCqXTj2!ZXr0neoOXGAmx6ms2HVjk7nNjUn36FHY2ASn4Fu33CyfeK-Z00dIvRLwePOLeCuqZhTugFRRTPVYc3pQw1pOQQE-b4KHJw$;>
>> Finally, I notice that you only have 4 authors. I have
>> contributed text to this document a few times over the years.
>> May I be author please? I took the liberty of adding myself.
>> - - -
>>
>> Mike Ounsworth
>>
>> Software Security Architect
>>
>> (pronouns: he/him)
>>
>> <image001.png>
>> <image002.png>
>>
>> --
>> Pqc mailing list [e-mail] <mailto:[e-mail]> <mailto:[e-mail] <mailto:[e-mail]>>
>> To unsubscribe send an email [e-mail] <mailto:[e-mail]>
>> <mailto:[e-mail] <mailto:[e-mail]>>
>>
>> --
>> Pqc mailing list -- [e-mail] <mailto:[e-mail]>
>> To unsubscribe send an email to [e-mail] <mailto:[e-mail]>
>
>


--
Sofía Celi
@claucece
Cryptographic research and implementation at many places.
Reach me out at: [e-mail] <mailto:[e-mail]>
Website: https://sofiaceli.com/ <https://sofiaceli.com/>


--
Pqc mailing list -- [e-mail] <mailto:[e-mail]>
To unsubscribe send an email to [e-mail] <mailto:[e-mail]>