# Questions tagged [elgamal-encryption]

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

314 questions
Filter by
Sorted by
Tagged with
335 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 ...
135 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 ...
520 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 ?
126 views

471 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 ...
493 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 ...
114 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 ...
522 views

### EL gamal cryptosystem

I have this question which gives me q=71(my prime number) , a=7(generator), Yb=3(public key), m=30(message), c1=59(first cipher text) and he wants me to find c2 (second cipher text) I know that c2 = ...
324 views

### Proof of correctness of Exponential ElGamal

I have an assignment for proving the correctness of both ElGamal and exponential ElGamal homomorphic features (multiplicative and additive respectively). I have managed to prove the former but am ...
1k views

### Exponentiation in ECC

I have a naive question, what is the nomenclature of exponentiation mean in ECC? I was reading about exponential ElGamal, what does it mean if a generator point $G^x$ ? What does $G * \ldots * G$ ...
112 views

### Subgroup generation: should we check that order is not 2? or g in not too small?

For $p=2q+1$,where p and q are primes, we have subgroups of order $p−1$, $q$, $2$ and $1$. To find $G_q$, usually we just check that $g^q\bmod p=1$ and that's it. However,here it's mentioned that ...
307 views

### Lenght of the ElGamal cipher

Ok, it's kind of stupid question, but I want to make sure. What is the length of the ElGamal cipher? It's equal to the size of 2 elements of the cyclic group, right? But lengths of elements are NOT ...
667 views

### Information leak in ElGamal encryption with message in base group

Assume a finite commutative base group $\mathbb B$, some $g$ in $\mathbb B$, and $\mathbb{G} = \langle g\rangle$ the subgroup that $g$ generates, with choice of $\mathbb B$ and $g$ such that ElGamal ...
1k views

### ElGamal in $\mathbb Z^*_p$ with $g$ not a generator of $\mathbb Z^*_p$

Let $G$ be a subgroup of $\mathbb{Z}^*_p$, $p=23$. The order of $G$ is $|G|=11$. Let $g=4$ be a generator of $G$. Consider the key generation algorithm of the ElGamal encryption scheme. Assume that ...
288 views

### Can I use modulo $n^2$ arithmetic where $n=p \cdot q$ for ElGamal encryption?

In the paper which I was reading, the authors were using ElGamal encryption with modulo $p$, where $p$ was a prime. Do the commitment properties still hold if we use modulo $n^2$ where $n=p \cdot q$ ...
325 views

### CDH between two groups implies weakness of El-Gamal

Let $G$ a cyclic group of prime order $p$ with a generator $g$. Let $H$ a cyclic group of prime order $p$ with a generator $h$. Suppose that you have an algorithm $\mathcal{A}$ that given two ...
225 views

### Does ElGamal authentication exist?

Are there any natural ways to transform ElGamal encryption system or ElGamal signature scheme into an authentication protocol?
2k views

### How to find a generator g for a large prime p?

Trying to implement ElGamal. I have a 1024-bit prime p and now need to find a primitive root g for it. How do you find such a g in an acceptable time? It takes so long, my sage server actually ...
196 views

### Understanding ElGamal encryption for a Mental Poker Case

I am looking to understand ElGamal encryption as it is used in a specic context described below. I am interested in creating a practical form of Mental Poker for games other than poker developed by ...
687 views

### why doesn't quadratic residue attack work with Elgamal encryption with decisional diffie Hellman assumption?

I was reading this notes http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture4.pdf It's given that discrete log assumption is not enough for semantic security, I'm assuming there maybe chance of ...
2k 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$. ...
280 views

### Semi static ElGamal vulnerability when the secret is not truely random

Assume Alice wants to communicate with Bob. Bob provides his public parameters $(g,n,y)$ with $y=g^x$ where $x$ is his secret key Now Alice wants to send $m$ to Bob. She generates a random $r$ and ...
336 views

### Security proof of mix net

I am writing an exercise in cryptography about anonymous communication. One of the systems I have looked into is the mix net protocol. I want to prove that this is secure. I have seen many different ...
611 views

### Usage of pairings in proxy re-encryption algorithm

I am having trouble understanding one part of the AFGH algorithm for proxy re-encryption (my background in discrete mathematics is lacking a bit). The paper describes the algorithm setup the ...
462 views

### ElGamal proxy re-encryption

I wrote an algorithm to implement a suggestion in a paper by Ivan and Dodis to convert a regular ElGamal encryption scheme into a proxy re-encryption one (it's at page 6, left column of this but I ...
252 views

### Generating ElGamal parameters in a mix net

I am reading this paper regarding re-encryption mix nets. I want to implement my own for educational purposes and I am stuck at the initial steps of how I should generate the keys and distribute them. ...
205 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 ...
576 views

### XOR instead of Multiplication in ElGamal encryption

In the ElGamal encryption scheme, the message $m$ is multiplied with the secret $g^{xy}$ Wikipedia. I don't understand the advantage of it. Why we can't just XOR our message with the shared secret? As ...
152 views

### How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem?

On the group of multiplication modulo large prime $p$ of $m$ bits Given $$b_1^k=g_1 \;\text {mod}\;p$$ $$b_2^k=g_2 \;\text{mod}\;p$$ $$b_3^k=g_3 \;\text{mod}\;p$$ $$\vdots$$  b_n^k=g_n \;\...
100 views

### Can I overcome ElGamal malleability with AES preprocessing?

So textbook ElGamal is known to be vulnerable to CPA, and although there are several proposals (DHAES/EIES) for modifications none of those are formally accepted or standardized. My question is ...
404 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 ...