1
$\begingroup$

I was reading this paper by Philippe Golle on using the homomorphic properties of ElGamal encryption to play a game of mental poker (i.e. cryptographically secure poker without a trusted third party dealer). I decided that it would be a good project to try to implement some basic version of but I quickly ran into some problems.

It seems that ElGamal (and RSA, for that matter) are considered generally insecure and the prevailing advice seems to be to avoid them. Thus, the two big options for partial homomorphism fall are off the table for games with high enough stakes. Furthermore, I couldn't really find any other standardized cryptosystems that have this property and work on discrete values and not approximations (necessary to implement the algorithm outlined in the paper). Am I missing something obvious?

I guess my question is: if Golle was writing this paper in 2022, what would he have proposed instead of ElGamal for games of poker with high enough stakes?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

There are two obvious things to mention. First, with the caveat that I only briefly skimmed the paper you linked, I see section 3 state that the encryption scheme used needs 3 properties, namely

  1. additive homomorphism,

  2. "modular plaintext comparison", e.g. checking if $Enc(c)$ is an encryption of 0,

  3. a distributed key generation protocol.

it would be easier to answer this question if you could formalize precisely what operations/properties you need though.

Lattice-based

That all being said, by far the most common type of partially homomorphic encryption scheme currently are R(LWE) variants of encryption. This satisfy a "noisy" variant of additive homomorphism though, meaning that one can only evaluate some a priori bounded number of additive homomorphisms. If you need arbitrary additions, this can be done as well, for example the schemes FHEW/TFHE are perhaps suited well for this (note that these are fully homomorphic encryption schemes, although they are particularly efficient ones). It is plausible/likely this is fine in your case though.

For the other two points, I would need to more carefully read/know the precise requirements of the scheme. It seems plausible to me that RLWE-based encryption schemes could work for your situation though, but I don't bother trying to fill out details because...

El-Gamal based:

While you are right that "classical" El-Gamal (say based on finite-field Diffie Hellman) is somewhat dated, you can use El-Gamal based on elliptic curve groups. This is "modern" (although still weak against quantum computers, if this is your concern), and likely easier for your purposes than working out the details of how to use a lattice-based scheme. Note that for general encryption there is little reason to use elliptic curve variants of El Gamal (see here for details), but since you specifically want to use the additive homomorphism, using El Gamal makes sense.

If you are against using Elliptic Curve El Gamal for some reason, your main remaining options are lattice-based schemes. This will require more work to figure out the details of, which will be easier for people on this website to help you with if you can say precisely what requirements you have for the underlying encryption scheme.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Not all applications of additive isomorphism are possible with ElGamal. If we want to deal with integers up to $m$, the cost of decryption grows as $\sqrt m$, and that's often a limitation. I think there are some limitations to RLWE too, but I don't know exactly what they are. $\endgroup$
    – fgrieu ♦
    Commented Feb 28, 2022 at 11:30
  • $\begingroup$ Thank you for your answer. I think the lattice based schemes are maybe a bit too complex for what I'm trying to achieve but I will look into them as well. Can you provide a bit of context as to why doing ElGamal on elliptic groups is better than doing it on finite-field Diffie Hellman? I understand that I haven't been particularly precise in my question but that's because I'm very new to cryptography. $\endgroup$
    – user3450456
    Commented Feb 28, 2022 at 13:12
  • $\begingroup$ @fgrieu for RLWE one has to choose larger parameters to enable more additions, so decryption costs (sort of) increase implicitly through the larger parameters, but the growth should be logarithmic. One can ignore all of this by using TFHE/FHEW, which is FHE that "bootstraps after every operation". Despite being FHE, it is relatively performant, for example ~.1 s/op a few years ago (and probably better now). This is both bad compared to ~3GHz processors, and I get the impression OP needs ~60 ops, so perhaps may be reasonable. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 28, 2022 at 21:46
  • $\begingroup$ @user3450456 Attacks against Finite-field Diffie-Hellman are stronger, so one has to choose larger parameters for similar levels of security. Depending on particular relationships between parameters these can be gigantic (characteristic 2 diffie hellman is totally broken --- academics have solved ~30k bit DLOG), to simply much larger (~850-bit DLOGs are within reach of academics). For this reason, a "modern" Finite-Field Diffie hellman implementation should probably use between 2k-4k bit sizes for parameters. This is compared with Elliptic-Curve group protocols, which are in the ... $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 28, 2022 at 21:49
  • $\begingroup$ few hundred bit range. Of course bit size doesn't entirely control complexity, but it is a fairly relevant parameter still, and things must be roughly an order of magnitude larger when working with finite fields. This also ignores that current thought is that of the two, attacks on finite fields are more likely to improve --- improving elliptic curve group attacks would require showing they are "non-generic" --- while finite field discrete logarithms could plausibly be dramatically improved by adapting ~2012 work on the function field sieve to finite fields (I think, but do not know details) $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 28, 2022 at 21:51
3
$\begingroup$

ElGamal and RSA «are considered generally insecure» IF one assumes Cryptographically Relevant Quantum Computers. But these remain highly hypothetical. The world (internet, banking, mobile..) currently runs on cryptosystems which, when asymmetric, are theoretically vulnerable to these hypothetical CRQCs: RSA, ECDSA, EdDSA, ECIES…

Paillier's cryptosystem is worth consideration when one disregards the CRQC hypothesis. It's simple¹, provides additively homomorphic encryption of (possibly signed) integers with a small and clear restriction², has efficiency within a small constant factor of RSA decryption (thus bearable in many applications), is patent-free, is provably reducible to a mathematical problem widely believed to be super-polynomial for classical computers, and is regarded as secure as RSA for the same prime size.

The main reason Paillier's cryptosystem is not much used in practice is, I believe, that homomorphic encryption in general is not in high demand.

Addition: Paillier encryption is not vulnerable to padding oracle attack or poor choice of padding, since (contrary to RSA) it needs no padding. It's vulnerable to attacks on implementation about as RSA is, including exploiting poor random number generators at key generation or use, side channels and fault attacks. The similarity to RSA is good news, since effective countermeasures against attacks are known for RSA, and can largely be adapted to Paillier.

¹ Especially with the common restriction of $n$ the product of two primes of equal size, and $g=n+1$.

² Plaintext that exceeds $n$ gets reduced modulo $n$, with $n$ a public parameters huge enough that's not an issue for anything that can be counted, including any meaningful fraction of currency, even atoms. Contrast will the additively homomorphic variant of ElGamal, which has severe restrictions about the integers it can add.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks, I'll look into Paillier as I'm not particularly worried about quantum security. Me saying that ElGamal and RSA might be considered insecure does not stem from worry about quantum security but for worries of prime generation, side-channel attacks, and most specifically attacks through padding oracles as for the algorithm in the paper to work, I can't pad the plaintext before encryption. $\endgroup$
    – user3450456
    Commented Feb 28, 2022 at 13:14
  • $\begingroup$ @user3450456 if you are worried about various side-channels, this is a (relative) benefit of lattice-based schemes. There are relatively strong leakage resilience results known about secret key bits leaking (compared to RSA type things, where Coppersmith's method is quite powerful). Moreover, most of the (secret) randomness generation done is fairly straightforward. the only exception is the "LWE error $e$", although for encryption even this can be done in a straightforward way by choosing it from a "centered binomial distribution". $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 28, 2022 at 21:59
  • $\begingroup$ there are not padding oracle type attacks (at least that I know of) against lattice-based schemes, although there are other IND-CCA-type attacks, so perhaps it is a wash here. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 28, 2022 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.