Improved OT Extension for Transferring Short Secrets

In this post, we see an efficient Oblivious Transfer (OT) Extension technique for short secrets.  The OT extension protocol of IKNP stands as the basis for this protocol. The building block is an IKNP-based framework for 1-out-of-n OT extension. Before going into the details of the protocol, let’s have a quick overview of the IKNP protocol.

IKNP Protocol

We assume the existence of a correlation-robust hash function, H, and the protocol works in the static semi-honest security model.

Protocol Overview

S first acts as the receiver and R as the sender in the underlying k OTs. S chooses a random string s ∈ {0,1}^k as the selection bits and R inputs (tⁱ, tⁱ ⊕ r), i ∈ [k], tⁱ ∈ {0,1}ⁿ where r are the actual selection bits of R. S calls her ith chosen message in the underlying OTs qⁱ = tⁱ ⊕ s_i .r, where qⁱ is the ith column of a m x k matrix Q. Note that jth row of matrix Q, q_j = t_j ⊕ r_j . s. Finally, S sends the actual messages by sending z_j,0 = H(q_j) ⊕ x_j,0 and z_j,1 = H(q_j ⊕ s) ⊕ x_j,1 and R recovers x_j,ri by computing x_j,ri = H(t_i) ⊕ z_j,ri , where j ∈ [m] and H(∙) is the hash function.

Protocol Efficiency

The protocol makes a single call to OT^k_m. In addition, each party evaluates at most 2m times (an implementation of) a random oracle mapping k+log m bits to l bits. All other costs are negligible. The cost of OT^k_m is no more than k times the cost of OT¹_k (the type of OT realized by most direct implementations) plus a generation of 2m pseudo-random bits. In terms of round complexity, the protocol requires a single message from S to R in addition to the round complexity of the OT^k_m implementation. To summarize, the communication complexity of IKNP is O(m(k+l)) and for bit messages (l=1), the complexity turns out to be O(mk).

Now we can look to the efficient Oblivious Transfer (OT) Extension protocol of KK13. The main difference from IKNP is that each row of the matrix possessed by S is now used to perform a 1-out-of-n OT instead of 1-out-of-2, but of shorter secrets. On a very intuitive level, the protocol works as follows: Let C denote a binary code, and let r_j denote the input of R to the j-th instance of 1-out-of-n OT. For each row j, S receives (via OT) the actual j-th row of the m x k matrix XORed with a vector that is the result of the r_j-th codeword in C bitwise ANDed with the k-bit selection vector. This allows S to generate n random pads from each row of the matrix- the i-th such pad being the j-th row it received (via OT) XORed with a vector that is the result of the i-th codeword in C bitwise ANDed with the k bit selection vector. These n random pads may then be used by S to carry out a 1-out-of-n OT with R

KK Protocol

We assume the existence of a hash function (in the random oracle model), H, and the protocol works in the static semi-honest security model. It trades the length of messages for more gained OTs from the extensions.

Protocol Overview

Input of S is m tuples (x_j,0, … ,x_j,n-1) of l-bit strings while input of R is an m element selection vector r = (r₁, … , r_m) where each r_i can ranges from 1 to n. S first acts as the receiver and R as the sender in the underlying k OTs. S chooses a random string s ∈ {0,1}^k as the selection bits. R forms m x k matrices T₀ and T₁ in the following way: Choose t_j,0 , t_j,1 ← {0,1}^k  at random such that t_j,0 ⊕  t_j,1 = c_rj , where c_rj  is a Walsh-Hadamard code. R then inputs {(t_j,0, t_j,1)}_j∈[k]  for each of the k base OTs. S calls her ith chosen message in the underlying OTs qⁱ = t_i,si , where qⁱ is the ith column of a m x k matrix Q. Note that jth row of matrix Q, q_j = t_j,0 ⊕ c_rj . s. Finally, S sends  messages z_j,r = x_j,r ⊕ H(j, q_j ⊕ c_r.s) for 1≤ r ≤ n  and R recovers x_j,ri by computing x_j,ri = H(j,t_j,0) ⊕ z_j,ri , where j ∈ [m] and H(∙) is the hash function.

Protocol Efficiency

The protocol makes a single call to OT^k_m. The cost of OT^k_m is the cost of OT^k_k (which is independent of m) plus a generation of 2k pseudo-random strings each of length m. Other than this, each party evaluates at most mn times a random oracle. Thus the total communication cost of  OT^m_l is the communication cost of implementing OT^k_m plus mnl bits transferred between S and R, which turns out to be O(m(k+nl). In the semi-honest model, a single instance of 1-out-of-n OT may be used to generate log n instances of 1-out-of-2 OT over slightly shorter strings with no additional cost. More precisely, the cost of OT^m_l is exactly equal to the cost of 1-out-of-n OT^{m/log n}_{l.log n} . To summarize, the communication complexity of KK for 1-out-of-2 OT extension is O(mk / log(k/l) ) and for bit messages (l=1), the complexity turns out to be O(mk / log k).