Reusing base Oblivious Transfers

Question

I am new to Oblivious Transfer (OT) and am having trouble finding a definitive answer regarding if/when/how baseOTs can be reused in a computation when using OT-extension (for passive security only).

Say two parties are running a secure function evaluation (SFE) protocol and need to use multiple rounds of oblivious transfer for some part of it (e.g., evaluating a 1-out-of-4 OT for each AND gate in the GMW protocol). It is my understanding that the parties can use, for example, k = 128 baseOTs in the “offline” phase to exchange symmetric keys and then later use these baseOTs to transfer the actual inputs in the “online” phase.

For each round of OT required by the SFE protocol, do the parties need to run the baseOTs again, or can one initial set of baseOTs be re-used for each SFE OT round?

Now say that, after computing the secure function evaluation protocol, both parties disconnect from each other and go offline. Later, they come back online and want to engage in another evaluation of the SFE protocol (e.g. over a different set of inputs).

Again, do the parties need to run the baseOTs again, or can the same baseOTs from before be re-used here?

Finally, say the parties want to evaluate a different type of secure function evaluation protocol that also uses OT. Can the same baseOTs be re-used here?

My intuition is that the answers to all of these questions are yes, but I cannot find any confirmation of this. I assume that it is probably good for the parties to repeat the baseOT step anyway every so often in case the seeds get compromised, but I am mostly just wondering if reusing the baseOTs in this way would be secure theoretically.

Answer 1

Once you and I have done 128 true base OTs, we never need to do any more of them again. By "true base OTs" I mean OTs that are implemented using public-key cryptography.

Here's an easy way to see it: Each time our protocol calls for a batch of $n$ OT instances from OT extension, we instead generate $n+128$ OT instances. We use the $n$ as usual, and save the other 128 to use as the "base OTs" for our next batch of OT extension. I call them base OTs because they are used as the seeds for OT extension, but they did not require any public-key operations so they are not "true" base OTs.

In practice, this approach turns out to be a little inelegant because IKNP-style OT extension protocols swap the role of sender and receiver compared to the base OTs. So you may have to do OT extension twice in this appraoch to keep the "orientation" of the OTs the way you want it.

There is a more direct way to see that you can reuse base OTs, by looking into the details of IKNP OT extension. After the base OTs, the IKNP protocol has all parties expand their OT values using a PRG. Each bit of the expanded OT values leads to an extended OT instance. In other words, if I want $n$ OT instances then I need a PRG that expands from 128-bit seeds to $n$-bit outputs.

These expanded OT values cannot be reused in the protocol, but you can keep expanding the original seed/base OT values with an indefinitely long PRG. So if you want to run OT extension, but have already used these base OTs to generate $n$ extended OT instances, you can run IKNP, expand the seeds with a PRG, but ignore the first $n$ bits of those expansions. You'll get a fresh/secure batch of extended OTs in this way. In practice it would be better to replace or combine the PRG with a PRF so you can get random access to this pseudorandom stream of bits.

Answer 2

Many OT extension protocols give you what is known as “Random OT”, which is like OT but the messages can’t be chosen and they are set to random instead. To get “chosen input” OT from Random OT, a simple de-randomization protocol is executed.

With this in mind, you can use a single instance of Random OT (perhaps generated with OT extension) and then de-randomize it, possibly over multiple rounds, to get OT.