Part1Introduction

Zero-knowledge [GMR89] proofs of knowledge [BG93] allow a prover to convince a verifier that he knows a secret piece of information, without revealing anything else that what is already revealed by the claim itself. Many practically relevant proof goals can be realized using so-called -protocols, or their non-interactive counterparts, which can be proven secure in the random oracle model without the need for a common reference string. Introduced by Schnorr [Sch91] over 30 years ago, they are now widely used in practice because of their simplicity, maturity, and versatility.

-protocols played an essential component in the building of a number of cryptographic constructions, such as anonymous credentials [CMZ14], password-authenticated key exchange [HR11], signatures [Sch90], ring signatures [MP15], blind signatures [PS97], multi signatures [NRSW20], threshold signatures [KG20] and more. Lueks et al. [LKF+19], reported that solely in the years 2018-2019 editions of PETS, ACM CCS, WPES, NDSS, 7 publications use -protocols. Yet, there is no standardized way of implementing them and as a result a lot of implementations have shared common pitfalls.

We make a first attempt at the standardization of -protocols by proposing a framework for proving statements about discrete logarithms and related relations in prime-order groups, targeting specifically groups in elliptic curves. To the best of our knowledge, currently deployed and implemented -protocols mostly rely on the following sub-set of features:

• Discrete logarithm equality, Diffie-Hellman triples. Proving discrete logarithm equality, DDH triples, or more in general linear relations among secrets is an essential task for some protocols. This is the case of some VOPRFs such as [JKK14], which is currently in process of standardization [DSW19], and internally employs -protocols to prove discrete logarithm equality. DLEQ proofs are also being used by Privacy Pass [DGS+18], a lightweight anonymous credential that has been implemented and deployed at scale by Cloudflare, Brave Browser, and others. There are also other works, published in recent academic conferences, that rely on this type of relations: Cryptography for #metoo [KKR19]; Solidus [CZJ+17]; ClaimChain [KLI+18].

• Knowledge of plaintexts, openings of commitments. The so- called AND-composition of dlog relations has been used over a number of protocols, including in Algebraic MACs [CMZ14]. Algebraic MACs are now used in Signal’s group chats [CPZ20] and deployed to millions of users.

• Proving knowledge of one among multiple discrete logarithms.OR-composition of -protocols has been used for range proofs [MP15], and ring signatures: it enables for private transactions in CryptoNote (Monero) [Noe15]. OR-composition is also used in other tools such as Mesh [AG19].

All these protocols can be implemented using the API that we propose.

Part2Background and Motivation

So far, there has been little literature meant to help cryptography engineers implement correctly -protocols for arbitrary statements about discrete logs. Despite Schnorr signatures and zero-knowledge proofs have already been standardized (respectively in [JL17] and [Hao17]), there is still no formal, established way to implement -protocols and their composition. Additionally, as academic papers focus on proving the security of -protocols in generic cyclic groups, the implementation details are often times overlooked, and, as a result, a lot of insecure implementations have been published in the past. To name a few, well-known pitfalls that have led to insecure implementations:

• Implementation over non-prime order groups led to small subgroup attacks. The cyclic group where proofs are being implemented must be carefully selected. Implementing -protocol over Weierstrass curves is appealing for its performances and straight-line scalar multiplication formulæ. However, the presence of a small cofactor could be fatal for security. In 2017, Monero [tt17] disclosed a vulnerability in Cryptonote-based e-currencies that would allow double- spending due to the use of curve25519 [Ber06] in place of a prime-order curve.

• Leakage, partial leakage, or reuse of the commitment is fatal. The first message in a -protocol, sometimes called nonce or commitment, must be uniformly distributed in order to preserve zero-knowledge. Leakage of even just of a few bits of the nonce could allow for the complete recovery of the witness [HGS01,Ble00,ANT+20]. A blatant instance of this mistake was uncovered in 2010, by the hacker group fail0verflow (for EC-DSA). They showed how SONY was reusing the same nonce for digitally signing PlayStation 3 games. The member could exploit this to calculate the private key, and create valid signatures.

• A weak implementation of Fiat-Shamir heuristic compromises adaptive security. The second message in a -protocol, sometimes called challenge, if computed non-interactively must include not only the commitment, but the full statement and the group description. If the random oracle is invoked solely on the commitment (c.f. weak Fiat-Shamir transformation [BPW12, Def. 2]), then it is possible, given a proof , to produce another proof for a different statement without knowing its witness. For instance, if the group generator is not included in the hash input, then it is possible to prove statements under a different generator , for any Similarly, if part of the statement, is not included in the query to the random oracle, it is possible to compute proofs for , for any Mistakes of this class were uncovered by Bernhard et al. [BPW12], by Haines et al. [HLPT20], and by Cortier et al. [CGY20]. They all showed how some voting systems, respectively Helios, Scytl-SwissPost, and Belenios, incorrectly implemented the Fiat–Shamir heuristic, allowing for tampering of votes.

We stress that is not straightforward to implement -protocols given the currently available engineering literature. For instance, the current standardized ed25519 cannot be immediately adapted to a zero-knowledge proof in a secure way, because of its malleability [BDL+12, p. 7], and the different behavior on the batched and compressed form.

Hence, we hereby propose the creation of a working group that includes both recent cryptanalytic insights as well as the (partial) solutions described in other known standardization documents.