[SUGGESTION NEEDED] A request for suggestion on furthering the discussion over ElGamal

[Weikeng Chen]

Hi Werner, Niibe, and other developers,


This is a request for a suggestion.

I am going to continue my post last month on the ElGamal in gcrypt. I
am sorry to say gcrypt is the beginning of many wrong implementations
of ElGamal. Some Github repo owners use this to show their
implementation is correct. It uses a safe prime but the generator is
still wrong. This makes the ElGamal not semantic secure.

My post in September "question on ElGamal implementation" has made the
beginning of that. I would like to make a post to continue this
further and make sure that we fix ElGamal eventually. Niibe has
mentioned that ElGamal used for hybrid encryption in general (which
would be secure), but we two agree that we should improve. Some
programmers may use ElGamal for homomorphic encryption and computation
over encrypted data.


Before my post which would explain the details, I have some observations:

(1) Showing the current ElGamal implementation is not secure would be
easy, as Wikipedia and some 17 years ago papers have some information.
If we consult expert cryptographers in the field. They can clearly say
the current implementation is insecure. --------- Do you think an
experiment or proof-of-concept will be necessary?

(2) Providing a corrected version is not trivial -- it is not just
making the generator correct. We also need to embed the message (a
binary string) into an element in a specific subgroup (and recovered
later). There are many papers, and many years ago, to say some ideas
about this encoding. One of that is my proposed solution.

However, there is no official example. Even the original paper by El
Gamal is not secure under this concern. Besides gcrypt, ---------- how
to find a gold standard for ElGamal implementations? OpenSSL
implements DH (also wrong but not a big deal in the real world,
because it is for DH key exchange not ElGamal) ------ and one thing
for sure, how to make it easy to follow in order to persuade a
sufficiently large community to accept this change?

(3) The solution will be incompatible with existing applications
running ElGamal in gcrypt -- their ciphertexts will be undecryptable.
----- What is your opinion to deal with this?



My question list is:

(1) What do you think is needed, served as sufficient evidence, to
persuade people to believe (1) current implementation is wrong; (2)
the proposed algorithm is correct?

(2) What do you think would be a solution for compatibility?

(3) Should we consider the external review from cryptographic experts?


My doubt on ElGamal encryption is a result of my cryptographic class
CS276 at Berkeley. This page contains some reading
(http://people.eecs.berkeley.edu/~alexch/classes/CS276-F2015.html).
LEC NOTE 14 and PROB SET 4 have further information.


Weikeng


-- 

Weikeng Chen @ 795 Soda Hall