Efficient Adaptive Oblivious Transfer Without q-type Assumptions in UC Framework

Adaptive Oblivious Transfer (\(\mathsf{OT}^{N}_{k \times 1}\)) is a two-party protocol, where a sender with messages \(m_1, m_2, \ldots , m_N\) interacts with a receiver with indices \(\sigma _1, \sigma _2, \ldots \), \(\sigma _k \in [N]\) in such a way that at the end the receiver obtains \(m_{\sigma _1}, m_{\sigma _2}, \ldots , m_{\sigma _k}\) without learning anything about the remaining \(N-k\) messages and the sender does not learn anything about the indices \(\sigma _1, \sigma _2, \ldots , \sigma _k\). The receiver may obtain \(m_{\sigma _{i-1}}\) before deciding on \(\sigma _i\). The \(\mathsf{OT}^{N}_{k \times 1}\) protocol consists of a initialization phase and k transfer phases. In initialization phase, the sender encrypts the messages \(m_1, m_2, \ldots , m_N\) using some encryption scheme and publishes the encrypted database. In each transfer phase, the receiver interacts with the sender to decrypt the ciphertext of its choice in order to recover the desired message. The \(\mathsf{OT}^{N}_{k \times 1}\) is an interesting primitive. It is a basic building block for secure multiparty computation and adaptive oblivious search of large database such as medical, financial, patent etc.

Naor and Pinkas [18] introduced the first \(\mathsf{OT}^{N}_{k \times 1}\) protocol in half-simulataion model in which the security of one party follows real/ideal world paradigm while the security of other party is supported by heuristic argument only. The first fully-simulatable \(\mathsf{OT}_{k\times 1}^{N}\) in which security of both the parties follow real/ideal world paradigm is proposed by Camenisch et al. [7]. Afterwards, there are quite a number of \(\mathsf{OT}_{k\times 1}^{N}\) protocols [1, 12–15, 17, 20, 22]. Peikert et al. [19] introduced the universal composabe (UC) secure oblivious transfer protocols. The security of \(\mathsf{OT}_{k\times 1}^{N}\) protocols [1, 14, 17, 20] are also proven in UC framework [8, 9]. The UC secure \(\mathsf{OT}^{N}_{k \times 1}\) protocols retain their security even when composed with arbitrary protocols during concurrent execution. The aforementioned \(\mathsf{OT}^{N}_{k \times 1}\) protocols are based on q -type assumptions except [1, 15]. The q-type assumptions state that given q solutions of the underlying problem, it is not possible to come up with a new solution. During simulation, these q solutions are used by the simulator to answer the queries by an adversary and then convert the adversary’s forgery into a new solution of the problem. Abe et al. [1] introduced \(\mathsf{OT}^{N}_{k \times 1}\) without q-type assumptions in UC framework.

Our Contribution. Adaptive Oblivious Transfer (\(\mathsf{OT}^{N}_{k \times 1}\)) is an extensively used primitive in cryptography. Designing an efficient \(\mathsf{OT}^{N}_{k \times 1}\) is not a trivial task. In this paper, we provide an efficient \(\mathsf{OT}^{N}_{k \times 1}\) protocol without q-type assumptions which is provable secure in UC framework. Our scheme assumes a common reference string \(\mathsf{CRS}\) similar to existing works as UC secure \(\mathsf{OT}^{N}_{k \times 1}\) protocol cannot be constructed without any trusted setup assumptions. The proposed \(\mathsf{OT}^{N}_{k \times 1}\) protocol couples Water’s signature [21] with non-interactive Groth-Sahai [16] proofs and is secure under Decision Linear (DLIN), Decision Bilinear Diffie-Hellman (DBDH) and Square Decision Bilinear Diffie-Hellman (SqDBDH) assumptions. The Water’s signature [21] and non-interactive Groth-Sahai [16] proofs are used to create some checks during protocol construction to control the malicious activities of the parties. If the receiver or sender deviates from the protocol constructions, it will get detected with these checks.

Security is proven in static corruption model in which corrupted parties are pre-decided by the adversary. Throughout the protocol execution, corrupted parties remain corrupted and honest parties remain honest. The security of the proposed \(\mathsf{OT}^{N}_{k \times 1}\) protocol is proved by proving the sender and receiver’s security separately in the trusted setup assumptions. The sender’s (receiver’s) security requires the existence of an efficient simulator such that no distinguisher can distinguish real world (where an honest sender (receiver) is interacting with an adversary) from ideal world (where the simulator is given access to ideal functionality).

The proposed \(\mathsf{OT}^{N}_{k \times 1}\) protocol is efficient as compared to the existing similar schemes [1, 14, 17, 20]. The efficiency includes number of rounds, computation complexity and communication complexity. The computation complexity is measured by counting the number of pairings and exponentiations which are performed during initialization and transfer phases. The communication complexity includes number of rounds, storage and group elements transformation from the sender to the receiver and vice-versa.

Throughout, we use \(\rho \) as the security parameter, \(x \xleftarrow {\$} A\) means sample an element x uniformly at random from the set A, \(y \leftarrow B\) indicates y is the output of algorithm B, \(X \mathop {\approx }\limits ^{c} Y\) means X is computationally indistinguishable from Y, \([\ell ]\) denotes \(\{1, 2, \ldots , \ell \}\) and \(\mathbb {N}\) the set of natural numbers. A function f(n) is negligible if \(f = o(n^{-c})\) for every fixed positive constant c.

2.1 Bilinear Pairing and Mathematical Assumptions

Definition 1

(Bilinear Pairing). Let \(\mathbb {G}_1, \mathbb {G}_2\) and \(\mathbb {G}_T\) be three multiplicative cyclic groups of prime order p and \(g_1\), \(g_2\) be generators of groups \(\mathbb {G}_1\) and \(\mathbb {G}_2\) respectively. Then the map \(e : \mathbb {G}_{1} \times \mathbb {G}_{2} \rightarrow \mathbb {G}_T\) is bilinear if it satisfies the following conditions. (i) Bilinear – \(e(x^{a}, y^{b}) = e(x, y)^{ab} ~\forall ~ x \in \mathbb {G}_1, y \in \mathbb {G}_2, a, b \in \mathbb {Z}_{p}\). (ii) Non-Degenerate – e(x, y) generates \(\mathbb {G}_T\), \(~\forall ~ x \in \mathbb {G}_1, y \in \mathbb {G}_2, x \ne 1, y \ne 1\). (iii) Computable – the pairing e(x, y) is computable efficiently \(~\forall ~ x \in \mathbb {G}_1, y \in \mathbb {G}_2\).

If \(\mathbb {G}_1 = \mathbb {G}_2\), then e is symmetric bilinear pairing. Otherwise, e is asymmetric bilinear pairing. Throughout the paper, we use symmetric bilinear pairing.

Definition 2

(DBDH [21]). The Decision Bilinear Diffie-Hellman (DBDH) assumption in \((\mathbb {G}, \mathbb {G}_T)\) states that for all PPT algorithm \(\mathcal {A}\), with running time in \(\rho \), the advantage \(\mathsf{Adv}^{DBDH}_{\mathbb {G}, \mathbb {G}_T}(\mathcal {A}) = \mathsf{Pr}[\mathcal {A}(g, g^a, g^b, g^c, e(g, g)^{abc})] - \mathsf{Pr}[\mathcal {A}(g, g^a, g^b, g^c\), Z)] is negligible in \(\rho \), where \(g \xleftarrow {\$} \mathbb {G}, Z \xleftarrow {\$} \mathbb {G}_T, a, b, c \in \mathbb {Z}_{p}\).

Definition 3

(SqDBDH [10]). The Square Decision Bilinear Diffie-Hellman assumption in \((\mathbb {G}, \mathbb {G}_T)\) states that for all PPT algorithm \(\mathcal {A}\), with running time in \(\rho \), the advantage \(\mathsf{Adv}^{SqDBDH}_{\mathbb {G}, \mathbb {G}_T}(\mathcal {A}) = \mathsf{Pr}[\mathcal {A}(g, g^a, g^b, e(g, g)^{a^2b})] - \mathsf{Pr}[\mathcal {A}(g, g^a, g^b, Z)]\) is negligible in \(\rho \), where \(g \xleftarrow {\$} \mathbb {G}, Z \xleftarrow {\$} \mathbb {G}_T, a, b \in \mathbb {Z}_{p}\).

Definition 4

(DLIN [5]). The Decision Linear (DLIN) assumption in \(\mathbb {G}\) states that for all PPT algorithm \(\mathcal {A}\), with running time in \(\rho \), the advantage \(\mathsf{Adv}^{DLIN}_{\mathbb {G}}(\mathcal {A})\) \(= \mathsf{Pr}[\mathcal {A}(g, g^a, g^b, g^{ra}, g^{sb}, g^{r+s})] - \mathsf{Pr}[\mathcal {A}(g, g^a, g^b, g^{ra}, g^{sb}, t)]\) is negligible in \(\rho \), where \(g \xleftarrow {\$} \mathbb {G}, t \xleftarrow {\$} \mathbb {G}, a, b, r, s \in \mathbb {Z}_{p}\).

2.2 Non-Interactive Verification of Pairing Product Equation [16]

The Groth-Sahai proofs are two party protocols between a prover and a verifier for non-interactive verification of a pairing product equation

where \(a_{q =1, 2, \ldots , Q} \in \mathbb {G}, b_{q =1, 2, \ldots , Q} \in \mathbb {G}\), \(\{\alpha _{q, i}, \beta _{q, i}\}_{q =1, 2, \ldots , Q, i =1, 2, \ldots , n} \in \mathbb {Z}_{p}\) and \(t_{T} \in \mathbb {G}_{T}\) are the coefficients of the pairing product Eq. 1 which are given to the verifier. The prover knows secret values \(x_{i =1, 2, \ldots , n}, y_{i =1, 2, \ldots , n} \in \mathbb {G}\) also called witnesses that satisfy the Eq. 1. The prover wants to convince the verifier in a non-interactive way that he knows \(x_{i}\) and \(y_{i}\) without revealing anything about \(x_{i}\) and \(y_{i}\) to the verifier. Let \(\mathcal {W} = \{x_{i =1, 2, \ldots , n}, y_{i =1, 2, \ldots , n}\}\) be the set of all secret values in the pairing product Eq. 1. The set \(\mathcal {W}\) is referred as witnesses of the pairing product equation. The product of two vectors is defined component wise, i.e., \((a_1, a_2, a_3)(b_1, b_2, b_3) = (a_1b_1, a_2b_2, a_3b_3)\) for \((a_1, a_2, a_3), (b_1, b_2, b_3) \in \mathbb {G}^3\) for a finite order group \(\mathbb {G}\).

For non-interactive verification of the pairing product Eq. 1, a trusted party upon input a security parameter \(\rho \) generates common reference string \(\mathsf{GS} = (\mathsf{params}, u_1, u_2, u_3, \mu , \mu _T)\), where \(\mathsf{params} = (p, \mathbb {G}, \mathbb {G}_{T}, e, g)\)  \(\leftarrow \mathsf{BilinearSetup}(1^\rho )\), \(u_1 = (g^a, 1, g) \in \mathbb {G}^{3}, u_2 = (1, g^b, g) \in \mathbb {G}^{3}\), \(u_3 = u_{1}^{\xi _{1}}u_{2}^{\xi _{2}} = (g^{a\xi _{1}}, g^{b\xi _{2}}, g^{\xi _{1} + \xi _{2}}) \in \mathbb {G}^{3}\), \(\xi _{1}, \xi _{2} \xleftarrow {\$} \mathbb {Z}_{p}\), \(a, b \xleftarrow {\$} \mathbb {Z}_{p}\) and \(\mu : \mathbb {G} \rightarrow \mathbb {G}^3\), \(\mu _T : \mathbb {G}_T \rightarrow \mathbb {G}_{T}^9\) are two efficiently computable embeddings such that

Note that \(\mu _T(t_T)\) is an element of \(\mathbb {G}_{T}^9\). For convenience, it has been written in matrix form. The product of two elements of \(\mathbb {G}_{T}^9\) is also component wise. The trusted party publishes \(\mathsf{GS}\) to both the parties. The prover generates commitment to all the witnesses \(x_{i =1, 2, \ldots , n}\) and \(y_{i =1, 2, \ldots , n}\) using \(\mathsf{GS}\). To commit \(x_i \in \mathbb {G}\) and \(y_i \in \mathbb {G}\), the prover picks \(r_{1i}, r_{2i}, r_{3i} \xleftarrow {\$} \mathbb {Z}_{p}\) and \(s_{1i}, s_{2i}, s_{3i} \xleftarrow {\$} \mathbb {Z}_{p}\), sets

The prover generates the proof components

using random values \(r_{ji}, s_{ji}\), which were used for generating commitments to \(x_{i =1, 2, \ldots , n}, y_{i =1, 2, \ldots , n}\), and gives proof \(\pi = (c_1, c_2, \ldots , c_n, d_1, d_2, \ldots , d_n, P_1, P_2, P_3)\) to the verifier, where \(\widehat{d_q} = \mu (b_q)\prod _{i=1}^{n}d_{i}^{\beta _{q, i}}\), \(i = 1, 2, \ldots , n, j = 1, 2, 3\). The verifier computes

using \(c_i, d_i\), coefficients \(\alpha _{q, i}, \beta _{q, i}\) and outputs VALID if the following equation holds

where \(F : \mathbb {G}^3 \times \mathbb {G}^3 \rightarrow \mathbb {G}_{T}^9\) is defined as

Note that the function F is also symmetric bilinear and \(F((x_1, x_2, x_3), (y_1, y_2, y_3))\) is an element of \(\mathbb {G}_{T}^9\). The product of two elements of \(\mathbb {G}_{T}^9\) is component wise. For convenience, it has been written in matrix form.

The Eq. 2 holds if and only if Eq. 1 holds. The Eq. 1 is non-linear. If in Eq. 1 only \(y_{i = 1, 2, \ldots , n}\) are secrets, then it is a linear equation. For a linear equation, the verifier has to verify the following equation

Note that there are two types of settings in Groth-Sahai proofs - perfectly sound setting and witness indistinguishability setting. The common reference string \(\mathsf{GS} = (u_1, u_2, u_3)\) discussed above is in perfectly sound setting, where \(u_1 = (g^a, 1, g)\), \(u_2 = (1, g^b, g)\), \(u_3 = (g^{a\xi _{1}}, g^{b\xi _{2}}, g^{\xi _{1} + \xi _{2}})\). One who knows the extractable trapdoor \(\mathsf{t_{ext}} = (a, b, \xi _1, \xi _2)\), can extract the secret values from their commitments. In witness indistinguishability setting, \(\mathsf{GS'} = (u_1, u_2, u_3)\), where \(u_1 = (g^a, 1, g)\), \(u_2 = (1, g^b, g)\), \(u_3 = (g^{a\xi _{1}}, g^{b\xi _{2}}, g^{\xi _{1} + \xi _{2} + 1})\). One who knows the simulation trapdoor \(\mathsf{t_{sim}} = (a, b, \xi _1, \xi _2)\), may open the commitment differently in a pairing product equation as shown in an example given below.

Example 1

Let \(\mathsf{Com}(x) = \mu (x)u_{1}^{\theta _1}u_{2}^{\theta _2}u_{3}^{\theta _3}\) in witness indistinguishability setting, where \(\theta _1, \theta _2, \theta _3 \xleftarrow {\$} \mathbb {Z}_{p}\). Opening values to \(\mathsf{Com}(x)\) are \((D_1 = g^{\theta _1}, D_2 = g^{\theta _2}, D_3 = g^{\theta _3})\). The simulator knowing witness x opens \(\mathsf{Com}(x)\) to any value \(x'\) using \(\mathsf{t_{sim}} = (a, b, \xi _1, \xi _2)\) and \(D_1, D_2, D_3\) as follows. The simulator sets \(D_1' = D_1(\frac{x'}{x})^{\xi _1}, D_2'= D_2(\frac{x'}{x})^{\xi _2}\), \(D_3'= D_3\frac{x}{x'})\) and opens the \(\mathsf{Com}(x)\) to \(x'\) by computing \(\frac{xg^{\theta _1 + \theta _2 + \theta _3(\xi _1 + \xi _2 + 1)}}{D_1'D_2'(D_3')^{\xi _1+\xi _2+1}}\).

In \(\mathsf{GS}\), \(g^a, g^b, g, g^{a\xi _{1}}, g^{b\xi _{2}}, \) \(g^{\xi _{1} + \xi _{2}}\) forms a DLIN tuple, whereas in \(\mathsf{GS'}\), \(g^a, g^b, g, g^{a\xi _{1}}\), \(g^{b\xi _{2}}\), \(g^{\xi _{1} + \xi _{2} + 1}\) is not a DLIN tuple. The commitments in both the setting are computationally indistinguishable by the following theorem.

Theorem 1

[16]. The common reference string in perfectly sound setting is computationally indistinguishable from the common reference string in witness indistinguishability setting under DLIN assumption.

Definition 5

(\(\mathsf{NIWI}\)). The non-interactive witness-indistinguishable (\(\mathsf{NIWI}\)) proof states that for all PPT algorithm \(\mathcal {A}\), with running time in \(\rho \), the advantage

is negligible in \(\rho \) under DLIN assumption, where \(\mathsf{GS}\) is the common reference string in perfectly sound setting, \(\mathcal {S}\) is a pairing product equation, \(\mathcal {W}_0, \mathcal {W}_1\) are two distinct set of witnesses satisfying \(\mathcal {S}\) and \(\pi \) is the proof for \(\mathcal {S}\).

Definition 6

(\(\mathsf{NIZK}\)). The non-interactive zero-knowledge (\(\mathsf{NIZK}\)) proof states that for all PPT algorithm \(\mathcal {A}\), with running time in \(\rho \), the advantage

is negligible in \(\rho \) under DLIN assumption, where \(\mathsf{GS'}\) is the common reference string in witness indistinguishability setting, \(\mathcal {S}\) is a pairing product equation, \(\mathcal {W}\) is a set of witnesses satisfying \(\mathcal {S}\), \(\pi _0\) is the proof for \(\mathcal {S}\) and \(\pi _1\) is the simulated proof for \(\mathcal {S}\).

The notations \(\mathsf{NIWI}\left\{ (\{x_{i}, y_{i}\}_{1\le i\le n}) | \prod _{q=1}^{Q}e(a_q\prod _{i=1}^{n}x_{i}^{\alpha _{q, i}}, b_q\prod _{i=1}^{n}y_{i}^{\beta _{q, i}}) = \right. \left. t_{T} \right\} \) and \(\mathsf{NIZK}\left\{ (\{x_{i}, y_{i}\}_{1\le i\le n}) | \prod _{q=1}^{Q}e(a_q\prod _{i=1}^{n}x_{i}^{\alpha _{q, i}}, b_q\prod _{i=1}^{n}y_{i}^{\beta _{q, i}}) = t_{T} \right\} \), for \(\mathsf{NIWI}\) and \(\mathsf{NIZK}\) proof are followed respectively in our construction. The convention is that the quantities in the parenthesis denote elements the knowledge of which are being proved to the verifier by the prover while all other parameters are known to the verifier. We have the following theorem.

Theorem 2

[16]. The Groth-Sahai proofs are composable \(\mathsf{NIWI}\) and \(\mathsf{NIZK}\) for satisfiability of a set of pairing product equation over a bilinear group under DLIN assumption.

UC Framework: The security of the proposed \(\mathsf{OT}^{N}_{k \times 1}\) is done in universal composable (UC) model assuming static corruption. The UC framework consists of two worlds, one is a real world and other is an ideal world. In the real world, a sender, a receiver and a real world adversary \(\mathcal {A}\), who has the ability of corrupting the parties (sender and receiver), interact with each other according to \(\mathsf{OT}^{N}_{k \times 1}\) protocol \(\varPsi \). In the ideal world, there are dummy parties (sender and receiver), an ideal world adversary \(\mathcal {A'}\) and a trusted party called ideal functionality \(\mathcal {F}_\mathsf{OT}^{N \times 1}\). The parties are dummy in the sense that they submit their inputs to \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) and receive respective outputs from \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) instead of performing any computation by themselves. A protocol is said to be secure in UC framework if no interactive distinguisher, called environment machine \(\mathcal {Z}\), can distinguish the execution of the protocol \(\varPsi \) in the real world from the execution of the protocol in the ideal world.

Let us now describe ideal functionality \(\mathcal {F}_{\mathsf{CRS}}^{\mathcal {D}}\) for the generation of common reference string (\(\mathsf{CRS}\)) parameterized by some specific distribution \(\mathcal {D}\) and ideal functionality \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) for \(\mathsf{OT}^{N}_{k \times 1}\) protocol following [9].

• \(\mathcal {F}_{\mathsf{CRS}}^{\mathcal {D}}\) Hybrid Model– Upon receiving a message \((\mathsf{sid}, P, \mathsf{CRS})\), from a party P (either S or R), \(\mathcal {F}_{\mathsf{CRS}}^{\mathcal {D}}\) first checks if there is a recorded value \(\mathsf{crs}\). If there is no recorded value, \(\mathcal {F}_{\mathsf{CRS}}^{\mathcal {D}}\) generates \( \mathsf{crs} \xleftarrow {\$} \mathcal {D}(1^{\rho })\) and records it. Finally, \(\mathcal {F}_{\mathsf{CRS}}^{\mathcal {D}}\) sends \((\mathsf{sid}, P, \mathsf{crs})\) to the party P and \(\mathcal {A'}\), where \(\mathsf{sid}\) is the session identity. In the proposed construction \(\mathcal {D}\) is \(\mathsf{CRSSetup}\) algorithm, i.e., \( \mathsf{crs} \leftarrow \mathsf{CRSSetup}(1^{\rho })\)

In the ideal world, the parties just forward their inputs to the \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) and get back their respective outputs. The functionality \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) is as follows:

• \(\mathsf{DBInit}\) – The \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) upon receiving a message \((\mathsf{sid}, S, \mathsf{dbsetup}, \mathsf{DB})\) from S, stores \(\mathsf{DB}\), where \(\mathsf{DB} = (m_1, m_2, \ldots , m_{N})\), \(m_i \in \mathbb {G}_T\), \(i = 1, 2, \ldots , N\).

• \(\mathsf{Transfer}\) – Upon receiving the message \((\mathsf{sid}, R, \mathsf{transfer}, \sigma )\) from R, \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) sends \((\mathsf{sid}, \mathsf{request})\) to S and receives \((\mathsf{sid}, S, b)\) in response from S. If \(b=1\), then \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) returns \(m_{\sigma }\) to R. Otherwise, \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) returns \(\bot \) to R.

Definition 7

A protocol \(\varPsi \) securely realizes the ideal functionality \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) if for any real world adversary \(\mathcal {A}\), there exists an ideal world adversary \(\mathcal {A'}\) such that for any environment machine \(\mathcal {Z}\), \(\mathsf{REAL}_{\varPsi , \mathcal {A}, \mathcal {Z}} \mathop {\approx }\limits ^{c} { \mathsf IDEAL}_{\mathcal {F}_\mathsf{OT}^{N \times 1}, \mathcal {A'}, \mathcal {Z}}\), where \(\mathsf{REAL}_{\varPsi , \mathcal {A}, \mathcal {Z}}\) is the output of \(\mathcal {Z}\) after interacting with \(\mathcal {A}\) and the parties running the protocol \(\varPsi \) in the real world and \(\mathsf{IDEAL}_{\mathcal {F}_\mathsf{OT}^{N \times 1}, \mathcal {A'}, \mathcal {Z}}\) is the output of \(\mathcal {Z}\) after interacting with \(\mathcal {A'}\) and dummy parties interacting with \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) in the ideal world.

A high level description of our adaptive oblivious transfer (\(\mathsf{OT}^{N}_{k \times 1}\)) is given in Fig. 1. Formally our \(\mathsf{OT}^{N}_{k \times 1}\) protocol is a tuple of the following PPT algorithms: \(\mathsf{OT}^{N}_{k \times 1}\)= (\(\mathsf{CRSSetup}\), \(\mathsf{DBInit} = (\mathsf{DBSetup}, \mathsf{DBVerify})\), \(\mathsf{Transfer} = (\mathsf{RequestTra}\), \(\mathsf{ResponseTra}\), \(\mathsf{CompleteTra})\)).

Communication flow of our \(\mathsf{OT}^{N}_{k \times 1}\) for the jth transfer phase, \(j = 1, 2, \ldots , k\).

Full size image

• \(\mathsf{CRSSetup}(1^{\rho }\)): This randomized algorithm on input security parameter \(\rho \) generates common reference string \(\mathsf{crs}\) as follows. It first generates \(\mathsf{params} \leftarrow \mathsf{BilinearSetup}(1^\rho )\), where \(\mathsf{params} = (p, \mathbb {G}, \mathbb {G}_{T}, e, g)\). The algorithm chooses \(a, b, \xi _1, \xi _2, \widetilde{a}, \widetilde{b}, \widetilde{\xi _1}, \widetilde{\xi _2} \xleftarrow {\$} \mathbb {Z}_{p}^{*}\) and sets \(g_1 = g^{a}, g_2 = g^{b}, \widetilde{g_1} = g^{\widetilde{a}}, \widetilde{g_2} = g^{\widetilde{b}}, u_1 = (g_1, 1, g), u_2 = (1, g_2, g), u_3 = u_{1}^{\xi _1}u_{2}^{\xi _2} = (g_{1}^{\xi _1}, g_{2}^{\xi _2}, g^{\xi _1 + \xi _2})\), \(\widetilde{u_1} = (\widetilde{g_1}, 1, g), \widetilde{u_2} = (1, \widetilde{g_2}, g), \widetilde{u_3} = \widetilde{u_{1}}^{\widetilde{\xi _1}}\widetilde{u_{2}}^{\widetilde{\xi _2}} = (\widetilde{g_{1}}^{\widetilde{\xi _1}}, \widetilde{g_{2}}^{\widetilde{\xi _2}}, g^{\widetilde{\xi _1} + \widetilde{\xi _2}}), \mathsf{GS}_R = (u_1, u_2, u_3), \mathsf{GS}_S = (\widetilde{u_1}, \widetilde{u_2}, \widetilde{u_3}), \mathsf{crs} = (\mathsf{params}, \mathsf{GS}_R, \mathsf{GS}_R)\). \(\mathsf{GS}_R\) is used for creating non-interactive witness indistinguishable (\(\mathsf{NIWI}\)) proof by a receiver and \(\mathsf{GS}_S\) for generating non-interactive zero-knowledge (\(\mathsf{NIZK}\)) proof by a sender.

• \(\mathsf{DBSetup}(\mathsf{crs})\): This randomized algorithm upon input \(\mathsf{crs} = (\mathsf{params}, \mathsf{GS}_R, \mathsf{GS}_S)\) from the sender S, generates database public key \(\mathsf{pk}\), database secret key \(\mathsf{sk}\), proof \(\psi \) and ciphertext database \(\mathsf{cDB}\), where \(\mathsf{params} = (p, \mathbb {G}, \mathbb {G}_{T}, e, g)\), \(\mathsf{GS}_R = (u_1, u_2, u_3)\), \(\mathsf{GS}_S = (\widetilde{u_1}, \widetilde{u_2}, \widetilde{u_3})\). It chooses \(\alpha \xleftarrow {\$} \mathbb {Z}_{p}^{*}, \widehat{g_{2}}, f', f_1, f_2, \ldots \), \(f_n \xleftarrow {\$} \mathbb {G}\), sets \(\widehat{g_1} = g^{\alpha }\). The algorithm sets

  $$\mathsf{pk} = (\widehat{g_1}, \widehat{g_2}, f', f_1, f_2, \ldots , f_n), \mathsf{sk} = (\alpha , \widehat{g_{2}}^{\alpha }).$$

  The algorithm generates \(\mathsf{NIZK}\) proof \(\psi \) using \(\mathsf{GS}_S = (\widetilde{u_1}, \widetilde{u_2}, \widetilde{u_3})\) as

  $$\begin{aligned} \psi= & {} \mathsf{NIZK}\{(\widehat{g_{2}}^{\alpha }, g')~|~ e(g, \widehat{g_{2}}^{\alpha })e(g', \widehat{g_{2}}^{-1}) = 1 \wedge e(g', \widehat{g_{2}}) = e(\widehat{g_{1}}, \widehat{g_{2}}) \}. \end{aligned}$$

  The \(\mathsf{Com}(\widehat{g_{2}}^{\alpha }) = \mu (\widehat{g_{2}}^{\alpha })\widetilde{u_{1}}^{s_1} \widetilde{u_{2}}^{s_2}\widetilde{u_{3}}^{s_3}\), \(\mathsf{Com}(g') = \mu (g')\widetilde{u_{1}}^{\ell _1} \widetilde{u_{2}}^{\ell _2}\widetilde{u_{3}}^{\ell _3}\) and proof components for the equations \(e(g, \widehat{g_{2}}^{\alpha })e(g', \widehat{g_{2}}^{-1}) = 1 \wedge e(g', \widehat{g_{2}}) = e(\widehat{g_{1}}, \widehat{g_{2}})\) are embedded in proof \(\psi \) as in Sect. 2.2, where \(s_1, s_2, s_3, \ell _1, \ell _2, \ell _3 \xleftarrow {\$} \mathbb {Z}_{p}^{*}\).

  For \(i = 1 \mathrm{~to}~ N\), the algorithm generates \(\varPhi _i = (c_{i}^{(1)}, c_{i}^{(2)}, c_{i}^{(3)})\) as follows.

  1. 1.

     Pick \(r_i \xleftarrow {\$} \mathbb {Z}_{p}^{*}\), set \(c_{i}^{(1)} = g^{r_i}\).

  2. 2.

     Let \(\mathcal {I}_i = i_1i_2\ldots i_n\) be the n bit representation of i, \(i_{\ell }\) be the \(\ell \)-th bit of i and \(\mathcal {M}_i \subseteq \{1, 2, \ldots , n\}\) be the set of all \(\ell \) for which \(i_{\ell }\) is 1. The algorithm sets \(c_{i}^{(2)} = \widehat{g_{2}}^{\alpha }\left( f'\displaystyle \prod _{\ell \in \mathcal {M}_i}f_{\ell }\right) ^{r_i}\).

  3. 3.

     Set \(c_{i}^{(3)} = m_i\cdot e(\widehat{g_1}, \widehat{g_2})^{r_i}\).

  The ciphertext database is set to be \(\mathsf{cDB} = (\varPhi _1, \varPhi _2, \ldots , \varPhi _{N})\). The algorithm outputs \((\mathsf{pk}, \mathsf{sk}, \psi , \mathsf{cDB})\) to the sender S. The sender S publishes \(\mathsf{pk}, \psi , \mathsf{cDB}\) to all parties and keeps \(\mathsf{sk}\) secret to itself. The computation cost involved in this algorithm is \(3N+25\) exponentiations and 1 pairing.

• \(\mathsf{DBVerify}(\mathsf{pk}, \psi , \mathsf{cDB}, \mathsf{crs})\): The receiver R upon receiving \(\mathsf{pk}, \psi , \mathsf{cDB}\) from S runs this randomized algorithm to verify the correctness of proof \(\psi \) and ciphertext database \(\mathsf{cDB}\) as follows. The validity of proof \(\psi \) is checked by verifying the pairing product equation as in Sect. 2.2. The ciphertext database is verified for each \(\varPhi _i = (c_{i}^{(1)}, c_{i}^{(2)}, c_{i}^{(3)})\), by verifying the following equation

  $$\begin{aligned} e\left( c_{i}^{(2)}, g\right) = e(\widehat{g_{1}}, \widehat{g_{2}}) e\left( f'\prod _{\ell \in \mathcal {M}_i}f_{\ell }, c_{i}^{(1)}\right) , ~ i =1, 2, \ldots , N, \end{aligned}$$

  (5)

  where \(c_{i}^{(1)} = g^{r_i}, c_{i}^{(2)} = \widehat{g_{2}}^{\alpha } \left( f'\prod _{\ell \in \mathcal {M}_i}f_{\ell }\right) ^{r_i}\), \(\mathcal {M}_i \subseteq \{1, 2, \ldots , n\}\) be the set of all \(\ell \) for which \(i_{\ell }\) is 1, \(i_{\ell }\) be the \(\ell \)-th bit of i. If the the proof \(\psi \) and Eq. 5 hold, the algorithm outputs \(\mathsf{VALID}\), otherwise, \(\mathsf{INVALID}\). This algorithm has to perform \(2N+23\) pairings.

• \(\mathsf{RequestTra}(\mathsf{crs}, \mathsf{pk}, \sigma _j, \varPhi _{\sigma _j})\): The receiver R runs this randomized algorithm to generate request \(\mathsf{Req}_{\sigma _j}\) as follows.

  1. 1.

     Pick \(v_{\sigma _j} \xleftarrow {\$} \mathbb {Z}_{p}^{*}\), set \(d_{1, \sigma _j} = c_{\sigma _j}^{(1)}\cdot g^{v_{\sigma _j}} = g^{r_{\sigma _j} + v_{\sigma _j}}\),

  2. 2.

     \(d_{2, \sigma _j} = c_{\sigma _j}^{(2)}\cdot (f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell })^{v_{\sigma _j}} = \widehat{g_{2}}^{\alpha }(f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell })^{r_{\sigma _j} + v_{\sigma _j}}\), \(t_{\sigma _j} = \widehat{g_{2}}^{v_{\sigma _j}}\).

  3. 3.

     Generate \(\mathsf{NIWI}\) proof \(\pi _{\sigma _j} =\mathsf{NIWI} \{(c_{\sigma _j}^{(1)}, c_{\sigma _j}^{(2)}, f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell }, t_{\sigma _j}, d_{2, \sigma _j}) ~| ~\)

     $$e(c_{\sigma _j}^{(1)}, \widehat{g_{2}}) e(t_{\sigma _j}, g) = e(d_{1, \sigma _j}, \widehat{g_{2}}) \wedge $$
     $$e(c_{\sigma _j}^{(2)}, \widehat{g_{2}})e(f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell }, t_{\sigma _j}) = e(d_{2, \sigma _j}, \widehat{g_{2}}) \wedge $$
     $$e(d_{1, \sigma _j}, f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell })e(\widehat{g_1}, \widehat{g_2}) = e(d_{2, \sigma _j}, g) \} $$

     using \(\mathsf{GS}_R = (u_1, u_2, u_3)\). The proof \(\pi _{\sigma _j}\) consists of commitments to \(c_{\sigma _j}^{(1)}, c_{\sigma _j}^{(2)}, f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell }, t_{\sigma _j}, d_{2, \sigma _j},\) and proof components for three equations. As each commitment takes 3 group elements, proof component of a linear equation takes 3 group elements and of a nonlinear equation takes 9 group elements, so, the size of \(\pi _{\sigma _j}\) is 30 group elements. The computation cost involved in generating \(\pi _{\sigma _j}\) is 68 exponentiations and 1 pairing.

  4. 4.

     Set \(\mathsf{Req}_{\sigma _j} = (d_{1, \sigma _j}, \pi _{\sigma _j})\), \(\mathsf{Pri}_{\sigma _j} = t_{\sigma _j}\).

• \(\mathsf{ResponseTra}(\mathsf{crs}, \mathsf{pk}, \mathsf{sk}, \mathsf{Req}_{\sigma _j})\): The sender S upon receiving \(\mathsf{Req}_{\sigma _j}\) from R runs this randomized algorithm to generate \(\mathsf{Res}_{\sigma _j}\) as follows.

  1. 1.

     The algorithm verifies the proof \(\pi _{\sigma _j}\) by verifying each pairing product equation in \(\pi _{\sigma _j}\) as in Sect. 2.2. The verification of \(\pi _{\sigma _j}\) takes 62 pairings. If fails, it aborts the execution.

  2. 2.

     Otherwise, the algorithm generates \(\mathsf{Res}_{\sigma _j} = e(d_{1, \sigma _j}, \widehat{g_{2}}^{\alpha }) = e(d_{1, \sigma _j}^{\alpha }, \widehat{g_{2}})\) using secret \(\alpha \) and \(\widehat{g_{2}}^{\alpha }\).

  3. 3.

     Generate \(\mathsf{NIZK}\) proof \(\delta _{\sigma _j}\) using \(\mathsf{GS}_S = (\widetilde{u_1}, \widetilde{u_2}, \widetilde{u_3})\) as

     $$\begin{aligned} \delta _{\sigma _j} = \mathsf{NIZK}&\{(a_{1, \sigma _j}, a_{2, \sigma _j}, a_{3, \sigma _j}) ~| ~ e(d_{1, \sigma _j}, a_{2, \sigma _j})e(a_{3, \sigma _j}, \widehat{g_{2}}^{-1}) = 1\\&\wedge e(a_{1, \sigma _j}, \widehat{g_2}^{-1})e(g, a_{2, \sigma _j}) = 1 \wedge e(a_{1, \sigma _j}, \widehat{g_2}) = e(\widehat{g_1}, \widehat{g_2}) \} \end{aligned}$$

     The proof \(\delta _{\sigma _j}\) consists of commitments to \(a_{1, \sigma _j} = \widehat{g_{1}}, a_{2, \sigma _j} = \widehat{g_{2}}^{\alpha }, a_{3, \sigma _j} = d_{1, \sigma _j}^{\alpha }\) and proof components of three pairing product equations. The size of proof \(\delta _{\sigma _j}\) is 18 group elements and computation cost in generating \(\delta _{\sigma _j}\) is 36 exponentiations.

  The algorithm outputs \((\mathsf{Res}_{\sigma _j}, \delta _{\sigma _j})\). The sender S sends \((\mathsf{Res}_{\sigma _j}, \delta _{\sigma _j})\) to R.

• \(\mathsf{CompleteTra}(\mathsf{crs}, \mathsf{Res}_{\sigma _j}, \delta _{\sigma _j}, \mathsf{Pri}_{\sigma _j}, \varPhi _{\sigma _j})\): The receiver R with input \((\mathsf{crs}, \mathsf{Res}_{\sigma _j}\), \(\delta _{\sigma _j}, \mathsf{Pri}_{\sigma _j}, \varPhi _{\sigma _j})\) runs this deterministic algorithm to recover \(m_{\sigma _j}\) as follows.

  1. 1.

     The algorithm verifies the proof \(\delta _{\sigma _j}\) by verifying each pairing product equation in \(\delta _{\sigma _j}\) as discussed in the Sect. 2.2. The verification of \(\delta _{\sigma _j}\) takes 36 pairings. If fails, it aborts the execution.

  2. 2.

     Otherwise, it computes

     $$\begin{aligned} \frac{c_{\sigma _j}^{(3)}\cdot e(\widehat{g_1}, t_{\sigma _j})}{\mathsf{Res}_{\sigma _j}} = m_{\sigma _j} \end{aligned}$$

     (6)

Correctness of Eq. 6 :

as \(\widehat{g_1} = g^{\alpha }\), \(t_{\sigma _j} = \widehat{g_{2}}^{v_{\sigma _j}}\), \(c_{\sigma _j}^{(3)} = m_{\sigma _j}\cdot e(\widehat{g_1}, \widehat{g_2})^{r_{\sigma _j}}\).

Theorem 3

The \(\mathsf{OT}^{N}_{k \times 1}\) presented in Sect. 4 securely realizes the ideal functionality \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) in the \(\mathcal {F}_\mathsf{CRS}^{\mathcal {D}}\)-hybrid model described in Sect. 3 under the DLIN, DBDH and SqDBDH assumptions.

Proof

Let \(\mathcal {A}\) be a static adversary interacting with the protocol \(\varPsi \) in the real world. Our task is to construct an ideal world adversary \(\mathcal {A'}\) in the ideal world interacting with the ideal functionality \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) such that no environment machine \(\mathcal {Z}\) can distinguish its interaction with the protocol \(\varPsi \) and \(\mathcal {A}\) in the real world from its interactions with \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) and \(\mathcal {A'}\) in the ideal world. We will show \(\mathsf{IDEAL}_{\mathcal {F}_\mathsf{OT}^{N \times 1}, \mathcal {A'}, \mathcal {Z}} \mathop {\approx }\limits ^{c} \mathsf{REAL}_{\varPsi , \mathcal {A}, \mathcal {Z}}\) in each of the cases: (a) simulation when the receiver R is corrupted and the sender S is honest, (b) simulation when the sender S is corrupted and the receiver R is honest. When both the parties (the sender S and the receiver R) are honest or both the parties are corrupt are not discussed as these are trivial cases.

The security proof is presented using sequence of hybrid games. Let \(\mathsf{Pr}[\mathsf{Game}~ i]\) be the probability that \(\mathcal {Z}\) distinguishes the transcript of \(\mathsf{Game} ~i\) from that in the real execution.

(a) Simulation when the receiver R is corrupted and the sender S is honest. In this case, the receiver R is controlled by \(\mathcal {A}\) and \(\mathcal {A'}\) simulates the honest sender S without knowing the database \(\mathsf{DB}\).

: This game is same as the real world protocol in which R interacts with honest S having database \(\mathsf{DB} = (m_1, m_2, \ldots , m_N)\). So, \(\mathsf{Pr}[\mathsf{Game}~ 0] = 0\).

: This game is exactly the same as \(\mathsf{Game} ~0\) except that \(\mathcal {A'}\) simulates the common reference string \(\mathsf{crs}\). The adversary \(\mathcal {A'}\) first generates \(\mathsf{params} = (p, \mathbb {G}, \mathbb {G}_{T}, e, g) \leftarrow \mathsf{BilinearSetup}(1^\rho )\), picks \(a, b, \xi _1, \xi _2, \widetilde{a}, \widetilde{b}, \widetilde{\xi _1}, \widetilde{\xi _2} \xleftarrow {\$} \mathbb {Z}_{p}^{*}\) and sets \(g_1 = g^{a}, g_2 = g^{b}, \widetilde{g_1} = g^{\widetilde{a}}, \widetilde{g_2} = g^{\widetilde{b}}, u_1 = (g_1, 1, g), u_2 = (1, g_2, g), u_3 = u_{1}^{\xi _1}u_{2}^{\xi _2} = (g_{1}^{\xi _1}, g_{2}^{\xi _2}, g^{\xi _1 + \xi _2}), \widetilde{u_1} = (\widetilde{g_1}, 1, g), \widetilde{u_2} = (1, \widetilde{g_2}, g), \widetilde{u_3} = \widetilde{u_{1}}^{\widetilde{\xi _1}}\widetilde{u_{2}}^{\widetilde{\xi _2}}(1, 1, g) = (\widetilde{g_{1}}^{\widetilde{\xi _1}}, \widetilde{g_{2}}^{\widetilde{\xi _2}}\), \(g^{\widetilde{\xi _1} + \widetilde{\xi _2} + 1}), \mathsf{GS}_R = (u_1, u_2, u_3), \mathsf{GS}_S = (\widetilde{u_1}, \widetilde{u_2}, \widetilde{u_3})\), \(\mathsf{crs} = (\mathsf{params}, \mathsf{GS}_R, \mathsf{GS}_S)\), trapdoors \(\mathsf{t_{ext}} = (a, b, \xi _1, \xi _2)\), \(\widetilde{\mathsf{t_{sim}}} = (\widetilde{a}, \widetilde{b}, \widetilde{\xi _1}, \widetilde{\xi _2})\). The \(\mathsf{GS}_R\) is generated in perfectly sound setting and \(\mathsf{GS}_S\) in witness-indistinguishability setting. When the parties query \((\mathsf{sid}, \mathsf{CRS})\), \(\mathcal {A'}\) returns \((\mathsf{sid}, \mathsf{CRS}, \mathsf{crs})\). The trapdoors \(\mathsf{t_{ext}}\) and \(\widetilde{\mathsf{t_{sim}}}\) are kept secret by \(\mathcal {A'}\). The \(\mathsf{crs}\) generated by \(\mathcal {A'}\) in \(\mathsf{Game} ~1\) and that by algorithm \(\mathsf{CRSSetup}\) in actual protocol run are computationally indistinguishable by Theorem 1. Therefore, there exists a negligible function \(\epsilon _{1}(\rho )\) such that \(|\mathsf{Pr}[\mathsf{Game}~ 1] - \mathsf{Pr}[\mathsf{Game}~ 0]| \le \epsilon _{1}(\rho )\).

: This game is exactly the same as \(\mathsf{Game} ~1\) except that \(\mathcal {A'}\) extracts the index \(\sigma _{j}\) for each request by \(\mathcal {A}\) as follows in each transfer phase \(j=1, 2, \ldots , k\). The adversary \(\mathcal {A'}\) parses \(\mathsf{Req}_{\sigma _j}\) as \((d_{1, \sigma _j}, \pi _{\sigma _j})\) and checks the correctness of \(\pi _{\sigma _j}\). If fails, \(\mathcal {A'}\) aborts the execution, otherwise, \(\mathcal {A'}\) extracts the witnesses and index from proof \(\pi _{\sigma _j}\) as follows. The proof \(\pi _{\sigma _j}\) consists of commitments to \(c_{\sigma _j}^{(1)}, c_{\sigma _j}^{(2)}, f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell }, t_{\sigma _j}, d_{2, \sigma _j}\), and proof components of the pairing product equations

• The adversary \(\mathcal {A'}\) extracts first witness \(\mathsf{wit}_1\) from \(\mathsf{Com}(c_{\sigma _j}^{(1)})= \mu (c_{\sigma _j}^{(1)})u_{1}^{\widetilde{r_1}}u_{2}^{\widetilde{r_2}}u_{3}^{\widetilde{r_3}}\) \(= (g_{1}^{\widetilde{r_{1}} + \widetilde{r_{3}}\xi _1}\), \(g_{2}^{\widetilde{r_{2}} + \widetilde{r_{3}}\xi _2}, c_{\sigma _j}^{(1)}g^{\widetilde{r_{1}} + \widetilde{r_{2}} + \widetilde{r_{3}}(\xi _1 + \xi _2)})\) as \(\frac{c_{\sigma _j}^{(1)}g^{\widetilde{r_{1}} + \widetilde{r_{2}} + \widetilde{r_{3}}(\xi _1 + \xi _2)}}{(g_{1}^{\widetilde{r_{1}} + \widetilde{r_{3}}\xi _1})^{\frac{1}{a}}(g_{2}^{\widetilde{r_{2}} + \widetilde{r_{3}}\xi _2})^{\frac{1}{b}}} = c_{\sigma _j}^{(1)} = \mathsf{wit}_1\) using \(\mathsf{t_{ext}} = (a, b, \xi _1, \xi _2)\), where \(\widetilde{r_1}, \widetilde{r_2}, \widetilde{r_3}\) are random values which were used for generating \(\mathsf{Com}(c_{\sigma _j}^{(1)})\). Similarly, \(\mathcal {A'}\) extracts \(\mathsf{wit}_2 = c_{\sigma _j}^{(2)}\), \(\mathsf{wit}_3 = f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell }\), \(\mathsf{wit}_4 = t_{\sigma _j}\), \(\mathsf{wit}_5 = d_{2, \sigma _j}\) from their respective commitments.

• The adversary \(\mathcal {A'}\) checks whether \(\mathsf{wit}_1 = c_{\zeta }^{(1)}\) and \(\mathsf{wit}_2 = c_{\zeta }^{(2)}\), \(\zeta = 1, 2, \ldots , N\). Suppose no matching index found, i.e., \(\sigma _j \notin \{1, 2, \ldots , N\}\) and a valid proof \(\pi _{\sigma _j}\) is constructed by \(\mathcal {A}\) for the ciphertext \(\varPhi _{\sigma _j} \notin \mathsf{cDB} = (\varPhi _1, \varPhi _2, \ldots , \varPhi _{N})\) in order to generate \(\mathsf{Req}_{\sigma _j}\). The validity of the proof \(\pi _{\sigma _j}\) generated by \(\mathcal {A}\) for \(\varPhi _{\sigma _j}\) indicates that the ciphertext \(\varPhi _{\sigma _j}\) must be a correct ciphertext. This eventually means that \(\mathcal {A}\) generates a valid Water’s signature on index \(\sigma _j\) and outputs \(c_{\sigma _j}^{(1)}, c_{\sigma _j}^{(2)}\) as a forgery contradicting the fact that the Water’s signature is existentially unforgeable under the hardness of DBDH problem [21]. Let \(\sigma _j\) be the matching index and \(\mathcal {I}_{\sigma _j} = {\sigma _j}_1{\sigma _j}_2\ldots {\sigma _j}_n\) be the n bit representation of \(\sigma _j\). The adversary \(\mathcal {A'}\) checks whether \(\mathsf{wit}_3 = f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell }\), where \(\mathcal {M}_{\sigma _j}\) be the set of all \(\ell \in [n]\) for which \({\sigma _j}_{\ell }\)is 1. If fails, aborts the execution.

• Otherwise, \(\mathcal {A'}\) queries \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) with the message \((\mathsf{sid}, \mathsf{transfer}, \sigma _j)\). The \(\mathcal {F}_\mathsf{OT}^{N \times 1}\) gives \(m_{\sigma _j}\) to \(\mathcal {A'}\).

The difference between \(\mathsf{Game} ~3\) and \(\mathsf{Game} ~2\) is negligible provided that DBDH assumptions hold. Therefore, there exists a negligible function \(\epsilon _{3}(\rho )\) such that \(|\mathsf{Pr}[\mathsf{Game}~ 3] - \mathsf{Pr}[\mathsf{Game}~ 2]| \le \epsilon _{3}(\rho )\).

: This game is the same as \(\mathsf{Game} ~2\) except that the response \(\mathsf{Res}_{\sigma _j}\) and proof \(\delta _{\sigma _j}\) are simulated by \(\mathcal {A'}\) for each transfer phase j, where \(j = 1, 2, \ldots , k\). The ciphertext \(\varPhi _{\sigma _j} = (c_{\sigma _j}^{(1)} = g^{r_{\sigma _j}}, c_{\sigma _j}^{(2)} = \widehat{g_{2}}^{\alpha }(f'\prod _{\ell \in \mathcal {M}_{\sigma _j}}f_{\ell })^{r_{\sigma _j}}, c_{\sigma _j}^{(3)})\). The adversary \(\mathcal {A'}\) simulates response \(\mathsf{Res'}_{\sigma _j}\) and proof \(\delta '_{\sigma _j}\) as follows. The simulated response

The honestly generated response

as \(\widehat{g_1} = g^{\alpha }\). The simulated \(\mathsf{Res}'_{\sigma _j}\) has the same distribution as honestly generated response \(\mathsf{Res}_{\sigma _j}\) by algorithm \(\mathsf{ResponseTra}\) discussed in the Sect. 4. The adversary \(\mathcal {A'}\) also simulates \(\delta '_{\sigma _j}\) to prove that \(\mathsf{Res}'_{\sigma _j}\) is correctly framed. The proof

consists of commitments to secret values \(a_{1, \sigma _j} = \widehat{g_{1}}, a_{2, \sigma _j} = \widehat{g_{2}}^{\alpha }, a_{3, \sigma _j} = d_{1, \sigma _j}^{\alpha }\) and proof components to 3 pairing product equations. For simulation, \(\mathcal {A'}\) sets \(a_{1, \sigma _j}= a_{2, \sigma _j} = a_{3, \sigma _j} = 1\) and generate commitments to \(a_{1, \sigma _j}, a_{2, \sigma _j}\), \(a_{3, \sigma _j}\) using \(\mathsf{GS}_S\). The adversary \(\mathcal {A'}\) also generates opening value of commitment \(a_{1, \sigma _j}\). With the help of trapdoor \(\widetilde{\mathsf{t_{sim}}}\) and opening value, \(\mathcal {A'}\) can open the commitment of \(a_{1, \sigma _j}\) to 1 in second equation and \(a_{1, \sigma _j}\) to \(\widehat{g_{1}}\) in third equation as discussed in Example 1 in Sect. 2.2. As Groth-Sahai proofs are composable \(\mathsf{NIZK}\) by Theorem 2, the simulated proof \(\delta '_{\sigma _j}\) is computationally indistinguishable from the honestly generated proof \(\delta _{\sigma _j}\) under the DLIN assumption. Therefore, there exists a negligible function \(\epsilon _{4}(\rho )\) such that \(|\mathsf{Pr}[\mathsf{Game}~ 4] - \mathsf{Pr}[\mathsf{Game}~ 3]| \le \epsilon _{4}(\rho )\).

: This game is the same as \(\mathsf{Game} ~3\) except that the S’s database \(\mathsf{DB} = (m_1, m_2, \ldots , m_N)\) is replaced by random database \(\mathsf{\widehat{DB}} = (\widehat{m}_1, \widehat{m}_2, \ldots , \widehat{m}_N)\), thereby, \(\mathcal {A'}\) replaces S’s first message \((\mathsf{sid}, S, \mathsf{pk}, \psi , \mathsf{cDB})\) by \((\mathsf{sid}, S, \mathsf{pk}', \psi ', \mathsf{\mathsf{cDB}'})\), where \((\mathsf{pk}', \psi ', \mathsf{cDB}')\) are simulated by \(\mathcal {A'}\) with a database \(\mathsf{DB'}=(\widehat{m}_{1}, \widehat{m}_{2}, \ldots , \widehat{m}_{n})\), where \(\widehat{m}_1, \widehat{m}_2, \ldots , \widehat{m}_N \xleftarrow {\$} \mathbb {G}_T\). In each transfer phase, the response \((\mathsf{sid}, S, \mathsf{Res}_{\sigma _j}\), \(\delta _{\sigma _j})\) is replaced by the simulated response \((\mathsf{sid}, S, \mathsf{Res}'_{\sigma _j}, \delta '_{\sigma _j})\) as in above game, but here the simulated response is computed on invalid statement. The only difference between \(\mathsf{Game}~ 4\) and \(\mathsf{Game}~ 3\) is in the generation of ciphertexts. In \(\mathsf{Game}~ 4\), \(\mathsf{cDB}'\) is the encryption of random messages \(\widehat{m}_{1}, \widehat{m}_{2}, \ldots , \widehat{m}_{n}\), whereas \(\mathsf{cDB}\) in \(\mathsf{Game}~ 3\) is that of perfect messages \(m_1, m_2, \ldots , m_N\). By the Lemma 1 given below, \(\mathsf{Game}~ 3\) is computationally indistinguishable from \(\mathsf{Game}~ 4\). Therefore, \(|\mathsf{Pr}[\mathsf{Game}~ 4] - \mathsf{Pr}[\mathsf{Game}~ 3]| \le \epsilon _{4}(\rho )\), where \(\epsilon _{4}(\rho )\) is a negligible function.

Lemma 1

Let \(\mathsf{DB} = (m_1, m_2, \ldots , m_N)\) be any database and \(\mathsf{\widehat{DB}} = (\widehat{m}_1, \widehat{m}_2, \ldots \), \(\widehat{m}_N)\) be a set of random messages. Under the hardness of SqDBDH, no distinguisher \(\mathcal {Z}\) can distinguish the transcript of \(\mathsf{Game}~ 3\) from the transcript of \(\mathsf{Game}~ 4\).

Thus \(\mathsf{Game} ~4\) is the ideal world interaction whereas \(\mathsf{Game} ~0\) is the real world interaction. Now \( |\mathsf{Pr}[\mathsf{Game}~ 4] - [\mathsf{Game}~ 0]| \le |\mathsf{Pr}[\mathsf{Game}~ 4] - [\mathsf{Game}~ 3]| + |\mathsf{Pr}[\mathsf{Game}~ 3] - [\mathsf{Game}~ 2]| + |\mathsf{Pr}[\mathsf{Game}~ 2] - [\mathsf{Game}~ 1]| + |\mathsf{Pr}[\mathsf{Game}~ 1] - [\mathsf{Game}~ 0]|\le \epsilon _{5}(\rho ), \) where \(\epsilon _{5}(\rho ) = \epsilon _{4}(\rho ) + \epsilon _{3}(\rho ) + \epsilon _{2}(\rho ) + \epsilon _{1}(\rho )\) is a negligible function. Hence, \(\mathsf{IDEAL}_{\mathcal {F}_\mathsf{OT}^{N \times 1}, \mathcal {A'}, \mathcal {Z}}\) \(\mathop {\approx }\limits ^{c} \mathsf{REAL}_{\varPsi , \mathcal {A}, \mathcal {Z}}\).

(b) Simulation when the sender S is corrupted and the receiver R is honest. Due to lack of space, proof of Lemma 1 and simulation of Case (b) will be given in full version.

In this section, we compare our \(\mathsf{OT}_{k \times 1}^{N}\) with the existing similar schemes [1, 14, 17, 20]. Green and Hohenberger’ [14] scheme employes Boneh, Boyen and Shacham (BBS) [5] encryption, Camenisch-Lysyanskaya (CL) signature [6], Boneh-Boyen signature [3], non-interactive Groth-Sahai proofs [16] and is secure under symmetric external Diffie-Hellman (SXDH), DLIN, q-hidden Lysyanskaya, Rivest, Sahai and Wolf (LRSW) assumptions. Rial et al.’s [20] UC secure priced \(\mathsf{OT}_{k \times 1}^{N}\) protocol combines BBS [5] encryption, P-signatures [2], non-interactive Groth-Sahai proofs [16] and achieves security under hidden strong Diffie-Hellman (HSDH), triple Diffie-Hellman (TDH) and DLIN assumptions. Guleria and Dutta’s [17] scheme combines BBS [5] encryption, batch Boneh and Boyen (BB) [4] signature with non-interactive Groth-sahai proofs [16], trapdoor commitments of Fischlin et al. [11] and is secure under q-SDH, DLIN assumptions.

The schemes [14, 17, 20] use dynamic q-type assumptions. Abe et al. [1] proposed the first adaptive oblivious transfer without q-type assumptions in UC framework. It uses ElGamel encryption, structure preserving signature [1], non-interactive Groth-Sahai proofs [16], interactive zero-knowledge proofs. The construction is proven to be secure under the hardness of SXDH, DLIN and decisional Diffie-Hellman in target group (\(DDH_{T}\)) problems. Some components of the ciphertexts in [1, 14, 20] are never used in the real protocol. Instead they are included to facilitate simulation of the security proof in UC model. Consequently, nothing can prevent a cheating sender to replace these components with garbage values without affecting the security and correctness of these protocols. However from efficiency point of view, we feel that these type of redundancies are not desirable in practice. It will be better if we can design a protocol in which all the components of the ciphertext are used in real protocol execution retaining the same security level.

Motivated by [1], our scheme also does not use q-type assumptions. We use Water’s signature [21], non-interactive Groth-sahai proofs [16], and our scheme is secure under DLIN and DBDH assumptions. Our proposed construction takes 2 rounds in each transfer phase while [1] takes 3 rounds in each transfer phase. As illustrated in Table 1, our \(\mathsf{OT}_{k \times 1}^{N}\) outperforms the best known schemes [1, 14, 17, 20], which are to best of our knowledge, the only existing basic UC secure adaptive oblivious transfer protocols so far.