Improved OT Extension for Transferring Short Secrets

In this post, we see an efficient Oblivious Transfer (OT) Extension technique for short secrets.  The OT extension protocol of IKNP stands as the basis for this protocol. The building block is an IKNP-based framework for 1-out-of-n OT extension. Before going into the details of the protocol, let’s have a quick overview of the IKNP protocol.

IKNP Protocol

We assume the existence of a correlation-robust hash function, H, and the protocol works in the static semi-honest security model.

Protocol Overview

S first acts as the receiver and R as the sender in the underlying k OTs. S chooses a random string s ∈ {0,1}^k as the selection bits and R inputs (tⁱ, tⁱ ⊕ r), i ∈ [k], tⁱ ∈ {0,1}ⁿ where r are the actual selection bits of R. S calls her ith chosen message in the underlying OTs qⁱ = tⁱ ⊕ s_i .r, where qⁱ is the ith column of a m x k matrix Q. Note that jth row of matrix Q, q_j = t_j ⊕ r_j . s. Finally, S sends the actual messages by sending z_j,0 = H(q_j) ⊕ x_j,0 and z_j,1 = H(q_j ⊕ s) ⊕ x_j,1 and R recovers x_j,ri by computing x_j,ri = H(t_i) ⊕ z_j,ri , where j ∈ [m] and H(∙) is the hash function.

Protocol Efficiency

The protocol makes a single call to OT^k_m. In addition, each party evaluates at most 2m times (an implementation of) a random oracle mapping k+log m bits to l bits. All other costs are negligible. The cost of OT^k_m is no more than k times the cost of OT¹_k (the type of OT realized by most direct implementations) plus a generation of 2m pseudo-random bits. In terms of round complexity, the protocol requires a single message from S to R in addition to the round complexity of the OT^k_m implementation. To summarize, the communication complexity of IKNP is O(m(k+l)) and for bit messages (l=1), the complexity turns out to be O(mk).

Now we can look to the efficient Oblivious Transfer (OT) Extension protocol of KK13. The main difference from IKNP is that each row of the matrix possessed by S is now used to perform a 1-out-of-n OT instead of 1-out-of-2, but of shorter secrets. On a very intuitive level, the protocol works as follows: Let C denote a binary code, and let r_j denote the input of R to the j-th instance of 1-out-of-n OT. For each row j, S receives (via OT) the actual j-th row of the m x k matrix XORed with a vector that is the result of the r_j-th codeword in C bitwise ANDed with the k-bit selection vector. This allows S to generate n random pads from each row of the matrix- the i-th such pad being the j-th row it received (via OT) XORed with a vector that is the result of the i-th codeword in C bitwise ANDed with the k bit selection vector. These n random pads may then be used by S to carry out a 1-out-of-n OT with R

KK Protocol

We assume the existence of a hash function (in the random oracle model), H, and the protocol works in the static semi-honest security model. It trades the length of messages for more gained OTs from the extensions.

Protocol Overview

Input of S is m tuples (x_j,0, … ,x_j,n-1) of l-bit strings while input of R is an m element selection vector r = (r₁, … , r_m) where each r_i can ranges from 1 to n. S first acts as the receiver and R as the sender in the underlying k OTs. S chooses a random string s ∈ {0,1}^k as the selection bits. R forms m x k matrices T₀ and T₁ in the following way: Choose t_j,0 , t_j,1 ← {0,1}^k  at random such that t_j,0 ⊕  t_j,1 = c_rj , where c_rj  is a Walsh-Hadamard code. R then inputs {(t_j,0, t_j,1)}_j∈[k]  for each of the k base OTs. S calls her ith chosen message in the underlying OTs qⁱ = t_i,si , where qⁱ is the ith column of a m x k matrix Q. Note that jth row of matrix Q, q_j = t_j,0 ⊕ c_rj . s. Finally, S sends  messages z_j,r = x_j,r ⊕ H(j, q_j ⊕ c_r.s) for 1≤ r ≤ n  and R recovers x_j,ri by computing x_j,ri = H(j,t_j,0) ⊕ z_j,ri , where j ∈ [m] and H(∙) is the hash function.

Protocol Efficiency

The protocol makes a single call to OT^k_m. The cost of OT^k_m is the cost of OT^k_k (which is independent of m) plus a generation of 2k pseudo-random strings each of length m. Other than this, each party evaluates at most mn times a random oracle. Thus the total communication cost of  OT^m_l is the communication cost of implementing OT^k_m plus mnl bits transferred between S and R, which turns out to be O(m(k+nl). In the semi-honest model, a single instance of 1-out-of-n OT may be used to generate log n instances of 1-out-of-2 OT over slightly shorter strings with no additional cost. More precisely, the cost of OT^m_l is exactly equal to the cost of 1-out-of-n OT^{m/log n}_{l.log n} . To summarize, the communication complexity of KK for 1-out-of-2 OT extension is O(mk / log(k/l) ) and for bit messages (l=1), the complexity turns out to be O(mk / log k).

BMR: Extended version of Yao's protocol for n players

Here we discuss how to extend Yao's protocol for any arbitrary 'n' players. In Yao's protocol, the responsibilities of the two players (Circuit constructor and Circuit Evaluator) are not at all alike. Hence, it is not trivial to see how to extend the protocol for any 'n' number of parties.

We start by assuming that the logical circuit C corresponding to the multi-party computation function f is already given, and we expect Semi-honest behaviour (at worst) from the parties, and the threshold for corrupted parties is (n-1).

In this extended protocol (BMR protocol), both construction and evaluation of the circuit is done collaboratively. Now we see how the protocol works.

BMR Protocol is having an Offline Phase and an Online Phase.

Offline Phase:

In the offline phase, we need to know nothing other than the circuit. Let there be 'W' wires in the circuit, indexed from 0 to W-1. At first, all players will (collaboratively) choose one random bit for each wire, namely λ­₀, λ­_1…, λ­_­w-1. Each λ­_i values are secret shared among all n parties. Then λ_j is reconstructed to party P_i, if ‘j’ is one of the input wires of P_i.

Now, each player will choose two random string (we call them 'two seeds') of length 'k', for each wire. Without loss of generality, we name those seeds s_­­­­­­­­­ⁱ_w,0 and s_­­­­­­­­­ⁱ_w,1 for each player i, for each wire w. Now we define SuperSeed for a wire w.

            S_w,0 = s¹_w,0 || s²_w,0 || .. sⁱ_w,0 .. || sⁿ_w,0

            S_w,1 = s¹_w,1 || s²_w,1 || .. sⁱ_w,1 .. || sⁿ_w,1

These two SuperSeeds will act as two different keys, and bears the meaning of the bits; just like two keys for each wire in Yao's protocol. But here, the SuperSeed S_­w,j need not represent the bit 'j' ; instead S_w,0 represent the bit λ­_w, and S_w,0 represent the bit λ­_w^c.

Please note that individual players know only their seeds on each wire, and λ values of all wires.

For the implementation of 4 (generally, but for NOT gate it’s 2) encryption boxes of a logic gate, We need two PRGs G¹ and G² both maps {0,1}^k → {0,1}^nk. Let a and b be the input wires of the gate g, and c be output wire of g. The cyphertexts corresponding to each Encryption Box is of the form:

Box 1: C₁ := ( G¹_­(s¹_a,0) ⊕ G¹_­(s²_a,0) .. ⊕ G¹_­(sⁿ_a,0) ) ⊕ ( G¹_­(s¹_b,0) ⊕ G¹_­(s²_b,0) .. ⊕ G¹_­(sⁿ_b,0) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a, λ_b) = λ_c ; r = 1 otherwise)

Box 2: C₂ := ( G²_­(s¹_a,0) ⊕ G²_­(s²_a,0) .. ⊕ G²_­(sⁿ_a,0) ) ⊕ ( G¹_­(s¹_b,1) ⊕ G¹_­(s²_b,1) .. ⊕ G¹_­(sⁿ_b,1) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a, λ_b^c) = λ_c ; r = 1 otherwise)

Box 3: C₃ := ( G¹_­(s¹_a,1) ⊕ G¹_­(s²_a,1) .. ⊕ G¹_­(sⁿ_a,1) ) ⊕ ( G²_­(s¹_b,0) ⊕ G²_­(s²_b,0) .. ⊕ G²_­(sⁿ_b,0) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a^c_, λ_b) = λ_c ; r = 1 otherwise)

Box 4: C₄ := ( G²_­(s¹_a,1) ⊕ G²_­(s²_a,1) .. ⊕ G²_­(sⁿ_a,1) ) ⊕ ( G²_­(s¹_b,1) ⊕ G²_­(s²_b,1) .. ⊕ G²_­(sⁿ_b,1) ) ⊕ S_c,r  ,

(Where r =0 if g(λ_a^c_, λ_b^c) = λ_c ; r = 1 otherwise)

We can see that, if each party just shares the PRG outputs of both seeds for the computation of these 4 cypherboxes and adversary have corrupted t parties, then the adversary can gain extra information about the messages in the boxes, that are not supposed to open in an execution (For eg: if t = n-1, and without loss of generality P₁ is the only honest player, then G¹(s¹_a,0)), G²(s¹_a,0)), G¹(s¹_a,1)), G²(s¹_a,1)) are leaked to the adversary, and he can compute all the S_c,r in all Boxes). So C₁, C₂, C₃ and C₄ should be a computed only by a Multi-Party Computation function. If that’s the case, adversary, who doesn’t know the seed(s) of honest party, will see the cypherboxes as One-Time padded messages with PRG outputs.

Now the λ_i for all output wires i are reconstructed and shared with every party. In the end of Offline phase, every party P_i knows,

•          2 Seeds of each wires
•          4 Cypherboxes for each gate g
•          Secret share of λ_j , for all wires j
•          λ_k , for all output wire k
•          λ_m , for all input wire (m) of the party P_i

Online Phase

Each party will evaluate the circuit in this phase. All parties know their input to their input wires. We define a new bit Δ_j of a wire j as follows:

                        Δ_j = b_j ⊕ λ_j

where b_j is the actual bit in a wire, in a specific evaluation. The Δ_j value of the input wire j of P_i can be calculated by the party P_i only; because only P_i knows λ_j. But everybody needs Δ to evaluate the circuit. So the owner of the input wire(s) will broadcast the Δ values of his input wires. In fact, after this step, all parties will get to know the Δ values of all the input wires in the circuit. For decrypting one logic gate, we need exactly one SuperSeed for each input wire. So every party will share their seeds sⁱ_w,Δ_w so that every party will get exactly one SuperSeed corresponding to Δ_j for each input wire j. With this information, players can decrypt exactly one CypherBox as follows:

Δa	Δb	Decryptable Box
0	0	C1
0	1	C2
1	0	C3
1	1	C­4

Using the SuperSeeds S_a,Δ_a and S_b,Δ_b , all parties can decrypt the CypherBox and get the SuperSeed of the output wire, and so on. But it’s not clear how to get Δ value of the new (output) wire. But every player knows their seeds on all the wires, and SuperSeed is nothing but appending all the seeds of players. So he will just check the seed bits corresponding to that player ((i-1)*k + 1 to i*k for player P_i) in the SuperSeed. If that happened to be equal to sⁱ_c,0 then the Δ_c is 0. Otherwise, it will be 1.

In short, after computing and sharing Δ_w values and SuperSeeds S_w,_Δw of all input wires w, no other communication between the parties are required. The entire circuit evaluation is done as local computation. Note that, Δ values are found and propagated in the circuit. As far as λ values are chosen random, by disclosing Δ values, no information about the actual bit b will be leaked.

Correctness

Consider the case when Δ_a = Δ_b = 0. We have to prove that Δ_c and S_c,Δc are correctly computed.

Δ_a = 0 ⇒ b_a = λ_a

Δ_b = 0 ⇒ b_b = λ_b

As per the table of decryptable cypherboxes, we will decrypt C₁.

• If g(λ_a, λ_b) = λ_c , that means g(b_a, b_b) = λ_c and we will be encrypting S_c,0 as message, in C₁ (see definition). We can see that Δ_c = 0, which is consistent with the definition of Δ. In this case,

1.      g(b_a, b_b) = λ_c

2.      g(b_a, b_b) = b_c

1 & 2 ⇒ λ_c = b_c

           ⇒ Δ_c = b_c ⊕ λ_c = 0

•  If g(λ_a, λ_b) = λ_c^c , that means g(b_a, b_b) = λ_c^c. We will de deciphering C₁, which is an encryption of SuperSeed S_c,1. We see Δ_c = 1 here, and consistent with definition of Δ. Here,

1.      g(b_a, b_b) = λ_c^c

2.      g(b_a, b_b) = b_c

1 & 2 ⇒ λ_c = b_c^c

          ⇒ Δ_c = λ_c ⊕ b_c  =  b_c^c ⊕ b_c = 1

When both Δ_a and Δ_b are 0, SuperSeed and Δ_c calculated are shown to be correct. All the other cypherboxes, we can prove with similar argument.

At the end of circuit evaluation, all parties will get to know the Δ values of output wires. We know the λ values of output wires (shared in offline phase). Hence we can compute b_c using the equation b_c =  λ_c ⊕ Δ_c  for each output wire c.

A Framework for Efficient and Composable Oblivious Transfer

We will explore a generic secure Oblivious Transfer protocol with the help of any dual-encryption cryptosystem. An Oblivious Transfer (OT) protocol is a cryptographic protocol between a sender A and a receiver B, which enables B to receive one out of two (or more) messages from A with respect to B's choice bit(s). The OT almost resembles an Encoder, omitting the security part. The transfer is said to be oblivious, because A is unaware of which message B received, and B does not receive any information about the remaining messages of A.

With this requirement in mind, we now see a new cryptographic primitive known as dual-mode encryption cryptosystem.  As the name suggests, this cryptosystem can be operated in 2 modes, which differ only in the Setup phase, which is run before the execution of protocol. The difference between the modes of operation is achieved through the generation of a parameter crs by the corresponding Setup algorithm, which is then passed to the remaining operations. The two modes are Messy Mode and Decryption Mode, and they each have their corresponding SetupMessy() and SetupDecryption() algorithms.

In addition to this, the cryptosystem can be operated in two branches. Denoting them as 0 and 1, it has the property that a message encrypted in one branch can only be decrypted in the same branch. This is fulfilled by giving the Key Generation algorithm an additional parameter b=0 or 1 to denote the branch.  It then outputs a public key-secret key pair for use in that particular branch.  

Additionally, Encryption also takes the branch as a parameter.  Decryption can only succeed if the given ciphertext and secret key are generated using Encryption and Key Generation (respectively) with respect to the same branch.

For a chosen mode, we can operate the cryptosystem in either of the two branches.

Given the properties we can intuitively see that a one-out-of-two OT protocol can be constructed as follows, for any mode of operation.

•        Both A and B receive the same crs corresponding to either Messy Mode/Decryption Mode.

•        A has messages m₀ and m₁

•        B picks a bit b, for which message he wishes to receive, and runs the key generation for branch b. He receives a secret key (sk) and public key (pk) for this branch.

•        B sends pk to A, who encrypts both his messages using this public key  as follows

•        He encrypts m₀ with the public key, and branch 0 to get c₀

•        He encrypts m₁ with the public key, and branch 1 to get c₁

•        He then sends both c₀ and c₁ to B

•        It is now easy to see that if B has b=0, he has the secret key for branch 0 and can decrypt c0. Similarly if he had b=1, he would have the secret key for branch 1 and he would be able to decrypt c₁.

We can clearly see from the property of the dual-mode cryptosystem that B cannot decrypt the ciphertext c_1-b as he does not have the secret key corresponding to the branch (1-b).  Additionally, since the sender receives only the public key, he cannot know which branch the receiver is operating in. This protocol satisfies the properties of OT. We also saw the security proof for each of the modes as follows.

Mode Security for	Messy	Decryption
Sender	Statistical Security	Computational Security
Receiver	Computational Security	Statistical Security

Security specified in each cell of this table can be proven using a Real World-Ideal World paradigm where we use the remaining functions defined (TrapKeyGen(), FindMessy() in cases of Decryption mode and Messy mode, respectively) along with the properties of the dual-mode cryptosystem, to aid the Simulator. The Simulator, who is the adversary in the ideal world, can then simulate the protocol with the real world adversary such that it is indistinguishable to the adversary from a complete real world execution.

Knowing that the only difference between the two modes lies in the generation of crs in the Setup phase, we can conveniently switch the mode of operation of the cryptosystem to change the levels of security for the sender and the receiver, depending on our protocol requirements.

There also exist several practical instantiations of the protocol, with security based on the DDH assumption and the Quadratic Residuosity assumption, among others.

We have seen that the dual-encryption primitive intuitively leads to a secure and practical OT protocol.

Multi Party Computation From Threshold Homomorphic Function in Semi-honest setting

Notation: m' is the ciphertext on encrypting m

Threshold homomorphic encryption is a homomorphic encryption scheme where t (threshold) parties alone cannot decrypt the secret. Decrypt algorithm takes common input m' and public key pk and secret input sk_i from party p_i (secret key is distributed among all parties) decrypts m' and discloses m to all parties.

PrivateDecrypt

PrivateDecrypt is a decryption sub-protocol that decrypts an encryption m' in such a way that only one particular participant learns the message. It is implemented in the following way:

 Let the intended party to receive decrypted message be p_i.

 1. p_i chooses a random value d and broadcasts d'.

 2. All the parties then compute e' = m' + d' and call Decrypt.

 3. Decrypt discloses the message e to all parties.

But only p_i can know original message m from the operation m = e - d.

  

Additive secret sharing

All participating parties know a' = ENC(a). They want to secret share a'.

 1. Each party p_i chooses a random value d_i and broadcasts d_i'.

 2. All parties compute d' such that d' = ∑d_i'.

 3. All parties compute e'=a' + d' and call Decrypt.

 4. Fix an ordering among parties. The first party in the order computes its share as a_i' = e' - d_i', a_i = e - d_i. Rest of the parties compute -d_j', -d _j as their share.

 Thus if all parties add their respective shares which is e'- d' = a'.

Multiplication protocol

The goal of this protocol is given two encryptions a', b' we have to share (ab)' among n parties.

 1. All parties additively secret share a'.

 2. Then every party multiplies a_i with b'.

 3. By the second homomorphic property of constant multiplication all parties together can compute (ab)' .