2
$\begingroup$

It is known that by adding an extra round of communication, it is possible to convert a random OT (where the choice bits and the sender input are random) to a standard OT, see https://crypto.stackexchange.com/a/84206/48273 for details. OLE (oblivious linear function evaluation) is a generalization of OT. Specifically, for a random OLE, Alice gets output $(x', a')$ and Bob gets output $(y', b')$, where each element are in a finite field satisfying $x'y' = a' + b'$.

My question is: if Alice and Bob are given the tuples above, how do they perform OLE using their own input $x$ from Alice and $y$ from Bob so that $xy = a+b$ for some $a$ and $b$ using one round of communication?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Given the random OLE $(x',a'), (y',b')$:

  • Alice sends $u = x+x'$ and Bob sends $v = y+y'$.
  • Alice outputs $\alpha = a'-x'v$ and Bob outputs $\beta = b' + uy$.

Correctness follows easily:

$\alpha + \beta = a'+b' + uy - x'v = x'y' + (x+x')y - x'(y+y') = xy$,

and (perfect) security follows from the fact that $x',y'$ are uniformly random and perfectly mask $x,y$ (over, say, a finite field or a finite ring).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.