Questions tagged [elgamal-encryption]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
109 views

Decrypting a ciphertext in ElGamal's cryptosystem

I am a student in computer science currently working on a problem set in cryptography (practical problem but stuck on the math part). Basically, suppose we receive a message that has been encrypted ...
1
vote
1answer
90 views

Understanding Practical Differences Between ElGamal and Diffie-Hellman

I've been tasked with building a Web Assembly site that implements E2EE. I was thinking of using ElGamal Encryption to encrypt the message and Diffie-Hellman to establish the key. After doing further ...
2
votes
0answers
64 views

ElGamal with elliptic curves and semantic security

To encrypt a group element $P$ with public key $K$ and randomness $r$ using ElGamal on elliptic curves with base point $G$ we do the following $(c_1, c_2) = (r\cdot G; P+r\cdot K)$. When we want to ...
0
votes
1answer
65 views

Decryption of ElGamal ciphertext

If someone says that the decryption of an ElGamal ciphertext is "x", how can I be sure that the real value is "x" and not "y", even if he is the owner of the respective ...
0
votes
0answers
102 views

Using GP/PARI how would you solve this randomised Elgamal question?

I know how to solve this question manually, but I don't know how to solve it using the program gp/pari. It is based on randomised Elgamal Let p = 739. Given the following ciphertext of some message m1 ...
0
votes
1answer
63 views

ElGamal, message > p

Assume that we have: p = 89 g = 5 public key: 17 private key: 73 If we try to encrypt message M = 53 (M < p), then we get (c1, c2) == (55, 67) and further ...
2
votes
1answer
63 views

What is the quadratic character of the field over which elliptic curve is defined?

I'm trying to understand the injective encoding of a message to an elliptic curve point (from this paper). However, I'm not sure what do they mean by the quadratic character of the field. Do you know ...
0
votes
0answers
20 views

How to prove lifted ElGamal encryption with square root communication?

I'm looking for a more efficient solution to prove the correctness of multiple ciphertexts sent to different parties are correct. The background is that $P_i$ uses lifted ElGamal encryption to encrypt ...
0
votes
0answers
19 views

Group Signature by Camenisch and Stadler

Page 8, Paper: "Efficient Group Signature Schemes for Large Groups" by Camenisch and Stadler (1) I was trying to understand membership certificate part. I am have only basic knowledge of ...
0
votes
1answer
43 views

Can I use a certificate authority with Elgamal encryption?

Can I use a certificate authority with Elgamal encryption? Is this type of keys in CA?
0
votes
1answer
73 views

malleability of the Elgamal cryptosystem

In bidding for a contract, a company might outbid its competitor by simply multiplying its rival company’s encrypted bid by 0.9, without even knowing the bid. Now Suppose we are given the ciphertext c ...
1
vote
1answer
35 views

Short randomness in ElGamal and Paillier

In the Paillier cryptosystem the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$. My question is, what if short (E.g. 512bits) $r$ is used? ...
3
votes
1answer
106 views

Asymmetric encryption scheme with the shortest output for encrypting 1 byte of information

Imagine that one needs to periodically encrypt very short messages (i.e., a boolean Yes/No, a single byte, or 3-4 bytes in the worst case). We assume that there is no session, and we just need to ...
3
votes
3answers
180 views

How to calculate the n in n-bit security of a crypto algorithm?

I think I'm likely missing the term because searching for this is coming up with not so precise results. I'm looking to calculate the n-bit security of say Paillier vs ElGamal vs EC ElGamal, when I ...
2
votes
1answer
60 views

Paillier versus Lifted ElGamal for homomorphic addition for e-voting

I'm looking to create an anonymous e-Voting system which will assign a certain number of bits to each candidate during a vote, e.g. 010000 for Alice, 000100 for Bob, and 000001 for Charlie. It works ...
2
votes
2answers
261 views

What does OIW stand for

There seem to be many OID's that have been put in the ASN.1 tree that have the following ISO identified organization: OIW. One example is SHA-1 (ElGamal seems to be another): ...
1
vote
1answer
28 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
75 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
votes
1answer
123 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 ...
1
vote
0answers
52 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
1answer
2k views

Proving the CCA-insecurity of El Gamal encryption scheme

I am trying to prove that El Gamal Encryption is not CCA-Secure. If an adversary queried the encryption oracle for the encryption of $m=1$, he'll get a pair $(c_1,c_2)=(g^y,g^{xy}\cdot m)=(g^y,g^{xy}\...
0
votes
0answers
71 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
145 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
103 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
64 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
87 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
170 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 ...
1
vote
1answer
217 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
81 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 ...
2
votes
1answer
330 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://...
0
votes
0answers
62 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
2answers
127 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
53 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 ...
2
votes
1answer
184 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 ...
4
votes
1answer
245 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?
4
votes
1answer
436 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 ...
0
votes
0answers
81 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
86 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
60 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 ...
0
votes
0answers
63 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., ...
5
votes
1answer
571 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 ...
0
votes
1answer
75 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
95 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
40 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
108 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
2answers
325 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 ...
1
vote
1answer
590 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.
1
vote
0answers
112 views
0
votes
1answer
102 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
2 3 4 5
7