ElGamal encryption, decryption, and rerandomization, with circom support

zk-s[nt]arks
1

MACI anonymization requires ElGamal cryptographic functions in zero knowledge. Support for anonymization in MACI will come sometime in the future, but I took a stab at implementing its required building blocks:

This library implements ElGamal encryption, decryption, and rerandomization in Typescript for the BabyJub elliptic curve. It also provides decryption and rerandomization circuits written in circom.

A quick note about how it encodes plaintext. We define a plaintext value as a BigInt in the BabyJub finite field. To encrypt it, we need to first convert it into a safe BabyJub elliptic curve point. Instead of using a map-to-curve function, the encodeToMessage function generates a random value r, computes g ^ {r}, and outputs both g ^ {r} and the x-increment e that must be added to the plaintext to obtain the x-value of g ^ {r}.

The ciphertext is therefore two elliptic curve points and one field element: (c_1, c_2, e).

After decrypting (c_1, c_2) to obtain the elliptic curve point m, we convert it to the original plaintext by computing m_x - e where m_x is the x-coordinate of m.

I’d love any feedback and suggestions on how to improve it. Thanks to @kobigurk, @snjax, and others in the iden3 Telegram group for their help.

6 Likes
2

I see the decryption and rerandomization, but not the encryption. Does it exist?
Thanks!

3

I couldn’t find the encryption circuit either. But this is what I came up with:

pragma circom 2.1.2;

include "../lib/circomlib/circuits/bitify.circom";
include "../lib/circomlib/circuits/escalarmulfix.circom";
include "../lib/circomlib/circuits/escalarmulany.circom";
include "../lib/circomlib/circuits/babyjub.circom";

template ComputeC2() {
    signal input r1Bits[253];
    signal input r2;
    signal input messageScalar;
    signal input recipentPublicKey[2];
    signal output xout;
    signal output yout;
    signal output xDelta;


    signal rP[2] <== EscalarMulAny(253)(p <== recipentPublicKey, e <== r1Bits);


    var BASE8[2] = [
        5299619240641551281634865583518297030282874472190772894086521144482721001553,
        16950150798460657717958625567821834550301663161624707787222815936182638968203
    ];

    signal r2Bits[253] <== Num2Bits(253)(r2);
    signal randomPoint[2] <== EscalarMulFix(253, BASE8)(r2Bits);


    (xout, yout) <== BabyAdd()(x1 <== rP[0], y1 <== rP[1], x2 <== randomPoint[0], y2 <== randomPoint[1]);

    xDelta <== randomPoint[0] - messageScalar;
}
1 Like
4

I am bringing up this discussion again because I believe it may be of interest to everyone in here.

The teams at 0x3327 and Privacy & Scaling Explorations (PSE) collaborated on an MVP a few months ago. Although the work is currently on pause but planned (according to the MACI roadmap). Feedback and suggestions on the current design of the solution would be greatly appreciated. I hope will soon become a reality to provide unconditional voter privacy in MACI.

All relevant information can be found in the issue #796 on the MACI repository - kudos to Sam for bringing everything together!

1 Like
5

A few quick comments: