Comparison to your classic elgamal repository

[numtel]

Hello, I'm new to writing Circom circuits and was wondering about the security status of this repository versus the classic elgamal implementation repository.

As far as I can tell, both repos use 254 bit private keys so it seems like the warning about intentional insecurity should also apply to this code.

Is this correct? If so, is there a way to encrypt/decrypt using a larger 2048 bit key?

Thanks

[Shigoto-dev19]

That's a fair point @numtel, and that's the reason that motivated me to try to do the classic ElGamal implementation on Circom.

• Given that the inputs of a circuit are constrained to the field element size, an encryption key is accordingly constrained to be 254-bit.
• I was trying to optimize the ElGamal Circom Circuit and I found out that the classic implementation with normal exponentiation is more efficient the the EC implementation. Regarding that, exponentiation is less expensive (addition/ multiplication gates) than EC operations over Circom.
• It is evident that ECDH(Elliptic Curve Diffie-Hellman) can provide the same level of security with shorter key lengths compared to classical DH. Hence, a 254-bit key ensures the 128-bit security when encrypting over elliptic curves, which not the case the classic one as explained in the readme.
• For a more detailed documentation on my work, I share with you this notion page that I prepared for better understanding EC ElGamal over Elliptic Curves.
  • Note: The notion page was an old documentation of ElGamal over the alt_bn128 curve that I hardcoded its implementation myself --> it is not explaining the babyjubjub curve.

[numtel]

Thanks for the response. This is definitely at the limit of my mathematical understanding but I've read through this linked notion page. Pollard's rho seems like the biggest potential vulnerability? Seeing the potential attacks listed was very helpful because in my calculations, a brute force attack was infeasible. Of course, circom limits the key size to the field element size but I think I was wondering if it were possible to split a longer key into multiple encryptions if necessary. Although the ciphertext doubles the plaintext length with each encryption, it seems possible albeit cumbersome.

Some backstory about my application: At the Bogota 2022 hackathon, I was on the Ethereum Social Contract team. After what had gone down with OFAC and Tornado Cash, we wanted to make a legally-compliant mixer (by allowing a single very private key [like as secret as the ICANN DNS key] access to decrypt transactions) but I had no clue at the time how to implement it.

We need a method of proving that a ciphertext corresponds to a particular plaintext value encrypted by a specific key. At this time, I see using the encode/encrypt circuits from this repo added to a fork of Semaphore v4 that also outputs the ciphertext and public key as part of its circuit's public signals.

I've started trying to implement this but I'm running into the issue of the encoding done in javascript not matching the encoding done by the circuit, since I'll be encoding the identityCommitment as the plaintext value. I don't know if I'm doing something wrong or if there is something missing here.

See this failing test: https://github.com/Shigoto-dev19/ec-elgamal-circom/commit/2a5156f13a58417b7f7a42729b892af1fd5fb980 I noticed that I was comparing the wrong values. It should be:

            expect(prove_encode.publicSignals[0]).to.equal(encoded.x.toString());
            expect(prove_encode.publicSignals[1]).to.equal(encoded.y.toString());

:crossed_fingers: Nice, ok continuing on semaphore fork...

From your response, I gather that this repo is more secure than the classic version because of the EC used. As a result of this though, it limits the plaintext input to 32 bits. I think 32 bits of the identityCommitment would be enough for an MVP.

Again, thanks so much for this work

[Shigoto-dev19]

@numtel I am glad that my work is helpful to a fellow enthusiast.

• Pollard's rho seems like the biggest potential vulnerability:
  • answer: yes, because it is an attack to break down the security of the ECDLP.
  • The other attacks concern the security of the curve which is not the concern of a developer.
• My implementation of EC ElGamal was aimed to ensure additive homomorphism, that's why the message is encoded as a point on curve and later decoded breaking the ECDLP using baby-step giant-step algorithm.
  • Note that any change or any other encoding method would still be valid for ElGamal encryption but the scheme won't be homomorphic anymore which is crucial for voting systems(my case).
• Parsing circuit inputs using JS/TS whether using snarkjs or circom_tester is a pain to learn,
  • The elgamal-baby-jubjub-tester branch is a good resource to have an understanding of how to test and process circuit inputs in general.
• You can see my work merged in light-protocol which I describe as a hyper-optimized tornado-nova protocol on Solana.
  • circuit-lib.circom for circom circuits.
  • circuit-lib.js for TS client code and tests.
• If you just want to use an encryption algorithm, then it might be useful to encrypt and check integrity of secret asserting on ciphertext as public input.
  • For this, I used my forked poseidon-encryption algorithm.
• I see you are working hard on your protocol, keep grinding :100:
• It is a pain in the neck to find good resources or documentation of circom circuits and that's the reason that I started publishing some circuits with better documentation to my understanding.

I hope my work will be of more help to you and others :)