# 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 `r`elements. 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](https://aztecprotocol.github.io/aztec-connect/primitives.html#2-grumpkin---a-curve-on-top-of-bn-254-for-snark-efficient-group-operations). 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 `id`is considered invalid. A user can use only a valid `id` for its account because validity is checked in the first transaction.