Recently, Boyle et. al. proposed silent OT extension. In the paper, silent OT, it seems that a GGM based PPRF used as building blocks. However, after reading the paper, I have two questions that are not clear:

  1. For $t$-points PPRF, the authors proposed to have $t$ independent single point PPRFs to be constructed such that those single point PPRFs can be added together to form one multiple point PPRF. Compared to Correlated OT(IKNP-style), which asks the receiver to input the choice bit vector (a.k.a. the points in PPRF), does it mean if I want $t$ 1's in COT choice bit vector, I need to set $t$ corresponding points in multiple point PPRF?

  2. Even compared this multiple point PPRF to Random OT, which still asks the receiver to input the choice bit vector, is there anyway to convert this random choice bit to chosen choice bit with little or no extra communication costs?

Thanks for any suggestions and helps.


1 Answer 1

  1. No, because this is just an intermediate step. Roughly, if you want to get $n$ standard (correlated or not) OTs where the receiver chooses what he gets, our construction has four main steps:

a) Build a correlated OT where the choice vector is a random $t$-sparse vector (a very large vector, but with only $t$ random 1's). This is what is done using a sum of $t$ PPRFs.

b) Transform the "correlated OT with sparse choice vector" into a "correlated OT with pseudorandom choice vector". This is done using the dual LPN assumption. The idea here is simple: after doing (a), the sender has $\Delta, \vec q_0$, and the receiver has $\vec b, \vec q_1$, where $\vec q_0 + \vec q_1 = \Delta\cdot \vec b$, where the vectors are of length $n$ and $\vec b$ is $t$-sparse (this is exactly $n$ correlated OT with a $t$-sparse vector of choice bits). Now, all parties multiply their vectors using a public random compressing matrix $H$: the sender has $(\Delta, H\cdot \vec q_0)$ and the receiver has $(H\cdot \vec b, H\cdot \vec q_1)$. Observe that

$H\cdot \vec q_0 + H\cdot \vec q_1 = H\cdot (\vec q_0+\vec q_1) = H\cdot (\Delta\cdot \vec b) = \Delta\cdot (H\cdot \vec b)$,

so this is still $n$ correlated OT, but now the vector of choice bits is $H\cdot \vec b$. By the dual-LPN assumption, if $\vec b$ is a random $t$-sparse vector, then this $H\cdot \vec b$ is indistinguishable from a truly random vector.

c) If you want non-correlated OTs in the end, transform the $n$ correlated OTs with pseudorandom choice bits above into $n$ standard OTs with random choice bits; this uses IKNP-style decorrelation, i.e., just hash everything with a correlation-robust hash function to "break" the correlation. If you are fine with correlated OTs, skip this step.

d) It only remains to convert your $n$ OTs with pseudorandom choice bits into OTs with chosen choice bits. This is actually your question 2:

  1. There is standard method to convert an OT with random choice bit (and random inputs as well) into a standard OT witch chosen inputs and choice bits. This involves three bits of communication per OT, which is optimal (you cannot hope to transmit one bit out of two chosen bits, using a chosen 'choice bit', using less than three bits of communication). Note that silent OT has communication sublinear in the total number of OTs generated, but only because the inputs and choice bits are pseudorandom - converted into standard OTs, they give OT with quasi-optimal communication, $3+o(1)$ bits per OT (amortized over $n$ instances).

The standard method is relatively simple. The sender has random inputs $(r_0,r_1)$ and true inputs $(s_0,s_1)$. The receiver has random choice bit $b$, knows $r_b$ (because of the random OT), and has true choice bit $\sigma$. Then, the receiver does the following ($\oplus$ denotes XOR):

  • If $b = \sigma$, ask the receiver to send $(u_0, u_1) = (r_0 \oplus s_0, r_1 \oplus s_1)$, and recover $s_\sigma = s_b = u_b \oplus r_b$.
  • If $b \neq \sigma$, ask the receiver to send $(u_0, u_1) = (r_0 \oplus s_1, r_1 \oplus s_0)$, and recover $s_\sigma = s_b = u_{1-b} \oplus r_b$.

Note that the message from the receiver to the sender involves communicating only $b \oplus \sigma$, i.e., telling the sender if $b = \sigma$ or not. Since $b$ is random, this reveals nothing about $\sigma$. Sender security is easy to see as well and is left as exercise for the reader :) In total, the above has two rounds and involves three bits of communication for each chosen OT.

  • $\begingroup$ Wow, it is my great honor to have the author answered my question. Thanks for your excellent explanations and now most things about the entire idea is quite clear and I really appreciate this fantastic idea. @geoffroy-couteau $\endgroup$
    – alexander
    Sep 29, 2020 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.