In the paper: "Universal One-Way Hash Functions and their Cryptographic Applications". The following is proven: "If 1-1 one-way functions exist, then the one-way based signature scheme described above is secure." For a signature scheme defined in the paper, where by secure they mean "existentially unforgeable under an adaptive chosen plaintext attack", if I understand correctly this is EU-CMA.

Now SPHINCS constructs a post-quantum EU-CMA, PQ-EU-CMA (SPHINCS definition) scheme from the stronger assumptions of among others collision-resistant hashes. If I understand correctly CRHFs are black-box separated from OWFs, in "Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?". Is there any work proving PQ-EU-CMA from OWFs only?

Based on the suggestions by lamontap and some more thought, is there a study of PQ-EU-CMA from some post-quantum generalization of OWFs? Such as those defined in One-Way Functions Imply Secure Computation in a Quantum World


1 Answer 1


Yes, there are post-quantum signature schemes that rely only on OWFs. A notable example is Picnic. If $f(\cdot)$ is a one-way function, Picnic's private key is an element $x$ in the domain of $f$ and its corresponding public key is $y=f(x)$. To sign a message, you compute a non-interactive message-dependent zero-knowledge proof of knowledge. The non-interactive proof itself relies on the existence of OWF (with security proved in the random oracle model).

In slightly more details:

  • The signature scheme relies on the MPC-in-the-Head paradigm to build a public-coin proof of knowledge of $x$ such that $y=f(x)$. The proof of knowledge requires bit commitment schemes, which are known to exist from OWFs. The prover performs an MPC protocol for checking $y=f(x)$ "in its head" where the parties hold secret shares of $x$. The prover commits to views of MPC parties and sends the commitments to the verifier. The verifier challenges the prover to open all but one of the views and checks for consistency with the MPC protocol. Since the verifier doesn't get all the shares of $x$, this is zero-knowledge and soundness comes from the security of the MPC protocol.
  • The Fiat-Shamir transform is then applied to the proof: the verifier's challenge is computed by the prover by hashing the commitments.
  • By adding the message $m$ to the hash input, this becomes a signature for $m$.

As far as I know, none of this requires collision resistance. Of course, provable security is only attainable in the random oracle model since the Fiat-Shamir transform has some pretty strong impossibility results. I hope this still answers your question. Note that there are more recent iterations of MPC-in-the-head signature schemes, some of them in NIST's recent call for additional signature schemes.

  • 1
    $\begingroup$ Yes, I think having to use correlation-intractable hashes (CIHs) to use Fiat-Shamir in standard model (to provably instantiate the random oracle) is bit of a long shot from just turning OWFs into PQ-EU-CMA, the way we can turn OWFs into EU-CMA. Concretely CIHs and OWFs are also black-box separated, so I see no difference in settling for Fiat-Shamir and settling for collision-resistance instead of an OWF. That black-box separation is eprint.iacr.org/2021/057.pdf Indeed SPHINCS needs more than CRHF, but CRHF is one of the requirements. $\endgroup$
    – Ilk
    Commented Aug 28, 2023 at 19:17

Your Answer

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

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