4
$\begingroup$

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 :)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thank you for the response @Mark ! This was wildly helpful and I appreciate you taking the time. Reading the second paper you link (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). $\endgroup$
    – Rory
    Feb 6 at 15:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark
    Feb 6 at 18:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark
    Feb 7 at 21:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark
    Feb 7 at 21:38
  • 1
    $\begingroup$ 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. :) $\endgroup$
    – Rory
    Feb 27 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.