# Questions tagged [elgamal-encryption]

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

361 questions
Filter by
Sorted by
Tagged with
47 views
+100

### EC-ElGamal scalar-to-point mapping for a secure multiparty computation setting

The ElGamal cipher is additively homomorphic for points, but not for scalars. In a single party setting, people usually get around this by mapping the scalar m to ...
• 1
529 views

### Is ElGamal homomorphic encryption using additive groups works only for Discrete Log ElGamal? What about EC ElGamal?

It is known that in Discrete Log ElGamal encryption, the ciphertext $E$ is encrypted as: $a\ =\ g^k$, where $k$ - random scalar from $[0,\ p)$, $g$ - group generator $b\ =\ (Y^k*m)\mod\ p$, where $Y$ -...
• 77
167 views

### Is it possible to abstract an ElGamal encryption for EC and Discrete Log by using a Group Law?

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 ...
• 77
35 views

### Zero-Knowledge Proof of a number being generated "randomly" (similar to a dice roll)

If party1 asks other parties to give a random number, for simplicity, say in a range from 1 to 6 (like in a dice). Is it possible for party1 to ensure that the number received is in a given range and ...
• 307
1 vote
18 views

### Mental Poker: Can the shuffle of the deck be done Publicaly by a single player at the start of the game

Ref: Mental Poker Revisited by Barnett and Smart. I am looking at mental poker problem. Generally, the shuffling process is done by a single player who starts the game and not by all players. But, in ...
• 307
1 vote
41 views

### Mask-Shuffle in Mental Poker Revisited from Barnett and Smart

I am going through the paper "Mental Poker Revisited" by Barnett and Smart. I understood Section 5 in which the author explains Chaum-Pedersen (CP) protocol and how it is used in methods ...
• 307
115 views

### How do I solve a discrete log using pen paper for exam without bruteforcing it?

I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this 3 = (10^XA) mod 19 now everywhere I am finding only ...
• 141
334 views

### How can I understand the gap between CPA and CCA1?

I have read lots of books about CPA,CCA1,CCA2. I understand how to get an example satisfies CPA but not CCA2. However, I can't find such a scheme which is CPA but not CCA1. What is the extra advantage ...
65 views

### El Gamal encryption variant and its security

We are given an El Gamal variant and are requested to find the decryption scheme and the security of the encryption. The variant operates on a group $\mathbb{G}$ of prime order q and g, h are two ...
101 views

### One group element hybrid encryption for El Gamal

I am really curious about this one problem 10.12 from Katz/Lindell's book. It goes as follows: I am quite sure we can assume that $\textsf{Enc}_k(m) \in \mathbb{G}$, as the authors devoted the whole ...
1 vote
44 views

### Dealing with MITM attack in e-voting systems

I've read many e-voting papers that use El-Gamal scheme which I recall is vulnerable to man-in-the-middle attack, yet I find no discussion or even mentioning of it in those papers. -Does anyone knows ...
• 160
123 views

### ElGamal signature scheme problem and unsure whether my calculations are wrong or that's the answer

Trying to solve problem with verifying a message through the ElGamal signature scheme and I end up getting two different values. I'm given a prime number p=881 , e1=3, d=60 , and a random value r=11 . ...
80 views

### Is ElGamal secure if we fix the generator for all users?

In the ElGamal cipher, the key generation algorithm needs to randomly sample a generator g and test whether g is a safe generator or not each time. I wonder whether we can use a fixed safe generator ...
1 vote
83 views

### Why exclude the last group element when picking Elgamal secret key

Christof Paar explains in his lectures that Elgamal encryption scheme picks the private key from $\{2, \ldots, p-2\}$, is there a reason for excluding the last and first elements?
• 123
1 vote
31 views

• 373
66 views

### Text to Divisor Class Encoding in Hyperelliptic Curve Cryptography

When trying to implement ElGamal Public Key Encryption using Hyperelliptic Curves, one needs to map the message that will be encrypted to a valid Divisor (in my case in the Mumford representation, ...
• 61
80 views

### To prove equality/inequality of plaintexts of 2 ciphertexts encypted under different encryption schemes

We have 2 ciphertexts, one encrypted using Paillier and another encrypted under Elgamal encryption schemes. Is there a way to design ZK-proof to prove equality of the underlying plaintexts of these 2 ...
122 views

### What bitlength should I use for generating primes for a ElGamal Encryption Cyclic Group (given the data to encrypt has a short time-value vector)?

I am generating large prime numbers to create a cyclic group for ElGamal encryption, I can specify the bit-length n but want to limit the size because this will ultimately allow me to limit the amount ...
• 71
25 views

### Anonymized Spatial Conflict Assessment - Suggested Approaches?

Scenario: There are 3 people: PERSON1, PERSON2, and PERSON3 PERSON1 and PERSON2 each have a 2-dimensional polygon on an x,y plane It is PERSON3's job to assess whether the polygons overlap However, ...
• 31
133 views

### Dynamic Distributed Key Generation for elGamal

I am looking for a scheme for dynamic threshold public-key encryption, which includes dynamic distributed key generation. Namely, the number of parties that participate in DKG is bounded, but unknown. ...
1 vote
51 views

### Elliptic curve ElGamal cryptosystems [closed]

I have been working through a book on cryptography and have recently come across elliptic curves. This particular question has me stumped and the book isn't much help, unfortunately. I was wondering ...
• 41
152 views

### Solving DDH from an ElGamal adversary

Suppose an adversary wins IND-CPA against ElGamal, They're given public key $h=g^x$, Give a pair of messages $m = [m0,m1]$, Get back ciphertext $(a,b) = (g^r, g^{xr} \cdot g^{m[b]})$, from which ...
• 83
252 views

### Proving same value in ciphertext and Pedersen commitment Using Sigma Zero Knowledge

Let we have 2 generator $G$ and $H$ in any elliptic curve. A prover creates a ciphertext with Homomorphic ElGamal, $(r_1G,\;mG + r_1P)$ such that $r_1$ is random and $P$ is public key of the prover. ...
• 75
142 views

### Proxy Re-Encryption based on standard ElGamal

ElGamal-based BBS proxy re-encryption is well known, but it works on a variant of ElGamal like ($mg^r$,$g^{xr})$ not standard ElGamal ($g^r$,$mg^{xr}$). After reading the original paper, I found the ...
• 21
1 vote
53 views

### Using exponential elgemal on ecc to encrypt and aggregate binary values

I am trying to implement an electronic voting scheme which uses the exponential version of elgamal cryptosystem, voters encrypt their votes for each candidate and send them all to the ballot box. Now ...
132 views

### How does this libgcrypt elgamal decryption work?

Update: The question below was asked before I realized that this is being done to prevent a side channel attack: https://github.com/advisories/GHSA-5p8v-2xvp-pwmc What I am still curious about, is the ...
• 155
117 views

### Is there a special limit in the range of the hash function?

Is there a special limit in the range of the hash function? More specifically, is it possible that there is a cryptographic hash function that outputs c-membered subsets of the n-membered set? In ...
1 vote
169 views

### Are real-or-random model and LR-model are equivalent?

Are real-or-random(rr) model and LR-model are equivalent? In the definition of ciphertext indistinguishability, LR-model is used. However I think rr model and LR model are somewhat equivalent. Here is ...
• 373
319 views

### Zero secret key in EC ElGamal: standards vs theory

I'm a bit confused by the standards and some replies regarding zero (the point at infinity) in elliptic curves ElGamal. TL;DR: Why do some people recommend excluding zero? It has nothing to do with ...
• 558
1 vote
107 views

### Is it possible to use Batching with any of the Partial Homomorphic Cryptosystems?

I'm familiar with the concept of batching in the context of (Fully) Homomorphic Encryption - whereby many values can be encrypted as a single ciphertext and operated on simultaneously in an SIMD/...
• 177
1 vote
73 views

### On a public e-voting, how do I keep the votes from being disclosed prematurely without a trustee?

I am trying1 to build a Proof Of Concept of a e-voting scheme on a blockchain. Before the elaboration, the question: On a public e-voting, how do I keep the votes from being disclosed prematurely ...
142 views

### ElGamal cryptosystem

ElGamal cryptosystem provides multiplicative homomorphic property which can also be converted to additive homomorphic property. Can we use both properties simultaneously? For example, we want to ...
122 views

### How to reduce Diffie Hellman problem to ElGamal?

I'm trying to answer without success questions (ii - iv) Any hint will be appreciated :)
386 views

### Range proof for ElGamal ciphertext

Alice has an ElGamal public key $y=g^x$. Bob encrypts a value $g^b$ based on Alice's Elgamal public key and he ends up with a ciphertext $(g^by^r, g^r)$. Can Bob prove that the value $b$ is in some ...
1 vote
103 views

### Can I prove that from a set of ciphertexts one is encrypting $g^0$ and the others are encrypting $g^b$ where $b$ is a negative value?

Consider for example this set of encrypted values under the Elgamal keys $y_0$,$y_1$,$y_2$: $$Enc_{y0}(g^0),Enc_{y1}(g^{-20}),Enc_{y2}(g^{-10})$$ Can I prove that one value is $g^0$ and the others ...
1 vote
131 views

### How to decrypt a homomorphically modified ciphertext in Elgamal cryptosystem?

From the wiki, we know that to encrypt a message $M$ using Elgmal encryption, one should firstly map the message $M$ to an element $m$ of G using a reversible mapping function, then run the ElGamal ...
• 797
1 vote
250 views

### Using ElGamal instead of RSA in FDH

In RSA-FDH to sign a message $m$, we apply a hash function $H$ and then "decrypt" it using the private key $d$, so $Sign(m) = H(m)^d \mod N =: \sigma$ and then to verify, we use the public ...
• 13
89 views

### ElGamal same private and random key attack

I'm having difficulty understanding this. Consider two messages are encrypted using the same cyclic group of order $q$, generator $g$, private key $x$, and random parameter $y$. The attacker knows a ...
622 views

### ElGamal same private and random key attack

I'm having difficulty understanding this. Consider two messages are encrypted using the same cyclic group order $q$, generator $g$, private key $x$, and random parameter $y$. The attacker knows a ...
786 views

### Zero Knowledge proof of correct ElGamal encryption

Suppose for $sk = x$, $pk = g^x$ we encrypt message $m$ with ElGamal encryption as $(g^r,m\cdot pk^r)$. My goal is to prove that I performed the encryption correctly, i.e. that the same $r$ is used ...
• 334
303 views

### ElGamal-based BBS proxy re-encryption implementation? [closed]

are there any available tools/libraries that implement the idea of EIGamal-based proxy re-encryption scheme shown below? Preferably in Golang. Thank you! Source of this picture: https://www.cs.jhu....
• 99
150 views

### EC ElGamal multiplicatively Homomorphic

Can we make EC ElGamal have multiplicative homomorphic property?
1 vote
58 views

### Distributed key generation when all parties need to participate

Suppose $n$ parties where $t$ are honest want to perform a distributed key generation protocol. There are many existing schemes. In the simpler setting where all $n$ parties must be online, otherwise ...
• 1,365
1 vote
For ElGamal encryption, safe prime $p$ is used such that $p = 2q+1$. However, can someone explain to me, in simple terms, why we would need, in this context, a large order of $G$ and how it will ...