Questions tagged [elgamal-encryption]
ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.
296
questions
1
vote
1answer
25 views
How are the points computed in the ElGamal elliptic curve encryption algorithm?
I was looking at an example of the ElGamal encryption operation here (page 24), but I can't seem to understand why:
$$\beta = 3(10, 3) = (10, 8)$$
0
votes
2answers
71 views
ElGamal and Pailler combined
currently I am working on some secure accounting application. I have few requirements:
Application should store items which can be searched by name.
Every item has price and tax.
Every invoice ...
1
vote
0answers
35 views
Is it possible to apply the El Gamal encryption/decryption technique using Edwards curve in Montgomery form
I've been trying to understand the ElGamal encryption/decryption technique. I plan to use it for sending a private message to the server. That is: Alice needs to send $Pm$ (private message encoded via ...
0
votes
0answers
35 views
Difficult to guess the targeted receiver
The protocol is defined as :
Bob want to send message to one of his friends say $k$ friends , he does not want his others friends (except one whom he want to send message ) to tell who is targeted ...
0
votes
0answers
57 views
Can you obtain private key d and compute plaintext from El-Gamal?
Given an Elgamal encryption scheme with public parameters $k_{pub}=(p,\alpha,\beta)$ and an unknown private key $k_{pr}=d$.
Due to an erroneous implementation of the random number generator of the ...
1
vote
0answers
102 views
Zero-knowledge proof of knowledge of a plaintext in exponential ElGamal
Consider the exponential ElGamal cryptosystem over some group $G$ with generator $g$. Let $m$ be a plaintext, and $(R, C) = (g^r, g^m \cdot y^r)$ an encryption thereof for some public key $y$.
Assume ...
0
votes
0answers
64 views
Zero Knowledge Proof: Prove correct ElGamal encryption without leaking message
I know it is possible to prove zero knowledge that a given ElGamal ciphertext $(c,d)$ encrypts a plaintext belonging to some set ($\{0,1\}$ is frequently used for electronic voting applications).
Next ...
0
votes
1answer
49 views
Modified ElGamal encryption (ElGamal encryption with messages in the exponent ) is implemented in a pairing friendly elliptic curve. Is it secure?
In my scenario, I need to distinguish if the encrypted message is 0 or not. The message is encrypted by Elgamal encryption but with the message in the exponent. i.e. $(C,R)=(g^my^r,g^r)$ where $y$ is ...
1
vote
1answer
65 views
ElGamal Encryption over a Subgroup
Say for instance we are encrypting over a subgroup of ($Z_{67}^*, \bmod 67$).
To perform a round of El Gamal's encryption scheme we should:
Choose a subgroup of ($Z_{67}^*, \bmod 67$), of prime order....
0
votes
2answers
127 views
Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair?
I vaguely recall reading about a scheme that accomplished this but am not able to figure out which one it was. For the sake of brevity I'm gonna omit any nonces.
Let's say we have an asymmetric ...
0
votes
0answers
78 views
Request for a zero-knowledge proof (or hint)
I want to design a zero-knowledge proof (ideally a NIZK, but could be a sigma protocol) so that Alice can prove that a certain encryption contains a value that has been signed by a certain key.
More ...
1
vote
1answer
179 views
ElGamal encryption of concatenated messages
Suppose an encrypter separately produces three ElGamal ciphertexts $c_1 = E(m_1)$, $c_2 = E(m_2)$ and $c_3 = E(m_3)$, which encrypt the messages $m_1$, $m_2$ and $m_3$, respectively.
Is it possible ...
0
votes
0answers
52 views
ElGamal variant Encryption scheme
I was asked about the following variant of $ElGamal$ Encryption Scheme (Preparing for exam):
Instead of encrypting $(g^r,h^r*m)$, encrypt $(g^r,h^r+m)$. And the question is whether the new variant CPA ...
2
votes
1answer
231 views
Python library that implements additive homomorphism of Elgamal Encryption on the Elliptic curve i.e X25519 or P-256
I'm trying to find a Python library that implements Elgamal Encryption on the Elliptic curve i.e X25519 or P-256.
My purpose is to use the additive homomorphic property of Elgamal.
I'm using https://...
2
votes
2answers
98 views
ElGamal encryption security
Assume we have 2 prime numbers in form p = 2q + 1.
Is it safe to use the cyclic group of order p-1 instead of one with order <...
0
votes
0answers
48 views
Attack on ElGamal Encryption
Bob is holding a secret-bid auction using ElGamal encryption. He chooses a “safe” prime $p$ of sufficient size, a generator $g$ in $\operatorname{QR}(\mathbb Z_p)$ and a value $b$ in $[1, p]$. He then ...
0
votes
0answers
65 views
Is there an Elgamal implementation in javascript?
Does anyone know a good, well known implementation of ElGamal encryption and decryption in JavaScript?
I was told that Stanford Javascript Crypto Library https://github.com/bitwiseshiftleft/sjcl/ ...
0
votes
1answer
63 views
Why Bellare-Micali Oblivious Transfer Construction requires ElGamal with hashed key?
The idea of the Bellare-Micali Oblivious Transfer Constructions is the following:
Informally, the receiver is required to generate two public keys $y_b$, $y_{b-1}$ such that it knows only the secret ...
0
votes
0answers
48 views
How to determine if ElGamal message was a quadratic residue?
Consider the following ElGamal encryption (using a generator of $\mathbb Z^*_p$):
Key gen:
find a big prime $p$ and $g$ a generator of $\mathbb Z^*_p$.
choose $a\in \mathbb Z_{p-1}$ randomly and ...
-1
votes
1answer
100 views
Breaking Elgamal private key
I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than ...
0
votes
0answers
54 views
Is there a concept of Pedersen commitment “in the base”?
This question Can Elgamal be made additively homomorphic and how could it be used for E-voting?
says ElGamal can be made homomorphic over multiplication. So you can have $(g^r, h^r g^m)$ (i.e., ...
0
votes
0answers
68 views
ElGamal with massage hashed ind-cca secure?
It is well known that text book ElGamal is not IND-CCA secure, because an attacker can just have $$(Y,W)\leftarrow E_{x}(LR(M1,M2,b))$$ where M1, and M2 can be any message in the group, and than just ...
0
votes
1answer
63 views
ElGamal Decryption variant
I am trying to do some ElGamal encryption but having a different encryption formula.
For that I doing the following steps:
The key generator:
Choosing value $p = 107$ and $a = 2$
Random number $d = ...
0
votes
1answer
79 views
Elgamal Encryption: Why does Bob get to reuse his keypair while Alice has to generate a new one for every message?
From Christof Paar's book
The protocol consists of two phases, the classical DHKE (Steps a–f) which is followed by the message encryption and decryption (Steps g and h, respectively). Bob computes ...
2
votes
0answers
39 views
Why is confusion & diffusion not required PKI encryption schemes like Elgamal encryption?
The Elgamal encryption scheme is a Multiplicative Mask with the shared key. It doesn't seem to have any confusion or diffusion.
So why is it not necessary here as compared to Block Ciphers?
2
votes
1answer
102 views
Questions about Symmetric Encryption part of TLS
In TLS, we use DHKE for establishing the session key & then encrypt the actual communication with session key using symmetric encryption. While reading about DHKE, I learnt that you could use the ...
1
vote
0answers
82 views
0
votes
1answer
71 views
Is there a way to confirm that a homomorphic division (multiplication with inverse) using ElGamal produced the correct result?
By running some tests I observed that if I perform a homomorphic division (multiplication with the multiplicative inverse) between two values using the ElGamal scheme, I get the correct result when ...
1
vote
2answers
279 views
Adversary for attack on one variant of ElGamal
I came by the following question:
Consider the following variant of ElGamal encryption. Let $p= 2q+ 1$,
let $G$ be the group of squares modulo $p$ so $G$ is a subgroup of
$Z_p^*$ of order $q$, and ...
3
votes
1answer
100 views
How do I encrypt a long message using ElGamal encryption correctly?
According to ElGamal encryption, in order to encrypt a message I need to generate a shared secret s and after that I am to calculate ...
2
votes
1answer
221 views
Negative numbers with additive ElGamal
I'm trying to implement Private Set Intersection using the additive ElGamal public key encryption system. The code I've written can encrypt and decrypt numbers using the ElGamal system, so far so good....
0
votes
1answer
163 views
Number of operations for Elgamal cryptosystem
In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says
"Roughly speaking, in order to achieve $k$ bits of security,
encryption and decryption for ...
2
votes
1answer
142 views
Can Eve break this public key cryptosystem if she can solve DLP or DHP?
The PKC is in this way:
Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and ...
0
votes
0answers
41 views
Secure asymmetric encryption with 32byte ciphertext
I need securely asymmetrically encrypt the up to 16 bytes plaintext and receive up to 32 bytes ciphertext. I found that ElGamal produces ciphertext that is 2 times keysize. So I would need to use ...
0
votes
0answers
145 views
How can breaking the ElGamal encryption scheme break the Diffie-helman protocol?
I have been studying how ElGamal is a public-key algorithm built on top of the Diffie-Hellman key exchange but I got confused. How exactly could an attacker break the Diffie-Hellman protocol (i.e. ...
1
vote
1answer
71 views
Standard for asymmetric encryption based on elliptic curves
Most parts of public key cryptography has established standards which are in turn used in a large amount of real world applications. There is PKCS#1 for RSA based encryption and signatures and there ...
1
vote
0answers
39 views
Two ElGamal ciphertexts equivalence
Is there a way to prove that two ElGamal ciphertexts encrypt the same message with different public keys without knowing the private keys?
The prover is the producer of both ciphertexts.
4
votes
1answer
220 views
How can I prove that ElGamal encryption in $\mathbb{Z}_p^*$ with OAEP padding is ind-CPA secure?
How I can prove that ElGamal encryption in $\mathbb{Z}_p^*$ with Optimal Asymmetric Encryption Padding (OAEP) is IND-CPA secure?
0
votes
0answers
21 views
Does reusing the same $R$ in Elliptic Curve ElGamal breach its security? [duplicate]
In Elliptic Curve ElGamal if I reuse the same randomness to get the same point $R$ for different messages, how can it breach its security ?
Can you please illustrate with an example?
Please see my ...
3
votes
1answer
208 views
How to secure Elliptic Curve ElGamal encryption against known plaintext attacks?
If I have an encoding function $f(x)$ that maps a message $m$ to a point $P$ on a suitable Elliptic Curve $E$ . If I have the public key $Q$ of my recepient then I can encrypt the message as follows:
...
0
votes
1answer
363 views
ElGamal Threshold Cryptosystem
Suppose we have a threshold ElGamal cryptosystem $(t, n)$ over an Elliptic Curve $E_p$, $p$ being a large prime, with the following parameters:
$G$ is a generator point of $E_p$ with order $q$
A ...
9
votes
2answers
2k views
What is largest prime factor in Diffie-Hellman?
I was reading the paper of A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by TAHER ELGAMAL to better understand ElGamal public-key scheme, and he stated that for any ...
0
votes
0answers
334 views
What are the safe primes for $p$ and $q$ used in ElGamal?
I need to generate a 2048 bit key for ElGamal and I was looking for the $p$ and $q$ for PGP but I couldn't find them. the only thing I could find was this RFC but those are not safe primes.
Does ...
1
vote
1answer
195 views
Is it possible to perfom quadratic residues attack on elgamal cryptosystem?
I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.
0
votes
1answer
131 views
Message space when using the group of QR's for El Gamal Encryption
My textbook states, that the DDH-assumption is not satisfied when we use the group
$\mathbb{Z}/p \mathbb{Z}$ and demonstrates an attack using Eulers Criterion. After that, it states that one should ...
3
votes
0answers
72 views
How to know if an ElGamal ciphertext is well-formed?
Is there a way to prove/verify that an exponential ElGamal ciphertext of a message representative $\widetilde{m}=mG$ is well-formed, meaning that $r_1 = r_2$ in:
$$C = (R, S) = (r_1G, \widetilde m + ...
0
votes
1answer
74 views
Retrieving ElGamal message with negative exponent value
Although the ElGamal scheme states that the message $M$ must be $1 \le M \le p-1$ in this paper: A Secure and Optimally Efficient
Multi-Authority Election Scheme they propose a method where the ...
0
votes
1answer
309 views
decrypting el gamal encrypted messages in regards to k being used
i am trying to understand the differences of using k in the following scenarios to better understand the protocol and most importantly the consequences of using such k.
so i wonder, some user, call ...
1
vote
1answer
170 views
EL Gamal Attack without a secret key
I have the following data where all the inputs are Big Integers,
group size $p$,
group generator $g$
public key of the receiver $y$
$c_1$ and $c_2$
Random Number as well
I am trying to execute an ...
2
votes
2answers
801 views
Construct another ciphertext that decrypts to same message without knowing key in Elgamal
I read about ElGamal from various resources and I was wondering if the following is true. Would appreciate if you could elaborate on it so I can understand better:
Is it possible to construct, given ...
