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 nave 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