Score:4

Crypto

sUF-CMA security of Lyubashevsky's ID and signature protocol

Rory

2/3/24, 3:08 PM

I have been working on the post-quantum safe ID/signature-schemes of Vadim Lyubashevsky (https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf).

I am in particular studying the security proof, and wanting to structure this in a game based fashion. Any ideas on how to approach this in terms of sUf-CMA security?

Also, replay attacks in term of rewinding is used in the security proof. How can this be safe in a post-quantum setting? Or am I just getting confused with post-quantum and quantum oracle model QROM?

In advance, thank you :)

1 + 0

post-quantum-cryptography

random-oracle-model

game

zero-knowledge

Score:2

Crypto

Mark

2/3/24, 10:25 PM

In general, a good place to look for something like this is a "polished" version of the scheme. For post-quantum signatures, the "polished" schemes are most easily found in supporting documentation for the NIST PQC competition. In particular, the signature scheme CRYSTALS-DILITHIUM has been selected to be standardized, and is a "Fiat Shamir with Aborts" scheme (coauthored by Lybushavesky). You can find a writeup on this here. In particular, section 4.2 should be relevant to your question.

For your question regarding the rewinding, my understanding is that this is (roughly) the same as the forking lemma. From page 14 of the linked paper, we have that

A standard forking lemma argument can be used to show that an adversary solving the $[\mathsf{SelfTargetMSIS}]$ in the (standard) random oracle model can be used to solve the $\mathsf{MSIS}$ problem. While giving a reduction using the forking lemma is a good “sanity check”, it is not particularly useful for setting parameters due to its lack of tightness.

This is to say that, while one in principle could base things on $\mathsf{MSIS}$, due to (classical!) non-tightness of the reduction, they instead base the scheme on $\mathsf{SelfTargetMSIS}$. While that particular writeup does not mention QROM security proofs, this paper they link does. This may be a better place to start --- it additionally contains a simplified/unoptimized version of Dilithium which might be more approachable to understand initially.

+ 9

Rory

2/6/24, 3:33 PM

Thank you for the response @Mark ! This was wildly helpful and I appreciate you taking the time. Reading the second paper you link (https://eprint.iacr.org/2017/916.pdf) I realise I might be misunderstanding the idea of security games... I have been under the impression that a game scheme, like the one presented in figure 8, is unique for a specific signature scheme. Is this correct? Or is it a general game that will be the same for all signatures in that category (?) and then one constructs the security proof around the estbalished game(s) for the specific signature (Dilithium for instance).

Mark

2/6/24, 6:00 PM

games tend to be generic across scheme. The idea is that games require some API (suf-CMA requires signing and verification oracles), and then for any adversary $A$, for any scheme $\Pi$ that exposes the relevant API, you can talk about the advantage $\mathsf{Adv}_\Pi^{suf-cma}(A)$ of that adversary in that game against that scheme. The *security reduction* (how you end up bounding $\mathsf{Adv}_\Pi^{suf-cma}(A)$ in terms of various other quantities, such as $\mathsf{Adv}_{MSIS}(A')$ or whatever) is usually scheme-specific. But the initial game itself is generic.

Rory

2/7/24, 11:50 AM

Again, thank you @Mark ! When you say API, does this abbreviation mean anything in particular? If I understand correcty you are refering to the _Gen_, _Sign_, _Ver_ algorithms?

Mark

2/7/24, 9:37 PM

by API of the game I essentially mean how the adversary formally interfaces with the game. For suf-cma, an adversary is first given a public key $sk$ (corresponding to some secret key $sk$ they do not know), then given oracle access to $\mathsf{S}(m) = \mathsf{Sign}_{sk}(m)$. Eventually, they submit some data (a forged signature hopefully) to some function (often called $\mathsf{Finalize}(\cdot)$). In this setting the API is $\mathsf{S}(\cdot), \mathsf{Finalize}(\cdot)$. Note that we assume the adversary knows the underlying algorithms $\mathsf{KeyGen}, \mathsf{Sign}, \mathsf{Verify}$ as well.

Mark

2/7/24, 9:38 PM

but the API is the abstract interface someone who wants to execute a game would need to provide for any adversary. Note that two adversaries against the same interface may not have similar advantage if we swap out some signature $\Pi$ to another $\Pi'$. IN particular, an adversary $\mathcal{A}$ might have $\mathsf{KeyGen}, \mathsf{Sign}, \mathsf{Verify}$ for $\Pi$ "hard coded" into it. This is fine though.

Rory

2/8/24, 2:45 PM

So an API as in Application Programming Interface (?) but in a more theoretical approach?

Rory

2/8/24, 2:48 PM

I think this makes sense. Does an adversary playing against a game, say sUF-CMA, for a signature $\Pi$ know how the _Sign_ algorithm is executed? I thought it only had oracle access to a signing oracle that the challenger "controls" and does not know exactly how the message query/queries are being signed, just what the signature of the message is.

Mark

2/8/24, 6:03 PM

It can, just like it can know anything else hard-coded into it (say a particular constant value, or a particular license). This is to say that an adversary $\mathcal{A}$ is often specific to a scheme $\Pi$, i.e. $\mathcal{A}_{\Pi}$ may itself contain the code of $\Pi$. One could run some other adversary $\mathcal{A}_{\Pi'}$ with code of some other signature hard-coded into it though. There's nothing *wrong* about doing this (it won't give some "syntax error" type thing) because they share an API. This other adversary likely just sucks though (in terms of having small advantage).

Rory

2/27/24, 12:56 PM

Thank you for the continous patience and all these answers @Mark . I think I understand most of what you are saying. The concept definately makes more sense now. :)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: sUF-CMA security of Lyubashevsky's ID and signature protocol

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.