Question

Security Against B* OK, now for the fun part! To prove security against a dishonest B ∗ we must show that B ∗ learns nothing about a 1−b ​ . Formally, we must show that no efficient adversary can win the following OT B ​ - game with probability 1/2+ε for non-negligible ε>0 . The OT B ​ . Game. This game is played between a challenger C and adversary A as follows. - A begins by sending (a b ​ ,b)∈{0,1} 2 to C . - C chooses a 1−b ​ ∼{0,1} and generates a transcript T ′ by playing the protocol between an honest A and B ∗ where A uses input (a 0 ​ ,a 1 ​ ) . C sends T ⊤ to A . - A returns a bit c ′ ∈{0,1} to C signaling the end of the game. A wins if c ′ =a 1−b ​ . 10 Problem 11. Complete the following outline to prove security against B* (a) Use any A who plays in the OT OT B ​ game to build another adversary A ′ who, just like A , sends (a b ​ ,b)∈{0,1} 2 , receives a partial transcript T ^ ′ =(z,u ′ ,N,e,y 0 ​ ,y 1 ​ ,T,r 0 ​ ,r 1 ​ ,w b ​ )(i.e . ​ , a full transcript except that w 1−b ​ is missing) and then outputs a bit c ′ ∈{0,1} such that: \[ \operatorname{Pr}\left[c^{\prime}=\left\langle x_{1-b}, r_{1-b}\right\rangle\right]=\operatorname{Pr}[\mathcal{A} \text { wins }] \text {, } \] where x 1−b ​ ∈Z N ​ is such that =y 1−b ​ =x 1−b e ​ . (b) Finally, use A ′ to describe an adversary B who wins the inner product prediction game for RSA with probability Pr[ c ′ =⟨x 1−b ​ ,r 1−b ​ ⟩]−ν for a negligible ν>0 . Deduce that if \[ \operatorname{Pr}\left[\mathcal{A} \text { wins the } O \mathrm{~T}_{\mathrm{B}} \text {. game }\right]=\frac{1}{2}+\varepsilon, \] for non-negligible ε>0 , then B wins the inner product prediction game with probability 2 1 ​ +(ε−ν) . Note, (ε−ν) is non-negligible since ε>0 is non-negligible and ν>0 is negligible. As mentioned above, B can be used to break the RSA assumption. Thus, assuming the RSA assumption, the above OT scheme is secure against B*.

Answer 1

Secure OT against B* by building adversary A' that simulates transcript and outputs bit like honest A. This A' helps build adversary B who wins inner product prediction game with non-negligible advantage, contradicting RSA assumption. Hence, OT secure!

Completing the outline to prove security against B

Part (a): Building adversary A'

1. **Input:** A' receives (a_b, b) from the challenger.

2. Simulation:

* A' generates random values
`(z, u', N, e, y_0, y_1, T, r_0, r_1)` following the protocol steps for an honest A.

*
`A' sets w_b = (y_b - a_b * r_b)`mod N. This ensures consistency with the protocol.

* A' sends the partial transcript
`T' = (z, u', N, e, y_0, y_1, T, r_0, r_1, w_b)` to the challenger.

3. Output:

* A' receives the challenge bit c from the challenger.

* A' outputs
`c' = a_(1-b).`

Analysis:

* The partial transcript T' is indistinguishable from a real transcript generated by an honest A and B*, as all values are generated following the protocol steps.

* The output
`c' = a_(1-b)` is the same as the bit A would output if it successfully won the OT_B game.

* Therefore
`, Pr[c' = (x_(1-b), r_(1-b))] = Pr[A wins the OT_B game].`

**Part (b): Building adversary B for inner product prediction**

1. Input: B receives (N, e, z, u') from the challenger.

2. Simulation:

* B sets
`(a_0, a_1)` = (0, 1).

* B runs A' as a subroutine, providing (a_0, a_1) and receiving the partial transcript T'.

* B extracts
`(y_0, y_1, w_0, w_1)` from
`T'.`

3. Output:

* B outputs
`c' = a_(1-b)`as calculated by A'.

Analysis:

* B is essentially running A' on two different inputs
`(a_0, a_1)`and extracting the relevant values from the partial transcript.

* If the challenge bit c from the challenger is 0, B obtains y_0 and w_0, which are related to the inner product of
`x_0 and r_0.`

* Similarly, if the challenge bit c is 1, B obtains
`y_1` and
`w_1,`which are related to the inner product of
`x_1 and r_1.`

* By comparing the extracted values, B can potentially determine the inner product of the vectors.

Winning probability and security:

* The probability of B winning the inner product prediction game is
`Pr[c' = (x_(1-b), r_(1-b))] - ν,` where ν is negligible due to the negligible probability of A' making an error.

* If the
`OT_B` scheme is insecure, i.e.
`, Pr[A wins the OT_B game] = 1/2 + ε,` then B's winning probability becomes
`1/2 + (ε - ν).`

* Since ε is non-negligible and ν is negligible, B's winning probability is also non-negligible.

* This contradicts the RSA assumption, as B can break the inner product encryption scheme.

Therefore, assuming the RSA assumption holds, the
`OT_B` scheme is secure against a dishonest B* attacker.

Note: This is a high-level overview of the proof. The actual proof might involve additional details and calculations to formally demonstrate the indistinguishability and advantage of the adversary.