# A Novelk-out-of-n Oblivious Transfer Protocol from Bilinear Pairing

Authors: Jue-Sam Chou
Journal: Advances in Multimedia
 (2012)

---

## Abstract

Oblivious transfer (OT) protocols mainly contain three categories: 1-out-of-2 OT, 1-out-of-n  OT, and k-out-of-n OT. In most cases, they are treated as cryptographic primitives and are usually executed without consideration of possible attacks that might frequently occur in an open network, such as an impersonation, replaying, or man-in-the-middle attack. Therefore, when used in certain applications, such as mental poker games and fair contract signings, some extra mechanisms must be combined to ensure the security of the protocol. However, after a combination, we found that very few of the resulting schemes are efficient enough in terms of communicational cost, which is a significant concern for generic commercial transactions. Therefore, we propose a novel k-out-of-n oblivious transfer protocol based on bilinear pairing, which not only satisfies the requirements of a k-out-of-n OT protocol, but also provides mutual authentication to resist malicious attacks. Meanwhile, it is efficient in terms of communication cost.


---

## Body

## 1. Introduction

An oblivious transfer (OT) is an important primitive for designing security services. It can be used in various applications like the signing of fair contracts, oblivious database searches, mental poker games, privacy-preserving auctions, secure multiparty computations [1], and so on. In 1981, Rabin [2] first proposed an interactive OT scheme in which the probability of the receiver’s capability to decrypt a message sent by the sender is 1/2. Rabin used the proposed OT to design a 3-pass secret exchange (EOS) protocol, hoping that two parties can exchange their secrets fairly. In 1985, Even et al. [3] presented a more generalized OT, called 1-out-of-2 OT (OT12), in which a sender sends two encrypted messages to a chooser with only one of which the chooser can decrypt. They also presented a contract-signing protocol by evoking OT12 multiple times to prevent one party from obtaining the other party’s contract signature without first showing his own. In 1986, Brassard et al. [4] further extended OT12 into a 1-out-of-n OT (OT1n, also known as “all-or-nothing”), in which only one out of n sent messages can actually be obtained by the chooser. The authors pointed out that their OT1n scheme can be used to implement a multiparty mental poker game [5] against a player coalition. In contrast to the interactive versions described above, Bellare and Micali [6] first proposed a noninteractive OT12 scheme in 1989. In this scheme, a user obliviously transfers two messages to another party equipped with two public keys to decrypt one of the messages.From 1999 to 2001, based on the above-mentioned interactive and noninteractive OT schemes, Naor and Pinkas proposed some related OT methods, such as an adaptiveOTkn [7], proxy OT12 [8], distributed OTkn [9], efficient OT1n [10], and efficient OTkn [11]. Here, OTkn is the final form of the OT schemes. In this form, from the n encrypted messages sent, the chooser can obtain k chosen messages in plaintext form without the sender’s knowledge regarding which part of the messages are decrypted. In Naor and Pinkas’s distributed OTkn schemes [9], the sender distributes two messages (M0,M1) among n servers, and the chooser contacts k(k<n) servers to receive one (Mσ,σ=0or1) of them. The authors claimed that their schemes can protect the privacy of both parties. However, in 2007, Ghodosi [12] showed two possible attacks on these schemes. In the first attack, two collaborating servers can reveal the chooser’s choice of σ, while, in the second attack, the chooser can learn both M0 and M1 by colluding with only a single server. In 2002, Mu et al. [13] proposed three OTkn schemes constructed using RSA encryption, a Nyberg-Rueppel signature, and an ElGamal encryption scheme, respectively. Two of these are interactive, while the other can be either interactive or noninteractive. The authors claimed that their schemes are complete, robust, and flexible and induce a significant improvement in communication cost. However, in 2006, Ghodosi and Zaare-Nahandi [14] showed that these schemes fail to satisfy the requirements of an oblivious transfer protocol. In 2004, Ogata and Kurosawa [15] proposed another OTkn scheme, based on an RSA blind signature, which can be employed in either an adaptive or a nonadaptive manner. The authors claimed that their scheme can be applied to oblivious key searching. In 2005, three OTkn  schemes are proposed [16–18]. Among these, Chu and Tzeng's scheme [16] is the most efficient as it needs only 2 passes to send 1024 k bits from the chooser to the sender, and 1024*(k+1)+n*|Data| bits from the sender to the chooser, where Data is a message or ciphertext, and |Data| represents the bit length of Data. In 2006, Parakh [19] proposed an elliptic-curve-based algorithm allowing A to obliviously transfer his secrecy, nA, to B with a 50% probability of success. However, we found that A can decide whether B can obtain his secret nA (which is one-to-one mapped to PnA) by first assuming that PA=PB. Under this assumption, upon receiving {nBPB;nB(nAPA)+R;nBR} from B, Acan obtain B’s one-time random variable R by computing (nB(nAPA)+R)-nA(nBPB). Then, by computing nA(nBR) = nB(nAR), A can obtain nBK. Subsequently, by computing (nA(nBR)+PnA)-nBK, A obtains ZB, just as B does in step 5(b). Therefore, if A finds ZB = PnA, it confirms that B can obtain nA after the protocol runs; otherwise, it knows B cannot obtain the value of nA. This violates B’s privacy. In the same year, for coping with all possible attacks encountered in an open network, Kim and Lee [20] proposed two OT12 protocols, which are modified from Bellare-Micali noninteractive OT12 scheme [6] by appending the sender’s signature to make the sender undeniable about what he sent and be authentic to the chooser. However, we found, other than the weaknesses pointed by Chang and Shiao [21], Kohnfelder’s protocol still has the reblocking problem [22]. Because when modulus nA>nB, message MA cannot be recovered by Bob. This makes legal Alice unable to be authenticated by Bob.In 2007, Halevi and Kalai [23] proposed another OT12 scheme by using smooth projective hashing and showed that the used RSA composite in their scheme need not be a product of safe primes. Also in 2007, Camenish et al. and Green and Hohenberger proposed two related OT schemes [24, 25], respectively. Both focus on the security of full simulatability for the sender and receiver to resist against selective-failure attack [7]. In 2009, Qin et al. [26] proposed two noninteractive OT1n schemes. However, in their protocols, a receiver has to interact with a third party to obtain the choice-related secret key each time it wants to select one of the n sent message. This makes their scheme somewhat inconvenient and inconsistent with the meaning of noninteractive protocols as indicated in the title (this phenomenon can also be found in some proposed noninteractive OT schemes). In the same year, Chang and Lee [27] presented a robust OTkn scheme using both the RSA blind signature and Chinese Remainder Theorem. However, we found their scheme fails since the sender can decide which parts of the messages were chosen by the chooser. We will describe this weakness in Section 3.2. In addition, in 2011, Ma et al. [28] proposed an oblivious transfer using a privacy scheme for a timed-release receiver. Their scheme has a good timed-release property. However, it needs to call ZKP k times to learn k of the n sent messages. This makes their protocol less efficient. Moreover, it does not have mutual authentication. Therefore, when the sender and receiver want to communicate, they need a secure channel. Otherwise, without identity authentication, malicious attackers can simultaneously launch many ZKPs. This will degrade the system performance and may cause the system to suffer from a denial-of-service (DOS) attack (according to the definition in [29]).After surveying all of the above-mentioned OT schemes, we found that almost all of them lack the consideration of adding security features. Only [2, 20] do consider the protection against all possible attacks. However, study [20] fails which we have described earlier. Hence, if we wish all of the proposed OT protocols, other than scheme [2], to be able to resist against various attacks, we should run them through secure channels. This would incur extra communicational overhead. For this reason, in this paper, we propose a novel interactive OTkn scheme that needs only two passes but can get rid of using a secure channel to avoid adding extra communicational overhead. It not only is simple in concept but also encompasses some essential security features such as mutual authentication, the prevention of man-in-the-middle (MIMA) attack, and replay attack. Thus, when compared with other interactive OT schemes, our scheme promotes not only in the communicational efficiency but also in the aspect of security.The rest of this paper is organized as follows. The introduction has been presented in Section1, and some preliminaries are shown in Section 2. In Section 3, we review Chang et al.’s scheme and show its weakness. After that, we show our protocol in Section 4. Then, the security analyses and communicational cost comparisons among related works and our scheme are made in Section 5. Finally, a conclusion is given in Section 6.


## 2. Preliminaries

In this section, we briefly introduce the security features of ourOTkn scheme in Section 2.1, the principles of bilinear pairing in Section 2.2, and some intractable problems used in this paper in Section 2.3.


### 2.1. Security Features of OurOTkn Scheme

Just as traditional OT schemes, ourOTkn also has two parties, the sender S and the chooser C. In the scheme, S obliviously transfers n messages to C, and C can choose k messages among them without S’sknowledge about which k messages were selected, where n≥2 and k<n. In addition, our scheme also possesses the following three security features which are needed in a traditional OT scheme.(1) Correctness
After the protocol run,C should be able to obtain the valid data chosen by him before.(2) Chooser’s Privacy
In the protocol, each of thek chooser’s choices should not be known to the sender or any third party. More precisely, each of the chooser’s encrypted choice can be any valid choice with equal probability, that is, for an encrypted choice y and any valid choice x, Pr[x∣y]=Pr[x]. This property is known as Shannon  perfect secrecy.(3) Sender’s Privacy
At end of the protocol run, the chooser cannot get any knowledge about the other messages it did not choose. More formally, the ciphertexts sent by the sender are semantically secure [30]. The chooser can obtain a plaintext decrypted from its ciphertext only if it has the key offered by the sender.Except for the above three properties, our interactiveOTkn scheme also has the following three security features, (4) through (6), to guard against possible security threats.(4) Impersonation Attack Resistance
Each party has to authenticate the counterpart. That is, it should be a mutual-authentication OT.(5) Replaying Attack Resistance
An adversary could not obtain any messages by only replaying old messages sent by the sender.(6) Man-in-the-Middle Attack (MIMA) Resistance
MIMA is an attack that an adversary eavesdropping on the communication line between two communicating parties uses as some means to make them believe that they each are talking to the intended party. But indeed, they are talking to the adversary.


### 2.2. Bilinear Pairing

LetG1 be an additive group composed of points on an elliptic curve with order q, and let G2 be a multiplicative group with the same order. A bilinear mapping is defined as ê:G1×G1→G2 which must satisfy the following properties [31].(1)
Bilinear: a mappingê:G1×G1→G2 is bilinear if ê(aP,bQ)=ê(P,Q)ab for all P, Q∈G1 and all a,b∈Zq*.(2)
Nondegenerate: the mapping does not map all pairs inG1×G1 to the identity in G2.(3)
Computable: there is an efficient algorithm to computeê(P,Q) for any P,Q∈G1.(4)
IfP is a generator for G1 then ê(P,P) is a generator for G2.(5)
Commutative: for allP1,P2∈G1,ê(P1,P2)=ê(P2,P1).(6)
Distributive: for allP1,P2,P3∈G1,ê(P1+P2,P3)=ê(P1,P3)ê(P2,P3).


### 2.3. Some Diffie-Hellman Problems

Leta,b,c,g∈RZq*, let P be a base point of a group on an Elliptic curve, and let G=〈g〉, G1=〈P〉, and G2=〈g(=ê(P,P))〉  bethree groups with each having a prime order q. Using these definitions, we describe some well-known intractable Diffie-Hellman problems [32] that will be used in this paper.(1) The Computational Diffie-Hellman (CDH) Problem
InG, given (g,ga,gb), finding the element C=gab mod q.(2) The Decisional Diffie-Hellman (DDH) Problem
InG, given (g,ga,gb,gc), deciding whether c=ab mod q.(3) The Bilinear Computational Diffie-Hellman (BCDH) Problem
Given(P,aP,bP,cP) in G1, finding ê(P,P)abc in G2.
According to Boneh and Franklin’s study [31], the BCDH problem is no harder than the CDH problem in G (or equivalently G2).(4) Chosen-Target CDH (CTCDH) Problem
LetH:{0,1}*→G be a hash function, let T(·) be a target oracle which returns a random element in G, and (·)c a helper oracle which returns T(j)c when queried by T(j), where c is an unknown random integer in Zq*. Also, let qt be the number of queries to T(·) and qh the number of queries to (·)c. The CTCDH problem is finding l pairs of (j1,v1),…,and(jl,vl), with each satisfying vi=(T(ji))c, for 1≤i≤l and qh<l≤qt. Without loss of generality, we can let qh and qt be l-1 and l, respectively. The CTCDH problem can then be rephrased as that after obtaining T(j1),…,T(jl) and (j1,v1),…,(jl-1,vl-1) via querying the T(·) oracle and the helper oracle (·)c correspondingly, trying to find the lth pair (jl,vl) without the knowledge of c. The CTCDH problem is proposed and considered as a hard problem by Boldyreva in 2002 [33]. Its former version in RSA is proved by Bellare et al. in [34].


## 2.1. Security Features of OurOTkn Scheme

Just as traditional OT schemes, ourOTkn also has two parties, the sender S and the chooser C. In the scheme, S obliviously transfers n messages to C, and C can choose k messages among them without S’sknowledge about which k messages were selected, where n≥2 and k<n. In addition, our scheme also possesses the following three security features which are needed in a traditional OT scheme.(1) Correctness
After the protocol run,C should be able to obtain the valid data chosen by him before.(2) Chooser’s Privacy
In the protocol, each of thek chooser’s choices should not be known to the sender or any third party. More precisely, each of the chooser’s encrypted choice can be any valid choice with equal probability, that is, for an encrypted choice y and any valid choice x, Pr[x∣y]=Pr[x]. This property is known as Shannon  perfect secrecy.(3) Sender’s Privacy
At end of the protocol run, the chooser cannot get any knowledge about the other messages it did not choose. More formally, the ciphertexts sent by the sender are semantically secure [30]. The chooser can obtain a plaintext decrypted from its ciphertext only if it has the key offered by the sender.Except for the above three properties, our interactiveOTkn scheme also has the following three security features, (4) through (6), to guard against possible security threats.(4) Impersonation Attack Resistance
Each party has to authenticate the counterpart. That is, it should be a mutual-authentication OT.(5) Replaying Attack Resistance
An adversary could not obtain any messages by only replaying old messages sent by the sender.(6) Man-in-the-Middle Attack (MIMA) Resistance
MIMA is an attack that an adversary eavesdropping on the communication line between two communicating parties uses as some means to make them believe that they each are talking to the intended party. But indeed, they are talking to the adversary.


## 2.2. Bilinear Pairing

LetG1 be an additive group composed of points on an elliptic curve with order q, and let G2 be a multiplicative group with the same order. A bilinear mapping is defined as ê:G1×G1→G2 which must satisfy the following properties [31].(1)
Bilinear: a mappingê:G1×G1→G2 is bilinear if ê(aP,bQ)=ê(P,Q)ab for all P, Q∈G1 and all a,b∈Zq*.(2)
Nondegenerate: the mapping does not map all pairs inG1×G1 to the identity in G2.(3)
Computable: there is an efficient algorithm to computeê(P,Q) for any P,Q∈G1.(4)
IfP is a generator for G1 then ê(P,P) is a generator for G2.(5)
Commutative: for allP1,P2∈G1,ê(P1,P2)=ê(P2,P1).(6)
Distributive: for allP1,P2,P3∈G1,ê(P1+P2,P3)=ê(P1,P3)ê(P2,P3).


## 2.3. Some Diffie-Hellman Problems

Leta,b,c,g∈RZq*, let P be a base point of a group on an Elliptic curve, and let G=〈g〉, G1=〈P〉, and G2=〈g(=ê(P,P))〉  bethree groups with each having a prime order q. Using these definitions, we describe some well-known intractable Diffie-Hellman problems [32] that will be used in this paper.(1) The Computational Diffie-Hellman (CDH) Problem
InG, given (g,ga,gb), finding the element C=gab mod q.(2) The Decisional Diffie-Hellman (DDH) Problem
InG, given (g,ga,gb,gc), deciding whether c=ab mod q.(3) The Bilinear Computational Diffie-Hellman (BCDH) Problem
Given(P,aP,bP,cP) in G1, finding ê(P,P)abc in G2.
According to Boneh and Franklin’s study [31], the BCDH problem is no harder than the CDH problem in G (or equivalently G2).(4) Chosen-Target CDH (CTCDH) Problem
LetH:{0,1}*→G be a hash function, let T(·) be a target oracle which returns a random element in G, and (·)c a helper oracle which returns T(j)c when queried by T(j), where c is an unknown random integer in Zq*. Also, let qt be the number of queries to T(·) and qh the number of queries to (·)c. The CTCDH problem is finding l pairs of (j1,v1),…,and(jl,vl), with each satisfying vi=(T(ji))c, for 1≤i≤l and qh<l≤qt. Without loss of generality, we can let qh and qt be l-1 and l, respectively. The CTCDH problem can then be rephrased as that after obtaining T(j1),…,T(jl) and (j1,v1),…,(jl-1,vl-1) via querying the T(·) oracle and the helper oracle (·)c correspondingly, trying to find the lth pair (jl,vl) without the knowledge of c. The CTCDH problem is proposed and considered as a hard problem by Boldyreva in 2002 [33]. Its former version in RSA is proved by Bellare et al. in [34].


## 3. Review of Chang et al.’s Protocol

In 2009, Chang et al. proposed a robustOTkn scheme based on CRT, hoping that their scheme can achieve the security requirements of a general OTkn scheme. However, we found their scheme cannot satisfy the chooser’s privacy. In the following, we first review the scheme in Section 3.1 then show the weakness found in Section 3.2.


### 3.1. Review

We roughly describe the protocol by listing the relevant steps in the following (see [27] for more details).Step 1.
After receiving the request from Bob for all messagesa1,a2,…,an, Alice owning these n messages selects n relatively prime integers, d1,d2,…,dn, and computes D= d1*d2*⋯*dn. She then constructs the congruence system
(1)C≡a1mod⁡d1,C≡a2mod⁡d2,…,C≡anmod⁡dn.Furthermore, Alice computes the following values: T1=d1emodN, T2=d2emodN,…, and Tn=dnemodN, where N be the product of two large primes and (e,d) be Alice public/private key pair satisfying ed=1modφ(N), by using her public key e. Finally, she publishes C and the n pairs of (IDi,Ti), for i=1 to n, in the public board.Step 2.
If Bob wants to learnk messages among them, he must select k pairs of (IDj′,Tj′), for j=1 to k, from the public board and first generate k corresponding random numbers r1,r2,…,rk, for each pair of (IDj′,Tj′). Then, he subsequently computes the following:
(2)α1=r1e*T1′mod⁡N,α2=r2e*T2′,mod⁡N,…,αk=rke*Tk′mod⁡N,
by using Alice’s public key e and sends {α1,α2,…,αk} back to Alice.Step 3.
Upon receiving the messages sent by Bob, Alice employs her private keyd to compute β1=α1d=r1T1′d=r1d1′modN, β2=α2d=r2T2′d=r2d2′modN,…,βk=αkd=rkTk′d=rkdk′modN and then sends the results {β1,β2,…,βk} to Bob.Step 4.
After receiving the messages from Alice, Bob computes the following values:d1′=r1-1*β1modN,d2′=r2-1*β2modN,dk′=rk-1*βkmodN. Consequently, Bob learns the demanded messages successfully by computing
(3)b1=Cmod⁡d1′,b2=Cmod⁡d2′,…,bk=Cmod⁡dk′.


### 3.2. Weaknesses

Although Chang et al. claimed that their scheme can satisfy the security requirements demanded by theOTkn scheme, we found that Bob’s privacy has been violated, since according to their protocol, Alice first sets n values of di (i=1 to n), and Bob commits his k choices to the k values of αj(j=1 to k). After computing the k values of βj (=1 to k), Alice can use each of the di-1s (i=1 to n) to compute rji = βj*di-1, for j=1 to k and i=1 to n. In addition, using each rji, Alice can compute the n values of αi(*) = (rji*di)e, for i= 1 to n, to compare with the k committed values, αj. For example, suppose Bob chooses the first message, T1=d1e mod N, and Alice wants to guess which Ti Bob chose, Alice starts to use d1-1  to compute r11 = β1*d1-1  mod N=α1d(=r1*d1)*d1-1modN=r1modN. He will get α1(*)=(r11*d1)e mod N=α1 = r1e*T1. That is, Alice will find a match, α1, and knows that Bob chose the first message. Conversely, if Alice uses di-1, (i=2,n) to compute r1i=β1*di-1, he will get αi(*) = (r1i*di)e mod N, which is not equal to α1. In other words, Alice cannot know the correct message T1 that Bob chose. That is, once a pair, (αi(*), αi), for example, has been matched, Alice knows that Bob chose the ith message. Hence, we can easily see that such explorations cost at most n*k multiplications to obtain  rji, and n2*k multiplications and n2*k exponentiations to yield all values of αi(*). Therefore, with at most (n2*k+n*k) multiplications and n2*k exponentiations, it is computationally feasible for Alice to decide which k values Bob selected, which violates Bob’s privacy.


## 3.1. Review

We roughly describe the protocol by listing the relevant steps in the following (see [27] for more details).Step 1.
After receiving the request from Bob for all messagesa1,a2,…,an, Alice owning these n messages selects n relatively prime integers, d1,d2,…,dn, and computes D= d1*d2*⋯*dn. She then constructs the congruence system
(1)C≡a1mod⁡d1,C≡a2mod⁡d2,…,C≡anmod⁡dn.Furthermore, Alice computes the following values: T1=d1emodN, T2=d2emodN,…, and Tn=dnemodN, where N be the product of two large primes and (e,d) be Alice public/private key pair satisfying ed=1modφ(N), by using her public key e. Finally, she publishes C and the n pairs of (IDi,Ti), for i=1 to n, in the public board.Step 2.
If Bob wants to learnk messages among them, he must select k pairs of (IDj′,Tj′), for j=1 to k, from the public board and first generate k corresponding random numbers r1,r2,…,rk, for each pair of (IDj′,Tj′). Then, he subsequently computes the following:
(2)α1=r1e*T1′mod⁡N,α2=r2e*T2′,mod⁡N,…,αk=rke*Tk′mod⁡N,
by using Alice’s public key e and sends {α1,α2,…,αk} back to Alice.Step 3.
Upon receiving the messages sent by Bob, Alice employs her private keyd to compute β1=α1d=r1T1′d=r1d1′modN, β2=α2d=r2T2′d=r2d2′modN,…,βk=αkd=rkTk′d=rkdk′modN and then sends the results {β1,β2,…,βk} to Bob.Step 4.
After receiving the messages from Alice, Bob computes the following values:d1′=r1-1*β1modN,d2′=r2-1*β2modN,dk′=rk-1*βkmodN. Consequently, Bob learns the demanded messages successfully by computing
(3)b1=Cmod⁡d1′,b2=Cmod⁡d2′,…,bk=Cmod⁡dk′.


## 3.2. Weaknesses

Although Chang et al. claimed that their scheme can satisfy the security requirements demanded by theOTkn scheme, we found that Bob’s privacy has been violated, since according to their protocol, Alice first sets n values of di (i=1 to n), and Bob commits his k choices to the k values of αj(j=1 to k). After computing the k values of βj (=1 to k), Alice can use each of the di-1s (i=1 to n) to compute rji = βj*di-1, for j=1 to k and i=1 to n. In addition, using each rji, Alice can compute the n values of αi(*) = (rji*di)e, for i= 1 to n, to compare with the k committed values, αj. For example, suppose Bob chooses the first message, T1=d1e mod N, and Alice wants to guess which Ti Bob chose, Alice starts to use d1-1  to compute r11 = β1*d1-1  mod N=α1d(=r1*d1)*d1-1modN=r1modN. He will get α1(*)=(r11*d1)e mod N=α1 = r1e*T1. That is, Alice will find a match, α1, and knows that Bob chose the first message. Conversely, if Alice uses di-1, (i=2,n) to compute r1i=β1*di-1, he will get αi(*) = (r1i*di)e mod N, which is not equal to α1. In other words, Alice cannot know the correct message T1 that Bob chose. That is, once a pair, (αi(*), αi), for example, has been matched, Alice knows that Bob chose the ith message. Hence, we can easily see that such explorations cost at most n*k multiplications to obtain  rji, and n2*k multiplications and n2*k exponentiations to yield all values of αi(*). Therefore, with at most (n2*k+n*k) multiplications and n2*k exponentiations, it is computationally feasible for Alice to decide which k values Bob selected, which violates Bob’s privacy.


## 4. Proposed Protocol

In this section, we present our ID-basedOTkn protocol based on bilinear pairings, which were proved and applied to cryptography by Boneh and Franklin in 2001 [31]. Our scheme consists of two phases: (1) an initialization phase and (2) an oblivious transfer phase. In the following, we first describe these two phases. Then, to demonstrate the chooser’s privacy preservation, we use a misleading attack for an explanation. As the receiver’s privacy preservation can be reasoned in a similar fashion, we omit its description here.(1) Initialization Phase
In this phase, we adopt the same system parameters as the ones used in [31]. In addition, there also exists a trusted key generation center (KGC) which is assumed to be key-escrow-attack free. Initially, KGC chooses an additive group G1=〈P〉 of order q, a multiplicative group G2=〈ê(P,P)〉 of the same order, where ê is a bilinear mapping, that is, ê:G1×G1→G2, and three one-way hash functions: H: {0,1}*→{0,1}l, H2:G1→{0,1}l, and H1 which maps a string (a user’s ID) to an element in G1, that is, H1:{0,1}*→G1. Moreover, it selects s∈Zq* as its private master key and computes the corresponding system public key asPpub=sP. Then, KGC publishes the system parameter set {G1,G2,q,ê,P,Ppub,H,H1,H2}. After that, when a user U (sender/chooser) registers his identifier IDU, KGC will compute a public/private key pair Upub/Upriv for him, where Upub= H1(IDU) and Upriv = sUpub.(2) Oblivious Transfer Phase
In this phase, when a sender possessingn messages (m1,m2,…, and mn) wants to obliviously transfer k messages of them (mσ1,mσ2,…,and mσk) to a chooser, they together will execute the following steps, where the public/private key pairs of the sender and chooser are Spub/Spriv and  Cpub/Cpriv, respectively, and {σ1,σ2,…,σk}⊂{1,2,…,n} are the set of k choices selected by the chooser in advance. We also depict them in  Table 1.Table 1
The proposedk-out-of-n authentic OT protocol.
Sender (Spub/Spriv(=sSpub))Chooser(Cpub/Cpriv(=sCpub))(1) Selects,b∈RZq*, computes V=abCpub, for  j=1 to k, computes Vj=bH(σj)Cpriv, computes h=H2(V) and Sig=hCpriv.←IDC,V,V1,…,Vk,Sig(2) Computesh=H2(V) and verifiesê(P,Sig)=?ê(Ppub,hCpub). If it does not hold, aborts.      Selects c∈RZq* and computes Uj=cVj, for j=1,…,k, and cti=mi⊕ê(H(i)V,Spriv)c, for i=1,…,n.→U1,…,Uk,ct1,…,ctn(3) Forj=1 to k and i=1 to n, computes mσi=ctσi⊕ê(Uj,Spub)a.Step 1.
The chooser randomly chooses two integersa,b∈Zq* and computes V=abCpub, Vj=bH(σj)Cpriv, where j=1,2,…,k and Vj are the k random choices. After that, he generates a signature Sig on V by computing h=H2(V) and Sig=hCpriv. Then, he sends IDc,V,V1,…,Vk together with Sig to the sender.Step 2.
After receivingIDc,V,V1,…,Vk and Sig from the chooser, the sender computes h=H2(V) and verifies the chooser’s signature by checking whether the equation ê(P,Sig)= ê(Ppub,hCpub) holds. If it holds, he believes that the chooser is the intended party as claimed. Then, the sender randomly chooses an integer c∈Zq* and computes Uj=cVj and cti=mi⊕ê(H(i)V,Spriv)c, where j=1,…,k,i=1,…,n, and mi are the n messages. He/She then sends U1,…,Uk,ct1,…,andctn to the chooser.Step 3.
After receiving the messageU1,…,Uk,ct1,…,  and ctn from the sender, the chooser can obtain the k intended messages by at most computing the equation, mσj=ctσj⊕ê(Uj,Spub)a,nk-·(k(k-1)/2)(=n+(n-1)+⋯+(n-(k-1))) times.(3) A Misleading Attack for Chooser’s Privacy Preservation
To demonstrate the chooser’s privacy more clearly, we take the following as a counterexample. According to step1 in our protocol, the chooser computes V1,…,Vk, where Vj=bH(σj)Cpriv and j= 1 to k. Since b and Cpriv are both the same for Vi and Vj, a misleading attack may be that Vi/Vj=H(σi)/H(σj). A malicious sender can pre-compute H(σi)/H(σj) for each  i,j in the interval [1,n]. After receiving V1,…,Vk from the chooser, he computes each Vi/Vj for all i,j in [1,k] for a comparison with the precomputed values. Consequently, the sender may guess some or all of the chooser’s choices. Therefore, the protocol cannot achieve chooser privacy. However, the mistake here is that both Vi  and Vj are points in the additive group G1. The division operation Vi/Vj is invalid because G1 is an additive group.


## 5. Security Analysis

In this section, we use the following claims to show that our protocol not only is correct but also possesses the properties of mutual authentication, chooser’s privacy, and sender’s privacy and can resist against active attacks such as relay attack, man-in-the-middle attack, and denial of service attack.Claim 1.
The proposed protocol is correct.Proof.
After the protocol runs, the chooser can exactly obtain thek messages which he/she selected by computing
(4)ctσj⊕ê(Uj,Spub)a=ctσj⊕ê(cbH(σj)Cpriv,Spub)a=ctσj⊕ê(H(σj)bcsCpub,Spub)a=ctσj⊕ê(H(σj)abCpub,sSpub)c=ctσj⊕ê(H(σj)V,Spriv)c=mσj.Claim 2.
The proposed protocol can achieve mutual authentication.Proof.
We show the holdness of this claim by using the following two reasons.
(1)
Apparently, it can be easily seen that the sender can authenticate the chooser by verifying the chooser’s signature, Sig (as described in step2 of the oblivious transfer phase).(2)
For that the ciphertextcti(=mi⊕ê(H(i)V,Spriv)c) contains the sender’s private key Spriv(=sSpub), the chooser can compute the meaningful message mσj only via using the sender’s public key Spub (also refer to the equation in claim 1). This means that only the true sender can produce the right cti and thus can be authenticated by the chooser using his public key.Claim 3.
The proposed protocol can achieve the chooser’s privacy.Proof.
Due to the fact that each of the chooser’sk choices σj∈{1,2,…,n} are first hashed and randomized by H and b respectively, and then signed as Vj=bH(σj)Cpriv by chooser C in step 1, where b is a random number. We argue that nobody except for the chooser can know the choice σj. Because even an attacker might steal the chooser’s private key Cpriv, he/she cannot obtain bH(σj) from Vj owing to the hardness of ECDLP. That is, he cannot figure out bH(σj), and therefore not to mention σj. More formally, let 𝒜={(b,σj)∈Zq*Zn∣bH(σj)Cpriv=Vj}; that is, 𝒜 consists of all the possible ordered pairs (b,σj) satisfying the equation bH(σj)Cpriv=Vj. If we are given a value Vj, then under fixed Cpriv, there only exists a unique value bH(σj) satisfying the equation. And for a given bH(σj), under the definition of a collision-free one-way hash function, once σj has been determined, the value of b is determined as well. That is, the relationship between b and σj is one-to-one. Having this observation in mind and the dimension of σj is n, we can see that there are n(b,σj) pairs in 𝒜. In other words, Pr [σj∣Vj] = Pr [σj] = 1/n which means that, under seeing a specific Vj, the choice σj of the chooser cannot be revealed other than guessing. This achieves the Shannon perfect secrecy. Therefore, the proposed protocol possesses chooser’s privacy.Claim 4.
The proposed scheme can achieve the sender’s privacy.Proof.
Assume that malicious chooserĈ wants to obtain more than k messages in the protocol. If he/she could succeed, then, the sender’s privacy is violated (see Section 2.1). However, we will prove that, other than his k chosen messages, it is computationally infeasible for Ĉ to obtain the (k+1)th message by using the following two arguments, (I) and (II). In argument (I), we show why Ĉ must follow the protocol to form the values of V and kVjs; otherwise, he/she cannot obtain the k chosen messages. In argument (II), we show that if Ĉ intends to obtain the (k+1)th message, he/she will face the intractable CTCDH problem under the assumption that H(·) is a random hash function.Argument (I)
Ĉmust follow the protocol to form the values of V(=abĈpub) and Vj(=bH(σj)Ĉpriv), for j=1 to k; otherwise, he cannot obtain the k chosen messages, mσ1,…,mσj.
In the following, we further divide this argument into three cases: (a)Ĉfakes V but forms Vj honestly, (b)  Ĉ fakes Vj but forms V honestly, and (c)  Ĉ fakes both the values of V and Vj. (For each case’s explanation, refer to Table 1.)
(a)
Ĉ fakes V but forms Vj honestly. Assume that Ĉ is dishonest in forming V but forms Vj honestly as specified in the protocol. For example, without loss of generality, it replaces V with a specific X∈G1 and computes Vj=bH(σj)Ĉpriv. Then, the sender will compute Uj=cVj, cti=mi⊕ê(H(i)X,Spriv)c and send them back to Ĉ. As a result, Ĉ cannot decrypt ctσj(ctσj=mσj⊕ê(Uj,Spub)a) to obtain the k messages since ê(Uj,Spub)a is obviously not equal to ê(H(σj)X,Spriv)c (refer to claim 1). Perhaps, for obtaining the k messages, Ĉ may try another way by computing ê(H(i)X,Spriv)c expected to be equal to ê(Uj,Spub)a. But this is computationally infeasible since Ĉ does not know both the sender’s private key Spriv and the one-time secrecy c. To extract c from Uj is an ECDLP.(b)
Ĉ fakes Vjs but forms V honestly. Assume that Ĉ is dishonest in forming Vjs but forms V in the same manner as specified in the protocol. For example, without loss of generality, he replaces each Vj with a specified Xj∈G1 and computes V=abĈpub. Then, the sender will compute Uj=cVj=cXj,cti=mi⊕ê(H(i)V,Spriv)c=mi⊕ê(H(i)abĈpub,Spriv)c, for i=1 to n, and send them back to Ĉ. As a result, Ĉ cannot decrypt ctσj since ê(Uj,Spub)a=ê(cXj,Spub)a is obviously not equal to ê(H(i)V,Spriv)c. Perhaps, for obtaining the k messages, Ĉ may try another way by computing ê(H(i)V,Spriv)c(=ê(H(i)abĈpub,Spriv)c) expected to be equal to (Uj,Spub)a. But again this is computationally infeasible since Ĉ does not know both the sender’s private key Spriv and the one-time secrecy c. Even he knows Spriv, extracting c from Uj(=cXj) is an ECDLP. Hence, Ĉ cannot compute the value ê(H(i)V,Spriv)c to decrypt ctσj for obtaining the k messages, mσj.(c)
Ĉ fakes both the values of V and Vj. Without loss of generality, we assume that Ĉ replaces V with X and also fakes Vj as H(σj)X. Under this construction, the value of Uj computed by the sender would be Uj=cVj=cH(σj)X and the ciphertexts ctσj would be mσj⊕ê(H(σj)X,Spriv)c, for j=1 to k, or equivalently, ctσj=mσj⊕ê(cH(σj)X,Spriv). Although, Ĉ knows the value of cH(σj)X (since it just equals to Uj received from the sender), it still cannot compute ê(cH(σj)X,Spriv) without the knowledge of Spriv. From above description, we know that when the setting of V is X and Vj is H(σj)X, Ĉ cannot obtain mσj. Not to mention, Ĉ might set Vj as H(σj)Y, where Y(≠X) is a random chosen element in G1. In summary, Ĉ cannot obtain the k selected messages under the violation of setting both the values, V and Vj.Argument (II)
IfĈ follows the protocol honestly to obtain k messages, but intends to extract the (k+1)th message then it will face the intractable CTCDH problem under the assumption that H(·) is a random hash function.
ThatĈ wants to obtain message mi implies Ĉ would have the knowledge of ê(H(i)V,Spriv)c(=ê(Uj,Spub)a) (in fact, according to argument (I), an honest chooser C could know k of the n values, ê(H(i)V,Spriv)c, for i=1 to n, since ê(H(i)V,Spriv)c = ê(Uj,Spub)a, for i=σj and j=1 to k). Let y(i)∈G2 and ê(H(i)V,Spriv)c=y(i). According to argument (I), for obtaining the k chosen messages, Ĉ cannot change the structures of V(=abĈpub) and Vj(=bH(σj)Ĉpriv). Under this situation, y(i) only can be decomposed as y(i)=ê(H(i)abĈpub,Spriv)c=ê(abH(i)Ĉpriv,Spub)c since Spriv=sSpub and Ĉpriv=sĈpub. Moreover, under the assumption that H(·) is a random hash function and the fact that Ĉ has the knowledge of a,b,Ĉpriv, and Spub, y(i) can be represented as (gi)c, where gi equals to ê(abH(i)Ĉpriv,Spub) and is a random element in G2 due to the assumption that H(·) is a random hash function. Consequently, the problem Ĉ really faces is finding the (k+1)th pair (σk+1,(gσk+1)c) with the knowledge of k pairs of (σ1,(gσ1)c), (σ2,(gσ2)c),…, and (σk, (gσk)c), where (gσj)c=ê(Uj,Spub)a, but without the knowledge of sender’s one-time secrecy c (since it is an ECDLP for extracting c from Uj(=cVj)). This is known as the intractable CTCDH problem introduced in Section 2.3 by letting k=(l-1). Therefore, the chooser cannot obtain the (k+1)th message.
According to arguments I and II, we have proven claim4 that our scheme has the sender’s privacy.Claim 5.
The proposed scheme can resist against replay attack.Proof.
Suppose that an adversary intercepts a chooser’s OT request (containingIDC,V,Vj, and Sig) and replays it later. After receiving the sender’s new response (U1,…,Uk, ct1,…,ctn) computed from the replayed V and Vj, the adversary cannot obtain the k selected messages by computing mσj=ctσj⊕ê(Uj,Spub)a since he/she does not know the value of a embedded in the replayed message V. It is computationally infeasible for the adversary to extract a from V=abCpub, due to the hardness of ECDLP.Claim 6.
The proposed scheme can resist against man-in-the-middle attack (MIMA).Proof.
MIMA is an attack that an adversaryE intercepts the communication line between two communicating parties and uses some means to make them believe that they each are talking to the intended party as claimed. But indeed, they are talking to E. Figure 1 illustrates the scenario of such a MIMA. We first argue that the adversary E cannot succeed in this scenario since it cannot generate the valid message (2), (IDC,V′,V1′,…,Vk′, Sig′) as shown in the figure. More clearly, without the knowledge of chooser’s private key Cpriv, he/she cannot forge a valid signature Sig′ in message (2) to be successfully verified by the sender since Sig′ should be equal to H2(V)Cpriv. In addition, it is also hard for E to forge valid message (4), (U1′,…,Uk′,ct1′,…,ctn′), to be accepted by the chooser. Since that for embedding a meaningful mi′ into cti′, E must have the knowledge of ê(H(i)V,Spriv)c. Although E can choose another random nonce c′ such that Uj′=c′Vj, it still has to know the sender’s private key Spriv to form the valid cti′(=mi⊕ê(H(i)V,Spriv)c′). Therefore, without the knowledge of Spriv, E cannot launch such a MIMA attack.Figure 1
The scenario of MIMA attack.Claim 7.
The proposed scheme can resist a denial of service attack (DOS).Proof.
Our protocol has a built-in mutual authentication property; thus, it can prevent this kind of attack, as the sender needs only one hash and two bilinear pairing computations to authenticate the chooser in step (2). Once the sender finds that the authenticating equationê(P,Sig)=ê(Ppub,hCpub) does not hold, it aborts the procedure.


### 5.1. Communicational Cost Comparisons

Generally, the communicational cost of a protocol run consists of three factors: (1) needed passes, (2) computational overhead, and (3) needed transmission data size (NTDS) or bandwidth consumption. It is well known that factor (1) is always dominant over factor (2). Hence, in this section, we focus only on factor (1) and (3) to demonstrate the communication cost comparisons among our nonadaptiveOTkn protocol and the other same type OTkn protocols, such as Chu and Tzeng’s [16] (which is to our best knowledge, the most efficient OTkn scheme up to date), Mu et al.’s [13], Naor and Pinkas’s [7], and recent works [17, 18, 24, 27]. From factor (1), our scheme is the most efficient since it only requires two passes. As to factor (3), the data size transmitted in our scheme is also the minimal among such type of OTkn schemes. For demonstrating this in the following, we will first describe two underlying facts and used notations for making comparisons about factor (3).Generally speaking, we have the following two facts for cryptosystems.Fact 1.
To the same security level, a RSA cryptosystem would require a key length of 1024 bits while an ECC-based cryptosystem only needs 160 bits.Fact 2.
The length of the ciphertexts for RSA, ElGamal, and ECC-based cryptosystems is 1024 bits, 1024 bits, and 160 bits, correspondingly.Notations
We use|string/action| to represent the bit length of a string, or the required bit length that an action performs.After the description of used facts and notations, we now use them to estimate the needed transmission data size (NTDS) of our scheme and the above-mentionedOTkn protocols. In our scheme, each of the variables V,V1,…,Vk,Sig,U1,…,Uk transmitted between the chooser and sender is an ECC point. Thus, the NTDS from the chooser to the sender is estimated as 160*(k+2) bits and from the sender to the chooser is 160k+n*|ciphertext| bits. Naor and Pinkas’s  scheme [7] constructs their OTkn scheme by evoking an OT12 primitive logn times. Thus, the needed number of passes is logn times the number of passes required in one of their OT12’s protocol run and likewise the NTDS is aboutlogn times of the NTDS that an OT12’s work demands. Therefore, their scheme has the most expensive communicational cost. As for Camenisch et al.’s protocol [24], the communicational cost is expensive as well due to the complexity of the protocol. In their protocol, the sender first sends n commitments to the chooser, and then the sender and the chooser together run a proof-of-knowledge (Pok) subprotocol for assuring the correctness of the commitments. If the proof is valid, the sender sends n ciphertexts to the chooser, and the chooser then runs the BlindExtract subprotocol k times with the help of the sender to extract the blind choices to decrypt the ciphertexts.Consequently, the number of passes for executing protocol [24] is 2+k*Pok, where Pok represents the required passes for executing the proof-of-knowledge subprotocol. Besides, the NTDS from chooser to sender is estimated as |Pok|+k*|BlindExtract| and from sender to chooser is n*|ciphertext|+|Pok|+k*|BlindExtract|. Similarly, the passes and NTDS of other studies can be estimated in the same manner. We show the comparison results in Table 2.Table 2
Needed rounds and data size comparisons amongOTkn protocols.
ProtocolPassesSize of message:C→S (bits)Size of message:S→C (bits)Mutual authenticationOurs2160 * (k+2)160k+n*|ciphertext|YesNaor and Pinkas [7]k* log nOT12depends onOT12depends onOT12NoMu et al.’s scheme (1) [13]31024k1024n+nk*|ciphertext|NoMu et al.’s scheme (2) [13]21024 * 2nn*|ciphertext|NoChu and Tzeng [16]21024k1024*(k+1)+n*|ciphertext|NoZhang and Wang [17]21024 * (k+3)1024n+n*|ciphertext|NoHuang and Chang [18]31024k(n+k)*|ciphertext|Camenisch et al. [24]2+k*Pok|Pok|+k*|BlindExtract|n*|ciphertext|+|Pok|+k*|BlindExtract|NoChang and Lee [27]41024k(n+2k+2) * 1024NoMa et al. [28]k*(2+Pok)k * 3|ciphertext|k*(n*2|ciphertext|)NoFrom Table2, we can see that our scheme not only possesses the mutual authentication function but also is the most efficient in both needed passes and NTDS among these related. Therefore, our scheme can be gracefully used when applied in commercial applications (e.g., Kerschbaum et al.’s method [1] used OT scheme as a building block in constructing RFID benchmarking protocols).


## 5.1. Communicational Cost Comparisons

Generally, the communicational cost of a protocol run consists of three factors: (1) needed passes, (2) computational overhead, and (3) needed transmission data size (NTDS) or bandwidth consumption. It is well known that factor (1) is always dominant over factor (2). Hence, in this section, we focus only on factor (1) and (3) to demonstrate the communication cost comparisons among our nonadaptiveOTkn protocol and the other same type OTkn protocols, such as Chu and Tzeng’s [16] (which is to our best knowledge, the most efficient OTkn scheme up to date), Mu et al.’s [13], Naor and Pinkas’s [7], and recent works [17, 18, 24, 27]. From factor (1), our scheme is the most efficient since it only requires two passes. As to factor (3), the data size transmitted in our scheme is also the minimal among such type of OTkn schemes. For demonstrating this in the following, we will first describe two underlying facts and used notations for making comparisons about factor (3).Generally speaking, we have the following two facts for cryptosystems.Fact 1.
To the same security level, a RSA cryptosystem would require a key length of 1024 bits while an ECC-based cryptosystem only needs 160 bits.Fact 2.
The length of the ciphertexts for RSA, ElGamal, and ECC-based cryptosystems is 1024 bits, 1024 bits, and 160 bits, correspondingly.Notations
We use|string/action| to represent the bit length of a string, or the required bit length that an action performs.After the description of used facts and notations, we now use them to estimate the needed transmission data size (NTDS) of our scheme and the above-mentionedOTkn protocols. In our scheme, each of the variables V,V1,…,Vk,Sig,U1,…,Uk transmitted between the chooser and sender is an ECC point. Thus, the NTDS from the chooser to the sender is estimated as 160*(k+2) bits and from the sender to the chooser is 160k+n*|ciphertext| bits. Naor and Pinkas’s  scheme [7] constructs their OTkn scheme by evoking an OT12 primitive logn times. Thus, the needed number of passes is logn times the number of passes required in one of their OT12’s protocol run and likewise the NTDS is aboutlogn times of the NTDS that an OT12’s work demands. Therefore, their scheme has the most expensive communicational cost. As for Camenisch et al.’s protocol [24], the communicational cost is expensive as well due to the complexity of the protocol. In their protocol, the sender first sends n commitments to the chooser, and then the sender and the chooser together run a proof-of-knowledge (Pok) subprotocol for assuring the correctness of the commitments. If the proof is valid, the sender sends n ciphertexts to the chooser, and the chooser then runs the BlindExtract subprotocol k times with the help of the sender to extract the blind choices to decrypt the ciphertexts.Consequently, the number of passes for executing protocol [24] is 2+k*Pok, where Pok represents the required passes for executing the proof-of-knowledge subprotocol. Besides, the NTDS from chooser to sender is estimated as |Pok|+k*|BlindExtract| and from sender to chooser is n*|ciphertext|+|Pok|+k*|BlindExtract|. Similarly, the passes and NTDS of other studies can be estimated in the same manner. We show the comparison results in Table 2.Table 2
Needed rounds and data size comparisons amongOTkn protocols.
ProtocolPassesSize of message:C→S (bits)Size of message:S→C (bits)Mutual authenticationOurs2160 * (k+2)160k+n*|ciphertext|YesNaor and Pinkas [7]k* log nOT12depends onOT12depends onOT12NoMu et al.’s scheme (1) [13]31024k1024n+nk*|ciphertext|NoMu et al.’s scheme (2) [13]21024 * 2nn*|ciphertext|NoChu and Tzeng [16]21024k1024*(k+1)+n*|ciphertext|NoZhang and Wang [17]21024 * (k+3)1024n+n*|ciphertext|NoHuang and Chang [18]31024k(n+k)*|ciphertext|Camenisch et al. [24]2+k*Pok|Pok|+k*|BlindExtract|n*|ciphertext|+|Pok|+k*|BlindExtract|NoChang and Lee [27]41024k(n+2k+2) * 1024NoMa et al. [28]k*(2+Pok)k * 3|ciphertext|k*(n*2|ciphertext|)NoFrom Table2, we can see that our scheme not only possesses the mutual authentication function but also is the most efficient in both needed passes and NTDS among these related. Therefore, our scheme can be gracefully used when applied in commercial applications (e.g., Kerschbaum et al.’s method [1] used OT scheme as a building block in constructing RFID benchmarking protocols).


## 6. Conclusion

An OT scheme which is secure and efficient in communicational cost is essential and eager for commercial applications. After reviewing most of the OT schemes, we found that, other than considering the protocol’s correctness and privacy of both communication parties, almost all of them lack the security services, such as mutual authentication, and the prevention of replay, DOS, and main-in-the-middle attacks. Hence, they should run under a secure channel when applied in commercial applications. This will increase execution overhead. Therefore, to get rid of using the secure channel (for improving the communicational efficiency in some applications, such as mental poker playing, oblivious key searching), we propose a novelk-out-of-n oblivious transfer protocol by combining an OT scheme with a security mechanism based on bilinear pairing. We have proved that our scheme not only is correct but also possesses the properties of mutual authentication, the sender’s privacy, and the chooser’s privacy and can resist against replay and MIMA attacks. Further, we have compared our scheme with other nonadaptive k-out-of-n OT schemes in the aspects of needed passes, NTDS, and the function of mutual authentication and shown the result in Table 2. From Table 2, we can see that our scheme is the most efficient in communicational cost (including needed passes and NTDS). In addition, to our knowledge, it is the only OTkn scheme that has successfully integrated the function of mutual authentication nowadays.



---

*Source: 630610-2012-06-20.xml*