Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# Tag Info

## Hot answers tagged elgamal-encryption

13 votes
Accepted

### Zero knowledge proof for sign of message value

What you are looking for is called a range proof. There has been a vast body of research on the topic recently - so vast, in fact, that it can be quite hard to know what is the state of the art, and ...
• 20.2k
13 votes
Accepted

### What is largest prime factor in Diffie-Hellman?

How to determine if the largest prime factor of $p-1$ is in fact large? Most often, it is not determined from $p$ that $p-1$ has a large prime factor. Rather, a large prime factor $q$ is chosen, ...
• 142k
12 votes
Accepted

### Exponentiation in ECC

In a group, where there is by definition only one operation, exponentiation means repeated application of the group operation, whatever that is. That is, if the group operation is noted $\circ$, $g$ ...
• 8,152
11 votes
Accepted

### ECIES/ ECDHE/ EC-ElGamal encryption comparison

Fix a group $G$ of order $q$ in which discrete logs are hard, and fix a standard base point $g \in G$. Fix an authenticated cipher $E_k$ of bit strings. In (EC)IES, roughly: A public key is a point ...
• 48.6k
9 votes

9 votes
Accepted

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

As a general rule most counterexamples will be very contrived. If you don't mind that, it's actually not too hard to come up with a separating example. First consider what power we have in CCA1 that ...
• 6,852
8 votes

### Time gap between Diffie-Hellman Key Exchange and ElGamal encryption?

Actually, if you read Diffie and Hellman's paper closely, you'll see that they explicitly talk about taking another's party value from a public file. Thus, it really already does public-key encryption....
8 votes
Accepted

### ElGamal with elliptic curves II

I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen ...
• 148k
8 votes
Accepted

### XOR instead of Multiplication in ElGamal encryption

One small question, from the DDH assumption we know $g^{xy}$ is random. Actually, that's not true. What the DDH assumption says is that we cannot distinguish $g^{xy}$ from $g^z$; however it does not ...
• 148k
7 votes
Accepted

### Why is it claimed that ElGamal is worse than RSA?

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's ...
• 142k
7 votes
Accepted

### ElGamal CPA secure

So let's go through the IND-CPA game, shall we? Pick two messages $m_0$ and $m_1$ arbitrarily. Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c=E(m_b)$. ...
• 46.1k
7 votes
Accepted

### ElGamal in $\mathbb Z^*_p$ with $g$ not a generator of $\mathbb Z^*_p$

Because in the exercise $g$ is is not a generator of $\mathbb Z^*_p$, the exercise would indeed be incorrect in a context explicitly giving a definition of ElGamal encryption that both requires $g$ ...
• 142k
7 votes

### What is largest prime factor in Diffie-Hellman?

My question is the following: how to determine if the largest prime factor of $p-1$ is in fact large? Yes, showing that $p-1$ is not smooth (terminology for "has a large prime factor") for random ...
• 148k
6 votes
Accepted

### One-wayness proof of Elgamal

You are confusing two different security notions. The proof you describe is regarding the Onewayness under chosen-plaintext attacks (OW-CPA). Basically, this notion covers the idea that it shouldn't ...
• 5,002
6 votes
Accepted

### On getting beyond LSB in discrete log

If $p = 2q+1$ where $q$ is prime, and then we can efficiently solve for $x_0 \in \{0, 1\}$ for $g^{2x+x_0} = h \pmod p$, if $g$ is a generator. This is true; this is a special case of the observation ...
• 148k
6 votes
Accepted

### How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem?

Having multiple sets $b_i^k = g_i$ with a common solution $k$ do not help you recover $k$; it cannot make the problem much easier than if you had the simple equation $b^k = g$. Here's the proof; ...
• 148k
6 votes

• 221
5 votes
Accepted

### How to create an EC point from a plaintext message for encryption

The standard approach for this goes as follows, which I think is usually attributed to this paper by Koblitz: Suppose you have a curve over an $k$-bit prime field. Also suppose you want to encode a ...
• 46.1k
5 votes
Accepted

• 5,002
4 votes

### What is the correct test/s to do in asymmetric algorithms to test their security?

If you're looking to test the parameters for an RSA or ElGamal implementation, well, that's fairly straightforward (assuming you can look at the innards of the implementation, and ask "are these ...
• 148k

Only top scored, non community-wiki answers of a minimum length are eligible