Efficient Post Quantum Random Oblivious Transfer Based on Lattice

Abstract

The large scale multiparty computation and private set intersection requires a number of oblivious transfer instances as subroutines, but the implementation of oblivious transfer protocols is relatively slow. An feasible way is to use the oblivious transfer variant called random oblivious transfer. In this paper, we propose a 1-out-of-2 random oblivious transfer protocol and extend it to a 1-out-of-k random oblivious transfer protocol based on the LWE assumption, quantum computation and measurement. Then, we analysis the stand-alone security of our 1-out-of-2 random oblivious transfer protocol under various malicious situations and prove its universally composable security in UC framework. As for the security of our 1-out-of-k random oblivious transfer protocol, the similar results can be obtained.

Supported by the National Key Research and Development Program of China (No. 2021YFA1000600), the National Key Research and Development Program of China (Grant No. 2018YFA0704702), and the National Natural Science Foundation of China (Grant No. 61832012).

1 Introduction

Oblivious transfer (OT) is an important cryptographic primitive which can be used for designing secure multi-party computation (MPC) [1,2,3], bit commitment [4,5,6] and private set intersection (PSI) [7, 8]. The OT protocol was firstly proposed, by Michael O. Rabin in 1981, to construct a secrets exchange scheme [9]. The original OT protocol has two participants, where one party (the sender) sends a message to another (the receiver) with the requirement that the receiver obtains this message with probability $\frac{1}{2}$ and the sender remains oblivious of whether the message has been received or not.

In order to build protocols for secure two-party computation, a more useful kind of OT protocol, called the 1-out-of-2 OT protocol, was developed [10,11,12,13]. In these protocols, the receiver is allowed to get one message from the sender’s message pair without knowing anything about the other message, and the sender is required not to know about the receiver’s choice. Another OT variant is the randomized oblivious transfer (ROT), the only difference from 1-out-of-2 OT lies in that the receiver is required to get one message randomly.

As is know, MPC protocols based on oblivious-circuit evaluation techniques require a large number of OT. Since the OT schemes are relatively slow, they become a major bottleneck for the large-scale MPC implementations. In order to deal with the problem of OT efficiency, Ishai et al. introduce the concept of OT extension [14] where one needs to use ROT instances as base OTs. In addition, the ROT scheme also is a main tool in designing efficient PSI protocols [8] which is one of the most popular MPC technique.

Motivated by the construction of trapdoor, claw free, 2-regular functions in [15,16,17], we propose a 1-out-of-2 ROT protocol based on quantum mechanics and LWE assumption. Then, we construct a family of trapdoor claw-free k-regular functions and extend the 1-out-of-2 ROT protocol to a 1-out-of-k ROT protocol. Furthermore, we analysis the stand-alone security of our ROT protocols under various malicious situations and prove their universally composable security in UC framework. The key technique of our protocol is to construct a family of trapdoor, claw free, k-regular function based on the LWE assumption. Another technique used in our protocol is quantum computation and quantum entanglement by which Bob can obtain only one of k preimages after measuring the produced quantum state.

2 The Construction of TCF k-Regular Functions

In this section, we will describe the construction of trapdoor claw-free (TCF) 2-regular functions defined in [17] and the construction of trapdoor claw-free k-regular functions, which are necessary for our ROT protocols. We start with the definition of trapdoor claw-free k-regular functions as follows:

Definition 1 (Trapdoor claw-free k-regular). A deterministic function $f: D\rightarrow R$ is a trapdoor claw-free k-regular function if the following conditions hold:

• k-regular: $\forall y\in Im(f),$ we have $|f^{-1}(y)| = k$.

• collision resistance: It is impossible to find out any pair $(x_{0}, x_{1})$ such that $x_{0} \ne x_{1} \wedge f(x_{0}) = f(x_{1})$ for any QPT algorithm without the trapdoor.

• Trapdoor one-way: Given $y\in Im(f)$ and the trapdoor $t_{f}$ of the function f, there exists a QPT algorithm that can return the set $f^{-1}(y)$. Moreover, it is impossible to get any $x \in f^{-1}(y)$ for any QPT algorithm without the trapdoor.

2.1 Requirements on Parameters

Let $\lambda \in \mathbb {Z}$ be the security parameter in the LWE problem, all other parameters be the functions of $\lambda$.

• $n = \lambda$, the length of vector ${\textbf {s}}$ ;

• $q = poly(n)$, the prime modulus;

• $m \approx 2n\lg q$, the length of the error vector ${\textbf {e}}$;

• $\alpha \in (0,1)$, the discrete Gaussian distribution $\overline{\varPhi }_{\alpha }$ is centered around 0 with standard deviation $\alpha q \ge 2\sqrt{n}$.

Under the setting of the parameters above, the LWE problem is at least as hard as solving $\textrm{SIVP}$ [18, 19]. And thus, the functions constructed in Sect. 3.2 and Sect. 3.3 are all trapdoor claw-free.

2.2 On the TCF 2-Regular Functions

In [17], the authors constructed a family $\mathcal{F}_2$ of TCF 2-regular functions based on the existence of a family $\mathcal {G}$ of injective, homomorphic, trapdoor one-way functions. For the completeness, we will recall the construction of $\mathcal{F}_2$ and related knowledge in this subsection.

The specific family $\mathcal{G}$ of injective, homomorphic, trapdoor one-way functions was constructed by Micciancio and Peikert [20]. Here, we list the outline of their construction and leave the detail to readers. First, generate a $n \times \bar{m}$ matrix A by randomly choosing its elements from $\mathbb {Z}_{q}$ and a $\bar{m}\times kn$ trapdoor matrix R by sampling its elements from a discrete Gaussian distribution $\mathcal{D}_{\alpha q}^{\bar{m}\times \omega }$ with mean 0 and standard deviation $\alpha q$. Then, select a fixed matrix G as in [20] for which the function $g_{G}(s,e) = s^{t}G + e^{t}$ can be efficiently inverted, and construct the index matrix K by concatenating A and $G - AR$, i.e. $K = (A, G - AR)$. Finally, define the function $g_{K}$ with trapdoor $t_K = R$, which forms the family $\mathcal{G}$, as follow:

$$\begin{aligned} g_{K}(s,e) = s^{t}K - e^{t},\end{aligned}$$

(1)

where $s\in \mathbb {Z}_{q}^{n}$ and $e\in L^{m}$, L is the domain of the errors in the LWE problem (the set of integers bounded in absolute value by $\mu$).

Theorem 1 ([20]). The functions in $\mathcal {G}$ are injective, homomorphic, trapdoor one-way.

2.3 The Construction of TCF k-Regular Functions

In order to design the $1-k$ ROT protocol, we need to construct a family $\mathcal{F}_k$ of TCF k-regular functions. Motivated by the idea of constructing TCF 2-regular functions in Sect. 3.2, we construct the family $\mathcal{F}_k$ also by using the family $\mathcal{G}$ of homomorphic injective trapdoor one-way functions.

Let $g_K \in \mathcal{G}$ with trapdoor $t_K$, $x^i \in \mathcal{D}\setminus \{0\} ( 0 \,\le \, i \,\le \, k-2)$ satisfying $x^{i} \ne x^{j}$ whenever $i \ne j$, we define the function $f: \mathcal{D}\times \mathbb {Z}_k \rightarrow \mathcal R$ with trapdoor $t_f = (t_K, x^0, ..., x^{k\,-\,1})$, which forms the family $\mathcal{F}_k$, as follows:

$$\begin{aligned} f(x,c) = \left\{ \begin{array}{lllll} g_K(x), &{} \hbox {if c = 0;} \\ g_K(x) + g_K(x^{0}), &{} \hbox {if c = 1;}\\ g_K(x) + g_K(x^{1}), &{} \hbox {if c = 2;}\\ ... &{} \hbox {}\\ g_K(x) + g_K(x^{k-2}), &{} \hbox {if c = k-1.} \end{array} \right. \end{aligned}$$

(2)

In a similar way as proving the functions in $\mathcal {F}_2$ are TCF 2-regular in [17], we can prove that the functions in $\mathcal {F}_k$ constructed above is TCF k-regular.

Theorem 2 . The functions in the family $\mathcal {F}_k$ are trapdoor claw-free k-regular.

3 Our $1-k$ ROT Protocols

In this section, we will present a $1-2$ ROT protocol by using the family $\mathcal {F}_2$ of TCF 2-regular functions in [17], and extend this protocol into a $1-k$ ROT protocol by using the family $\mathcal {F}_k$ of TCF k-regular functions constructed in Sect. 3. As in [17], for $k \ge 2$, we employ the family $\mathcal {F}_k$ of TCF k-regular functions in a convenient form as $\mathcal{F}_k = \{f: \{0,1\}^n \rightarrow \{0,1\}^m \}$, where the domain of each f is also denoted by D.

3.1 The $1-2$ ROT Protocol

In the prepare stage, first choosing a fixed function f and its trapdoor $t_f$ from the family $\mathcal{F}_2 = \{f: \{0,1\}^n \rightarrow \{0,1\}^m \}$ of TCF 2-regular functions. Then, giving $(f, t_f)$ to the sender Alice and f to the receiver Bob. To transfer the two messages $b_1, b_2 \in \{0,1\}^m$ from Alice to Bob obliviously, our $1-2$ ROT protocol performs as follows:

• 1. Bob prepares his registers at $\frac{1}{\sqrt{|D|}}\sum \limits _{x\in D}(|x\rangle \otimes |0\rangle )$.

• 2. Bob applies the operator $U_{f}$ by using the first register as control and the second one as target, and the state in the two registers is in the form of $\frac{1}{\sqrt{|D|}}\sum \limits _{x\in D}|x\rangle |f(x)\rangle$. After that, Bob sends the second register to Alice.

• 3. Alice measures her register in the computational basis and obtains the outcome y. Then, Bob’s register becomes $\frac{1}{\sqrt{2}} (|x_1\rangle +|x_2\rangle )$, where $f(x_1) = f(x_2) =y$. Bob measures his register in the computational basis and obtains the outcome $\widetilde{x}$ ($= x_1$ or $x_2$).

• 4. Alice computes the preimages $x_1, x_2$ of y by using the trapdoor $t_f$. Then, she sends the pairs $(a_{1}=b_{1}\oplus x_1, h(x_1))$ and $(a_{2}=b_{2}\oplus x_2, h(x_2))$ to Bob, where h(x) represents the last bit of x.

• 5. Bob computes the value of $f(a_{1}\oplus a_{2}\oplus \widetilde{x})$. If the result is y (which means $b_1 = b_2$), then he terminates this protocol.

• 6. Bob gets the message $b_\sigma$ by computing $a_\sigma \oplus \widetilde{x}$ if $h(x_\sigma ) = h(\widetilde{x})$ ($\sigma = 1$ or 2).

3.2 The $1-k$ ROT Protocol

To extend the protocol above into the general $1-k$ ROT protocol, we only need to substitute the TCF 2-regular function for a TCF k-regular function constructed in Sect. 3.3.

In the prepare stage, first choosing a fixed function f and its trapdoor $t_f$ from the family $\mathcal{F}_k = \{f: \{0,1\}^n \rightarrow \{0,1\}^m \}$ of TCF k-regular functions. Then, giving $(f, t_f)$ to the sender Alice and f to the receiver Bob. To transfer the k messages $b_1, b_2, ..., b_k \in \{0,1\}^m$ from Alice to Bob obliviously, our $1-k$ O.T. protocol performs as follows:

• 1. Bob prepares his registers at $\frac{1}{\sqrt{|D|}}\sum \limits _{x\in D}(|x\rangle \otimes |0\rangle )$.

• 2. Bob applies the operator $U_{f}$ by using the first register as control and the second one as target, and the state in the two registers is in the form of $\frac{1}{\sqrt{|D|}}\sum \limits _{x\in D}|x\rangle |f(x)\rangle$. After that, Bob sends the second register to Alice.

• 3. Alice measures her register in the computational basis and obtains the outcome y. Then, Bob’s register becomes $\frac{1}{\sqrt{k}}(|x_1\rangle + ... +|x_k\rangle )$ where $f(x_1)=...=f(x_k)=y$. Bob measures his register in the computational basis and obtains the outcome $\widetilde{x} (\in \{x_1, x_2, ..., x_k\})$.

• 4. Alice computes the preimages $x_{1}, ..., x_{k}$ of y by using the trapdoor $t_f$. Then, she sends the pairs $(a_{i} = b_{i} \oplus x_{i}, h(x_{i}))(1 \le i \le k)$ to Bob, where h(x) presents the last $\lfloor \log k\rfloor$ bits of x.

• 5. Bob computes the value of $f(a_{i}\oplus a_{j} \oplus \widetilde{x}) (1 \le i < j \le k)$. If some $f(a_{i}\oplus a_{j} \oplus \widetilde{x}) = y$ (which means $b_i = b_j$), then he terminates this protocol.

• 6. Bob gets the message $b_\sigma$ by computing $a_\sigma \oplus \widetilde{x}$ if $h(x_\sigma ) = h(\widetilde{x})$ where $\sigma \in \{1, 2, ..., k\}$.

3.3 The Security Analysis of Our $1-2$ ROT Protocol

In this section, we will consider the stand-alone security of our $1-2$ ROT protocol in two aspects, Bob’s malicious operation and Alice’s malicious operation. The extended version, $1-k$ ROT protocol, can be analysed in the same way. Let us first recall the following property of the family $\mathcal {F}_2$ described in Sect. 3.2, on which the security of our $1-2$ ROT protocol is based.

Theorem 3 [17]. The functions in the family $\mathcal {F}_2$ described in Sect. 3.2 are TCF 2-regular.

Bob’s Malicious Strategy. A malicious receiver Bob aims to get both two messages $b_{1}$ and $b_{2}$ from Alice. To achieve his aim, Bob has to find a method to get the collision $x'$ for his measurement outcome $\widetilde{x}$ in Step 3. Except for guessing $x'$, what he could do is computing $y = f(\widetilde{x})$, and managing to find the preimages of y with respect to f. But, the function f is one-way according to Theorem 3, and thus Bob cannot obtain the preimages of y by inverting f. So, it is impossible that Bob have an efficient method to get both $b_{1}$ and $b_{2}$.

Alice’s Malicious Strategy. A malicious sender Alice wants to know what message Bob gets from the transfer procedure. There are two ways for Alice to achieve her aim, one is to get Bob’s measurement outcome $\widetilde{x}$ and another is to cheat by sending illegal information to Bob in Step 4.

Note that, Alice gets y by measuring her register and Bob obtains $\widetilde{x}$ by measuring his register with the superposition state $\frac{1}{\sqrt{2}}(|x_1\rangle +|x_2\rangle )$ in Step 3. Although Alice can computes the preimages $x_1$ and $x_2$ of y by the trapdoor $t_f$ in Step 5, and $\widetilde{x}$ must be one of $x_1$ and $x_2$, Alice has no way to determine which one $\widetilde{x}$ is. So, the first way is not possible.

As for the second way, Alice may send two pairs $(a_{1}=b_{1}\oplus w_1, h(w_1))$ and $(a_{2}=b_{2}\oplus x_2, h(x_2))$ with $b_1 = b_2$ to Bob in Step 4. If Bob does not verify whether the two pairs are legal, he will always get $b_{1}$ in Step 6, no matter what his measurement outcome $\widetilde{x}$ is. And thus, Alice can know what the message Bob obtains. But in Step 5, Bob verifies the reality of the two pairs from Alice by computing the value of $f(a_{1}\oplus a_{2}\oplus \widetilde{x})$. If the result is y, then Bob infers that $b_1$ and $b_2$ are the same, and terminates the protocol. Therefore, this strategy also does not work.

4 The UC-security of Our $1-2$ ROT Protocol

In this section, we will prove the universally composable security of our $1-2$ ROT protocol in the UC framework. As for our $1-k$ ROT protocol, its UC-security can be proven in the same way.

We work in the standard universal composability framework of Canetti [21] with static corruption of some parties. The ideal world execution involves dummy parties (some of whom may be corrupted by an ideal adversary) interacting with the functionality $\mathcal{F}$. The dummy parties only relay the inputs to $\mathcal{F}$, and relay the outputs of $\mathcal{F}$ to the calling machine. The real world execution involves parties (some of whom may be corrupted by a real world adversary) interacting only with each other.

For our $1-2$ ROT protocol interacting with an adversary, the functionality $\mathcal{F}_{ROT}$ interacting with the simulator in the ideal world is defined as follows:

Fig. 1.

The functionality $\mathcal{F}_{ROT}$

Let $\mathcal {A}$ be a static adversary that interacts with the parties Alice and Bob running the $1-2$ ROT protocol, we now construct a simulator $\mathcal {S}$ in ideal world interacting with the ideal functionality $\mathcal {F}_{ROT}$, such that no environment $\mathcal{Z}$ can distinguish the interaction with $\mathcal{A}$ in the real world from the interaction with $\mathcal{S}$ in the ideal world. The simulator $\mathcal{S}$ starts by invoking a copy of $\mathcal{A}$ and runs a simulated interaction of $\mathcal{A}$ with $\mathcal{Z}$ and the parties Alice and Bob. More specifically, the simulator $\mathcal{S}$ works as follows:

Simulating the communication with $\mathcal{Z}$: Every input value that $\mathcal{S}$ receives from $\mathcal{Z}$ is written on the adversary $\mathcal{A}$’s input tape (as if coming from $\mathcal{A}$’s environment). Every output value written by $\mathcal{A}$ on its output tape is copied to $\mathcal{S}$’s output tape (to be read by the environment $\mathcal{Z}$).

Simulating the case when only Alice is corrupted: The simulator $\mathcal{S}$ randomly selects a function f with its trapdoor $t_f$ from the family $\mathcal{F}_2$ of TCF 2-regular functions, and sends $(f, t_f)$ to Alice and f to Bob respectively.

When $\mathcal{A}$ produces $(a_1, w_1)$ and $(a_2, w_2)$ with $w_1 \ne w_2$ for honest Bob, $\mathcal{S}$ randomly chooses some $\widetilde{x} \in D$. Then, $\mathcal{S}$ computes $y = f(\widetilde{x})$ and another preimage $\widetilde{x'}$ of y by the trapdoor $t_f$. After that, $\mathcal{S}$ computes $b_1 = a_1 \oplus \widetilde{x}$ and $b_2 = a_2 \oplus \widetilde{x'}$ where $h(w_1) = h(\widetilde{x}), h(w_2) = h(\widetilde{x'})$ and stores them. When dummy Bob is activated, $\mathcal{S}$ sends $b_1$ and $b_2$ to $\mathcal{F}_{ROT}$. When $\mathcal{F}_{ROT}$ returns $b_{\sigma }$, $\mathcal{S}$ outputs it as if from Bob.

Simulating the case when only Bob is corrupted: The simulator $\mathcal{S}$ randomly selects a function f and its trapdoor $t_k$ from the family $\mathcal{F}_2$ of TCF 2-regular functions, and sends $(f, t_f)$ to Alice and f to Bob respectively.

When the dummy Alice is activated, $\mathcal{S}$ gets $b_{\sigma }$ from the functionality $\mathcal{F}_{ROT}$ and stores it. When $\mathcal{A}$ is activated, $\mathcal{S}$ outputs $b_{\sigma }$ as if from Bob.

Simulating the remaining cases: When both parties are corrupted, the simulator just runs $\mathcal{A}$ internally (who itself generates the messages from both Alice and Bob). When neither party is corrupted, there is no necessity to construct $\mathcal{S}$.

According to the above models of different corrupted cases, we obtain the following two propositions. And thus, our $1-2$ ROT protocol possesses the UC-security.

Proposition 1 . If the adversary $\mathcal{A}$ corrupts Alice in an execution of our $1-2$ ROT protocol $\pi$, then we have

$$\begin{aligned} {\textbf {IDEAL}}_{\mathcal{F}_{ROT}, \mathcal{S}, \mathcal{Z}}\overset{s}{\approx }{} {\textbf {EXEC}}_{\pi , \mathcal{A}, \mathcal{Z}}. \end{aligned}$$

Proposition 2 . If the adversary $\mathcal{A}$ corrupts Bob in an execution of our $1-2$ ROT protocol $\pi$, then we have

$$\begin{aligned} {\textbf {IDEAL}}_{\mathcal{F}_{ROT}, \mathcal{S}, \mathcal{Z}}\overset{s}{\approx }{} {\textbf {EXEC}}_{\pi , \mathcal{A}, \mathcal{Z}}. \end{aligned}$$

Theorem 4 . Denote our $1-2$ ROT protocol as $\pi$, then

$$\begin{aligned} {\textbf {IDEAL}}_{\mathcal{F}_{ROT}, \mathcal{S}, \mathcal{Z}}\overset{s}{\approx }{} {\textbf {EXEC}}_{\pi , \mathcal{A}, \mathcal{Z}}. \end{aligned}$$

Thus, $\pi$ UC-emulates the ideal function $\mathcal{F}_{ROT}$, in other word, $\pi$ is UC-secure.

5 Conclusion

Motivated by the construction of trapdoor claw-free 2-regular functions in [17], we propose a $1-2$ ROT protocol and construct a family of trapdoor claw-free k-regular functions based on which we extend the $1-2$ ROT protocol to the $1-k$ ROT protocol. In our protocols, the key techniques are quantum computation and the family of trapdoor, claw free, k-regular functions. Furthermore, We analysis the stand-alone security of our $1-2$ ROT protocol in various malicious situations and prove its composable security in the UC framework. Certainly, the security of our $1-k$ ROT protocol can be obtained by a similar discussion.

Comparing with other OT protocols, our $1-2$ ROT protocol possesses stronger security and needs fewer rounds between the sender and the receiver. We give an intuitional comparison between our $1-2$ ROT protocol and the others presented before in the following table:

Table 1. Comparison with other OT (ROT) protocols