Skip to main content

Cryptography Primitives

ElGamal encryption

The ElGamal encryption in the Zei library is defined over the Ristretto curve, where the base G\mathbf{G} is the base point of the Ristretto group. Note that the message m\mathbf{m} is encoded into a group element as mG\mathbf{m}\cdot \mathbf{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 P\mathbb{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)σ:\mathsf{Sign}(\mathsf{sk},\mathbf{m})\rightarrow \sigma:

    • r ⁣$F\mathbf{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 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
    • 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 y\vec{\mathbf{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.