More Like this

1. Designing a Practical Code-Based Signature Scheme from Zero-Knowledge Proofs with Trusted Setup

   https://doi.org/10.3390/cryptography6010005  

   Gueron, Shay; Persichetti, Edoardo; Santini, Paolo (March 2022, Cryptography)

   This paper defines a new practical construction for a code-based signature scheme. We introduce a new protocol that is designed to follow the recent paradigm known as “Sigma protocol with helper”, and prove that the protocol’s security reduces directly to the Syndrome Decoding Problem. The protocol is then converted to a full-fledged signature scheme via a sequence of generic steps that include: removing the role of the helper; incorporating a variety of protocol optimizations (using e.g., Merkle trees); applying the Fiat–Shamir transformation. The resulting signature scheme is EUF-CMA secure in the QROM, with the following advantages: (a) Security relies on only minimal assumptions and is backed by a long-studied NP-complete problem; (b) the trusted setup structure allows for obtaining an arbitrarily small soundness error. This minimizes the required number of repetitions, thus alleviating a major bottleneck associated with Fiat–Shamir schemes. We outline an initial performance estimation to confirm that our scheme is competitive with respect to existing solutions of similar type. 

   more » « less
2. The Fiat-Shamir Zoo: Relating the Security of Different Signature Variants

   Backendal, Matilda; Bellare, Mihir; Sorrell, Jessica; Sun, Jiahao (November 2018, Secure IT Systems - 23rd Nordic Conference, NordSec 2018, Oslo, Norway, November 28-30, 2018, Proceedings. Lecture Notes in Computer Science 11252, Springer 2018)

   The Fiat-Shamir paradigm encompasses many different ways of turning a given identification scheme into a signature scheme. Security proofs pertain sometimes to one variant, sometimes to another. We systematically study three variants that we call the challenge (signature is challenge and response), commit (signature is commitment and response), and transcript (signature is challenge, commitment and response) variants. Our framework captures the variants via transforms that determine the signature scheme as a function of not only the identification scheme and hash function (to cover both standard and random oracle model hashing), but also what we call a signing algorithm, to cover both classical and with-abort signing. We relate the security of the signature schemes produced by these transforms, giving minimal conditions under which uf-security of one transfers to the other. To apply this comprehensively, we formalize linear identification schemes, show that many schemes in the literature are linear, and show that any linear scheme meets our conditions for the signature schemes given by the three transforms to have equivalent uf-security. Our results give a comprehensive picture of the Fiat-Shamir zoo and allow proofs of security in the literature to be transferred automatically from one variant to another. 

   more » « less
3. On the Multi-User Security of Short Schnorr Signatures with Preprocessing

   Blocki, Jeremiah; Lee, Seunghoon. (January 2022, Advances in Cryptology - EUROCRYPT)

   The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$-bit signatures for $$k$$ bits of security. A Schnorr signature $$\sigma$$ over a group of size $$p\approx 2^{2k}$$ consists of a tuple $(s,e)$, where $$e \in \{0,1\}^{2k}$$ is a hash output and $$s\in \mathbb{Z}_p$$ must be computed using the secret key. While the hash output $$e$$ requires $2k$$ bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security. In this paper, we prove that \emph{short} Schnorr signatures of length $$3k$ bits provide $$k$$ bits of multi-user security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multi-user security of key-prefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length $$3k + \log S + \log N$$ bits. Here, $$N$$ denotes the number of users and $$S$$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $$S=2^{k/2}$$, then we would obtain secure $3.75k$-bit signatures for groups of up to $$N \leq 2^{k/4}$$ users. Our techniques easily generalize to several other Fiat-Shamir-based signature schemes, allowing us to establish analogous results for Chaum-Pedersen signatures and Katz-Wang signatures. As a building block, we also analyze the $$1$$-out-of-$$N$$ discrete-log problem in the generic group model, with and without preprocessing. 

   more » « less
4. BooLigero: Improved Sublinear Zero Knowledge Proofs for Boolean Circuits

   Gvili, Yaron; Scheffler, Sarah; Varia, Mayank (March 2021, Financial Cryptography and Data Security)

   null (Ed.)

   We provide a modified version of the Ligero sublinear zero knowledge proof system for arithmetic circuits provided by Ames et. al. (CCS ‘17). Our modification "BooLigero" tailors Ligero for use in Boolean circuits to achieve a significant improvement in proof size. Although the original Ligero system could be used for Boolean circuits, Ligero generally requires allocating an entire field element to represent a single bit on a wire in a Boolean circuit. In contrast, our system performs operations over words of bits, allowing a proof size savings of between O(log(|F|)^1/4) and O(log(|F|)^1/2) compared to Ligero, where F is the field that leads to the optimal proof size in original Ligero. We achieve improvements in proof size of approximately 1.1-1.6x for SHA-2 and 1.7-2.8x for SHA-3. In addition to checking constraints of standard Boolean operations such as AND, XOR, and NOT over words, BooLigero also supports several other constraints such as multiplication in GF(2^w), bit masking, bit rearrangement within and across words, and bitwise outer product. Like Ligero, construction requires no trusted setup and no computational assumptions, which is ideal for blockchain applications. It is plausibly post-quantum secure in the standard model. Furthermore, it is public-coin, perfect honest-verifier zero knowledge, and can be made non-interactive in the random oracle model using the Fiat-Shamir transform. 

   more » « less
5. On the Security of Proofs of Sequential Work in a Post-Quantum World

   https://doi.org/10.4230/LIPIcs.ITC.2021.22  

   Blocki, J; Lee, S; Zhou, S. (January 2021, 2nd Conference on Information-Theoretic Cryptography (ITC 2021))

   Tessaro, Stefano (Ed.)

   A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depth-robust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depth-robust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long ℋ-sequence and that any malicious party running in sequential time T-1 will fail to produce an ℋ-sequence of length T except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time T-1 will fail to produce an ℋ-sequence except with negligible probability - even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry’s recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak’s efficient construction (EUROCRYPT 2018). 

   more » « less