OT Extension

To meet the large-scale demand of OTs, OT extensions can be used. An OT extension protocol works by running a small number of base OTs that are used as a base for obtaining many OTs via the use of cheap symmetric cryptographic operations only. This is conceptually similar to hybrid encryption.

In this subsection, we focus on the maliciously secure OT extension presented in KOS15.

To be compatible with the garbled circuit optimizations, Correlated OT (COT) is considered here. COT is a variant of OT, where the sender chooses a secret string and the receiver has a choice bit . After the protocol, then sender obtains two strings and and the receiver obtains , where is a random string.

                    Sender                               Receiver
                       Delta  ------->|          |<------ b
                                      | COT Prot.|
     x_0 = x, x_1 = x + Delta <-------|          |-------> x_b 

Notation. Let be the security parameter, we use in zkOracles. Identify with the finite field . Use “” for multiplication in and “” for the component-wise product in . Given a matrix , denote its rows by subindices and its columns by superindices . Use to denote the -th entry of .

The KOS15 OT protocol to generate OTs is described as follows.

  • Initialize

    1. The receiver samples pairs of -bit seeds .

    2. The sender choose a uniformly random -bit string .

    3. The two parties calls the base OT with inputs and .

      • Note that the sender acts as the receiver in the base OT, and the receiver acts as the sender in the base OT.
    4. The sender obtains for .

  • Extend

    1. The receiver takes as input the choice bits , defines , where is the statistic parameter, and we set in zkOracles. Let , with uniformly chosen.

    2. The receiver defines vectors as for .

    3. The receiver expands and with a pseudo random generator (), letting

    4. The sender expands with the same and gets

    5. The receiver computes and sends them to the sender.

    6. The sender computes

    7. Let be the -th row of the matrix , and similarly let be the -th row of . Note that

  • Correlation Check

    1. The sender and receiver run a protocol to obtain random elements . will be described later.

    2. The receiver computes and sends them to the sender.

    3. The sender computes and checks . If the check fails, abort.

  • Output

    1. The sender computes and sends them to the receiver. is a tweakable hash function as used in garbled circuit.

    2. The sender outputs

    3. For , the receiver outputs the following:

This ends the description of the KOS15 protocol. We note that a very recent work pointed out that there is a flaw in the security proof of the main lemma of KOS15 and provided a fix, which is less efficient. They also pointed out that this the original KOS15 protocol is still secure in practice. Therefore, we choose the original KOS15 protocol in zkOracles in this version.

We begin to describe the protocol as follows.

  • The sender and receiver locally choose uniformly -bit random seeds and , respectively.

  • The sender and receiver compute commitments of the seeds by choosing -bit random strings and generate and , respectively.

  • The sender sends to the receiver, and the receiver sends to the sender.

  • On receiving the commitments, the sender and receiver open the commitments by sending and to each other, respectively.

  • The sender checks by re-computing it with , and the receiver checks by re-computing it with . If checks fail, abort.

  • The sender and receiver locally compute and generate random elements with a as