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

learn more… | top users | synonyms

3
votes
1answer
48 views

El Gamal special construction

The algorithm: I have to determine if the following algorithm is secure: $p,q \in \mathbb{P}$ and $N = p \cdot q$ $e \in [2, N - 1]$ such that $\gcd(e, N) = 1$ $r_1, r_2$ are random numbers ...
0
votes
0answers
21 views

Combining Elgamal encryption with the Elgamal signature scheme - Security issues?

For didactic (not real-world) purposes, I would like to teach other students the Elgamal encryption system and the Elgamal signature scheme. Are there known security issues when combining them? (i.e. ...
5
votes
1answer
60 views

Is ElGamal encryption still secure if the randomness is known to be even?

In ElGamal encryption $(g^r, g^mg^{kr})$, if the randomness $r$ is always chosen from even numbers, and the attacker knows about this, is it still provable secure?
3
votes
0answers
84 views

Elgamal with secret key equal to zero possible?

From various sources (e.g. this paper, page 3), the key generation algorithm of Elgamal samples the secret key $x$ from $\mathbb{Z}_q$, which is identifiable to $\{0, 1, 2, \dots, q-1\}$. My ...
1
vote
1answer
40 views

Attacks on schemes based on elliptic curves when the transmitted points are not on the curve

Some elliptic curve schemes require to send a curve point during the normal execution of the protocol. For example, ElGamal encryption and ElGamal signature require this. On the other hand, ECDSA does ...
3
votes
1answer
100 views

ElGamal - What if the Decisional Diffie-Hellmann problem could be solved?

I have read that if the DDH problem could be efficiently solved, the IND-CPA would not hold for ElGamal. I don't see why it makes ElGamal less secure if you have $g^a$, $g^b$ and $g^c$
2
votes
1answer
75 views

How is it possible that $g^q \equiv 1 \pmod p$ for a generator g?

The context of this question is coming up with the parameters for the ElGamal encryption scheme. One of the requirements for the parameters for ElGamal is that we have primes $p$ and $q$ such that $p ...
3
votes
1answer
197 views

How to perform decryption in this single-bit PKE scheme?

Consider a cyclic group $G$ of order $q$, and let $g$ be a generator for $G$. Assume $(G, q, g)$ is public. Consider the following 1-bit public-key encryption scheme. To $generate (pk,sk)$: $x \...
0
votes
2answers
46 views

How to find element g order q, given 2 large primes p and q where q|p-1

i have calculated 2 large primes, $p$ (minimum 2048 bits) and $q$ (minimum 224 bits), where $p-1 \mod q = 0$ by using SageMath. $p = $...
3
votes
1answer
91 views

Why do the subexponential algoriths for the DLP not work for the ECDLP?

Elliptic curve cryptography is much more secure for the same parameters because attacks that work on the DLP do not work on the ECDLP. Why do the attacks fail in the latter case?
1
vote
1answer
68 views

Is there an additive homomorphic encryption that supports exponentation

For example say we have two numbers a and b. Now is there any partial homomorphic encryption scheme that allows to compute (a-b)^2 over the ciphertexts of a and b without round trips.
0
votes
0answers
53 views

Simulation of a custom build network security algorithm with ElGamal Cryptosystem using Elliptic Curve

I am trying to build an algorithm to encrypt and decrypt text using ElGamal Cryptosystem using Elliptic Curve. My algorithm generation is done. But at simulation part I stuck. My algorithm steps are ...
2
votes
1answer
113 views

Elliptic curve ElGamal with homomorphic mapping

I am interested in ElGamal due to the fact that you can achieve some degree of homomorphic properties. I became interested in applying ElGamal to elliptic curves, and found this other question with an ...
5
votes
0answers
41 views

An MPC protocol from Elgamal is a good solution a homomorphic multiplication?

I want to compute a multiplication between many secret values and then distribute the result to everyone involved. For this, I thought about an MPC protocol built from Threshold Homomorphic Elgamal. ...
1
vote
1answer
41 views

Elliptic ElGamal Public Key Cryptosystem doubt

I need an example of Elliptic ElGamal Public Key Cryptosystem. I have been trying with some values but I don't get the right solution. I have $p=13$, the elliptic curve $E:y^2=x^3+11x+7$ and a point ...
2
votes
1answer
68 views

Which values are used for an elgamal cryptosystem public key?

I know that – within the elgamal cryptosystem – the values of $a$ and $b$ are public. But which values are used to create public keys?
1
vote
1answer
407 views

How is El Gamal different from Diffie Hellman Key Exchange [duplicate]

I am Reading RSA and Public-Key Cryptography by Mollin and I can't make out how El Gamal is different from Diffie Hellman Key Exchange. Any thoughts?
7
votes
2answers
99 views

ElGamal in a different group

Can Elgamal be secure in $\bmod {n^2}$? Meaning instead of using a prime order group to use a group where DCR assumption holds?
0
votes
2answers
153 views

Random Coin Flip

Quoting an old question: Consider the following protocol for two parties A and B to flip a fair coin (more complicated versions of this might be used for Internet gambling): A trusted ...
2
votes
1answer
114 views

How to calculate mapping in bilinear

I am trying to read a paper in cryptography. In key generation phase, paper give a definition for bilinear like G and Gt be two cyclic groups of prime order p $e: G * G \to G_t$. be a map with the ...
4
votes
1answer
104 views

How to compare the efficiency of public key cryptosystems, i.e., RSA vs El Gamal?

As part of my Mathematics degree I'm taking a Discrete Mathematics module which partially covers Public Key Cryptography but does not at all enter it in depth. I'm currently working on a project that ...
2
votes
0answers
185 views

How to prove that a commitment hides the decryption of an ElGamal ciphertext?

I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question. For this question I need to prove that I've committed to a ...
4
votes
1answer
125 views

ElGamal Signatures

I know various applications of RSA signatures. I wonder, is there any real-world applications of ElGamal signatures and encryption?
0
votes
0answers
44 views

Batch ElGamal Scheme

I know about ElGamal scheme and its key generation, encryption, and decryption methods. I'm not sure about what is meant by batch ElGamal. Can someone please clarify it. How it differs from ElGamal ...
3
votes
1answer
56 views

Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

Please consider we have finite field $\mathbb{F}_p$ for large prime number $p$. We have a fixed field element $\alpha$. By $r_i\leftarrow \mathbb{F}_p$ we mean we pick $r_i$ uniformly random from the ...
2
votes
1answer
119 views

Is Cramer-Shoup backdoorable?

We recently had the question whether it's possible to have multiple private keys with one public key for the cramer-shoup cryptosystem. There it was stated that finding such "secondary" private keys ...
0
votes
1answer
55 views

ElGamal in $Z^*_{p^n}$

If $p$ is an odd prime and $n$ natural,it is known that the group $Z^*_{p^n}$ is cyclic.Explain why the selection-choice of the group $Z^*_{{3^{1000}}}$ for the construction of a cryptosystem ElGamal ...
1
vote
0answers
74 views

ElGamal signatures systems

Let $p$ prime number $q/p-1$ prime and $g\in (Z/pZ)^*$ element of order $q$.Also $a\in \{1,...,q-1\}$ the private key and $y\equiv g^a\pmod p$ the correspoding public key.For each of the following ...
1
vote
1answer
80 views

Ephemeral key is held constant in ElGamal

Is there a known algorithm to recover the sender's messages in ElGamal $\mathbb{F}_p^*$ if the ephemeral key is held constant in two or more transmissions, assuming the messages are always distinct? ...
1
vote
1answer
294 views

ElGamal and Paillier key sizes for short messages

I am using ElGamal and Paillier schemes to encrypt a large number of short messages: typical 4-byte integers. I do this for the homomorphic properties of these schemes. However, the way the ...
0
votes
1answer
66 views

Brute forcing the secret key in Elgamal encryption

Crypto noob here, I am attempting to do this programming challenge. I do not have the secret key that is used to decrypt the message. However, the key is small enough for a brute force approach. I am ...
3
votes
1answer
144 views

Is ElGamal IND-CCA1?

We all know that textbook ElGamal falls due to chosen ciphertext attacks, because of its multiplicative homomorphic property ($E(A)*E(B)=E(AB)$). However these attacks require the ciphertext ($E(A)$ ...
4
votes
2answers
693 views

ElGamal against chosen ciphertext attacks

In Hoffstein, Pipher, and Silverman's book An Introduction to Mathematical Cryptography, the authors make the following remark: An attack in which Eve has access to an oracle that decrypts ...
0
votes
1answer
153 views

ElGamal scheme attack when one message is known and ciphertexts are intercepted

Let $G$ be a finite cyclic group of order $p$ and let $pk = (g, h=g^a)$ and $sk=(g,a)$ be Bob's ElGamal public/secret key pair in $G$. To encrypt a message $m$, a random number $r$ is selected and a ...
3
votes
0answers
35 views

El-Gamal and Lines on Planes

I've been thinking about a geometric picture for El-Gamal. The idea is to understand the set $\{(my^{x},g^x) \mid x \in Z_p\}$ (the set of encryption of $m$ for fixed $g$ and $y$) by taking the $\...
4
votes
1answer
96 views

Why is the re-encryption algorithm in Universal Re-encryption for Mixnets more complicated than apparently necessary?

This is the paper. On page 6, the paper describes a variant of El Gamal and a way of re-encrypting ciphertexts. I thought an easier way to do encryption is to output $(m(g^x)^y,g^y)$, and universal ...
1
vote
1answer
210 views

ElGamal Generator g problem

Having an ElGamal encryption scheme with p=19 which value can not be assigned to g? The answers were : 1,7,11,2 I think you can't assign value 1 to g.
0
votes
1answer
67 views

Break El-Gamal Algorithm by knowing the value of the random k

In El-Gamal Algorithm, the public key is $(p, g, A)$, and the secret key is $(a)$, in order to encrypt some data, the sender generate a random $k$, where: $(C_1, C_2) = (m.A^{k} \pmod{p}, g^{k} \pmod{...
0
votes
1answer
93 views

How to perform homomorphic multiplication in ElGamal?

How can I compute homomorphic multiplication in ElGamal? That is: Given two ciphertexts $(R_1,c_1)$ and $(R_2,c_2)$ corresponding to plaintexts $m_1$ and $m_2$ under some public key; how can I compute ...
-1
votes
1answer
60 views

What does L_n is the bit length of the group order n states need for my calculation in ECDSA algorithm?

I am doing the program of implementing ECDSA for which I am trying to solve the equation scenario. In ECDSA that signature generation algorithm which states as hash value from the SHA-1 and where $l$ ...
3
votes
1answer
150 views

Secure ElGamal with OAEP

Is it possible to make ElGamal IND-CCA2 using OAEP or OAEP+? (OAEP+ from: "OAEP Reconsiderd" by Shoup) The reason I ask is that I recently answered this question and it came to my mind that OAEP or ...
1
vote
1answer
76 views

Zero knowledge proof relation + number is binary

I want to develop a ZKPK for the following problem: $$Y=g_0^{r_Y} \prod_{i=1}^n g_i^{s_i}$$ and $$Z=h_0^{r_Z} \prod_{i=1}^n h_i^{s_i}$$ I want to proof knowledge of $r_Y,r_Z$ and $s_i$ which I have ...
4
votes
1answer
229 views

Can the same random number be used in encryption and signing?

In several public key algorithms, the person running the algorithm must generate a random number (that's separate from the key). Can this random number be the same for an encryption and a signature? ...
4
votes
1answer
425 views

Reusing the random exponent for ElGamal encryption with different plaintexts

In the basic ElGamal encryption scheme, we encrypt a message $m$ as $(g^r, h^r m)$, where $g$ is the group generator and $h$ is the public key of the recipient. If the sender has another message $m'$ ...
1
vote
1answer
396 views

Drawback of ElGamal encryption

I am trying to find out some disadvantages of ElGamal cryptography but I'm not able to figure out what's wrong with the algorithm. The only one I found is that a known-plain text attack is possible in ...
0
votes
1answer
63 views

Check if this cryptosystem is safe

Let $G$ be any group where group operations, as well as finding the inverse of an element, can be performed quickly, but the discrete log problem is difficult. Consider the following cryptosystem: ...
1
vote
2answers
138 views

Usage of GF(p^m) fields, where p != 2

$GF(2^m)$ Galois fields are widely used in different cryptographic algorithms, for example, in Rijndael. However, $GF(p^m)$ fields are possible with any prime $p$, not only 2, but $GF(2^m)$ fields ...
0
votes
1answer
75 views

Converting a number to a member of a multiplicative cyclic group

I am currently trying to make an implementation of the ElGamal encryption for educational purposes. As I understand it, when using the encryption with multiplicative cyclic groups, one generates a ...
1
vote
1answer
165 views

ElGamal and Schnorr groups

As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime $p$ and use a multiplicative cyclic group with modulus $p$ and order $q = (p-1)/2$. ...
4
votes
2answers
251 views

Which multiplicatively homomorphic encryption scheme supports encryption of 0?

I want a multiplicatively homomorphic encryption scheme that supports encryption of 0 (e.g. Elgamal doesn't support). I also want the multiplication to be operated on the ciphertext of 0, i.e., if ...