Linked Questions

0 votes
1 answer
202 views

Why is it hard to compute $g^{xy}\bmod p$ from $g^x\bmod p$ and $g^y\bmod p$? [duplicate]

Why is it hard to compute $$(g^x\bmod p, g^y\bmod p) \longmapsto g^{xy}\bmod p $$ when can we quickly compute $$x \longmapsto g^x\bmod p$$ ?
Diego Starr's user avatar
13 votes
1 answer
12k views

Explanation of the Decision Diffie Hellman (DDH) problem.

I'm extremely new to crypto, and very much inexperienced. Lately I've been reading about the Diffie-Hellman key-exchange methods, and specifically about the computational diffie-hellman assumption vs. ...
Nico Bellic's user avatar
7 votes
1 answer
2k views

Proofs of security methodologies

I'm looking for course material on the subject of proofs, reductions, and games, as used to prove cryptographic schemes secure. What are the methodologies? What are the preferred ones? In what cases ...
Dingo13's user avatar
  • 2,867
4 votes
1 answer
282 views

Weak Decisional Diffie-Hellman Problem

Is this problem still hard? Given $$(g,g^a,g^b,c)$$ decide if $c=a\cdot b$? If there is an adversary that solves the standard Decisional Diffie-Hellman Problem then it can solve my new problem. But I ...
Mahdi Mahdavi's user avatar
2 votes
1 answer
480 views

Derive one public key from ECDH when the other and and the shared secret is known

Suppose we have an elliptic curve Diffie-Hellman key exchange protocol, where Bob and Alice have public keys $pk_{Alice}= [sk_{Alice}]G$ and $pk_{Bob}= [sk_{Bob}]G$ ($[.]$ elliptic curve "...
swim's user avatar
  • 23
-1 votes
1 answer
744 views

Computational Diffie-Hellman problem

From here, The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$. What happens if I knew one of the $x_1$, would it ...
user153882's user avatar
1 vote
1 answer
173 views

On access to a Diffie Hellman oracle

Assume $g$ is generator of multiplicative group modulo prime $p$. Assume we know $g^X\bmod p$ and $g^{XY}\bmod p$ and assume we can have access to a Diffie-Hellman oracle. Can we find $g^Y\bmod p$ in ...
Turbo's user avatar
  • 930
0 votes
1 answer
159 views

What's the meaning of asterisk and PPT in this paper?

I'm very new to cryptography. I'm required to read a paper. I totally don't understand. First, what's the meaning of the asterisk in $H:\{0,1\}^*\rightarrow \{0,1\}^k ?$. Second, what does PPT mean ...
user900476's user avatar
1 vote
1 answer
197 views

Elliptic Curve Cryptography : discrete log and Diffie-Hellman

Here's my current understanding of how ECC works. There is a recipient and a sender - Alice and Bob and each has a public and private key - (Alice's private key is denoted by a and public key is ...
Laksh Sharma's user avatar
1 vote
1 answer
112 views

Is this problem same as discrete logarithm?

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\...
Turbo's user avatar
  • 930
0 votes
1 answer
42 views

Multiplying between generators degree

I have to elements of multiplicative group of finite field with generator g - $$g^x,g^y $$ Can I get? $$g^{xy} $$
Alex's user avatar
  • 1