# Questions tagged [elgamal-encryption]

ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.

232 questions
1answer
44 views

### ECIES/ ECDHE/ EC-ElGamal encryption comparison

I need to choose an encryption system, so I am trying to understand the differences between the existing options. I always find that people compare ECIES (Elliptic Curve Integrated Encryption Scheme) ...
1answer
41 views

### How much more secure is $c = mg_1^r + g_2(g_1(g_1^r-1)/(g_1-1)) \mod p$ compared to just $c = mg_1^r \mod p$ (dis. log), all known but $r$?

To encode a message $m$ to a cipher $c$ you can use the only hard solvable problem of computing the discrete logarithm with a generator $g$ in base over a prime $p$. $c = mg_1^r$ mod p If an ...
1answer
210 views

### Getting a key size of DSA/Elgamal certificate

I've tried to get a public key size of DSA/Elgamal PGP certificate. Using the Cleopatra I find out that there is actually two public keys - one with DSA with key ...
1answer
65 views

### Proof of correctness of an ElGamal encryption given a specific public key

Suppose Alice sends an ElGamal encryption of a value $v$ to Bob (using either the normal or exponential version of ElGamal). E.g. assuming publicly-known $pk_{BOB} = h$ and a generator $g$, Alice ...
1answer
826 views

### ElGamal encryption and signature using same keys

In ElGamal scheme we have message $M$; $p$, $g$ and $y=g^x \bmod p$ as public key where $x$ is unknown private key. Encrypted message $(c,d)$, where $c=g^k \bmod p$ and $d=M \cdot y^k \bmod p$. ...
0answers
43 views

### Beginners question regarding ElGamal

How to motivate, that in ElGamal Alice the recipient keeps her keys fixed, while Bob the sender changes the key each time - why not both of them change their keys each time?
1answer
123 views

1answer
15k views

### ElGamal with elliptic curves

I've searched some information on ECC, but so far I have only found Diffie-Hellman key-exchange implementations using ECC, but I don't want to exchange keys, I want to encrypt & decrypt data like ...
1answer
70 views

### Give a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$

We know that if the decisional Diffie-Hellmann problem is hard then the Elgamal encryption is CPA-secure. One show that if the chosen group is $\mathbb{Z}_p^*$ then the decisional Diffie-Hellman ...
0answers
25 views

### How to decrypt plain text x using man in the middle attack

Suppose Alice want to share a plain text $x = 5$ to Bob; using RSA, DHKE, and El-Gamal. My question is if Man-in-the-middle attack is applied then weather oscar can compute/decrypt plain text in all ...
1answer
56 views

### Simplified ECC non-point public key example, how it works

I know that ECC public key is in fact point on curve calculated by $(x,y) = k \times G$ , while $k$ is random and $G$ is the base point, it performs "Point addition" which involves some math behind. ...
1answer
64 views

### ElGamal variant

I came across this problem, while currently reading "Introduction to Modern Cryptography" by Katz and Lindell. I am new to crypto and just trying to go through the book and solve the exercises, ...
2answers
107 views

### NIZK proof for cipher randomisation

Is it possible to contract NIZK proof that a cipher was randomised? Suppose Alice creates a cipher $c = \text{Enc}(m,r)$ and ZK proof that $c$ was formed correctly (for example, $\text{Enc}$ could ...
1answer
111 views

### Non interactive ZKP that encrypted additive elgamal message is in set of valid messages

This is taken from Anonymous voting by two-round public discussion by F. Hao P.Y.A. Ryan P. Zielinski Votes are encrypted using the additive variant of ElGamal. I am also using ECElgamal. The idea is ...
1answer
105 views

### Can I perform a division of two integers homomorphically using ElGamal?

How can I perform a division of two integers homomorphically? (Simplifying assumptions can be made if needed, that is, I am fine with dividing numbers that are whole and the result will be whole as ...
1answer
111 views

### Verification of encryption for ElGamal cryptosystem

Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm ...
0answers
67 views

### El-Gamal like encryption, how can i guess the key?

There is $p$ (large prime number), $g$ (generator of $p$), and $x_a$, $x_b$, $r$ (which are between $1$ and $p-1$). I know $g^{x_a}$, $g^{x_b}$, $g^r$, $g^{x_a\cdot x_b\cdot r} \bmod p$. How can I ...
1answer
442 views

### Secure ElGamal with OAEP

Is it possible to make ElGamal IND-CCA2 using OAEP or OAEP+? (OAEP+ from: "OAEP Reconsiderd" by Shoup) The reason I ask is that I recently answered this question and it came to my mind that OAEP or ...
0answers
85 views

### Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
1answer
75 views

### Why $\alpha$ in ElGamal cryptosystem has to be a primitive root? [duplicate]

When choosing the public key for ElGamal, $\alpha$ must be chosen as a primitive mod p. What if $\alpha$ is not a primitive root ? How will it influence the encryption and decryption ?
1answer
84 views

1answer
213 views

### ElGamal with weak public key

Assuming this setup: A prime $p$, a generator $\alpha$ in $\mathbb{Z}_p^\ast$. Alice chooses her private exponent $d$ from $[2, p-2]$ and calculates her public key $\beta$ = $\alpha^d$. Bob then ...
1answer
141 views

### How to recover private key in ElGamal when random value k is known

Given following ElGamal encryption scheme: $\delta = M(\alpha^a)^k \mod{p}$. Assume that an attacker knows the random value $k$. How can he recover the private key $a$? I know that it's possible to ...
3answers
250 views

### Privacy of vote from tallying authority in El Gamal Voting Schemes

I've been reading this paper about ElGamal encryptions and its application in electronic voting: http://www.win.tue.nl/~berry/papers/euro97.pdf Section 2.3 talks about using Shamir secret sharing so ...
0answers
96 views

### Proof of knowledge of exponentiations

I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of ...