SNARK-friendly Asymmetric Encryption

For the use in anonymity revoking we require a SNARK-friendly asymmetric encryption. Recall that we use the BN254 curve for our cryptography. Let's denote the scalar field of BN254 by $\mathbb{F}_r$​ — a prime field with relements. In pseudocode we use the Scalar type — this is exactly the same as $\mathbb{F}_r$.​

Grumpkin Curve

For asymmetric encryption we use the familiar ElGamal cryptosystem, however to make it snark-friendly we need a specific choice of the group we work with. Specifically let $G$ be the Grumpkin elliptic curve — see Grumpkin. This group has the following properties:

• The base field of Grumpkin is $x^2$$\mathbb{F}_r$​ thus in other words, the group consists of pairs (affine coordinates) or triples (projective coordinates) of elements of $\mathbb{F}_r$​ that satisfy a certain simply arithmetic condition. Similarly, the group operation is defined in terms of a small constant number of arithmetic operations in $\mathbb{F}_r$​.

• The cardinality of $G$ is $∣G∣=p$ with $p$ being a prime, roughly $p≈2254$.

ElGamal Encryption

Let us denote any canonical generator of GG by gg (this is in principle any element of the group that is not the identity element, but it is typically chosen in a specific way). The ElGamal cryptosystem that we use is characterized by the following procedures.

1. Key generation. The procedure KeyGen()outputs the private key $x∈\mathbb{F}_p$​ uniformly at random. Moreover, the public key is then computed $h=g^x∈G$ and published.

2. Encryption. Any party having access to the public key $h$ can encrypt a message $m$. We assume the messages come from $G$ itself. $Enc(h,m)=(g^r,h^rm)∈G^2$

   where $r$ is chosen uniformly at random from $\mathbb{F}_p$​.

3. Decryption. The private key holder, given the ciphertext (c1, c2) computes: $Dec(x,(c_1,c_2)):=c_2⋅c_1^{−x}$

   and as one can easily verify, the original message $m$ is recovered this way.

Encoding into the message space

Note that the message space in ElGamal above is a little weird — points on the Grumpkin Curve $G$. In circuits we deal with elements in $\mathbb{F}_r$​ hence ideally we would like to encode elements of $\mathbb{F}_r$​ into $G$. That task however is unfortunately not that simple, because the encoding must be also snark-friendly. Recall that

$G={(x,y)∈\mathbb{F}_r:y^2=x^3−17}$

The simplest encoding would be then $x↦(x,y)$ with $y$ chosen so as to make this point on curve. This however doesn't work, because not every element $x$ is the first coordinate of some grumpkin element. However, it ALMOST works, in the sense that for a random $x$ the probability that $y$ exists is close to 1/2. This way half of all scalars can be trivially encoded into $G$.

In our application of ElGamal, we need to encrypt key(id) a scalar element that is pseudorandomly generated from id. We require that id has this property that key(id) is encodeable as a group element in the sense above, otherwise the idis considered invalid. A user can use only a valid id for its account because validity is checked in the first transaction.