Sage Journals: Discover world-class research

Abstract

In this article, we introduce a new concept of oblivious transfer with membership verification that allows any legitimate group users to obtain services from a service provider in an oblivious manner. We present two oblivious transfer with membership verification schemes, differing in design. In the first scheme, a trusted group manager issues credentials for a pre-determined group of users so that the group of users with a valid group credential can obtain services from the service provider, while the choices made by group users remain oblivious to the service provider. The second scheme avoids the trusted group manager, which allows any user in the group to be a group manager, thus it is more suitable in distributed systems. In particular, we prove that the two oblivious transfer with membership verification schemes can achieve receiver’s privacy and sender’s privacy under a half-simulation model.

Keywords

Oblivious transfer membership verification trusted group manager distributed systems

Introduction

It is a well-known economic strategy that the service providers are usually willing to sell their goods or services to a group of users with a discount price to attract customers. The more people who make a batch buy, the better prices the service providers are willing to offer. In addition to a good price, the customer’s privacy should be protected when buying goods or services from the service providers. With this motivation in mind, we aim to design oblivious transfer with membership verification schemes (MV-OT), which ensure that (1) user’s privacy (e.g. consumption transcript) is hidden from the service provider, (2) only legitimate group users can obtain services from the service provider, and (3) the proposed MV-OT schemes should incur same computation and communication costs as conventional oblivious transfer with access control schemes.

To see whether MV-OT is useful in practice, we consider a scenario where an issuer (group manager) forms a group which includes certain number of users wanting to purchase digital goods or services from a service provider. After forming a group of users, the issuer first generates the group credential for all users. Next, the issuer registers the group with a service provider, who will verify whether the real number of users in the group is in accordance with the claimed number. After a successful authentication with the service provider, a valid group user can acquire the digital goods or services obliviously.

We stress that designing MV-OT schemes is a non-trivial task. The straightforward way to achieve MV-OT is to combine a broadcast encryption or a membership encryption scheme with a conventional oblivious transfer with access control scheme.^1,2 The group manager first encrypts the credential and broadcasts the ciphertext to every user in the group, only valid users in the group could obtain the credential, with which the users in the group could acquire services from a sender. However, there are several drawbacks in this straightforward combination. First, the combined algorithm inherits the computation and storage costs of two independent algorithms. Second, every user in the group has to share the same credential, which means if a dispute happens, even the group manager cannot decide which user should be accused. Third, a straightforward combination of two different algorithms may lead to new security issues.

Our contributions

We formulate the concept of MV-OT and present two concrete MV-OT schemes that can be applied in different applications. In the first scheme, a central authority first forms a group of users willing to make a batch buy from a service provider (or sender). The central authority generates credentials for group users and group token which is sent to the sender. The sender encrypts the digital contends with the group token to ensure only group users with valid credentials can acquire the digital goods or services successfully. The users outside the group cannot gain any information transmitted between the sender and the valid users in the group. In the second scheme, we remove the central authority to make it much more suitable in distributed applications. Any member in the group or even the sender can play the role of an issuer to generate group information.

It is worth noticing that the proposed schemes achieve privacy as well as membership verification without involving too much computation and communication costs. The comprehensive efficiency analysis of the proposed schemes shows that our proposed schemes just involve few extra computation and communication costs compared with the oblivious transfer with access control schemes in Han et al.,¹ which makes the proposed MV-OT schemes applicable in many distributed systems such as ad hoc mobile networks.

Related works

Oblivious transfer

Oblivious transfer has been applied widely in secure multiparty computation,³ digital content browsing,⁴ exchange of secrets⁵ and other privacy-preserving systems.^1,2,6,7 Oblivious transfer has received much attention since it was first proposed by Rabin.⁵ In the early works,^5,8 the sender can only one message $m_{b, b \in {0, 1}}$ obliviously, which was soon extended to a more general k-out-of-n setting by Brassard et al.,⁹ where a receiver could choose $k$ messages obliviously from a sender. To ensure only legitimate receivers obtain contents from a receiver, Coull et al.¹⁰ proposed an oblivious transfer scheme with access control using state graphs, where the receivers in the system can only acquire contents successfully from a sender if he has some unused states. Liu et al.¹¹ proposed the concept of traceable oblivious transfer such that the privacy of users is treated separately. The privacy of the honest receivers is well-protected while the privacy of the dishonest receivers could be traced by the sender.

Broadcast encryption

The concept of broadcast encryption was proposed by Fiat and Naor.¹² Broadcast encryption enables one broadcaster to transmit messages to a dynamically chosen group of users $S$ such that $S \subseteq N$ , where $N$ refers to the set of all the users having access to the broadcast channel. Fiat and Naor¹² presented the first symmetric-key-based broadcast encryption scheme and the corresponding security model, which was extended to the public key setting by Dodis and Fazio.¹³ Recently, Gritti et al.¹⁴ proposed a novel broadcast encryption with dealership scheme which enables certain “dealers” in the broadcast system first to make a bulk buy from the broadcaster and then resell them in their own groups. Broadcast encryption with dealership accommodates a new business opportunity model and has received lots of attention.^15,16 Broadcast encryption can provide group membership verification; however, the “dealer” can trace the contents purchased by the users in the group, which in turn violates the privacy requirements in the aforementioned scenario.

Membership proof and membership encryption

Membership proof^17–20 is a very useful cryptographic primitive such that a user can prove to a verifier in a privacy-preserving manner that an attribute $A$ belongs to a group $G$ . Membership proof protocols can be further divided into two categories according to the information that can be accessed by the verifier. In the first category,^19,20 the verifier has knowledge of a token $P (A)$ on a single attribute and all the attributes in $1 G$ . The prover can convince the verifier that $A \in G$ without letting the verifier know which attribute it is in the group. In the second category,^17,18 the verifier has access to an attribute $A$ and the group token $P (G)$ containing information on a set of attributes. The prover can convince the verifier that $A \in P (G)$ without leaking information of other attributes in the group. Membership encryption is proposed by Guo et al.^21,22 as a useful alternative primitive of membership proof. It employs the privacy-preserving group token $P (G)$ in Au et al.¹⁷ such that given $P (G)$ , it is computationally difficult to know the attributes or identities in $P (G)$ ; however, a success decryption requires that a user holds the membership $A \in G$ .

Secret handshake

Secret handshake^23–25 is a useful primitive that can be applied in privacy-preserving applications where group membership verification is indispensable. The concept of secret handshake was introduced by Balfanz et al.,²³ which enables some entities in the same group to authenticate each other anonymously without leaking private information. Later on, Xu and Yung²⁴ proposed a secret handshake scheme achieving k-unlikability, which means an adversary can only infer that the participant is one out of the $k$ users in the group. Recently, Tian et al.²⁵ proposed a k-time secret handshake scheme that allows valid users in a group to authenticate each other up to $k$ times with a group credential. Otherwise, the private information can be traced in public. To achieve group membership verification, secret handshake schemes require that the service provider has to stay within the same group with all the users, which is impractical for the setting mentioned in the aforementioned scenario.

Article organization

The rest of the article is organized as follows. We introduce the formal definition and the security model of MV-OT in section “Security model.” Some preliminaries are presented in section “Preliminaries,” and concrete MV-OT schemes are presented in section “Our proposed schemes.” We prove their security and analyze their efficiency in section “Security analysis,” and the article is concluded in section “Conclusion.”

Security model

In this section, we present the formal definition and the security model for MV-OT schemes.

Definition

There are three entities in an MV-OT system, namely, a receiver, a sender, and an issuer who behaves on behalf of a group manager. We assume there exists a public key infrastructure (PKI) that issues certificates on users’ public keys. First, the issuer forms a group containing the users willing to obtain services from the sender. Then, the issuer generates the group token and sends it to the sender via a secure channel. The issuer generates credentials for each user in the group, with which the user (i.e. the receiver) could obtain services or digital goods from the sender. The system consists of four algorithms as follows:

1. Setup. Taking as input of a security parameter $κ$ , the Setup algorithm outputs the system public parameters $params$

p a r a m s \leftarrow Setup (1^{κ})

2. KeyGen. Taking as input of the system parameters $params$ , the KeyGen generates the public key pairs for the senders, receivers, and issuer, respectively, in the system

(p k_{I}, s k_{I}) \leftarrow KeyGen (params)

3. GroupGen. Taking as input of the systems parameters $params$ , pseudonyms of $l$ users $A_{1}, A_{2}, \dots, A_{l}$ , and the private key of the issuer, it returns the credential for the receivers and group token for the sender

\begin{matrix} σ_{i} \leftarrow GroupGen (s k_{I}, A_{i}; params), 1 \leq i \leq l \\ P (G) \leftarrow GroupGen (s k_{I}, A_{1}, A_{2}, \dots, A_{l}; params) \end{matrix}

4. Commitment. Taking as input of the group token $P (G)$ and the system parameter $params$ , the Commitment algorithm outputs $n$ ciphertexts

\begin{matrix} (c_{1}, c_{2}, \dots, c_{n}) \leftarrow Commitment (P (G), \\ m_{1}, m_{2}, \dots, m_{n}; params) \end{matrix}

5. Transfer. The polynomial probabilistic time algorithm Transfer is an interactive algorithm between a receiver $A_{i} (\in R)$ and the sender $S$ . The result of this algorithm is that the receiver with pseudonym $A_{i}$ obtains the intended message while the sender $S$ records a transcript on $A_{i}$ choice

\begin{matrix} R_{i_{j}} \leftarrow Transfe r_{R} (c_{i_{j}}, σ_{i_{j}}; params) \\ E_{i_{j}} \leftarrow Transfe r_{S} (R_{i_{j}}; params) \\ m_{i_{j}} \leftarrow Transfe r_{R} (c_{i_{j}}, E_{i_{j}}; params) \end{matrix}

6. Correctness. We require that for any security parameter $κ \in N$ , if $params \leftarrow Setup (1^{κ})$ , $(p k_{I}, s k_{I}) \leftarrow KeyGen (params)$ , $σ_{i} \leftarrow GroupGen (s k_{I}, A_{i}; params), 1 \leq i \leq l$ , $P (G) \leftarrow GroupGen (s k_{I}, A_{1}, A_{2}, \dots, A_{l}; params)$ , $(c_{1}, c_{2}, \dots, c_{n}) \leftarrow Commitment (P (G), m_{1}, m_{2}, \dots, m_{n}; params)$ , $R_{i_{j}} \leftarrow Transfe r_{R} (c_{i_{j}}, σ_{i_{j}}; params)$ , and $E_{i_{j}} \leftarrow Transfe r_{S} (R_{i_{j}}; params)$ , then the receiver can obtain the intended message

m_{i_{j}} \leftarrow Transfe r_{R} (c_{i_{j}}, E_{i_{j}}; params)

Security model

The security model presented in this section follows the half-simulation model in Naor and Pinkas.²⁶ We define that an MV-OT scheme is secure if the following conditions hold:

Receiver’s privacy. The sender $S$ cannot obtain any information about the receiver’s choices. To be specific, for any two different choice sets $C = {i_{1}, i_{2}, \dots, i_{k}}$ and $C^{'} = {i_{1}^{'}, i_{2}^{'}, \dots, i_{k}^{'}}$ , the corresponding transcripts $B = {B_{i_{1}}, B_{i_{2}}, \dots, B_{i_{k}}}$ and $B^{'} = {B_{i_{1}}^{'}, B_{i_{2}}^{'}, \dots, B_{i_{k}}^{'}}$ are indistinguishable if the corresponding messages $M = {m_{i_{1}}, m_{i_{2}}, \dots, m_{i_{k}}}$ and $M^{'} = {m_{i_{1}}^{'}, m_{i_{2}}^{'}, \dots, m_{i_{k}}^{'}}$ are identically distributed.

Sender’s privacy. A valid receiver $R$ cannot obtain any information other messages $m_{i}, i \notin {i_{1}, i_{2}, \dots, i_{k}}$ other than the intended contents. The security of the sender is defined through the real-world/ideal-world paradigm. In the real world, the sender and the receiver execute the protocols following the algorithm. In the ideal world, the protocol is executed with a trusted third party (TTP). The sender sends all the messages $m_{1}, m_{2}, \dots, m_{n}$ to the TTP, where the receiver acquires the intended choices $m_{i_{1}}, m_{i_{2}}, \dots, m_{i_{k}}$ adaptively. If ${i_{1}, i_{2}, \dots, i_{k}} \subseteq {1, 2, \dots, n}$ , then TTP sends $m_{i_{1}}, m_{i_{2}}, \dots, m_{i_{k}}$ to the receiver. An MV-OT scheme is said to provide the privacy of the sender if for any receiver $R$ in real world, there exists a probabilistic polynomial time (PPT) $R^{'}$ such that the outputs of $R$ and $R^{'}$ are indistinguishable.

Semantic security. If a receiver $R$ does not have a valid group credential $σ_{i}, 1 \leq i \leq l$ , she cannot obtain any useful information $m_{i}, 1 \leq i \leq n$ from the sender $S$ .

Preliminaries

Bilinear pairing

Let $G_{1}$ and $G_{2}$ be multiplicative cyclic groups with prime order $q$ . Let $g$ and $h$ be generators of $G_{1}$ . A bilinear map $e : G_{1} \times G_{1} \to G_{2}$ satisfies the following conditions:

Bilinearity: $e (g^{a}, h^{b}) = e (g, h)^{ab}$ for all $g, h \in G_{1}$ and $a, b \in G_{q}$ .

No-degeneracy: $e (g, h) \neq I_{G_{2}}$ , where $I_{G_{2}}$ is the identity in $G_{2}$ .

Computability: there is an efficient algorithm to compute $e (g, h)$ for all $g, h \in G_{1}$ .

Complexity assumptions

Definition 1

Discrete logarithm (DL) assumption. Let $G$ be a cyclic group with a prime order $q$ and $g$ be a generator of $G$ . Given a random element $X \in G$ , compute $x \in Z_{p}^{*}$ such that $X = g^{x} mod q$ . Let ${Adv}_{A}^{DL} (κ)$ be the advantage of a PPT adversary. We say that DL assumption holds in $G$ that for all PPT adversary $A$ , the following function ${Adv}_{A}^{DL} (κ)$ is negligible

{Adv}_{A}^{DL} (κ) = \Pr [(g^{x} = X, x \in Z_{q}^{*}) \leftarrow A (params, g, X, G)]

Definition 2

One-generator l-strong Diffie–Hellman (l-SDH) assumption.²⁷ Let $(G_{1}, G_{2})$ be a bilinear group, for a randomly chosen element $x \in Z_{q}^{*}$ and a random generator $g \in G_{1}$ , the l-SDH problem is, given $g, g^{x}, g^{x^{2}}, \dots, g^{x^{l}} \in G_{1}^{l + 1}$ , to compute a pair $(g^{1 / (x + c)}, c)$ . Define the advantage of a PPT adversary as ${Adv}_{A}^{OG - l - SDH} (κ)$ , and we say the l-SDH assumption holds if for all PPT algorithm $A$ , the following function ${Adv}_{A}^{OG - l - SDH} (κ)$ is negligible

\begin{matrix} {Adv}_{A}^{OG - l - SDH} (κ) = \Pr [(g^{\frac{1}{x + c}}, \\ c \in Z_{q}^{*}) \leftarrow A (params, g, g^{x}, \dots, g^{x^{l}})] \end{matrix}

Definition 3

Extended chosen-target computational Diffie–Hellman (XCT-CDH) assumption.¹ Let $G$ be a cyclic group with prime order $q$ and $x \in Z_{q}^{*}$ , there is a help oracle $H_{G} (\cdot)$ that takes $g_{i}$ as input and returns $g_{i}^{x}$ . Given a $(k + 1)$ tuple ${g^{a_{1}}, g^{a_{2}}, \dots, g^{a_{k + 1}}}$ , where $a_{i} \in z_{q}^{*}$ for $i = 1, 2, \dots, k + 1$ , define the advantage ${Adv}_{A}^{XCT - CDH} (κ)$ of a PPT adversary $A$ , and XCT-CDH assumption holds in $G$ , if for all PPT adversary $A$ that ${Adv}_{A}^{XCT - CDH} (κ)$ is negligible

\begin{matrix} {Adv}_{A}^{XCT - CDH} (κ) = \Pr [g^{x a_{k + 1}} \\ \leftarrow A^{H_{G} (\cdot)} (q, g, g^{x}, g^{a_{i_{1}}}, \dots, g^{a_{i_{k}}})] \end{matrix}

where $a_{i_{j}} \in {a_{1}, a_{2}, \dots, a_{k + 1}}$ , for all $j = 1, 2, \dots, k + 1$ .

Our proposed schemes

In this section, we present two MV-OT schemes. In the first scheme, there is an issuer generating credentials for the members in the group. Our construction takes advantage of the techniques of accumulator scheme in Nguyen.¹⁸ In the first proposed scheme, the system parameters contain two secret keys $(α, β)$ and some auxiliary parameters $g^{α}, g^{α^{2}}, \dots, g^{α^{l}}, g^{β}, g^{β α},$ $g^{β α^{2}}, \dots, g^{β α^{l}}$ . While the group token is $P (G) = (ω_{1}, ω_{2}) = (g^{τ Π_{i = 1}^{l} (α + A_{i})}, g^{τ β Π_{i = 1}^{l} (α + A_{i})})$ , the membership verification process is described as follows:

1. If user $A_{i}$ is a valid group user with credential $σ_{A_{i}} = g^{\frac{1}{(α + A_{i}) (β + A_{i})}}$ , then it would be computationally easy to recover

e ((ω_{2} ω_{1}^{A_{i}})^{t_{j}}, g^{\frac{1}{(α + A_{i}) (β + A_{i})}}) = e (g, g)^{τ t_{j} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})}

which is further used to extract the intended message.

2. Otherwise, if a dishonest user $A_{k}$ who does not belong to the group tries to interact with the sender, we have

e ((ω_{2} ω_{1}^{A_{k}})^{t_{j}}, g^{\frac{1}{(α + A_{k}) (β + A_{k})}}) = e (g, g)^{τ t_{j} \frac{Π_{j = 1}^{j = l} (α + A_{j})}{α + A_{k}}}

which contains the inversion exponent $g^{1 / (α + A_{k})}$ that is computationally infeasible to be computed from the system parameters.

MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I

The proposed scheme consists of a tuple of PPT algorithms as follows:

Setup. Taking as input a security parameter $κ$ , this algorithm outputs a bilinear group $(e, G_{1}, G_{2})$ where $e : G_{1} \times G_{1} \to G_{2}$ and $G_{1}, G_{2}$ are cyclic groups with prime $q$ . Let $g$ be a generator of $G_{1}$ . The system parameters $params = (e, G_{1}, G_{2}, q, g)$ .

KeyGen. Suppose there are $l$ users with pseudonyms $A_{1}, A_{2}, \dots, A_{l}$ in the group, the issuer (i.e. group manager) chooses $α, β \in Z_{q}^{*}$ and computes $g^{α}, g^{α^{2}}, \dots, g^{α^{l}}, g^{β}, g^{β α}, g^{β α^{2}}, \dots, g^{β α^{l}}$ and generates the group token $P (G) = (ω_{1}, ω_{2}) = (g^{τ Π_{i = 1}^{l} (α + A_{i})}, g^{τ β Π_{i = 1}^{l} (α + A_{i})})$ , where $τ \in Z_{q}^{*}$ is chosen at random by the issuer. For each user with pseudonym $A_{i}, 1 \leq i \leq l$ , the issuer computes $σ_{A_{i}} = g^{1 / ((α + A_{i}) (β + A_{i}))}$ and returns it to the individual users. $I$ sends $(P (G), α)$ to the sender $S$ .

Commitment. in response to the requirement from a user with pseudonym $A_{i}$ , $S$ chooses $n$ different random elements $t_{1}, t_{2}, \dots, t_{n} \in Z_{q}^{*}$ and a one-time secret $z \in Z_{q}^{*}$ , $S$ computes the ciphertext of $m_{1}, m_{2}, \dots, m_{n}$ as $c_{j} = (c_{j, 1}, c_{j, 2})$ where $c_{j, 1} = (ω_{2} ω_{1}^{A_{i}})^{t_{j}}$ and $c_{j, 2} = e (ω_{1}, g)^{\frac{z \cdot t_{j}}{α + A_{i}}} = e (g, g)^{τ z t_{j} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{j}$ , $S$ sends $c_{1}, c_{2}, \dots, c_{n}$ to $A_{i}$ .

Transfer. Upon receiving the ciphertexts from the sender, the receiver with pseudonym $A_{i}$ chooses $r_{i} \in Z_{q}^{*}$ and computes $B_{i_{j}} = e (c_{i_{j}, 1}, σ_{A_{i}})$ , $E_{i_{j}} = e (c_{i_{j}, 1}, σ_{A_{i}})^{r_{i}}$ , where $i_{j} \in {1, 2, \dots, n}$ , then the receiver $A_{i}$ sends $E_{i_{j}}$ to $S$ . $S$ computes $D_{i_{j}} = (E_{i_{j}})^{z}$ and sends it to $R$ . $R$ computes $K_{i_{j}} = D_{i_{j}}^{r_{i}^{- 1}}$ and obtains the intended message $m_{i_{j}} = c_{i_{j}, 2} / K_{i_{j}}$ .

Correctness

Suppose the receiver with pseudonym $A_{i}$ is a valid group member with credential $σ_{A_{i}}$ . The correctness check of MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme is as follows

\begin{matrix} E_{i_{j}} & = e {(c_{i_{j}, 1}, σ_{A_{i}})}^{r_{i}} \\ = e {((ω_{2} ω_{1}^{A_{i}})^{t_{i_{j}}}, g^{\frac{1}{(β + A_{i}) (α + A_{i}})})}^{r_{i}} \\ = e {(g^{τ t_{i_{j}} (β + A_{i}) Π_{j = 1}^{m} (α + A_{j})}, g^{\frac{1}{(β + A_{i}) (α + A_{i})}})}^{r_{i}} \\ = e {(g, g)}^{r_{i} τ t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \end{matrix}

and

\begin{matrix} \frac{c_{i_{j}, 2}}{K_{i_{j}}} & = \frac{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i_{j}}}{D_{i_{j}}^{r_{i}^{- 1}}} \\ = \frac{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i_{j}}}{E_{i_{j}}^{{zr}_{i}^{- 1}}} \\ = \frac{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i_{j}}}{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})}} \\ = m_{i_{j}} \end{matrix}

MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II

In the MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I scheme, it involves a central authority named issuer helps to form and maintain the group, which makes it unpractical in distributed scenarios. Therefore, we proposed the second scheme MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II without a central authority. Anyone who tries to make a batch buy or even the sender could behave as the group manager to initialize the system. The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme consists of a tuple of PPT algorithms as follows:

Setup. Taking as input a security parameter $κ$ , this algorithm outputs a bilinear group $(e, G_{1}, G_{2})$ where $e : G_{1} \times G_{1} \to G_{2}$ and $G_{1}, G_{2}$ are cyclic groups with prime $q$ . Let $g$ and $h$ be generators of $G_{1}$ and $G_{2}$ , respectively. The system parameters $params = (e, G_{1}, G_{2}, q, g, h)$ .

KeyGen. Suppose there is an initial setup phase and there have been $l$ users with pseudonyms $A_{1}, A_{2}, \dots, A_{l}$ in the group. The sender chooses $α \in Z_{q}^{*}$ and computes $g^{α}, g^{α^{2}}, \dots, g^{α^{l}}$ and generates the group token $P (G) = g^{τ Π_{i = 1}^{l} (α + A_{i})}$ , where $τ \in Z_{q}^{*}$ is randomly chosen by the sender. For each user with pseudonym $A_{i}, 1 \leq i \leq m$ , the sender computes and returns $σ_{A_{i}} = g^{1 / (α + A_{i})}$ .

Commitment. In response to the requirement from a user with pseudonym $A_{i}$ . $S$ chooses $n$ different random numbers $t_{1}, t_{2}, \dots, t_{n} \in Z_{q}^{*}$ and a one-time secret $z \in Z_{q}^{*}$ . $S$ computes the ciphertext of $m_{1}, m_{2}, \dots, m_{n}$ as $c_{i} = (c_{i, 1}, c_{i, 2})$ where $c_{i, 1} = g^{τ t_{i} Π_{j = 1}^{m} (α + A_{j})}$ and $c_{i, 2} = e (g, g)^{τ z t_{i} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i}$ . $S$ sends $c_{1}, c_{2}, \dots, c_{n}$ to $A_{i}$ .

Transfer. Upon receiving ciphertexts from the sender, $A_{i}$ chooses $r_{i} \in Z_{q}^{*}$ and computes $B_{i_{j}} = e (c_{i_{j}}, σ_{A_{i}})$ and $E_{i_{j}} = B_{i_{j}}^{r_{i}}$ , where $i_{j}$ is the index of message of the receiver’s choice and $i_{j} \in {1, 2, \dots, n}$ , then the receiver $A_{i}$ sends $E_{i_{j}}$ to $S$ . $S$ computes $D_{i_{j}} = (E_{i_{j}})^{z}$ and sends it to $R$ . $R$ computes $K_{i_{j}} = D_{i_{j}}^{r_{i}^{- 1}}$ and obtains the intended message $m_{i_{j}} = c_{i_{j}, 2} / K_{i_{j}}$ .

Correctness

Suppose the receiver with pseudonym $A_{i}$ is valid group member with credential $σ_{A_{i}}$ . The correctness check of MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme is as follows

\begin{matrix} E_{i_{j}} & = e {(c_{i_{j}, 1}, σ_{A_{i}})}^{r_{i}} \\ = e {(g^{τ t_{i_{j}} Π_{j = 1}^{m} (α + A_{j})}, g^{\frac{1}{α + A_{i}}})}^{r_{i}} \\ = e {(g, g)}^{r_{i} τ t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \end{matrix}

and

\begin{matrix} \frac{c_{i_{j}, 2}}{K_{i_{j}}} & = \frac{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i_{j}}}{D_{i_{j}}^{r_{i}^{- 1}}} \\ = \frac{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i_{j}}}{E_{i_{j}}^{{zr}_{i}^{- 1}}} \\ = \frac{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \cdot m_{i_{j}}}{e {(g, g)}^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})}} \\ = m_{i_{j}} \end{matrix}

Security analysis

The security result of our MV-OT schemes is shown by the following theorems.

Theorem 1

The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I scheme provides receiver’s privacy for honest receivers.

Proof

Suppose an honest receiver with pseudonym $A_{i}$ requests contents from the sender. ${E_{i_{1}}, E_{i_{2}}, \dots, E_{i_{k}}}$ is a set of transcripts on $A_{i}$ choices. For any $E_{i_{j}}$ such that $j \in {1, 2, \dots, k}$ , $E_{i_{j}} = e (g, g)^{r_{i} t_{i_{j}} τ \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})}$ . Set $W_{i} = e (g, g)^{τ \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})} \in G_{2}$ , then there exits $r_{i}^{'} \in Z_{q}^{*}$ such that $E_{i_{j}} = W_{i}^{r_{i} t_{i_{j}}} = W_{i}^{r_{i}^{'} t_{i_{w}}}$ , where $t_{i_{w}} \neq t_{i_{j}}$ and $t_{i_{w}} \in {t_{1}, t_{2}, \dots, t_{n}}$ , which means the choice of the receiver is computationally indistinguishable to the sender as long as the DL problem is hard in $G_{2}$ .

Theorem 2

The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I scheme provides sender’s privacy.

Proof

Suppose an honest receiver runs the MV-OT protocol with the sender $S$ to obtain $k$ messages. For any PPT malicious receiver $\hat{R}$ in the real world, we are able to construct a PPT malicious receiver ${\hat{R}}^{*}$ in the ideal model such that the outputs of $\hat{R}$ and ${\hat{R}}^{*}$ are indistinguishable. ${\hat{R}}^{*}$ simulates the honest sender $S$ in the real world and interacts with $\hat{R}$ as follows:

$S$ sends the messages $m_{1}, m_{2}, \dots, m_{n}$ to the $TTP$ .

${\hat{R}}^{*}$ sends $c_{1}^{*}, c_{2}^{*}, \dots, c_{n}^{*}$ to $TTP$ such that $c_{i}^{*} = (c_{i_{1}}, c_{i_{2}}) \in G_{1} \times G_{2}$ for $i = 1, 2, \dots, n$ , where $c_{1}^{*}, c_{2}^{*}, \dots, c_{n}^{*}$ are $n$ different pairs of random numbers selected from $G_{1}$ and $G_{2}$ by ${\hat{R}}^{*}$ .

${\hat{R}}^{*}$ monitors the outputs of ${\hat{R}}^{*}$ , if $\hat{R}$ can compute $B_{i_{1}}, B_{i_{2}}, \dots, B_{i_{k}}$ and $E_{i_{1}}, E_{i_{2}}, \dots, E_{i_{k}}$ . ${\hat{R}}^{*}$ chooses random $B_{i_{1}}^{*}, B_{i_{2}}^{*}, \dots, B_{i_{k}}^{*} \in G_{2}$ and $E_{i_{1}}^{*}, E_{i_{2}}^{*}, \dots,$ $E_{i_{k}}^{*} \in G_{2}$ .

When $\hat{R}$ requires $D_{i_{1}}, D_{i_{2}}, \dots, D_{i_{k}}$ from $E_{i_{1}}, E_{i_{2}}, \dots, E_{i_{k}}$ , ${\hat{R}}^{*}$ queries the help oracle $H_{G_{2}} (\cdot)$ on $E_{i_{1}}^{*}, E_{i_{2}}^{*}, \dots, E_{i_{k}}^{*}$ and gets back $D_{i_{1}}^{*}, D_{i_{2}}^{*}, \dots, D_{i_{k}}^{*}$ , where $D_{i_{j}}^{*} = (E_{i_{j}}^{z^{*}})$ , $j = 1, 2, \dots, k$ .

If $\hat{R}$ can compute $K_{i_{j}} = e (g, g)^{τ z t_{i_{j}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})}$ , ${\hat{R}}^{*}$ sends $i_{j}$ to $TTP$ , $TTP$ returns $K_{i_{j}}^{*} = c_{i_{j}, 2}^{*} / m_{i_{j}}$ .

${\hat{R}}^{*}$ outputs $(B_{i_{1}}^{*}, B_{i_{2}}^{*}, \dots, B_{i_{k}}^{*}, E_{i_{1}}^{*}, E_{i_{2}}^{*}, \dots, E_{i_{k}}^{*}, c_{1}^{*}, c_{2}^{*}, \dots, c_{n}^{*})$ .

In the simulation process, if $\hat{R}$ obtains $k + 1$ messages while ${\hat{R}}^{*}$ is unaware of the indices of the corresponding messages, the simulation aborts. Otherwise, we are able to show that $\hat{R}$ is only able to choose at most $k$ messages under the XCT-CDH assumption. If $\hat{R}$ can get $k + 1$ messages, he can compute $E_{i_{j}}$ for $j = 1, 2, \dots, k + 1$ . That is, if $\hat{R}$ can obtain

\begin{matrix} (e (g, g)^{τ t_{i_{1}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})})^{z}, (e (g, g)^{τ t_{i_{2}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})})^{z}, \\ \dots, (e (g, g)^{τ t_{i_{k}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})})^{z} \end{matrix}

$\hat{R}$ can compute

(e (g, g)^{τ t_{i_{k + 1}} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})})^{z}

which contradicts the XCT-CDH assumption. Therefore, $\hat{R}$ can only obtain the required messages from the sender and cannot obtain any information on other messages that he hasn’t required.

We can see from Theorem 1 that ${B_{i_{1}}, B_{i_{2}}, \dots, B_{i_{k}}}$ and ${E_{i_{1}}, E_{i_{2}}, \dots, E_{i_{k}}}$ are indistinguishable from random elements in $G_{2}$ and ${c_{1}, c_{2}, \dots, c_{n}}$ are indistinguishable from random elements in $G_{1} \times G_{2}$ by Theorem 3. In addition, the sets of ${D_{i_{1}}, D_{i_{2}}, \dots, D_{i_{k}}}$ and ${D_{i_{1}}^{*}, D_{i_{2}}^{*}, \dots, D_{i_{k}}^{*}}$ are identically distributed. Therefore, no distinguishers can distinguish the outputs of $\hat{R}$ and ${\hat{R}}^{'}$ with a non-negligible probability.

Theorem 3

The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ scheme is semantic secure.

Proof

The semantic security of MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I is analyzed through two aspects. First, if the adversary $A$ could forge $σ_{A_{i}} = g^{1 / ((β + A_{i}) (α + A_{i}))}$ , then $A$ could act as authorized receiver to communicate with the sender. In this case, there exists another PPT algorithm $B$ that could use $A$ to break l-SDH assumption. Second, if the adversary $A$ could compute $e (g, g)^{τ z t_{i} \underset{A_{j} \in A / A_{i}}{Π} (α + A_{j})}$ from the ciphertext $c_{i} = (c_{i, 1}, c_{i, 2})$ , then $A$ could also obtain messages from the receiver. In this case, there exists a PPT algorithm that could take advantage of $A$ to break the XCT-CDH assumption. Therefore, MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I is semantically secure.

Theorem 4

The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme provides receiver’s privacy for honest receivers. The security proof and the subsequent proofs of the MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme are similar as that for MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I, thus we omit it.

Theorem 5

The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme provides sender’s privacy.

Theorem 6

The proposed MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II scheme is semantic secure.

Efficiency analysis

We present a comprehensive complexity analysis in terms of computation and communication costs. The results are presented in Tables 1 and 2, respectively. By $l$ , $n$ , and $k$ , we denote the number of users in the group, the total number of the messages, and the number of messages selected by a receiver. Let $E_{G_{1}}$ and $E_{G_{2}}$ denote the exponential operations in $G_{1}$ and $G_{2}$ , and $P$ one pairing operation.

Table 1.

Computational costs of the proposed schemes.

Algorithm	KeyGen	Commitment	Transfer
MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I	$(3 l + 2) E_{G_{1}}$	$n (E_{G_{1}} + E_{G_{2}})$	$kP + 4 k E_{G_{2}}$
MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II	$(2 l + 1) E_{G_{1}}$	$n (E_{G_{1}} + E_{G_{2}})$	$kP + 4 k E_{G_{2}}$

Table 2.

Communication costs of the proposed schemes.

Algorithm	KeyGen	Commitment	Transfer
MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I	$(l + 2) G_{1}$	$n G_{1} + n G_{2}$	$2 k G_{2}$
MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II	$l G_{1}$	$n G_{1} + n G_{2}$	$2 k G_{2}$

Conclusion

In this article, we formulate the concept of MV-OT such that only legitimate users with proper membership can obliviously acquire digital goods or services from a service provider. We have proposed two MV-OT schemes with completed security analysis. The two MV-OT schemes are different in design, and the one without trusted group manager is preferable in distributed systems.

Footnotes

Handling Editor: José Camacho

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was partially sponsored by the National Science Foundation of China under grant no. 61872264.

ORCID iD

Weiwei Liu

Yangguang Tian

References

Han

Susilo

, et al. Efficient oblivious transfers with access control. Comput Math Appl 2012; 63(4): 827–837.

Han

Susilo

, et al. AAC-OT: accountable oblivious transfer with access control. IEEE T Inf Foren Sec 2015; 10(12): 2502–2514.

Yao

. Protocols for secure computations (extended abstract). In: 23rd annual symposium on foundations of computer science, Chicago, IL, 3–5 November 1982, pp.160–164. New York: IEEE.

Liu

Yang

, et al. Efficient e-coupon systems with strong user privacy. Telecommun Syst 2017; 64(4): 695–708.

Rabin

. How to exchange secrets with oblivious transfer. Technical report, Aiken Computation Laboratory, Harvard University, 20 May 1981.

Aiello

Ishai

Reingold

. Priced oblivious transfer: how to sell digital goods. In: International conference on the theory and application of cryptographic techniques: advances in cryptology, 2001, pp.119–135, https://www.iacr.org/archive/eurocrypt2001/20450118.pdf

Guo

Susilo

, et al. Privacy-preserving mutual authentication in RFID with designated readers. Wireless Pers Commun 2017; 96(3): 4819–4845.

Even

Goldreich

Lempel

. A randomized protocol for signing contracts. Commun ACM 1985; 28(6): 637–647.

Brassard

Crépeau

Robert

. All-or-nothing disclosure of secrets. In: Advances in cryptology—CRYPTO ’86, Santa Barbara, CA, 1 January 1987, pp.234–238. Berlin: Springer.

10.

Coull

Green

Hohenberger

Controlling access to an oblivious database using stateful anonymous credentials. In: Public key cryptography—PKC 2009, Irvine, CA, 18–20 March 2009, pp.501–520. Berlin: Springer.

11.

Liu

Zhang

, et al. Efficient traceable oblivious transfer and its applications. In: 14th international conference on information security practice and experience, ISPEC 2018, Tokyo, Japan, 25–27 September 2018, pp.610–621. Berlin: Springer.

12.

Fiat

Naor

Broadcast encryption. In: 13th annual international cryptology conference on advances in cryptology—CRYPTO ’93, Santa Barbara, CA, 22–26 August 1993, pp.480–491. Berlin: Springer.

13.

Dodis

Fazio

Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. In: 6th international workshop on theory and practice in public key cryptography—PKC 2003, Miami, FL, 6–8 January 2003, pp.100–115. Berlin: Springer.

14.

Gritti

Susilo

Plantard

, et al. Broadcast encryption with dealership. Int J Inf Sec 2016; 15(3): 271–283.

15.

Acharya

Dutta

Adaptively secure broadcast encryption with dealership. In: 19th international conference on information security and cryptology—ICISC 2016, revised selected papers, Seoul, South Korea, 30 November–2 December 2016, pp.161–177. Berlin: Springer.

16.

Kim

Lee

Eom

, et al. Recipient revocable broadcast encryption with dealership. In: 20th international conference on information security and cryptology—ICISC 2017, revised selected papers, Seoul, South Korea, 29 November–1 December 2017, pp.214–228. Berlin: Springer.

17.

Tsang

Susilo

, et al. Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems. In: Cryptographers’ track at the RSA conference 2009: topics in cryptology—CT-RSA 2009, San Francisco, CA, 20–24 April 2009, pp.295–308. Berlin: Springer.

18.

Nguyen

Accumulators from bilinear pairings and applications. In: Cryptographers’ track at the RSA conference 2005: topics in cryptology—CT-RSA 2005, San Francisco, CA, 14–18 February 2005, pp.275–292. Berlin: Springer.

19.

Camenisch

Chaabouni

Shelat

. Efficient protocols for set membership and range proofs. In: 14th international conference on the theory and application of cryptology and information security on advances in cryptology—ASIACRYPT 2008, Melbourne, VIC, Australia, 7–11 December 2008, pp.234–252. Berlin: Springer.

20.

Camenisch

Lysyanskaya

. Dynamic accumulators and application to efficient revocation of anonymous credentials. In: 22nd annual international cryptology conference on advances in cryptology—CRYPTO 2002, Santa Barbara, CA, 18–22 August 2002, pp.61–76, http://groups.csail.mit.edu/cis/pubs/lysyanskaya/cl02a.pdf

21.

Guo

Susilo

, et al. Membership encryption and its applications. In: 18th Australasian conference on information security and privacy, ACISP 2013, Brisbane, QLD, Australia, 1–3 July 2013, pp.219–234. Berlin: Springer.

22.

Guo

Susilo

. Subset membership encryption and its applications to oblivious transfer. IEEE T Inf Foren Sec 2014; 9(7): 1098–1107.

23.

Balfanz

Durfee

Shankar

, et al. Secret handshakes from pairing-based key agreements. In: 2003 IEEE symposium on security and privacy (S&P 2003), Berkeley, CA, 11–14 May 2003, pp.180–196. New York: IEEE.

24.

Yung

. k-anonymous secret handshakes with reusable credentials. In: Proceedings of the 11th ACM conference on computer and communications security, CCS 2004, Washington, DC, 25–29 October 2004, pp.158–167. New York: ACM.

25.

Tian

Zhang

Yang

, et al. Privacy-preserving k-time authenticated secret handshakes. In: 22nd Australasian conference on information security and privacy, ACISP 2017, part II, Auckland, New Zealand, 3–5 July 2017, pp.281–300. Berlin: Springer.

26.

Naor

Pinkas

. Computationally secure oblivious transfer. J Cryptology 2005; 18(1): 1–35.

27.

Tanaka

Saito

. On the q-strong Diffie–Hellman problem, 2010, https://eprint.iacr.org/2010/215.pdf

Efficient oblivious transfer with membership verification

Abstract

Keywords

Introduction

Our contributions

Related works

Oblivious transfer

Broadcast encryption

Membership proof and membership encryption

Secret handshake

Article organization

Security model

Definition

Security model

Preliminaries

Bilinear pairing

Complexity assumptions

Definition 1

Definition 2

Definition 3

Our proposed schemes

MV-OT n k × 1 -I

Correctness

MV-OT n k × 1 -II

Correctness

Security analysis

Security analysis

Theorem 1

Proof

Theorem 2

Proof

Theorem 3

Proof

Theorem 4

Theorem 5

Theorem 6

Efficiency analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References

MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -I

MV-OT $\begin{matrix} n \\ k \times 1 \end{matrix}$ -II