Cryptography Primitives

ElGamal encryption​​
The ElGamal encryption in the Zei library is defined over the Ristretto curve, where the base GG\mathbf{G}GGG
 is the base point of the Ristretto group. Note that the message mm\mathbf{m}mmm
 is encoded into a group element as m⋅Gm⋅G\mathbf{m}\cdot \mathbf{G}m⋅Gm⋅Gm⋅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})KeyGen(1λ)→(sk,pk)
:
​sk← ⁣$F\mathsf{sk} \leftarrow\!{\footnotesize \$} \hspace{3pt} \mathbb{F}sk←$F
​
​pk:=sk⋅G\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}pk:=sk⋅G
​
output (sk,pk)(\mathsf{sk},\mathsf{pk})(sk,pk)
​
​Enc(pk,m)→ct\mathsf{Enc}(\mathsf{pk}, \mathbf{m})\rightarrow \mathsf{ct}Enc(pk,m)→ct
:
​r← ⁣$F\mathbf{r}\leftarrow\!{\footnotesize \$} \hspace{3pt} \mathbb{F}r←$F
​
output ct:=EncWithRand(pk,m,r)\mathsf{ct} := \mathsf{EncWithRand}(\mathsf{pk},\mathbf{m},\mathbf{r})ct:=EncWithRand(pk,m,r)
.
​EncWithRand(pk,m,r)→ct\mathsf{EncWithRand}(\mathsf{pk},\mathbf{m}, \mathbf{r})\rightarrow \mathsf{ct}EncWithRand(pk,m,r)→ct
:
​ct1:=r⋅G\mathsf{ct}_1 := \mathbf{r}\cdot \mathbf{G}ct1​:=r⋅G
.
​ct2:=m⋅G+r⋅pk\mathsf{ct}_2 := \mathbf{m}\cdot \mathbf{G} + \mathbf{r}\cdot \mathsf{pk}ct2​:=m⋅G+r⋅pk
.
Output ct:=(ct1,ct2)\mathsf{ct} := (\mathsf{ct}_1,\mathsf{ct}_2)ct:=(ct1​,ct2​)
.
​Verify(sk,m,ct):=b∈{0,1}\mathsf{Verify}(\mathsf{sk},\mathbf{m},\mathsf{ct}):= \mathbf{b}\in\{0,1\}Verify(sk,m,ct):=b∈{0,1}
:
​(ct1,ct2):=ct(\mathsf{ct}_1, \mathsf{ct}_2) := \mathsf{ct}(ct1​,ct2​):=ct
​
check ct2−sk⋅ct1=?m⋅G\mathsf{ct}_2 - \mathsf{sk}\cdot \mathsf{ct}_1 \stackrel{?}{=} \mathbf{m}\cdot Gct2​−sk⋅ct1​=?m⋅G
​
​PartialDec(sk,ct):=m⋅G\mathsf{PartialDec}(\mathsf{sk}, \mathsf{ct}):= \mathbf{m}\cdot GPartialDec(sk,ct):=m⋅G
:
​(ct1,ct2):=ct(\mathsf{ct}_1, \mathsf{ct}_2) := \mathsf{ct}(ct1​,ct2​):=ct
​
output ct2−sk⋅ct1\mathsf{ct}_2 - \mathsf{sk}\cdot \mathsf{ct}_1ct2​−sk⋅ct1​
​
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}HybridEnc(sk,m)→ct
:
​r← ⁣$F\mathbf{r}\leftarrow\!{\footnotesize \$} \hspace{3pt} \mathbb{F}r←$F
​
​ct1:=r⋅G\mathsf{ct}_1 := \mathbf{r}\cdot \mathbf{G}ct1​:=r⋅G
​
derive an AES symmetric key k\mathbf{k}k
 from sk⋅ct1\mathsf{sk}\cdot\mathsf{ct}_1sk⋅ct1​
 using SHA256
​ct2:=AESEnc(k,m)\mathsf{ct}_2 := \mathsf{AESEnc}(\mathbf{k}, \mathbf{m})ct2​:=AESEnc(k,m)
​
output ct=(ct1,ct2)\mathsf{ct}=(\mathsf{ct}_1,\mathsf{ct}_2)ct=(ct1​,ct2​)
​
​HybridDec(sk,ct):=m\mathsf{HybridDec}(\mathsf{sk},\mathsf{ct}):= \mathbf{m}HybridDec(sk,ct):=m
:
​(ct1,ct2):=ct(\mathsf{ct}_1,\mathsf{ct}_2):= \mathsf{ct}(ct1​,ct2​):=ct
​
derive an AES symmetric key k\mathbf{k}k
 from sk⋅ct1\mathsf{sk}\cdot\mathsf{ct}_1sk⋅ct1​
 using SHA256
output m:=AESDec(k,ct2)\mathbf{m} := \mathsf{AESDec}(\mathbf{k}, \mathsf{ct}_2)m:=AESDec(k,ct2​)
​
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}PPP
 knows a scalar vector x⃗∈{0,1}n\vec{x}\in\{0,1\}^nx∈{0,1}n
 such that:
​M⋅x⃗T=y⃗​\mathbf{M}\cdot \vec{\mathbf{x}}^T = \vec{\mathbf{y}}​M⋅xT=y​​
​
where M∈Gm×n\mathbf{M}\in\mathbb{G}^{m\times n}M∈Gm×n
 is a matrix of group elements and y⃗∈Gm\vec{\mathbf{y}}\in\mathbb{G}^my​∈Gm
 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 \piProve(M,x)→π
:
append individual group elements in M\mathbf{M}M
 to the transcript
​r⃗← ⁣$Fn\vec{\mathbf{r}}\leftarrow\!{\footnotesize \$} \hspace{3pt}\mathbb{F}^nr←$Fn
​
​c⃗:=M⋅r⃗T\vec{\mathbf{c}} := \mathbf{M}\cdot \vec{\mathbf{r}}^Tc:=M⋅rT
​
append c⃗\vec{\mathbf{c}}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}}d:=βx+r
​
output π=(c⃗,d⃗)\pi = (\vec{\mathbf{c}}, \vec{\mathbf{d}})π=(c,d)
​
​Verify(M,y⃗,π):=b∈{0,1}\mathsf{Verify}(\mathbf{M},\vec{\mathbf{y}}, \pi):=\mathbf{b}\in\{0,1\}Verify(M,y​,π):=b∈{0,1}
​
​(c⃗,d⃗):=π(\vec{\mathbf{c}}, \vec{\mathbf{d}}) := \pi(c,d):=π
​
append individual group elements in M\mathbf{M}M
 to the transcript
append c⃗\vec{\mathbf{c}}c
 to the transcript
squeeze a challenge β\betaβ
 from the Fiat-Shamir transform
check M⋅d⃗=?β⋅y⃗+c⃗\mathbf{M}\cdot \vec{\mathbf{d}}\stackrel{?}{=} \beta\cdot\vec{\mathbf{y}} + \vec{\mathbf{c}}M⋅d=?β⋅y​+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}G
 with a generator G\mathbf{G}G
 with a scalar field F\mathbb{F}F
.
The Schnorr signature has the following syntax.
​KeyGen(1λ)→(sk,pk):\mathsf{KeyGen}(1^\lambda)\rightarrow(\mathsf{sk},\mathsf{pk}):KeyGen(1λ)→(sk,pk):
​
​sk← ⁣$F\mathsf{sk}\leftarrow\!{\footnotesize \$} \hspace{3pt}\mathbb{F}sk←$F
​
​pk:=sk⋅G\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}pk:=sk⋅G
​
output (sk,pk)(\mathsf{sk},\mathsf{pk})(sk,pk)
​
​Sign(sk,m)→σ:Sign(sk,m)→σ:Sign(sk,m)→σ:
​
​r← ⁣$F\mathsf{r}\leftarrow\!{\footnotesize \$} \hspace{3pt}\mathbb{F}r←$F
​
​R:=r⋅G\mathbf{R} := \mathbf{r} \cdot \mathbf{G}R:=r⋅G
​
append the message m\mathbf{m}m
, the public key pk:=sk⋅G\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}pk:=sk⋅G
, and R\mathbf{R}R
 to the transcript
squeeze a challenge c\mathbf{c}c
 from the Fiat-Shamir transform
​s:=r+c⋅sk\mathbf{s} := \mathsf{r} + \mathbf{c}\cdot \mathsf{sk}s:=r+c⋅sk
​
output σ:=(R,s)\sigma := (\mathbf{R}, \mathbf{s})σ:=(R,s)
​
​Verify(pk,m,σ):=b∈{0,1}\mathsf{Verify}(\mathsf{pk},\mathbf{m},\sigma) := \mathbf{b}\in\{0,1\}Verify(pk,m,σ):=b∈{0,1}
:
​(R,s):=σ(\mathbf{R}, \mathbf{s}) := \sigma(R,s):=σ
​
append the message mm\mathbf{m}mmm
, the public key pk:=sk⋅G\mathsf{pk} := \mathsf{sk}\cdot \mathbf{G}pk:=sk⋅G
, and R\mathbf{R}R
 to the transcript
squeeze a challenge c\mathbf{c}c
 from the Fiat-Shamir transform
check R+c⋅pk=?s⋅G\mathbf{R} + \mathbf{c}\cdot \mathsf{pk} \stackrel{?}{=} \mathbf{s}\cdot \mathbf{G}R+c⋅pk=?s⋅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}G
 and H\mathbf{H}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}Commit(m,r)→comm
:
output m⋅G+r⋅H\mathbf{m}\cdot\mathbf{G} + \mathbf{r}\cdot\mathbf{H}m⋅G+r⋅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}_1comm1​
 and comm2\mathbf{comm}_2comm2​
, whose blinding factors are correspondingly r1,r2\mathbf{r}_1, \mathbf{r}_2r1​,r2​
, commit to the same value m\mathbf{m}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 \piProve(comm1​,comm2​,m,r1​,r2​)→π
:
let matrix M\mathbf{M}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)M:=(GG​H1G​​1G​H​)
​
let vector x⃗\vec{\mathbf{x}}x
 be:
​x⃗:=(mr1r2)\vec{\mathbf{x}} := \left(\begin{array}{lll} \mathbf{m} & \mathbf{r}_1 & \mathbf{r}_2 \end{array}\right)x:=(m​r1​​r2​​)
​
output π=MatrixSigma.Prove(M,x⃗)\pi = \mathsf{MatrixSigma}.\mathsf{Prove}(\mathbf{M}, \vec{\mathbf{x}})π=MatrixSigma.Prove(M,x)
​
​Verify(comm1,comm2,π):=b∈{0,1}\mathsf{Verify}(\mathbf{comm}_1,\mathbf{comm}_2,\pi) := \mathbf{b}\in\{0,1\}Verify(comm1​,comm2​,π):=b∈{0,1}
:
let matrix M\mathbf{M}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)M:=(GG​H1G​​1G​H​)
​
let vector y⃗\vec{\mathbf{y}}y​
 be:
​y⃗:=(comm1,comm2)\vec{\mathbf{y}} := \left(\mathbf{comm}_1, \mathbf{comm}_2\right)y​:=(comm1​,comm2​)
​
check MatrixSigma.Verify(M,y⃗,π)=1\mathsf{MatrixSigma}.\mathsf{Verify}(\mathbf{M},\vec{\mathbf{y}},\pi) = 1MatrixSigma.Verify(M,y​,π)=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 \piBatchProve([commi​]1n​,m,[ri​]1n​)→π
:
append G,H,[commi]1n\mathbf{G},\mathbf{H},[\mathbf{comm}_i]_1^nG,H,[commi​]1n​
 to the transcript
​π1←Prove(comm1,comm2,m,r1,r2)\pi_1 \leftarrow \mathsf{Prove}(\mathbf{comm}_1,\mathbf{comm}_2,\mathbf{m},\mathbf{r}_1,\mathbf{r}_2)π1​←Prove(comm1​,comm2​,m,r1​,r2​)
​
squeeze ℓ3,ℓ4,...,ℓn\ell_3,\ell_4,...,\ell_nℓ3​,ℓ4​,...,ℓn​
from the Fiat-Shamir transform
​comm:=∑i=3nℓi⋅(commi−comm1)\mathbf{comm} := \sum_{i=3}^n \ell_i\cdot(\mathbf{comm}_i - \mathbf{comm}_1)comm:=∑i=3n​ℓi​⋅(commi​−comm1​)
​
​r:=∑i=3nℓi⋅(ri−r1)\mathbf{r} := \sum_{i=3}^n \ell_i\cdot (\mathbf{r}_i - \mathbf{r}_1)r:=∑i=3n​ℓi​⋅(ri​−r1​)
​
​π2←Prove(comm,1G,0F,r,0F)\pi_2 \leftarrow\mathbf{Prove}(\mathbf{comm},1_{\mathbb{G}}, 0_{\mathbb{F}}, \mathbf{r}, 0_{\mathbb{F}})π2​←Prove(comm,1G​,0F​,r,0F​)
​
output π:=(π1,π2)\pi := (\pi_1, \pi_2)π:=(π1​,π2​)
​
​BatchVerify([commi]1n,π):=b∈{0,1}\mathsf{BatchVerify}([\mathbf{comm}_i]_1^n, \pi) := \mathbf{b}\in\{0,1\}BatchVerify([commi​]1n​,π):=b∈{0,1}
:
append G,H,[commi]1n\mathbf{G},\mathbf{H},[\mathbf{comm}_i]_1^nG,H,[commi​]1n​
 to the transcript
​(π1,π2):=π(\pi_1,\pi_2) := \pi(π1​,π2​):=π
​
squeeze ℓ3,ℓ4,...,ℓn\ell_3,\ell_4,...,\ell_nℓ3​,ℓ4​,...,ℓn​
 from the Fiat-Shamir transform
​comm:=∑i=3nℓi⋅(commi−comm1)\mathbf{comm} := \sum_{i=3}^n \ell_i\cdot(\mathbf{comm}_i - \mathbf{comm}_1)comm:=∑i=3n​ℓi​⋅(commi​−comm1​)
​
check Verify(comm1,comm2,π1)=1\mathsf{Verify}(\mathbf{comm}_1,\mathbf{comm}_2,\pi_1)=1Verify(comm1​,comm2​,π1​)=1
​
check Verify(comm,1G,π2)=1\mathsf{Verify}(\mathbf{comm},1_\mathbb{G},\pi_2)=1Verify(comm,1G​,π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}r
 is multiplied over an independent group generator H\mathbf{H}H
, while in the ciphertext, r\mathbf{r}r
 is multiplied over some public key pk\mathsf{pk}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 \piProve(m,r,pk,ct,comm)→π
:
let matrix M\mathbf{M}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)M:=⎝⎛​0G​GG​GpkH​⎠⎞​
​
let vector x⃗\vec{\mathbf{x}}x
 be:
​x⃗:=(mr)\vec{\mathbf{x}} := \left(\begin{array}{cc} \mathbf{m} & \mathbf{r} \end{array}\right)x:=(m​r​)
​
output π:=MartixSigma.Prove(M,x⃗)\pi := \mathsf{MartixSigma}.\mathsf{Prove}(\mathbf{M},\vec{\mathbf{x}})π:=MartixSigma.Prove(M,x)
​
​Verify(pk,ct,comm,π):=b∈{0,1}\mathbf{Verify}(\mathsf{pk},\mathsf{ct},\mathbf{comm},\pi) := b\in\{0,1\}Verify(pk,ct,comm,π):=b∈{0,1}
:
let matrix M\mathbf{M}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)​M:=⎝⎛​0G​GG​GpkH​⎠⎞​​
​
let vector y⃗y​\vec{\mathbf{y}}y​y​y​
 be:
​y⃗:=(ctcomm)\vec{\mathbf{y}} := \left( \begin{array}{cc} \mathsf{ct} & \mathbf{comm} \end{array} \right)y​:=(ct​comm​)
​
check MatrixSigma.Verify(M,y⃗,π)=1\mathsf{MatrixSigma}.\mathsf{Verify}(\mathbf{M},\vec{\mathbf{y}},\pi)=1MatrixSigma.Verify(M,y​,π)=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.
Bulletproofs
Delegated Schnorr
Last modified 4mo ago
Cryptography Primitives

ElGamal encryption​​

Hybrid encryption​​

Matrix Sigma protocol​​

Schnorr signature​​

Pedersen commitment over Ristretto​​

Chaum-Pedersen proof of commitment equality​​

Pedersen-ElGamal proof of equality​​

Rescue hash function​​

ElGamal encryption

Hybrid encryption

Matrix Sigma protocol

Schnorr signature

Pedersen commitment over Ristretto

Chaum-Pedersen proof of commitment equality

Pedersen-ElGamal proof of equality

Rescue hash function
