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$$ ?
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. ...
• 525
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 ...
• 2,867
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 ...
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 "...
• 23
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 ...
• 507
1 vote
173 views

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 ...
• 930
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 ...
• 123
1 vote
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 ...
1 vote
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\...
• 930
I have to elements of multiplicative group of finite field with generator g - $$g^x,g^y$$ Can I get? $$g^{xy}$$