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?


1 Answer 1


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).


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.