Sigma Protocols
draft-orru-zkproof-sigma-protocols-00

Network Working Group                                            M. Orrù
Internet-Draft                                                      CNRS
Intended status: Informational                          26 February 2025
Expires: 30 August 2025

                            Sigma Protocols
                 draft-orru-zkproof-sigma-protocols-00

Abstract

   This document describes Sigma protocols, a secure, general-purpose
   non-interactive zero-knowledge proof of knowledge.  Concretely, the
   scheme allows proving knowledge of a witness, without revealing any
   information about the undisclosed messages or the signature itself,
   while at the same time, guarantying soundness of the overall
   protocols.

About This Document

   This note is to be removed before publishing as an RFC.

   The latest revision of this draft can be found at
   https://mmaker.github.io/stdsigma/draft-orru-zkproof-sigma-
   protocols.html.  Status information for this document may be found at
   https://datatracker.ietf.org/doc/draft-orru-zkproof-sigma-protocols/.

   Source for this draft and an issue tracker can be found at
   https://github.com/mmaker/stdsigma.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 30 August 2025.

Orrù                     Expires 30 August 2025                 [Page 1]
Internet-Draft               Sigma Protocols               February 2025

Copyright Notice

   Copyright (c) 2025 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Generic interface . . . . . . . . . . . . . . . . . . . .   3
   2.  Σ-protocols over prime-order groups . . . . . . . . . . . . .   5
     2.1.  Group abstraction . . . . . . . . . . . . . . . . . . . .   5
       2.1.1.  Group . . . . . . . . . . . . . . . . . . . . . . . .   5
       2.1.2.  Scalar  . . . . . . . . . . . . . . . . . . . . . . .   6
     2.2.  Witness representation  . . . . . . . . . . . . . . . . .   6
       2.2.1.  Constraint representation . . . . . . . . . . . . . .   6
     2.3.  Core protocol . . . . . . . . . . . . . . . . . . . . . .   9
       2.3.1.  Verifier procedure  . . . . . . . . . . . . . . . . .  10
       2.3.2.  Prover  . . . . . . . . . . . . . . . . . . . . . . .  10
       2.3.3.  Verifier  . . . . . . . . . . . . . . . . . . . . . .  10
     2.4.  Nonce and challenge derivation  . . . . . . . . . . . . .  11
       2.4.1.  Statement generation  . . . . . . . . . . . . . . . .  11
   3.  Ciphersuites  . . . . . . . . . . . . . . . . . . . . . . . .  12
     3.1.  P-384 . . . . . . . . . . . . . . . . . . . . . . . . . .  12
       3.1.1.  Elliptic curve group of P-384 (secp384r1)
               NISTCurves  . . . . . . . . . . . . . . . . . . . . .  12
       3.1.2.  Scalar Field of P-384 (secp384r1) . . . . . . . . . .  12
   4.  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .  13
   5.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  13
     5.1.  Normative References  . . . . . . . . . . . . . . . . . .  13
     5.2.  Informative References  . . . . . . . . . . . . . . . . .  13
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  13

1.  Introduction

   A Sigma Protocol is a simple zero-knowledge proof of knowledge.  Any
   sigma protocols must define three objects:

   *  A commitment, sometimes also called nonce.  This message is
      computed by the prover.

   *  A challenge, computed using the Fiat-Shamir transformation using a
      hash function.

Orrù                     Expires 30 August 2025                 [Page 2]
Internet-Draft               Sigma Protocols               February 2025

   *  A response, computed by the prover, which depends on the
      commitment and the challenge.

   A sigma protocol allows to convince a *verifier* of the knowledge of
   a secret *witness* satisfying a *statement*.

1.1.  Generic interface

   A sigma protocol is an interface exposing the following functions:

   def prove_short(label, statement, witness):
       sp = SigmaProtocol.new(statement)
       (prover_state, commitment) = sp.prover_commmit(witness)
       challenge = SHO
           .init(label)
           .absorb(commitment)
           .squeeze(1)

       response = sp.prover_response(commitment, challenge)
       return scalar_to_bytes(challenge) + scalar_to_bytes(response)

   def prove_batchable(label, statement, witness):
       sp = SigmaProtocol.new(statement)
       (prover_state, commitment) = sp.prover_commit(witness)
       challenge = SHO
           .init(label)
           .absorb(commitment)
           .squeeze(1)
       response = sp.prover_response(commitment, challenge)
       return point_to_bytes(commitment) + scalar_to_bytes(response)

   def verify_batchable(label, statement, proof):
       sp = SigmaProtocol.new(statement)
       commitment = read_group_elements(proof)

   Internally, each sigma protocol implements the following methods.

class SigmaProtocol:
   def new(instance: Statement) -> SigmaProtocol
   def prover_commit(self, witness: Witness) -> (commitment, prover_state)
   def prover_response(self, prover_state, challenge) -> response
   def verifier(self, commitment, challenge, response) -> bool
   # optional
   def simulate_response() -> response
   # optional
   def simulate_commitment(response, challenge) -> commitment

   Where:

Orrù                     Expires 30 August 2025                 [Page 3]
Internet-Draft               Sigma Protocols               February 2025

   *  new(il: [u8], cs: ConstraintSystem) -> SigmaProtocol, denoting the
      initialization function.  This function takes as input a label
      identifying local context information (such as: session
      identifiers, to avoid replay attacks; protocol metadata, to avoid
      hijacking; optionally, a timestamp and some pre-shared randomness,
      to guarantee freshness of the proof) and an instance generated via
      the ConstraintSystem, the public information shared between prover
      and verifier.  This function should pre-compute parts of the
      statement, or initialize the state of the hash function.

   *  prover_commit(self, witness: Witness) -> (commitment,
      prover_state), denoting the *commitment phase*, that is, the
      computation of the first message sent by the prover in a Sigma
      protocol.  This method outputs a new commitment together with its
      associated prover state, depending on the witness known to the
      prover and the statement to be proven.  This step generally
      requires access to a high-quality entropy source.  Leakage of even
      just of a few bits of the nonce could allow for the complete
      recovery of the witness.  The commitment meant to be shared, while
      prover_state must be kept secret.

   *  prover_response(self, prover_state, challenge) -> response,
      denoting the *response phase*, that is, the computation of the
      second message sent by the prover, depending on the witness, the
      statement, the challenge received from the verifier, and the
      internal state prover_state.  The returned value response is meant
      to be shared.

   *  verifier(self, commitment, challenge, response) -> bool, denoting
      the *verifier algorithm*. This method checks that the protocol
      transcript is valid for the given statement.  The verifier
      algorithm outputs nothing if verification succeeds, or an error if
      verification fails.

   The final two algorithms describe the *zero-knowledge simulator* and
   are optional.  The simulator is primarily an efficient algorithm for
   proving zero-knowledge in a theoretical construction, but it is also
   needed for verifying short proofs and for or-composition, where a
   witness is not known and thus has to be simulated.  We have:

   *  simulate_response() -> response, denoting the first stage of the
      simulator.  It is an algorithm drawing a random response that
      follows the same output distribution of the algorithm
      prover_response

   *  simulate_commitment(response, challenge) -> commitment, returning
      a simulated commitment -- the second phase of the zero-knowledge
      simulator.

Orrù                     Expires 30 August 2025                 [Page 4]
Internet-Draft               Sigma Protocols               February 2025

   The abstraction SigmaProtocol allows implementing different types of
   statements and combiners of those, such as OR statements, validity of
   t-out-of-n statements, and more.

2.  Σ-protocols over prime-order groups

   The following sub-section present concrete instantiations of
   Σ-protocols over prime-order groups such as elliptic curves.
   Traditionally, Σ-protocols are defined in Camenish-Stadtler notation
   as (for example):

   VRF(A, B, G, H) = PoK{
     (x):        // Secret variables
     A = x * B,  // Statements to prove
     G = x * H
   }

   This section describes how to build and prove statements of this form
   programmatically.

2.1.  Group abstraction

   Because of their dominance, the presentation in the following focuses
   on proof goals over elliptic curves, therefore leveraging additive
   notation.  For prime-order subgroups of residue classes, all notation
   needs to be changed to multiplicative, and references to elliptic
   curves (e.g., curve) need to be replaced by their respective
   counterparts over residue classes.  We therefore assume two objects
   are available to the programmer:

Group: Zero + Add<Group> + Sub<Group> + Mul<Scalar> + From<int> + Eq<Group> + Serialize + Deserialize
Scalar: Zero + One + Div<Scalar> + Add<Scalar> + Sub<Scalar> + From<int> + Eq<Group> + Serialize + Deserialize

   We detail the functions that can be invoked on these objects.
   Example choices can be found in Section 3.

2.1.1.  Group

   *  order(): Outputs the order of the group p.

   *  random(): outputs a random element

   *  serialize([Group; N]): serializes a list of group elements and
      returns a canonical byte array buf of fixed length Ng * N.

Orrù                     Expires 30 August 2025                 [Page 5]
Internet-Draft               Sigma Protocols               February 2025

   *  deserialize(buf): Attempts to map a byte array buf of size Ng * N
      into [Group; N], and fails if the input is not the valid canonical
      byte representation of an element of the group.  This function can
      raise a DeserializeError if deserialization fails.

2.1.2.  Scalar

   *  random(): outputs a random element

   *  serialize([Scalar; N]): serializes a list of scalars and returns
      their canonical representation of fixed length Ns * N.

2.2.  Witness representation

   A witness is simply a list of num_scalars elements.

   struct Witness {
       scalars: [Scalar; num_scalars] // The set of secret scalars
   }

2.2.1.  Constraint representation

   Internally, the constraint can be represented as:

struct Equations {
    // the list of statements to be proven
    matrix: [LinearCombination<ScalarIndex, &Group>; num_statements]
    // An list of references to group elements representing the left-hand side part of the equations
    image: [&Group; num_statements]

    // the number of secret scalars
    num_scalars: usize
    // the number of equations to be proven
    num_statements: usize
}

   The object LinearCombination encodes pairs of indices of the witness
   vector with group elements.  The initial example of the VRF can
   therefore be expressed with the following constraints:

   cs = Equations()
   [x] = cs.allocate_scalars(1)
   [A, B, G, H] = cs.allocate_group_elt(4)
   cs.append_equation(lhs=A, rhs=[(x, B)])
   cs.append_equation(lhs=G, rhs=[(x, H)])

   In the above, Equations.new() creates a new Equations with label
   "VRF".

Orrù                     Expires 30 August 2025                 [Page 6]
Internet-Draft               Sigma Protocols               February 2025

2.2.1.1.  Instantiation of the constraints

   new(label)

   Inputs:

   - labels, a byte array

   Outputs:

   - a ConstraintSystem instance

   Procedure:

   1.  return Equations {
   2.        label,
   3.        num_statements: 0,
   4.        num_scalars: 0,
   5.        group_elements: [],
   6.        matrix: [],
   7.        image: []
   8.    }

2.2.1.2.  Scalar witness allocation

allocate_scalars(self, n)

Inputs:
    - self, the current state of the ConstraintSystem
    - n, the number of scalars to allocate
Outputs:
    - indices, a list of integers each pointing to the new allocated scalars

Procedure:

1. indices = range(self.num_scalars, self.num_scalars + n)
2. self.num_scalars += n
3. return indices

2.2.1.3.  Public group element allocation

Orrù                     Expires 30 August 2025                 [Page 7]
Internet-Draft               Sigma Protocols               February 2025

allocate_group_elt(self, n)

Inputs:

   - self, the current state of the constraint system
   - n, the number of group elements to allocate

Outputs:

   - indices, a list of integers each pointing to the new allocated group elements.

Procedure:

1. indices = range(len(self.group_elts), len(self.group_elements) + n)
2. self.group_elements.extend([None] * n)
3. return indices

2.2.1.4.  Group element assignment

   assign_point(self, ptr, value)

   Inputs:

       - self, the current state of the constraint system
       - ptr, the pointer to the group element to be assigned
       - value, the value to be assigned to the group element

   Procedure:

   1. self.group_elements[ptr] = value

2.2.1.5.  Enforcing an equation

   This function adds an equation statement constraint to the instance,
   expressed as a left-hand side (the target group element), and a list
   of pairs encoding a linear combination of scalars and group elements.

Orrù                     Expires 30 August 2025                 [Page 8]
Internet-Draft               Sigma Protocols               February 2025

append_equation(self, lhs, rhs)

Inputs:

- self, the current state of the constraint system
- lhs, the left-hand side of the equation
- rhs, the right-hand side of the equation (a list of (ScalarIndex, GroupEltIndex) pairs)

Outputs:

- An Equation instance that enforces the desired relation

Procedure:

1. self.num_statements += 1
2. self.image.append(lhs)
3. self.matrix.append(rhs)

   A witness can be mapped to a group element via:

def map(self, witness: [Scalar; num_scalars]):
  assert self.num_scalars = self.scalars.len()
  image = [0; Group]
  for i in range(self.num_statements):
      eq_scalars = [self.scalars[idx_pair[0]]
                    for idx_pair in self.matrix[i]]
      eq_group_elt = [self..group_elements[idx_pair[1]] for idx_pair in self.matrix[i]]
      image[i] = multi_scalar_multiplication(eq_scalars, eq_group_elt)
  return image

2.3.  Core protocol

   class SigmaProtocol:
       def new(statement: Statement):
           self.statement = statement

       def prover_commit(self, witness: Witness):
           nonces = Scalar::random()
           prover_state = (witness, nonces)
           commitment = self.statement.map(witness)
           return (prover_state, commitment)

       def prover_response(self, prover_state, challenge):
           response = [0; self.cs.num_scalars]
           for i in range(self.cs.num_scalars):
               response[i] = witness[i] + challenge * nonces[i]
           return response

Orrù                     Expires 30 August 2025                 [Page 9]
Internet-Draft               Sigma Protocols               February 2025

2.3.1.  Verifier procedure

verify(self, commitment, challenge, response)

Inputs:

- self, the current state of the SigmaProtocol
- commitment, the commitment generated by the prover
- challenge, the challenge generated by the verifier
- response, the response generated by the prover

Outputs:

- A boolean indicating whether the verification succeeded

Procedure:

1. image = [equation.lhs for equation in self.statement.equations]
2. expected_commitment = challenge * image + self.statement.map(response)
3. return expected_commitment == commitment

2.3.2.  Prover

   We describe below the prover's wrapping function.

   def prove_short(statement, witness):
     sp = SigmaProtocol.new(statement)
     (prover_state, commitment) = sp.prover_commmit(witness)
     challenge = sp.challenge(commitment)
     response = sp.prover_response(commitment, challenge)
     return scalar_to_bytes(challenge) + scalar_to_bytes(response)

   def prove_batchable(statement, witness):
     sp = SigmaProtocol.new(statement)
     (prover_state, commitment) = sp.prover_commmit(witness)
     challenge = sp.challenge(commitment)
     response = sp.prover_response(commitment, challange)
     return point_to_bytes(commitment) + scalar_to_bytes(response)

2.3.3.  Verifier

   def verify_batchable(statement, proof):
     sp = SigmaProtocol.new(statement)
     commitment = read_group_elements(proof)

Orrù                     Expires 30 August 2025                [Page 10]
Internet-Draft               Sigma Protocols               February 2025

2.4.  Nonce and challenge derivation

   Two types of randomness are needed for a sigma protocol:

   1.  A nonce seeding the randomness used to produce the commitment of
       the first round of the protocol

   2.  A challenge representing the verifier's public random coin.

   The challenge of a Schnorr proof is derived with

 challenge = sho.init(iv).absorb_group_elt(commitment).squeeze_scalar(1)

   This can be generated with:

   nonce = sho.init(iv)
              .absorb_bytes(random)
              .ratchet()
              .absorb_scalars(witness)
              .squeeze_scalars(cs.num_scalars)

   The iv, which must properly separate the application and the
   statement being proved, is described below.

2.4.1.  Statement generation

   Let H be a hash object.  The statement is encoded in a stateful hash
   object as follows.

 hasher = H.new(domain_separator)
 hasher.update_usize([cs.num_statements, cs.num_scalars])
 for equation in cs.equations:
   hasher.update_usize([equation.lhs, equation.rhs[0], equation.rhs[1]])
 hasher.update(generators)
 iv = hasher.digest()

   In simpler terms, without stateful hash objects, this should
   correspond to the following:

   bin_challenge = SHAKE128(iv).update(commitment).digest(scalar_bytes)
   challenge = int(bin_challenge) % p

   and the nonce is produced as:

Orrù                     Expires 30 August 2025                [Page 11]
Internet-Draft               Sigma Protocols               February 2025

   bin_nonce = SHAKE128(iv)
               .update(random)
               .update(pad)
               .update(cs.scalars)
               .digest(cs.num_scalars * scalar_bytes)
   nonces = [int(bin_nonce[i*scalar_bytes: i*(scalar_bytes+1)]) % p
             for i in range(cs.num_scalars-1)]

   Where: - pad is a (padding) zero string of length 168 - len(random).
   - scalar_bytes is the number of bytes required to produce a uniformly
   random group element - random is a random seed obtained from the
   operating system memory

3.  Ciphersuites

3.1.  P-384

   This ciphersuite uses P-384 [NISTCurves] for the Group.

3.1.1.  Elliptic curve group of P-384 (secp384r1) [NISTCurves]

   *  order(): Return 0xffffffffffffffffffffffffffffffffffffffffffffffff
      c7634d81f4372ddf581a0db248b0a77aecec196accc52973.

   *  serialize([A]): Implemented using the compressed Elliptic-Curve-
      Point-to-Octet-String method according to [SEC1]; Ng = 49.

   *  deserialize(buf): Implemented by attempting to read buf into
      chunks of 49-byte arrays and convert them using the compressed
      Octet-String-to-Elliptic-Curve-Point method according to [SEC1],
      and then performs partial public-key validation as defined in
      section 5.6.2.3.4 of [KEYAGREEMENT].  This includes checking that
      the coordinates of the resulting point are in the correct range,
      that the point is on the curve, and that the point is not the
      point at infinity.

3.1.2.  Scalar Field of P-384 (secp384r1)

   *  serialize(s): Relies on the Field-Element-to-Octet-String
      conversion according to [SEC1]; Ns = 48.

   *  deserialize(buf): Reads the byte array buf in chunks of 48 bytes
      using Octet-String-to-Field-Element from [SEC1].  This function
      can fail if the input does not represent a Scalar in the range [0,
      G.Order() - 1].

Orrù                     Expires 30 August 2025                [Page 12]
Internet-Draft               Sigma Protocols               February 2025

4.  Acknowledgments

   Jan Bobolz, Stephan Krenn, Mary Maller, Ivan Visconti, Yuwen Zhang.

5.  References

5.1.  Normative References

   [KEYAGREEMENT]
              Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R.
              Davis, "Recommendation for pair-wise key-establishment
              schemes using discrete logarithm cryptography", National
              Institute of Standards and Technology,
              DOI 10.6028/nist.sp.800-56ar3, April 2018,
              <https://doi.org/10.6028/nist.sp.800-56ar3>.

5.2.  Informative References

   [NISTCurves]
              "Digital signature standard (DSS)", National Institute of
              Standards and Technology (U.S.),
              DOI 10.6028/nist.fips.186-4, 2013,
              <https://doi.org/10.6028/nist.fips.186-4>.

   [SEC1]     Standards for Efficient Cryptography Group (SECG), "SEC 1:
              Elliptic Curve Cryptography",
              <https://www.secg.org/sec1-v2.pdf>.

Author's Address

   Michele Orrù
   CNRS
   Email: m@orru.net

Orrù                     Expires 30 August 2025                [Page 13]