Planning issue

[tarcieri]

We've had various interest in having a @RustCrypto implementation of ElGamal. This issue is intended for discussion and planning around how it should be implemented.

While there are existing implementations of ElGamal in its various forms in Rust, most of them are specialized to specific elliptic curve groups. One way a new implementation can differentiate itself is by being implemented generically over elliptic curve groups. The group crate provides a system of traits which make it possible for the implementation to be generic over curve groups (and potentially other types of groups). Our RustCrypto/elliptic-curves curve implementations all support these traits.

A generic implementation is desirable for a number of reasons, but one in particular is to support curves with a larger field modulus like NIST P-384, which would make it possible to encrypt a 256-bit symmetric secret.

Some additional features which might be nice are k-of-n threshold ElGamal encryption (using e.g. Pedersen secret sharing) and additively homomorphic encryption.

cc to some people who have worked on ElGamal implementations in Rust who might be interested in contributing: @iquerejeta @eleanor-em @isislovecruft

[iquerejeta]

I'd be happy to implement ElGamal using the group crate. Adding additively homomorphic encryption should be fairly easy. For k-of-n threshold encryption, it might be a bit trickier if we want to do decentralised key generation. While encryption/decryption or centralised key distribution should be straight forward, the distributed key generation protocol should be a crate on its own IMO. I had a try at having a PoC for DKG for DLog based systems here.

I should have some free time this weekend - I might give it a go :)

[tarcieri]

I believe the state-of-the-art is Verifiable Secret Sharing, although I'm not particularly familiar with those schemes

[iquerejeta]

My suggestion is to offer a centralised key distribution mechanism (based on Shamir Secret Sharing) in the crate of ElGamal. This is still useful, for example if you want to distribute your own key across several devices, you can use that (you trust yourself). A verifiable secret sharing protocol is a bit more involved, and needs checks that participants are not misbehaving, with several rounds. IMO that should be a crate on its own - not only it will be a large piece of code, but it could be used with other DLog systems, such as Schnorr signatures.

Therefore, I'd suggest to have a centralised mechanism in the ElGamal crate, and leave verifiable secret sharing for a different crate.

[iquerejeta]

One of the difficulties of using ElGamal over elliptic curves is how do we encode messages? We need to encode them as elliptic curves. One place were ElGamal is often times used is for additively homomorphic encryption (sometimes called as 'lifted el gamal'), where one encodes an integer a as [a]G, and then, to decrypt, you brute force the value.

This is not useful for generic messages. Any ideas here? I'm not an expert on how to encode messages as elliptic curve points.

[tarcieri]

The associated group::Group::Scalar is bounded on the PrimeField trait which has an associated Repr type which is a generic bytestring that acts as an encoding for that Scalar, although the API is somewhat awkward in generic code, since you initialize it with Default and then write into it with AsMut<[u8]>, then use PrimeField::from_repr to attempt to decode it into the associated Scalar type.

The endianness is also curve-specific, so the specific way a message needs to be formatted into a bytestring varies from curve-to-curve depending on if they use a little or big endian encoding for scalars.

[iquerejeta]

But what you encrypt in ElGamal is a group element, not its associated scalar. Unless you use 'lifted' ElGamal, in which case, the message space must be really small, as you have to brute force it.

[tarcieri]

@iquerejeta there's a GroupEncoding trait for group elements

[iquerejeta]

But not all bytes have a corresponding group element. Say that you want to encrypt a random byte string the size of the base field. Only ~1/2 of those byte strings will be points in the curve. How do you handle the cases where the message is not a valid X coordinate?

[tarcieri]

Absent having an actual specification to implement, you'd need to provide one or more strategies.

Potentially we could leverage things from elliptic-curve instead of just group. Some of the traits in elliptic_curve::hash2curve might potentially be useful.

Barring that, it seems like you could do something like the naive hash-to-curve methods where if the message isn't a valid x-coordinate, you increment and retry (reserving a bit for that purpose)

[iquerejeta]

The hash to curve does not have an inverse (not always at least). So for encryption it does not seem to be the solution. My suggestion would be that at a first go, we expose encryption algorithms that work with group elements, and it is up to the user to decide how to encode their message. And then we expose an encryption function for u32 or u64 that allow for homomorphic operations with the ciphertext.

if the message isn't a valid x-coordinate, you increment and retry (reserving a bit for that purpose)

Yes, we could try something like that. I wonder if one bit is enough though. We'd have to look into that closer, but I'd say that we need more than one bit for that. Say the base field has 32 bytes. Then we could use 30 bytes for encoding the message, and 2 bytes for a counter:

    ┏━━━━━━━━━━━━━━━━━━━━━━━┯━━━━━━┓
    ┃         msg 30B       │ctr 2B┃
    ┗━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━┛
    <--------- 32 bytes  ---------->

Maybe one byte would be enough though 🤷

[iquerejeta]

In any case, I think that this is too speculative - I'd rather expose ElGamal just for the homomorphic property, which is usually what it is used for. I'd bee concerned of using it for any other scenario

https://en.wikipedia.org/wiki/Chosen-ciphertext_attack