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\approx 2^{254}$.

ElGamal Encryption

Let us denote any canonical generator of $G$ by $g$ (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\in \mathbb{F}_p$ uniformly at random. Moreover, the public key is then computed $h=g^x \in 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. $\mathrm{Enc}(h, m) = (g^r, h^rm) \in 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: $\mathrm{Dec}(x, (c_1, c_2)):= c_2\cdot 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)\in \mathbb{F}_r: y^2=x^3 - 17\}$

The simplest encoding would be then $x\mapsto (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.