2
$\begingroup$

ElGamal encryption for Discrete Log is defined as:

Bob side does:

$Y\ =\ (g^x)\ mod\ P$, where $g$ - generator, $x$ - random value among the group elements and $P$ - prime number, typically ultra large

Alice side does:

$a\ =\ (g^k)\ mod\ P$, where $k$ - random value among the group elements

$b\ =\ (Y^k*M)\ mod\ P$, where $M$ - encoded over a group plaintext (becomes part of a group element)

Bob receives:

$M\ =\ (b/(a^x))\ mod\ P$

And then EC Elgamal encryption is defined as:

Bob side:

$Y\ =\ x*G$, where $x$ - value of how many times we added together $G$ and $G$ - is predefined curve basepoint

Alice side:

$C1\ =\ r*G$, where $r$ - random scalar on a curve

$C2\ =\ r*Y\ +\ M$, where $M$ - encoded on a curve, using $G$ and some random scalar, which also then becomes a point on a curve

Bob receives:

$M\ =\ C2\ -\ x*C1$

My question is - looking at these two (Discrete Log and EC) ElGamal algorithms, how can I abstract from specific algorithm and only operate on algebraic groups? Because currently, if we, for example, look at EC ElGamal, then you can see there are plenty of multiplications done, however the EC ElGamal is additive group, not multiplicative as Discrete Log is.

$\endgroup$
2
  • $\begingroup$ Updated: In the first part there's still $b∗a∗x$ where there should be $b∗a^{-x}$, and $Y$ for $y$. Importantly, $x$ and $k$ are scalars, not group elements. And the group should be quadratic residues modulo $P$ if we want to avoid that the encryption leaks a bit about the plaintext. In the second part, we can use corrections and changes the parallel between the two parts will be more apparent. You'll find that the differences between the two parts is notation only, and both use an abstract group. $\endgroup$ Commented Jul 4, 2024 at 15:55
  • $\begingroup$ @fgrieu thanks for your patience! Made some changes in formulas, as you proposed (these are correct!). But my problem is that even if I look at both EC and Discrete Log ElGamal encryption and decryption processes - I cannot find a way to abstract the EC and Discrete Log behind the Group interface.. Right now, in my formulas, indeed, I can see the multiplicative operations on Discrete Log and additive operations on EC, however my goal is to abstract it all and leave behind pure ElGamal with only group interface operations provided, but yeah, which are implemented correctly under the hood $\endgroup$ Commented Jul 4, 2024 at 16:06

1 Answer 1

3
$\begingroup$

The modern academic presentation of ElGamal encryption is in an abstract group1. That applies to both the first and second part of the question. There are two common notations for the group: multiplicative or additive. Just choose the one you prefer when working in an abstract group (rather than in a particular group where one of the two notations is customary).

When we work modulo the prime $P$ as in the first part of the question, it's typically used $P=2q+1$ with $q$ prime, and the abstract group can be the quadratic residues modulo $P$, that is the set of the $q$ integers $u$ in $[1,P)$ with $u^q\bmod P=+1$, with multiplication modulo $P$ noted $*$ the group law. We write $\underbrace{g*g*\cdots*g}_{k\text{ terms}}$ as $g^k$. One detail is brushed off in the question: when encrypting an actual message consisting of arbitrary bits or bytes, we need to represent that message as an element $M$ of the group, and make the inverse transformation on decryption. One way to do this is to first map the actual message to an integer $i$ in $[1,q]$ as one more than the integer coded by the message per big-endian convention; then map $i$ to a quadratic residue $M=f(i)$ (thus a member of the group) called the message representative, and back $i=g(M)$, as follows: $$\begin{align} f(i)&=\begin{cases}i&\text{if }i^q\bmod P=+1\\ P-i&\text{otherwise, equivalently if }i^q\bmod P=P-1 \end{cases}\\\\ g(M)&=\min(M,P-M) \end{align}$$

When we work in an Elliptic Curve group as in the second part of the question, there's a difference in notation: group elements are uppercase letters which makes it easier to distinguish them from scalars, the group law is noted $+$, and we write $\underbrace{G+G+\cdots+G}_{k\text{ terms}}$ as $[k]\,G$, or perhaps as $k*G$ as in the question, but then $*$ is not an internal group law: it's scalar multiplication. And we just assume the message representative $M$ is a group element.

question, first part question, second part
(sub)group quadratic residues modulo $P$ elliptic curve (sub)group
(sub)group order (usually prime) $q=(P-1)/2$ $q$ (or $n$ )
notation multiplicative additive
internal group law $u*v$ (implicitly:$\bmod P$) $U+V$ (point addition)
group law applied to a single element $u*u$ or $u^2$ $U+U$ or $2*U$ or $[2]\,U$
group law applied on $k$ terms $u^k$ $k*U$ or $[k]\,U$
identity element $1$ $\mathcal O$ (or $\infty$ )
identity element property $1*u=u=u*1$ $\mathcal O+U=U=U+\mathcal O$
property of group order $u^q=1$ $q*U=\mathcal O$
inverse/opposite property $(1/u)*u=1=u*(1/u)$ $-U+U=\mathcal O=U-U$
group generator $g$ $G$
private key (scalar) $x\in[0,q)$ $x\in[0,q)$
public key (group element) $Y=g^x$ $Y=x*G$
message representative (group element) $M$ $M$
ephemeral secret (scalar) $k\in(0,q)$ $r\in(0,q)$
encryption step 1 $a=g^k$ $C_1=r*G$
encryption step 2 $b=Y^k*M$ $C_2=r*Y+M$
ciphertext $(a,b)$ $(C_1,C_2)$
decryption $M=b/(a^x)$ $M=C_2-x*C_1$

There is a slight difference beyond notation: in the first part, since we use a subgroup of the multiplicative group of integers modulo a safe prime $P$, we can be tempted to use the full group that is integers in $(0,P)$, as did Taher ElGamal in his 1985 article, because it makes the mapping of an integer interval to a group element and back more straightforward. When in an elliptic curve, if we do the equivalent, that is use all elements in an elliptic curve group of cofactor $h>1$, that does not (for non-singular curves) help to perform such mapping. Notice that in both cases, information about the plaintext then leaks from the ciphertext, see note below.


1 In order to prevent recovery of the private key (a total security break), we want a group such that Discrete Logarithm Problem is hard. Further, in order to avoid leak of information about the plaintext from the ciphertext (a break of security under Chosen Ciphertext Attack), we want the group to have an order with no small factor. Towards that, it is most commonly used a group of prime order. The group is sometime constructed as a subgroup of a larger group.

$\endgroup$
1
  • $\begingroup$ thanks for the detailed and clear explanation! I think that is enough for me, in order to work the problem of abstracting the ElGamal out $\endgroup$ Commented Jul 4, 2024 at 17:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.