# Tag Info

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.4k
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
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
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.7k

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,861
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

### 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....
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
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
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
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

### 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
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
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
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

• 221
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