1
$\begingroup$

In [1], the authors state:

[...] observe that unlike [32] the initial OT phase in Protocol 52 is completely independent of the actual inputs of the parties. Thus, the parties can perform the initial OT phase before their inputs are determined.

where “initial OT phase” refers to the base OT phase. In a follow-up/extension work by the same authors ([2]), the reference to [32] here is removed and the quote now reads:

[...] observe that the initial OT phase in Protocol 4 is completely independent of the actual inputs of the parties. Thus, the parties can compute the initial base-OTs before their inputs are determined.

My question is: is the claim in [1] (that [32]’s base OT phase is input-dependent) correct, or was it just a simple mistake? If it is correct, where in [32] is this shown? I could not find it but perhaps I am missing something.

References:

[1] (ALSZ) https://eprint.iacr.org/2013/552.pdf

[2] (ALSZ) https://eprint.iacr.org/2016/602.pdf

[32] (IKNP03) Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In Advances in Cryptology – CRYPTO’03, volume 2729 of LNCS, pages 145–161. Springer, 2003.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Yes, it is true. You can check for example this blog post: in the paragraph where it says “The OT extension we present here is from Ishai et al (2003)”, we can see that Step 4.1 requires the receiver to provide as input to the base OT two vectors $(t_j, u_j)$ such that the columns of the resulting matrices $T$ and $U$ (using the notation from the post) XOR to the choice bits, which are the receiver’s input.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So, [32] is “input-dependent” because T XOR-ed with U would give some value dependent on the choice bits r? It seems to me that the dependence on r is still present in [1], but it is just that the generation of the matrix U with information about the choice bits is moved to the “extension phase”, while generation of the random matrix T is (still) considered part of the baseOT phase. How is this different from similarly redefining what [32] calls the baseOT phase (i.e., considering the generation of T in [32] as part of the baseOT phase and the generation of U as part of the extension phase)? $\endgroup$
    – qmango
    Aug 2 at 4:42
  • $\begingroup$ Protocol 52 in [1] indeed uses the base OTs with input-independent data: “$S$ choose a random string $s = (s_1,\ldots,s_\kappa)$ and $R$ chooses $\kappa$ pairs of $\kappa$-bits seeds…” The base OT is run with these as inputs, which are uniformly random and independent of the actual inputs for the OT extension $\endgroup$
    – Daniel
    Aug 2 at 13:11
  • $\begingroup$ If generation of matrix U was moved out to the "extension phase" in [32], wouldn't its baseOT phase then also be input independent? $\endgroup$
    – qmango
    Aug 2 at 14:43
  • $\begingroup$ I don't think that's possible since it seems you do need both $T$ and $U$ for the base OTs (in fact these are the two messages) $\endgroup$
    – Daniel
    Aug 2 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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