1
$\begingroup$

I am working on an efficient mental poker framework. I have implemented a functional and secure commutative encryption scheme based on ElGamal as described in:

http://groups.csail.mit.edu/cis/theses/weis-phd-thesis.pdf

However, shuffling and dealing an entire deck is causing slowdown as the number of players involved in the game increases (more players means more commutative encryptions and decryptions). Even in initial, idealized tests things are pretty slow.

The system parameters currently used are an advisable 2048-bit safe prime (from RFC 5114) but I'm wondering if these key sizes are overkill in the case of something like mental poker where decryptions of relevant cards will happen within a few minutes and after the hand the security of the previous deck is irrelevant? This got me wondering in general if key sizes are flexible depending on "how long the encryption needs to last" - are there any guidelines here? Any pitfalls I'm not considering?

| improve this question | |
$\endgroup$
  • $\begingroup$ The thing with attacks on discrete logarithms is that they scale very sharply. That is once a parameter set is insecure, it's easy to compute discrete logarithms in that parameter set in a matter of minutes, but getting to this point requires a lot of computational work that scales with the group size. $\endgroup$ – SEJPM♦ Oct 21 '19 at 14:44
  • $\begingroup$ aha... yes this is what I was missing. So essentially you have to use reliably secure parameters, even for short lived encryptions. $\endgroup$ – ariel.py Oct 21 '19 at 14:55
  • $\begingroup$ You might want to consider a smaller EC curve (e.g. P192); that's not vulnerable to logjam-style attacks. $\endgroup$ – poncho Oct 21 '19 at 15:39
  • $\begingroup$ @poncho is it possible to get a commutative encryption scheme from EC cryptographic primitives though? (I know that's not a main part of the question but it is what is required for mental poker) $\endgroup$ – ariel.py Oct 21 '19 at 17:33
  • $\begingroup$ Depends on what you mean by "commutative encryption", but if you're happy with private keys, then yeah; the secret key is a value $a$; encryption of a point $X$ is $aX$; decryption of $Y = aX$ is $a^{-1}Y$; we have commutivity because $a(bX) = b(aX)$... $\endgroup$ – poncho Oct 21 '19 at 18:01
2
$\begingroup$

This got me wondering in general if key sizes are flexible depending on "how long the encryption needs to last" - are there any guidelines here? Any pitfalls I'm not considering?

Yes, you can down-scale the bit-length, e.g. to 1536-bit and it will still likely stay somewhat secure. But do note that for discrete-logarithm over finite fields based cryptosystems there's a steep cutoff in security. Once the parameters are so small that you can break the scheme, e.g. within a week or longer on your hardware, you get "precomputed" data that allows to find any discrete logarithm of interest in a matter of seconds / minutes.

This observation was widely made first with LogJam.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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