Links

Cryptography Primitives

ElGamal encryption

The ElGamal encryption in the Zei library is defined over the Ristretto curve, where the base
GG\mathbf{G}G
is the base point of the Ristretto group. Note that the message
mm\mathbf{m}m
is encoded into a group element as
mGmG\mathbf{m}\cdot \mathbf{G}m⋅G
, which means that it can only be decrypted through brute-force. One who wants to remove this restriction can use reversible encoding, but it is not implemented in the Zei library.
The ElGamal encryption scheme has the following syntax:
  • KeyGen(1λ)(sk,pk)\mathsf{KeyGen}(1^\lambda)\rightarrow (\mathsf{sk},\mathsf{pk})
    :
    • sk ⁣$F\mathsf{sk} \leftarrow\!{\footnotesize \$} \hspace{3pt} \mathbb{F}
    • pk:=skG\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}
    • output
      (sk,pk)(\mathsf{sk},\mathsf{pk})
  • Enc(pk,m)ct\mathsf{Enc}(\mathsf{pk}, \mathbf{m})\rightarrow \mathsf{ct}
    :
    • r ⁣$F\mathbf{r}\leftarrow\!{\footnotesize \$} \hspace{3pt} \mathbb{F}
    • output
      ct:=EncWithRand(pk,m,r)\mathsf{ct} := \mathsf{EncWithRand}(\mathsf{pk},\mathbf{m},\mathbf{r})
      .
  • EncWithRand(pk,m,r)ct\mathsf{EncWithRand}(\mathsf{pk},\mathbf{m}, \mathbf{r})\rightarrow \mathsf{ct}
    :
    • ct1:=rG\mathsf{ct}_1 := \mathbf{r}\cdot \mathbf{G}
      .
    • ct2:=mG+rpk\mathsf{ct}_2 := \mathbf{m}\cdot \mathbf{G} + \mathbf{r}\cdot \mathsf{pk}
      .
    • Output
      ct:=(ct1,ct2)\mathsf{ct} := (\mathsf{ct}_1,\mathsf{ct}_2)
      .
  • Verify(sk,m,ct):=b{0,1}\mathsf{Verify}(\mathsf{sk},\mathbf{m},\mathsf{ct}):= \mathbf{b}\in\{0,1\}
    :
    • (ct1,ct2):=ct(\mathsf{ct}_1, \mathsf{ct}_2) := \mathsf{ct}
    • check
      ct2skct1=?mG\mathsf{ct}_2 - \mathsf{sk}\cdot \mathsf{ct}_1 \stackrel{?}{=} \mathbf{m}\cdot G
  • PartialDec(sk,ct):=mG\mathsf{PartialDec}(\mathsf{sk}, \mathsf{ct}):= \mathbf{m}\cdot G
    :
    • (ct1,ct2):=ct(\mathsf{ct}_1, \mathsf{ct}_2) := \mathsf{ct}
    • output
      ct2skct1\mathsf{ct}_2 - \mathsf{sk}\cdot \mathsf{ct}_1

Hybrid encryption

The hybrid encryption in the Zei library supports the X25519 curve and the Ed25519 curve, and the symmetric encryption is done using the counter mode of the AES cipher.
The hybrid encryption scheme has the following syntax:
  • HybridEnc(sk,m)ct\mathsf{HybridEnc}(\mathsf{sk},m)\rightarrow \mathsf{ct}
    :
    • r ⁣$F\mathbf{r}\leftarrow\!{\footnotesize \$} \hspace{3pt} \mathbb{F}
    • ct1:=rG\mathsf{ct}_1 := \mathbf{r}\cdot \mathbf{G}
    • derive an AES symmetric key
      k\mathbf{k}
      from
      skct1\mathsf{sk}\cdot\mathsf{ct}_1
      using SHA256
    • ct2:=AESEnc(k,m)\mathsf{ct}_2 := \mathsf{AESEnc}(\mathbf{k}, \mathbf{m})
    • output
      ct=(ct1,ct2)\mathsf{ct}=(\mathsf{ct}_1,\mathsf{ct}_2)
  • HybridDec(sk,ct):=m\mathsf{HybridDec}(\mathsf{sk},\mathsf{ct}):= \mathbf{m}
    :
    • (ct1,ct2):=ct(\mathsf{ct}_1,\mathsf{ct}_2):= \mathsf{ct}
    • derive an AES symmetric key
      k\mathbf{k}
      from
      skct1\mathsf{sk}\cdot\mathsf{ct}_1
      using SHA256
    • output
      m:=AESDec(k,ct2)\mathbf{m} := \mathsf{AESDec}(\mathbf{k}, \mathsf{ct}_2)

Matrix Sigma protocol

The matrix Sigma protocol in the Zei library is a proof of knowledge for the following statement: the prover
PP\mathbb{P}P
knows a scalar vector
x{0,1}n\vec{x}\in\{0,1\}^n
such that:
MxT=y\mathbf{M}\cdot \vec{\mathbf{x}}^T = \vec{\mathbf{y}}​
where
MGm×n\mathbf{M}\in\mathbb{G}^{m\times n}
is a matrix of group elements and
yGm\vec{\mathbf{y}}\in\mathbb{G}^m
is a vector of group elements.
The matrix Sigma protocol has the following syntax. In the actual implementation, the Fiat-Shamir transform is performed over a transcript across one or more interactive protocols.
  • Prove(M,x)π\mathsf{Prove}(\mathbf{M}, \vec{\mathbf{x}})\rightarrow \pi
    :
    • append individual group elements in
      M\mathbf{M}
      to the transcript
    • r ⁣$Fn\vec{\mathbf{r}}\leftarrow\!{\footnotesize \$} \hspace{3pt}\mathbb{F}^n
    • c:=MrT\vec{\mathbf{c}} := \mathbf{M}\cdot \vec{\mathbf{r}}^T
    • append
      c\vec{\mathbf{c}}
      to the transcript
    • squeeze a challenge
      β\beta
      from the Fiat-Shamir transform
    • d:=βx+r\vec{\mathbf{d}} := \beta \vec{\mathbf{x}} + \vec{\mathbf{r}}
    • output
      π=(c,d)\pi = (\vec{\mathbf{c}}, \vec{\mathbf{d}})
  • Verify(M,y,π):=b{0,1}\mathsf{Verify}(\mathbf{M},\vec{\mathbf{y}}, \pi):=\mathbf{b}\in\{0,1\}
    • (c,d):=π(\vec{\mathbf{c}}, \vec{\mathbf{d}}) := \pi
    • append individual group elements in
      M\mathbf{M}
      to the transcript
    • append
      c\vec{\mathbf{c}}
      to the transcript
    • squeeze a challenge
      β\beta
      from the Fiat-Shamir transform
    • check
      Md=?βy+c\mathbf{M}\cdot \vec{\mathbf{d}}\stackrel{?}{=} \beta\cdot\vec{\mathbf{y}} + \vec{\mathbf{c}}

Schnorr signature

The Schnorr signature in the Zei library is the classical version. The multi-signature implementation extends from the simple Schnorr signature in a naive manner: the multi-signature is a list of simple Schnorr signatures from individual signers. The Schnorr signature scheme is defined over a group
G\mathbb{G}
with a generator
G\mathbf{G}
with a scalar field
F\mathbb{F}
.
The Schnorr signature has the following syntax.
  • KeyGen(1λ)(sk,pk):\mathsf{KeyGen}(1^\lambda)\rightarrow(\mathsf{sk},\mathsf{pk}):
    • sk ⁣$F\mathsf{sk}\leftarrow\!{\footnotesize \$} \hspace{3pt}\mathbb{F}
    • pk:=skG\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}
    • output
      (sk,pk)(\mathsf{sk},\mathsf{pk})
  • Sign(sk,m)σ:Sign(sk,m)→σ:
    • r ⁣$F\mathsf{r}\leftarrow\!{\footnotesize \$} \hspace{3pt}\mathbb{F}
    • R:=rG\mathbf{R} := \mathbf{r} \cdot \mathbf{G}
    • append the message
      m\mathbf{m}
      , the public key
      pk:=skG\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}
      , and
      R\mathbf{R}
      to the transcript
    • squeeze a challenge
      c\mathbf{c}
      from the Fiat-Shamir transform
    • s:=r+csk\mathbf{s} := \mathsf{r} + \mathbf{c}\cdot \mathsf{sk}
    • output
      σ:=(R,s)\sigma := (\mathbf{R}, \mathbf{s})
  • Verify(pk,m,σ):=b{0,1}\mathsf{Verify}(\mathsf{pk},\mathbf{m},\sigma) := \mathbf{b}\in\{0,1\}
    :
    • (R,s):=σ(\mathbf{R}, \mathbf{s}) := \sigma
    • append the message
      mm\mathbf{m}m
      , the public key
      pk:=skG\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}
      , and
      R\mathbf{R}
      to the transcript
    • squeeze a challenge
      c\mathbf{c}
      from the Fiat-Shamir transform
    • check
      R+cpk=?sG\mathbf{R} + \mathbf{c}\cdot \mathsf{pk} \stackrel{?}{=} \mathbf{s}\cdot \mathbf{G}

Pedersen commitment over Ristretto

The Pedersen commitment over Ristretto scheme in the Zei library is used to represent the amount and the asset type. The scheme is defined over a group with two independent generators
G\mathbf{G}
and
H\mathbf{H}
, where we do not know their discrete logs to each other. The commitment algorithm is as follows.
  • Commit(m,r)comm\mathsf{Commit}(\mathbf{m},\mathbf{r})\rightarrow\mathbf{comm}
    :
    • output
      mG+rH\mathbf{m}\cdot\mathbf{G} + \mathbf{r}\cdot\mathbf{H}

Chaum-Pedersen proof of commitment equality

The Chaum-Pedersen proof of commitment equality scheme in the Zei library is to show that two Pedersen commitments
comm1\mathbf{comm}_1
and
comm2\mathbf{comm}_2
, whose blinding factors are correspondingly
r1,r2\mathbf{r}_1, \mathbf{r}_2
, commit to the same value
m\mathbf{m}
. This proof is commonly used to show equality over commitments.
The Chaum-Pedersen proof of commitment equality scheme has the following syntax.
  • Prove(comm1,comm2,m,r1,r2)π\mathsf{Prove}(\mathbf{comm}_1,\mathbf{comm}_2,\mathbf{m},\mathbf{r}_1,\mathbf{r}_2)\rightarrow \pi
    :
    • let matrix
      M\mathbf{M}
      be:
      M:=(GH1GG1GH)\mathbf{M} := \left( \begin{array}{ccc} \mathbf{G} & \mathbf{H} & 1_\mathbb{G}\\ \mathbf{G} & 1_\mathbb{G} & \mathbf{H} \end{array}\right)
    • let vector
      x\vec{\mathbf{x}}
      be:
      x:=(mr1r2)\vec{\mathbf{x}} := \left(\begin{array}{lll} \mathbf{m} & \mathbf{r}_1 & \mathbf{r}_2 \end{array}\right)
    • output
      π=MatrixSigma.Prove(M,x)\pi = \mathsf{MatrixSigma}.\mathsf{Prove}(\mathbf{M}, \vec{\mathbf{x}})
  • Verify(comm1,comm2,π):=b{0,1}\mathsf{Verify}(\mathbf{comm}_1,\mathbf{comm}_2,\pi) := \mathbf{b}\in\{0,1\}
    :
    • let matrix
      M\mathbf{M}
      be:
      M:=(GH1GG1GH)\mathbf{M} := \left( \begin{array}{ccc} \mathbf{G} & \mathbf{H} & 1_\mathbb{G}\\ \mathbf{G} & 1_\mathbb{G} & \mathbf{H} \end{array}\right)
    • let vector
      y\vec{\mathbf{y}}
      be:
      y:=(comm1,comm2)\vec{\mathbf{y}} := \left(\mathbf{comm}_1, \mathbf{comm}_2\right)
    • check
      MatrixSigma.Verify(M,y,π)=1\mathsf{MatrixSigma}.\mathsf{Verify}(\mathbf{M},\vec{\mathbf{y}},\pi) = 1
There is an extended version of Chaum-Pedersen proof that checks the equality of multiple commitments, often used for checking the asset types. It has the following syntax. Note that there are alternative constructions, but due to compatibility reasons, we cannot easily upgrade.
  • BatchProve([commi]1n,m,[ri]1n)π\mathsf{BatchProve}([\mathbf{comm}_i]_1^n, \mathbf{m}, [\mathbf{r}_i]_1^n)\rightarrow \pi
    :
    • append
      G,H,[commi]1n\mathbf{G},\mathbf{H},[\mathbf{comm}_i]_1^n
      to the transcript
    • π1Prove(comm1,comm2,m,r1,r2)\pi_1 \leftarrow \mathsf{Prove}(\mathbf{comm}_1,\mathbf{comm}_2,\mathbf{m},\mathbf{r}_1,\mathbf{r}_2)
    • squeeze
      3,4,...,n\ell_3,\ell_4,...,\ell_n
      from the Fiat-Shamir transform
    • comm:=i=3ni(commicomm1)\mathbf{comm} := \sum_{i=3}^n \ell_i\cdot(\mathbf{comm}_i - \mathbf{comm}_1)
    • r:=i=3ni(rir1)\mathbf{r} := \sum_{i=3}^n \ell_i\cdot (\mathbf{r}_i - \mathbf{r}_1)
    • π2Prove(comm,1G,0F,r,0F)\pi_2 \leftarrow\mathbf{Prove}(\mathbf{comm},1_{\mathbb{G}}, 0_{\mathbb{F}}, \mathbf{r}, 0_{\mathbb{F}})
    • output
      π:=(π1,π2)\pi := (\pi_1, \pi_2)
  • BatchVerify([commi]1n,π):=b{0,1}\mathsf{BatchVerify}([\mathbf{comm}_i]_1^n, \pi) := \mathbf{b}\in\{0,1\}
    :
    • append
      G,H,[commi]1n\mathbf{G},\mathbf{H},[\mathbf{comm}_i]_1^n
      to the transcript
    • (π1,π2):=π(\pi_1,\pi_2) := \pi
    • squeeze
      3,4,...,n\ell_3,\ell_4,...,\ell_n
      from the Fiat-Shamir transform
    • comm:=i=3ni(commicomm1)\mathbf{comm} := \sum_{i=3}^n \ell_i\cdot(\mathbf{comm}_i - \mathbf{comm}_1)
    • check
      Verify(comm1,comm2,π1)=1\mathsf{Verify}(\mathbf{comm}_1,\mathbf{comm}_2,\pi_1)=1
    • check
      Verify(comm,1G,π2)=1\mathsf{Verify}(\mathbf{comm},1_\mathbb{G},\pi_2)=1

Pedersen-ElGamal proof of equality

The Pedersen-ElGamal proof of equality scheme in the Zei library is used for a very special situation for the Pedersen commitments and associated ElGamal ciphertexts. Particularly, the commitments and the ElGamal ciphertexts share the same message as well as the same randomness. The only difference is that, in the commitment, the random scalar
r\mathbf{r}
is multiplied over an independent group generator
H\mathbf{H}
, while in the ciphertext,
r\mathbf{r}
is multiplied over some public key
pk\mathsf{pk}
.
The Pedersen-ElGamal proof of equality has the following syntax.
  • Prove(m,r,pk,ct,comm)π\mathsf{Prove}(\mathbf{m},\mathbf{r},\mathsf{pk},\mathsf{ct},\mathbf{comm})\rightarrow \pi
    :
    • let matrix
      M\mathbf{M}
      be:
      M:=(0GGGpkGH)\mathbf{M} := \left(\begin{array}{cc} 0_\mathbb{G} & \mathbf{G}\\ \mathbf{G} & \mathsf{pk}\\ \mathbf{G} & \mathbf{H} \end{array}\right)
    • let vector
      x\vec{\mathbf{x}}
      be:
      x:=(mr)\vec{\mathbf{x}} := \left(\begin{array}{cc} \mathbf{m} & \mathbf{r} \end{array}\right)
    • output
      π:=MartixSigma.Prove(M,x)\pi := \mathsf{MartixSigma}.\mathsf{Prove}(\mathbf{M},\vec{\mathbf{x}})
  • Verify(pk,ct,comm,π):=b{0,1}\mathbf{Verify}(\mathsf{pk},\mathsf{ct},\mathbf{comm},\pi) := b\in\{0,1\}
    :
    • let matrix
      M\mathbf{M}
      be:
      M:=(0GGGpkGH)\mathbf{M} := \left(\begin{array}{cc} 0_\mathbb{G} & \mathbf{G}\\ \mathbf{G} & \mathsf{pk}\\ \mathbf{G} & \mathbf{H} \end{array}\right)​
    • let vector
      yy\vec{\mathbf{y}}y​
      be:
      y:=(ctcomm)\vec{\mathbf{y}} := \left( \begin{array}{cc} \mathsf{ct} & \mathbf{comm} \end{array} \right)
    • check
      MatrixSigma.Verify(M,y,π)=1\mathsf{MatrixSigma}.\mathsf{Verify}(\mathbf{M},\vec{\mathbf{y}},\pi)=1

Rescue hash function

The Rescue hash function implementation in the Zei library follows this reference implementation. The test against the reference implementation shows that the implementation has been correctly implemented.