Skip to main content
Cryptography

Return to Answer

added 1069 characters in body
Source Link
user2552
user2552

To show that the protocol is secure under DDH, we need a reduction $R$ that takes a triple as input and outputs a transcript and key such that

  • if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
  • if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.

EDIT: General case

A transcript of a protocol looks like this (order may vary):

A1 to B: g^{a_1} ... An to B: g^{a_n} B to A1: g^{a_1.b} ... B to An: g^{a_n.b} shared key: g^b

A fake transcript (that is indistinguishable from a real one if it's secure) is the same except that the key at the end is $g^r$ for independent $r$. Note that even in a fake transcript, the same exponent $b$ is used for all messages from $B$.

Reduction $R$ takes a tuple $(A, B, C)$ and makes $n$ tuples by picking $u_i$ for $i$ from 1 to $n$ and sets $(A_i, B_i, C_i) = (A^{u_i}, B, C^{u_i})$. It then outputs the transcript $A_1, \ldots, A_n, C_1, \ldots, C_n, B$. If the orignal tuple was DDH, so are all these ones - so it is identical to a real transcript (in the real transcript, each $a_i$ introduces a degree of freedom; in the reduction, the $u_i$ do). And $B$ matches up too.

If the original tuple was random, $B$ is independent of everything else but the $A_i/C_i$ relations still hold so it's all distributed correctly.

To show that the protocol is secure under DDH, we need a reduction $R$ that takes a triple as input and outputs a transcript and key such that

  • if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
  • if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.

To show that the protocol is secure under DDH, we need a reduction $R$ that takes a triple as input and outputs a transcript and key such that

  • if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
  • if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.

EDIT: General case

A transcript of a protocol looks like this (order may vary):

A1 to B: g^{a_1} ... An to B: g^{a_n} B to A1: g^{a_1.b} ... B to An: g^{a_n.b} shared key: g^b

A fake transcript (that is indistinguishable from a real one if it's secure) is the same except that the key at the end is $g^r$ for independent $r$. Note that even in a fake transcript, the same exponent $b$ is used for all messages from $B$.

Reduction $R$ takes a tuple $(A, B, C)$ and makes $n$ tuples by picking $u_i$ for $i$ from 1 to $n$ and sets $(A_i, B_i, C_i) = (A^{u_i}, B, C^{u_i})$. It then outputs the transcript $A_1, \ldots, A_n, C_1, \ldots, C_n, B$. If the orignal tuple was DDH, so are all these ones - so it is identical to a real transcript (in the real transcript, each $a_i$ introduces a degree of freedom; in the reduction, the $u_i$ do). And $B$ matches up too.

If the original tuple was random, $B$ is independent of everything else but the $A_i/C_i$ relations still hold so it's all distributed correctly.

Source Link
user2552
user2552

To show that the protocol is secure under DDH, we need a reduction $R$ that takes a triple as input and outputs a transcript and key such that

  • if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
  • if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.