MPC Study Group: Oblivious Transfer Extension Part 3

This week’s zoom meetup was postponed, these are some personal study notes for malicious oblivious transfer extension [1] which we partly covered last week.

Malicious Oblivious Transfer Extension

Last week we looked at how the semi-honest oblivious transfer protocol from [1, protocol 1] was not secure against a malicious receiver $P_r$. In particular, the protocol can be made malicious-secure if it is ensured that the receiver always uses the same $r$ in step 2(a) in protocol 1, for the computation of $u^i = t^i \oplus G(k^1_i) \oplus r$. We refer to this as checking the consistency of $r$, which is the topic of this post.

Consistency Check of $r$

First, let us deal with a somewhat easier problem. Instead of checking that all $u^i$ (or a sufficient amount of $u^i$) were created with the same $r$, we instead check that a pair $u^i$ and $u^j$ was created with the same $r$.

Before the start of the consistency check (step 3 in protocol 2 [1]):

  • The sender $P_s$ knows:
    • $s_i, s_j, k_i^{s_i}, k_j^{s_j}, u^i, u^j$.
  • The receiver $P_r$ knows:
    • $u^i, u^j, r^i, r^j, k_i^0, k_j^0, k_i^1, k_j^1$
    • Note: we define $r^i$ as its value as derived from $u^i$: $r^i = u^i \oplus t^i \oplus G(k_i^1)$.

The goal is for the sender $P_s$ to check that $r^i = r^j$, such that the verification passes if $r^i = r^j$ and $P_r$ is not trying to cheat, and that the verification fails with probability $\frac{1}{2}$ if $r^i \neq r^j$ or $P_r$ is trying to cheat.

Consistency check of a pair $u^i, u^j$:

  • $P_r$ computes and sends to $P_s$:
    • $h_{i, j}^{0,0} = H(G(k_i^0) \oplus G(k_j^0))$
    • $h_{i, j}^{0,1} = H(G(k_i^0) \oplus G(k_j^1))$
    • $h_{i, j}^{1,0} = H(G(k_i^1) \oplus G(k_j^0))$
    • $h_{i, j}^{1,1} = H(G(k_i^1) \oplus G(k_j^1))$
  • $P_s$ performs following checks, fail if any of the checks fail:
    • $h_{i, j}^{s_i, s_j} = H(G(k_i^{s_i}) \oplus G(k_j^{s_j}))$
    • $h_{i, j}^{\overline{s_i}, \overline{s_j}} = H(G(k_i^{s_i}) \oplus G(k_j^{s_j}) \oplus u^i \oplus u^j)$
    • $u^i \neq u^j$
    • Note: $s_i$, $s_j$ are the bits of the random vector of $P_s$, and $\overline{s_i} = 1 - s_i$.

This check fails with probability $\frac{1}{2}$ if $r^i \neq r^j$ or $P_r$ is trying to cheat, otherwise it passes. To verify this we should consider various cases, here we look at one specific case and refer to the paper for other cases:

  • Type 3 [1]: $r^i \neq r^j$ and two of $h_{i, j}^{a,b}$ for $a, b \in {0,1}$ are incorrect
    • wlog, assume that the adversary has set the values $h_{i, j}^{0,0}$ and $h_{i, j}^{0,1}$ correctly:
      • $h_{i, j}^{0,0} = H(G(k_i^0) \oplus G(k_j^0))$
      • $h_{i, j}^{0,1} = H(G(k_i^0) \oplus G(k_j^1))$
    • and the values for $h_{i, j}^{1,0}$ and $h_{i, j}^{1,1}$ incorrectly, a smart adversary may set these values to:
      • $h_{i, j}^{1,0} = H(G(k_i^0) \oplus G(k_j^1) \oplus u^i \oplus u^j)$
      • $h_{i, j}^{1,1} = H(G(k_i^0) \oplus G(k_j^0) \oplus u^i \oplus u^j)$
    • The verification passes if $s_i$ = 0, and the adversary learns that $s_i = 0$.
    • Because $s$ was chosen at random the verification fails with probability $\frac{1}{2}$.

Why does this work? Consider the four cases pf $s_i$ and $s_j$:

  • $s_i = 0$, $s_j = 0$, $P_s$ checks:
    • $h_{i, j}^{0, 0} = H(G(k_i^{0}) \oplus G(k_j^{0}))$
      • $h_{i, j}^{0, 0}$ was set correctly by adversary, so this check passes.
    • $h_{i, j}^{\overline{0}, \overline{0}} = H(G(k_i^{0}) \oplus G(k_j^{0}) \oplus u^i \oplus u^j)$
      • $h_{i, j}^{1, 1} = H(G(k_i^0) \oplus G(k_j^0) \oplus u^i \oplus u^j)$ (see above), thus the check passes.
    • $u^i \neq u^j$
  • $s_i = 0$, $s_j = 1$, $P_s$ checks:
    • Pass, similar to case $s_i = 0$, $s_j = 0$.
  • $s_i = 1$, $s_j = 0$, $P_s$ checks:
    • $h_{i, j}^{1, 0} = H(G(k_i^{1}) \oplus G(k_j^{0}))$
      • $P_r$ set $h_{i, j}^{1,0} = H(G(k_i^0) \oplus G(k_j^1) \oplus u^i \oplus u^j)$
      • Because $r^i \neq r^j$ we know that: $G(k_i^{s_i}) \oplus G(k_j^{s_j}) \oplus u^i \oplus u^j \neq G(k_i^{\overline{s_i}}) \oplus G(k_i^{\overline{s_j}})$.
      • Thus we know that $H(G(k_i^{1}) \oplus G(k_j^{0})) \neq H(G(k_i^0) \oplus G(k_j^1) \oplus u^i \oplus u^j)$ and the verification fails.
      • Note:
        • This is because $u^i \oplus u^j$
        • $= (t^i \oplus G(k_i^1) \oplus r^i) \oplus (t^j \oplus G(k_j^1) \oplus r^j)$
        • $= G(k_i^0) \oplus G(k_i^1) \oplus G(k_j^0) \oplus G(k_j^1) \oplus r^i \oplus r^j$.
        • From this it is easy to see that if $r^i = r^j$ they cancel out and: $u^i \oplus u^j = G(k_i^0) \oplus G(k_i^1) \oplus G(k_j^0) \oplus G(k_j^1)$.
        • Thus follows that iff $r^i = r^j$ then: $G(k_i^{s_i}) \oplus G(k_j^{s_j}) \oplus u^i \oplus u^j = G(k_i^{\overline{s_i}}) \oplus G(k_i^{\overline{s_j}})$.
  • $s_i = 1$, $s_j = 1$, $P_s$ checks:
    • Fail, similar to case $s_i = 1$, $s_j = 0$

This way we can check that a pair of $u^i$, $u^j$ used a consistent $r$. The protocol 2 [1] continues by performing this check for every pair of $u^i$, $u^j$. The verification passes with probability $(\frac{1}{2})^\rho$ for $p$ cheating attempts by the adversary. Meaning, the adversary may learn $\rho$ bits of $s$ but will be caught with a probability of $(\frac{1}{2})^\rho$. The consistency check does not reveal any further information.

Other Considerations

There are many details left out, so please check the reference [1]. The protocol requires further modifications to work with this consistency check. The number of oblivious transfers has to be increased by $\rho$ the statistical security parameter. And further, the $r$ value has to be appended with a random string $r’ = r || \tau$ to prevent a malicious sender from exploiting the consistency check. Further optimizations are possible, for example, reducing the number of consistency checks.


  • [1] Asharov, G., Lindell, Y., Schneider, T. and Zohner, M., 2015, April. More efficient oblivious transfer extensions with security for malicious adversaries. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 673-701). Springer, Berlin, Heidelberg. URL
MPC Study Group: Oblivious Transfer Extension Part 3 by Jonas Spenger, 24 Mar 2021, last updated on 24 Mar 2021.
Tags: Oblivious, Transfer, Extension, Secure, Multi-Party, Computation, Malicious, Zoom.
There are likely some errors I have missed, please contact me if you find any.
Check out more posts in the blog archive.
Next post: 29 Mar 2021 - Rust Language Test
Previous post: 17 Mar 2021 - MPC Study Group: Oblivious Transfer Extension Part 2
Most recent posts: