Questions tagged [elgamal-encryption]
ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.
1
vote
0answers
39 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 ...
0
votes
0answers
24 views
El-Gamal two times encryption, order of decryption [duplicate]
I would like to know in El-Gamal's Encryption, if a message is encrypted with Alice's public key and then the result is encrypted by Bob's public key, can someone decrypt first with Alice's private ...
0
votes
0answers
41 views
ZK verifiable shuffle of ElGamal encryption with different public keys
I need a zero-knowledge proof of correctness of a shuffle of $k$ El-Gamal ciphertexts, but where the public key is different for each ciphertext.
However, each public key can be generated from the ...
0
votes
0answers
23 views
Efficiently proving $PK\{ n : \bigwedge_{1 \leq i \leq k} c'_i = c_i^n\}$ for El Gamal ciphertexts $c_i$
Given El Gamal ciphertexts $c_1,...,c_k$, can $PK\{ n : \bigwedge_{1 \leq i \leq k} c'_i = c_i^n\}$ be efficiently proven (in zero-knowledge)?
Notation: $(\alpha,\beta)^n = (\alpha^n,\beta^n)$.
2
votes
1answer
81 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 ...
0
votes
0answers
22 views
Existence of a NIZK proof demonstrating that a ciphertext does not encrypt some specified plaintexts
Given a (El Gamal, for instance) ciphertext, can I (efficiently) prove that the ciphertext does not decrypt to plaintexts in a small set? For instance, given ciphertext $c = Enc(pk,2; r)$, can I (...
0
votes
0answers
48 views
How can I reuse ed25519 derived keys for asymmetric encryption?
I want to reuse my ed25519 derived keys (more specifically: from Stellar blockchain) to encrypt simple messages, without creating any shared secret key (for symmetric encoding). So I'm not interested ...
4
votes
0answers
57 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 ...
2
votes
1answer
39 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 ?
2
votes
1answer
73 views
Does this scheme break under a DHP adversary?
Consider the following cryptography scheme:
We are given a prime $p$.
Alice wants to send the plaintext $m \pmod p$ to Bob.
Alice chooses $a$ s.t. $\text{gcd}(a,p-1)=1$, and sends Bob, $u = m^a \...
2
votes
1answer
52 views
Usefulness of OAEP with ECC
Does OAEP make sense for use in an ECC ElGamal cryptosystem? The way I see it, OAEP makes questionable sense even for RSA because even though it's a "all or nothing" transformation, many RSA ...
0
votes
1answer
31 views
Given paramaters of an Edward's curve and x, determine a y value if it exists
I'm making a demonstration cryptosystem using ECC ElGamal. I've currently got a working implementation of Edward's Curve operations and a basic ElGamal implementation (Encrypts only points on the ...
3
votes
1answer
89 views
How to securely map messages to points on an elliptic curve
I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one ...
2
votes
0answers
75 views
Chinese Remainder Theorem and Elgamal
I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way.
I have a cyclic ...
-1
votes
1answer
66 views
Is this problem still as hard as discrete logarithm (modified ElGamal)?
I am trying to find a vulnerability or proof for the following problem:
ElGamal part.
Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate ...
1
vote
1answer
56 views
For ElGamal-based key encapsulation, is it necessary to hash before using as AES key?
I'm working with SJCL, specifically using ElGamal to encrypt messages. Behind the scenes, this is doing something similar to what's described in this SO post (emphasis mine):
Regardless how big ...
4
votes
0answers
132 views
Indistinguishability vs fixed bit-length
Suppose there is a cyclic group $\mathbb{G}$ of prime order $q$ of elements in $Z^{∗}_p$ with a generator $g$ and values $a,b,c,d \in Z_q$.
There is also an equation $g^{ab} = g^{cd}$, where $a,b,c$ ...
1
vote
1answer
115 views
What is an example of elgamal homomorphic double encryption?
I am looking for such an cipher algorithm that is based on assymetric cryptography where the order of encrypting is irrelevant.
For example:
There is a message "x", Bob encrypt that message with his ...
3
votes
3answers
274 views
Zero-knowledge transfer of value protocol inspired by EC El Gamal
This is a follow up on the question I asked here. I designed a scheme that allows the following:
Alice has a value $a$ which she wants to keep secret
Bob has a value $b$ which he wants to keep secret
...
2
votes
0answers
98 views
Is EC El Gamal the only option?
This question is related to the question I asked here. I'm looking for encryption scheme with the following properties:
Given $m$ is a 256-bit value, $pub_a$ and $pub_b$ are public keys, and $priv_a$ ...
1
vote
1answer
113 views
Commutative homomorphic encryption for zero-knowledge transfers
I am trying to design a scheme that would allow the following:
Alice has a number $a$ which she wants to keep secret
Bob has a number $b$ which he wants to keep secret
Alice can "transfer" a number ...
0
votes
0answers
89 views
How trapdoor key exposure affects security of trapdoor-based simulatable NIZKs?
I wonder if revealing a trapdoor key would help the verifier to distinguish real and fake proofs in NIZKs that are based on substituting the challenge with the result of a chameleon hash.
I don't ...
5
votes
1answer
167 views
How to encode messages in $\Bbb Z_p^*$ to be encrypted with ElGamal scheme?
In ElGamal encryption scheme, in order to achieve IND-CPA security, one must use a group where the DDH problem is assumed to be hard. As this answer suggests, one way to achieve that is the following:
...
3
votes
1answer
138 views
ElGamal ciphertext lenght
I'm studying for an exam and answering practice questions and I would love clarification on something. Apologies if it seems really simple.
My lecture notes indicate that for ElGamal:
the ...
0
votes
1answer
61 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 ...
1
vote
2answers
52 views
Implementing commitments and challenges for a distributed ElGamal encryption scheme
I am trying to implement a distributed encryption system by having as a main source of information this book (Introduction to Cryptography by Delfs and Knebl) and this Internet article (More Mix than ...
1
vote
0answers
81 views
Is it possible to re-cipher with Paillier?
I know that with ElGamal we can re-cipher and get a second ciphertext equal to the first.
Is it possible with Paillier too?
When saying "re-cipher", I mean "A sends me a message, that is encrypted ...
1
vote
1answer
174 views
How to recover secret $x$ from Elgamal signatures with repeated $k$?
Set generator $g \equiv 5 \pmod p$ where $p=647$ and $p$ is prime.
With the same $g$, $p$ and secret signing key $x$, Alice sends two messages, $428$ and $129$, with signatures $(433, 239)$ and $(433,...
0
votes
0answers
26 views
Validity of ElGamal signature
I'm trying out this practice question but dont know if I'm on the right path. Suppose I have generator $g≡5$ mod $p$ where $p$ = $647$ is a prime.
and Alice publishes her public key $y$ ≡ $57$ mod $p$...
0
votes
1answer
88 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 ...
0
votes
1answer
102 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 ...
4
votes
0answers
92 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 ...
0
votes
1answer
105 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 = ...
0
votes
1answer
87 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 ...
3
votes
1answer
538 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$ ...
1
vote
2answers
76 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 ...
0
votes
1answer
138 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 ...
2
votes
2answers
205 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 ...
0
votes
1answer
310 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 ...
0
votes
0answers
37 views
Comparing computational costs of modular multiplication against an elgamal encryption?
I've been looking for a comparison program measure of various encryption schemes relative to individual operations used by the different schemes.
I am having trouble finding one.
What would be the ...
3
votes
2answers
120 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$ ...
0
votes
1answer
78 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 ...
0
votes
0answers
113 views
Is there a way to prove plaintext equivalence under an additively homomorphic system using two different public keys?
The homomorphism only needs to hold under the same public key, but the plaintext equivalence is from two different public keys, as detailed in the final two steps.
Suppose the following protocol:
...
1
vote
1answer
102 views
Does ElGamal authentication exist?
Are there any natural ways to transform ElGamal encryption system or ElGamal signature scheme into an authentication protocol?
1
vote
1answer
533 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 ...
0
votes
0answers
201 views
One Way Chosen Plaintext Attacks on ElGamal Encryption
I'm trying to understand how OW-CPA attacks work against ElGamal system, specifically how the encryption system defeats the OW-CPA Adversary.
From my understanding, it comes down to the fact that if ...
2
votes
0answers
103 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 ...
2
votes
1answer
246 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 ...
3
votes
1answer
592 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$.
...
1
vote
1answer
107 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 ...
