Improved OT Extension for Transferring Short Secrets

Improved OT Extension for Transferring Short Secrets

Vladimir Kolesnikov, Ranjit Kumaresan
CRYPTO 2013 [pdf] [bibtex]

Prerequisite:

This summary expects the reader to have a basic understanding of the IKNP03 protocol.

Introduction

KK describe an generalization and optimization to IKNP03 protocol for ⚠ {$OT$} extension in the semi-honest setting. The protocol provides a ⚠ {$O(\log k)$} performance improvement over the IKNP 1-out-of-2 ⚠ {$OT$} protocol and generalizes it to a 1-out-of-⚠ {$n$} ⚠ {$OT$} with the same asymptotic improvement over the state of the art 1-out-of-⚠ {$n$} ⚠ {$OT$}. The protocol is also applicable in the multi-party setting unlike the original IKNP version. In concrete terms, this yields a 2-3 factor performance improvement for the 1-out-of-2 ⚠ {$OT$} protocol.

The main observation made by KK is that in the IKNP protocol, the ⚠ {$Receiver$}'s selection vector ⚠ {$r$} is reused on each of the ⚠ {$k$} initial ⚠ {$OT$}s. This can be seen below on the left.

On each one of the (red/green) Column pairs, a 1-out-of-2 ⚠ {$OT$} is performed in the IKNP protocol. If you take the transpose of these columns, each red row encoding is ⚠ {$t_j\oplus \{1\}^k$} or ⚠ {$t_j\oplus \{0\}^k$} based upon the bit ⚠ {$r_j$}. Inspired by the observation that these repetitious codes (⚠ {$\{1\}^k$} and ⚠ {$\{0\}^k$}) dictate the receivers selection, what if the codes were vectors of ⚠ {$\{0,1\}^k$}. Would this enable to protocol to generalize to a 1-out-of-⚠ {$n$} ⚠ {$OT$}?

To accommodate a 1-out-of-⚠ {$n$} ⚠ {$OT$} protocol, the IKNP ⚠ {$Receiver$} selection vector ⚠ {$r\in \{0,1\}^m$} will need to be expanded to ⚠ {$r\in \{0,1,...,n-1\}^m$} to denote the ⚠ {$Receiver$}'s 1-out-of-⚠ {$n$} selection on all ⚠ {$m$} ⚠ {$OT$}s.

To securely achieve this result, the new ⚠ {$\{0,1\}^k$} vector codes will need to have a relative distance of ⚠ {$\frac{1}{2}$} between each other. That is, each code must be different enough from the others to maintain the security. The Walsh-Hadamard codes have this exact property. We will denote the Walsh-Hadamard encoding of ⚠ {$r_j$} as ⚠ {$c(r_j)$}.

1-out-of-n Protocol

Let the ⚠ {$Receiver$} generate ⚠ {$T_0$} as a ⚠ {$m \times k$} random bit matrix, shown below as the green vectors. Let ⚠ {$T_1$} be the matrix whose ⚠ {$j^{th}$} row is the ⚠ {$j^{th}$} row of ⚠ {$T_0$} XOR ⚠ {$c(r_j)$}, as seen below by the red vectors. Note: ⚠ {$k$} is the security parameter.

where ⚠ {$t_{j,0}$} is the ⚠ {$j^{th}$} row of ⚠ {$T_0$}, and ⚠ {$t_x^i$} is the ⚠ {$i^{th}$} column of ⚠ {$T_x$}

The protocol now performs ⚠ {$k$} 1-out-of-2 ⚠ {$OT$}s on the ⚠ {$k$} columns of the two matrices ⚠ {$T_0$} and ⚠ {$T_1$}, where the ⚠ {$Receiver$} acts as the sender. Note: these ⚠ {$OT$}s are the same as the IKNP protocol except that the rows of ⚠ {$T_1$} are ⚠ {$t_{j,0}$}⚠ {$\oplus c(r_j)$} instead of ⚠ {$t_{j,0}$}⚠ {$\oplus \{r_j\}^k$}.

As before in IKNP, the ⚠ {$Sender$} will randomly select between these two (red/green) columns for each of the ⚠ {$k$} pairs. Let ⚠ {$s\in \{0,1\}^k$} be the vector denoting this random selection and let ⚠ {$Q$} be the matrix denoting the collection of these ⚠ {$k$} ⚠ {$OT$}s when they are stored column wise. That is ⚠ {$q^i=t^i_{s_i}$}

As shown in blue, each row of ⚠ {$Q$} (denoted as ⚠ {$q_i$}) will be the corresponding row in ⚠ {$T_0$} XORed with the Walsh-Hadamard code for ⚠ {$r_i$} bitwise ANDed with ⚠ {$s$}. The main take away here is that each row of ⚠ {$Q$} has 1-out-of-⚠ {$n$} possible values if you fix ⚠ {$T_0$} and ⚠ {$s$}. In particular, this 1-out-of-⚠ {$n$} decision is made by the ⚠ {$Receiver$} and is unknown to the ⚠ {$Sender$}.

The initialization phase has now completed and the real 1-out-of-⚠ {$n$} ⚠ {$OT$}s can now be performed.

The ⚠ {$Sender$} will send the ⚠ {$Receiver$} an one time pad encryption of each of the ⚠ {$n$} messages for each of the 1-out-of-⚠ {$n$} ⚠ {$OT$}s. The ⚠ {$i^{th}$} messages in this ⚠ {$OT$} will be encrypted with the hash, ⚠ {$H(j,q_j\oplus ( c(i)\odot s ))$} as a one time pad mask. Based upon the ⚠ {$receiver$}'s choice of ⚠ {$r_j$}, exactly one of these messages will be equivalent to ⚠ {$H(j,$}⚠ {$t_{j,0}$}⚠ {$)$}. That is ⚠ {$q_j\equiv $}⚠ {$t_{j,0}$}⚠ {$\oplus (c(r_j)\odot s)$} will cancel with ⚠ {$( c(i)\odot s )$} leaving ⚠ {$t_{j,0}$} when ⚠ {$i=r_j$}.

Put algorithmically,
For each ⚠ {$j$} in the ⚠ {$m$} ⚠ {$OT$}s:

For each ⚠ {$i$} in the ⚠ {$n$} messages of the ⚠ {$j^{th}$} ⚠ {$OT$}:
The ⚠ {$Sender$} sends the ⚠ {$Receiver$}: ⚠ {$y_{j,i}=M_{j,i}\oplus H(j,q_j\oplus ( c(i)\odot s ))$}

Where ⚠ {$M_{j,i}$} is the ⚠ {$i^{th}$} message of the ⚠ {$j^{th}$} ⚠ {$OT$}.

The ⚠ {$Receiver$} will then decrypt the ⚠ {$y_{j,r_j}$} message by re-XORing ⚠ {$y_{j,r_j}$} with ⚠ {$H(j,$}⚠ {$t_{j,0}$}⚠ {$)$}. This results in ⚠ {$M_{j,r_j}$}, which is precisely the ⚠ {$Receiver$}'s desired message on the ⚠ {$j^{th}$} ⚠ {$OT$}. All of the other message encryptions of the ⚠ {$j^{th}$} ⚠ {$OT$} will remain pseudo random because the ⚠ {$Receiver$} does not know the random bit vector ⚠ {$s$} that the ⚠ {$Sender$} picked.

In sum, ⚠ {$m$} instances of a 1-out-of-⚠ {$n$} ⚠ {$OT$} can be obtained by ⚠ {$k$} instances of a 1-out-of-2 ⚠ {$OT$} plus at most ⚠ {$mn$} calls to a random oracle by both parties. Since ⚠ {$k$} is the security parameter this can yeild a significant improvement when ⚠ {$m$} becomes large.

1-out-of-2 Optimization

Let ⚠ {$n\choose 1$}-⚠ {$OT_{l}^{m}$} denote ⚠ {$m$} instances of a 1-out-of-⚠ {$n$} ⚠ {$OT$} each of length ⚠ {$l$}.

From an observation not shown here, ⚠ {$\log n$} instances of a ⚠ {$2\choose 1$}-⚠ {$OT$} can be obtained from a single instance of ⚠ {$n\choose 1$}-⚠ {$OT$} of slightly longer message length. Put precisely, a ⚠ {$2\choose1$}-⚠ {$OT_{l}^m$} has the same exact cost as a ⚠ {$n\choose 1$}-⚠ {$OT_{l\log n}^{m/\log n}$}. This hints that the generalization KK describe can also be used to further optimize the 1-out-of-2 variant.

With the use of this observation, ⚠ {$m$} instances of a 1-out-of-2 ⚠ {$OT$} can be obtained with the additional asymptotic cost of ⚠ {$O(mk/\log(k/l))$}, where ⚠ {$k$} is the security parameter. This contrasts with the IKNP cost of ⚠ {$O(m(k+l))$}. In the important case when ⚠ {$l=1$}, we obtain a logarithmic improvement over IKNP.

Random Oracle

Similar to the IKNP protocol, a ⚠ {$Code$}-⚠ {$Correlation$} ⚠ {$Robust$} random oracle is required to ensure a semi-honest ⚠ {$Receiver$} cannot learn ⚠ {$s$} and therefore all of ⚠ {$M$}. ⚠ {$Code$}-⚠ {$Correlation$} ⚠ {$Robustness$} is a property of a random oracle ensuring that no information about the input is leaked when the input are known values XORed/ANDed with an unknown value. Even if polynomial many queries with different know values are made. Specifically, the joint distribution of

⚠ {$\{t_1,t_2,...,t_n\}$} , ⚠ {$\{c_1,c_2,...,c_n\}$} and ⚠ {$H(t_j\oplus (c_{j'}\odot s)),H(t_l\oplus (c_{l'}\odot s)),...,H(t_n\oplus (c_{n'}\odot s)) $}

must be pseudo random, where ⚠ {$s$} is unknown and ⚠ {$H$} is queried a polynomial number of times with respect to the security parameter. This is a requirement because the ⚠ {$Receiver$} knows all of these ⚠ {$t_i$} and ⚠ {$c_i$} values. i.e. ⚠ {$t_{i,0}$} and ⚠ {$c(r_i)$}. If the correlations between the inputs and the hash values are not pseudo random, the ⚠ {$Receiver$} could learn ⚠ {$s$}, and thereby all of ⚠ {$M$}.

Summary

In summary, this protocol reduces ⚠ {$m$} instances of a 1-out-of-⚠ {$n$} ⚠ {$OT$} to a small security parameter number of 1-out-of-2 ⚠ {$OT$}s. In practice ⚠ {$m$} can be several orders of magnitude larger than the security parameter ⚠ {$k$}. For example ⚠ {$m=30000, k=256$}. This yields a significant performance increase over a naïve implementation of ⚠ {$m$} instances of a 1-out-of-⚠ {$n$} ⚠ {$OT$}. At the time this paper was published, the protocol results in a logarithmic improvement over the state of the art, which translates to an approximate speed up of 5 fold.

In addition, this 1-out-of-⚠ {$n$} protocol yields a performance improvement for the 1-out-of-2 variant when they are implemented by a black box use of this 1-out-of-⚠ {$n$} protocol. Beyond these improvement, KK describe another optimization by using a pseudo random generator instead of the completely random matrix ⚠ {$T_0$}.

References:

IKNP03

Other links:

CRYPTO presentation video

Categories:

OTExtension Todo