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

[Weikeng Chen]

HI Niibe,

Actually, I feel the discussion enjoying. Hope I am not that annoying
:) Do you have FaceBook?

> In my opinion, if "ElGamal" can be understood as "the ElGamal crypto
> system in Multiplicative Group of Integers modulo p $Z_p^*$", as we do,
> application writer should know its limitation.

No. We should accept some modification. Otherwise, today, we should
say the RSA implemented in libgcrypt as 'RSA-Modified-Padded-Random',
not 'RSA'. In some modern cryptography books used for school, we call
the original RSA as 'textbook RSA' and show that it is not semantic
secure,

If semantic security is not that important, we can use the original
RSA -- but today we are revisionism!

> Well, by your posts, I learned that a sort of "revisionism", in the
> entry of "ElGamal encryption" in English version of Wikipedia (BTW,
> Japanese version is worse.  It simply denies the use of $Z_p^*$).
> There, it is stretched to... more general version, i.e., the one on a
> cyclic group.  While this sort of generalization and revision by
> generalization are useful for academies, I am concerned in some matter
> of misunderstanding between school and some fields in industry.

They are extended to the prime-order cyclic group where DDH assumption
holds (and semantic secure). There are reasons:

(1) Z_p^* ElGamal cannot achieve semantic security. We want to make it
easy for the numerical message. People discover Schnorr group which is
not difficult to find and achieves the security.

(2) ElGamal on curves. Because we have some curves that form a prime
group. People prefer curves: (1) the security assumption is stronger
than RSA, generally believed. (2) due to the previous reason, smaller
parameters can be chosen. ciphertexts and later signatures can be
small. It is used for short signature -- part of the reason why it is
popular in website HTTPS certificates.

I think there is always misunderstanding between school and industry.
Semantic security is something real I think.


> From OpenPGP perspective, there is no need for change.

I agree.


> For an exercise of programming, I think that you can write
> elgamal-schnorr.c based on libgcrypt/cipher/elgamal.c, only changing key
> generation.  Well, another change is needed for elg_names, too.

No. I need to both change primegen.c and create that. Maybe make a new function.

> It would be good to have elgamal-schnorr.c in libgcrypt, but I don't
> know if it's worth or not.  Which application uses that?

> Is that ElGamal so important, now, for what?  I wonder.

I agree that ElGamal seems no that useful today. But I think this is
the problem of the industry.

RSA is definitely not better then ElGamal. The assumption, the fast
growth, and complicated requirement for a secure composite... padding
is needed.

But ElGamal is easier. You have elegantly all good properties. The
security guarantee of such a Schnorr group is quite easy to follow and
sum up. The ElGamal is not that mainstream because THE CORRECT VERSION
IS NOT SUPPORTED BY YOUR GENERATION OF DEVELOPERS 15 YEARS AGO. And
sorry... honestly speaking, is the rise of ECC/ECDSA, which can be
treated as the ElGamal over curves. And also, we exchange key by DH,
we sign with ECDSA, but we rarely use hybrid encryption in SSL/HTTPS
-- because we have the concept of a session, and we want to reduce the
use of public-key encryption as much as possible to boost the
efficiency.

And in homomorphic encryption, it is important. Let me explain

> What's your purpose?  Do you intend to implement some crypto protocol
> on top of that? Some tool with homomorphic encryption?

That is my loved example for an application, which ElGamal is almost
the only option for some operations.

> If we design new a tool for homomorphic encryption, it seems for me that
> there are other crypto system which is better than ElGamal.

No. There are some public-key cryptosystems with homomorphic
encryption. Let me try to classify.

Additive where you can get Enc(3) from Enc(1) and Enc(2):
      Paillier (We didn't implement it!)

Multiplicative where you can get Enc(16) from Enc(8) and Enc(2):
      ElGamal, ***textbook*** RSA

XOR where you can get E(1) from E(1) and E(0)
      GM (very not useful)

Both with some limitations:
      BGN system (using bilinear mapping and pairing-based
cryptography -- they are not industry at all so not GNU-thing totally)

Both with no restriction but slow:
      Fully Homomorphic Encryption BGV system

Here, there are two for multiplicative encryptions, ElGamal and
textbook RSA. But textbook RSA is definitely not secure (everybody
tries to pad with random thing to meet some standard). However, the
padded version, which is semantic secure, loses the homomorphism.

But ElGamal is totally okay. After all the encoding things I mention,
it is both semantic secure and multiplicative homomorphism.

If I can add some more jargon things -- ElGamal supports ciphertext
anonymity (which can be used to build secure messaging systems). It
can be multiple layers. It can support rerandomization. It can support
rerandomization without the public key (called universal
rerandomization).

These are known in the small (maybe large) academic circle but I think
you can never find it in Wikipedia.

> If we design new crypto protocol on ElGamal, for some reason, it seems
> for me that we have better choice on a cyclic group other than Schnorr
> Group.  Say, Elliptic curve?

We need to encode the messages to a point before making it to the
curve. The general way is to try to hash the data into $x$ and then
find a $y$ -- so it becomes a point. Such technique removes the
homomorphism.



On Wed, Oct 18, 2017 at 6:35 PM, NIIBE Yutaka <gniibe at fsij.org> wrote:
> Weikeng Chen <w.k at berkeley.edu> wrote:
>> I want to note again that: If used in the way you mention, then it is
>> secure :) but also may not be good for some applications.
>
> In my opinion, if "ElGamal" can be understood as "the ElGamal crypto
> system in Multiplicative Group of Integers modulo p $Z_p^*$", as we do,
> application writer should know its limitation.
>
> Well, by your posts, I learned that a sort of "revisionism", in the
> entry of "ElGamal encryption" in English verion of Wikipedia (BTW,
> Japanese version is worse.  It simply denies the use of $Z_p^*$).
> There, it is stretched to... more general version, i.e., the one on a
> cyclic group.  While this sort of generalization and revision by
> generalization are useful for academies, I am concerned in some matter
> of misunderstanding between school and some fields in industry.
>
>> What would be the next step you suggest? Implementing an independent
>> elgamal-schnorr.c? Because in my proposed variant, $g$ is no longer a
>> generator for $Z_p^*$, this is not consistent with the OpenPGP
>> document for ElGamal configuration.
>
> From OpenPGP perspective, there is no need for change.
>
> For an exercise of programming, I think that you can write
> elgamal-schnorr.c based on libgcrypt/cipher/elgamal.c, only changing key
> generation.  Well, another change is needed for elg_names, too.
>
>
> It would be good to have elgamal-schnorr.c in libgcrypt, but I don't
> know if it's worth or not.  Which application uses that?
>
> Is that ElGamal so important, now, for what?  I wonder.
>
> What's your purpose?  Do you intend to implement some crypto protocol
> on top of that? Some tool with homomorphic encryption?
>
> If we design new a tool for homomorphic encryption, it seems for me that
> there are other crypto system which is better than ElGamal.
>
> If we design new crypto protocol on ElGamal, for some reason, it seems
> for me that we have better choice on a cyclic group other than Schnorr
> Group.  Say, Elliptic curve?
> --



--

Weikeng Chen @ 795 Soda Hall


-- 

Weikeng Chen @ 795 Soda Hall