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 ...