Linked Questions

0 votes
1 answer

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

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

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

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

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

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

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

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

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

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

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