Universally Composable Oblivious Transfer with Low Communication

Abstract

In this paper, a universally composable 1-out-of-N oblivious transfer protocol with low communication is built. This protocol obtained full simulation security based on the modulo learning with rounding (Mod-LWR) assumption. It can achieve universally composable security in the random oracle machine (ROM) model by combining random OT based on the key exchange protocol with the authentication encryption algorithm. It can be proven to resist static adversary attacks by simulating all corruption cases. Based on computer simulation and detailed mathematical derivation, this protocol was practicable and had better efficiency and lower communication.

1. Introduction

With the continuous updating and iteration of secure multi-party computation (MPC), many secure multi-party applications have been recently developed and used. For example, Cheetah [1], a new research achievement of Ali, is a secure two-party computing framework that can improve the performance of MPC. It has been used in the risk control field. In addition, many companies and institutes also participate in designing and developing privacy computing platforms [2,3], such as the morse secure computing platform developed by Fu-min bank.

Secure multi-party computation is not an independent technology. However, it includes many fundamental primitives such as secret sharing [4], homomorphic encryption [5], zero-knowledge proof [6], and bit commitment [7], as well as many secure multi-party applications based on the primitives above, such as private set insertion [8], private information retrieval, and secret geometry computing [9]. Besides, all of the efficient MPC applications are based on OT or OT extension. Thus, efficient OT protocols with low communication costs are the focus and difficulty in MPC research.

Oblivious transfer [10], an essential and fundamental primitive of MPC, was first proposed by Rabin in 1981. There are two participants in the OT protocol: the sender (S) and receiver (R). S sends R a message, and R has a 1/2 probability of receiving this message. Besides, S does not know whether R has received the message. In 1995, Even proposed a random 1-out-of-2 oblivious transfer [11] based on public-key cryptography, where the receiver can obtain only one of the two messages from the sender randomly. In 1986, Brassard expanded 1-out-of-2 OT to 1-out-of-N OT [12] to improve the efficiency of the OT protocol. Tzeng proposed a k-out-of-n OT protocol [13] based on the DDH (decisional Diffie–Hellman) difficult problem. It allows the receiver to obtain k of n messages from the sender to make the OT protocol more efficient and practical.

The OT protocol is the bottleneck of the efficiency and communication of the MPC because of its importance. In 2001, Naor and Pinkas proposed an efficient two-round 1-out-of-N OT protocol [14] based on the Diffie–Hellman difficult problem. However, it can obtain half-simulation security and construct a simulator for one party in the ideal environment. In 2008, Damgård proposed an attack method against MPC protocols [15] in the half-simulation paradigm, proving that OT protocols with half-simulation security cannot be used sequentially in combination with other protocols. Hence, the OT protocol is required to prove its security in a fully simulation-based paradigm, where the simulator can be constructed in any corruption case. In 2008, Yehuda proposed an OT protocol [16] with full-simulation security based on the cut-and-choose technology.

In 2001, Canetti proposed the concept of the universally composable (UC) security model [17] to explain and prove the security of the protocol combined with others. From then to now, many universally composable protocols have been designed. In 2019, Peikert et al. proposed an OT protocol based on dual-mode encryption [18], which obtains UC security under the LWE (learning with errors) assumption. In 2020, Lai proposed a UC-secure isogeny-based protocol [19] under ROM.

Most OT protocols are based on number theory, such as the discrete logarithm problem and the substantial number decomposition problem. Considering that these problems may be solvable for quantum computers in an efficient manner, the post-quantum MPC protocol is a hot spot and the focus of contemporary cryptography research. For example, the United States included post-quantum cryptography in the latest revision of the Critical and Emerging Technologies List on 8 February 2022. Post-quantum cryptography is divided into lattice-based cryptography and code-based cryptography, among others. The latticed-based cryptographic protocols have received more attention owing to their provable security and lower asymptotic complexity. In 2019, Pedor proposed a framework for the OT protocol [20] under the UC security model based on key exchange protocol and symmetric encryption. Based on the Pedor’s framework, Chou constructed a UC-secure OT protocol [21]. In addition, Liu proposed an efficient UC-secure OT protocol [22] based on the NewHope key exchange protocol [23] on the lattice. Quach proposed a two-round UC-secure OT protocol [24] under the CRS model. It achieved statistical sender security and statistical receiver security under the LWE assumption. The errors in the LWE difficult problem are not deterministic, which must be added. However, the errors in the LWR difficult problem are generated by scaling and rounding. Besides, you can solve the LWE problem with an LWR RO machine under special parameter settings.

The OT protocol is one of the most used fundamental cryptographic primitives in secure multi-party computation. The main problems of today’s oblivious transfer protocols are as follows:

• Most existing OT protocols are based on the number theory and cannot resist quantum computer attacks.

• Most existing OT protocols can only achieve full or half simulation security in the stand-alone model.

• The efficient MPC protocols with low communication costs [25] have become the research focus.

1.1. Our Contribution

Hence, a low communication OT protocol on lattice under Mod-LWR assumption was proposed in this paper. It obtained full-simulation security in the ROM. In addition, we extended it to a 1-out-of-N OT protocol with a minor tweak. Finally, we simulated this protocol and compared it with other protocols in the theoretical aspect. The simulation shows that the average communication and running time are only 2.45 kb and 0.5 ms per time, respectively. The comparison indicates that the protocol has the advantages of high efficiency and low communication.

1.2. Organization

This paper is organized as follows. Section 1 briefly introduces the technical background and Section 2 provides a detailed introduction to the notations and techniques used in the article. In Section 3, the components of the OT protocol are introduced. The 1-out-of-2 and 1-out-of-N OT protocols are presented in Section 4 and Section 5, respectively. Section 6 shows the results and the comparison with other protocols. Finally, a conclusion is given in Section 7.

2. Preliminaries

In this section, we introduce the notations and the techniques used in the paper.

2.1. Notations

Denote $Z_q$ as the ring of integers modulo an integer $q$. For any integer $z$, we define $z mod q$ as the reduction of $z$ in $\left[0,q\right)$ and define $p\mid q$ as the modulo operator on $R_q$ by modulo of all the coefficients. $R_q$ is a quotient ring $Z_q\left[X\right]/\left(X^n+1\right)$ with $n$, where n is a fixed power of 2. For a ring $R$, we define $R^{l\times k}$ as the ring of $l\times k$-matrices over $R$.

We denote $\mathcal{U}$ as the uniform distribution and denote ${\mathsf{\beta }}_{\mathsf{\mu }}$ as the centered binomial distribution with parameter $\mathsf{\mu }$, where the corresponding standard deviation $\mathsf{\sigma }=\sqrt{\mathsf{\mu }/2}$. If $\mathcal{X}$ is the probability distribution over a set $S.$ we denote $x\leftarrow \mathcal{X}$ as sampling from the set $S$ according to $\mathcal{X}$. If $\mathcal{X}$ is defined on $Z_q$, $X\leftarrow \mathcal{X}\left(R_q^{l\times k}\right)$ denotes that all coefficients are sampling from the set $R_q^{l\times k}$ according to $\mathcal{X}$.

2.2. MOD-LWR Problems

The LWR (learning with rounding) assumption was proposed by Banerjee to construct the pseudorandom function. Compared with the learning with error assumption, the errors in the LWR assumption are generated by scaling and rounding all of the coefficients from modulo $q$ to $p$ (with $p<q$). For a fixed $s\leftarrow {\beta }_{\mu }\left(R={\mathbb{Z}}_q^{l\times 1}\right)$ and a uniform random $a\leftarrow \mathcal{U}\left({\mathbb{Z}}_q^{l\times 1}\right)$, the LWR sample is as follows:

(1)$\left(a,b=\lfloor \frac{p}{q}\left(a^{T}s\right)\rceil \right)\in {\mathbb{Z}}_q^{l\times 1}\times {\mathbb{Z}}_p$

Definition 1 (the decisional LWR problem).

It is hard to distinguish LWR distribution samples from uniform distribution samples.

The Mod-LWR assumption is the variant of LWR, which replaces the ring ${\mathbb{Z}}_p$ with a quotient ring $R_p$. Then, for a fixed $s\leftarrow {\beta }_{\mu }\left(R_q^{l\times 1}\right)$ and a uniform random $a\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right),$ the Mod-LWR sample is as follows:

(2)$\left(a,b=\lfloor \frac{p}{q}\left(a^{T}s\right)\rceil \right)\in R_q^{l\times 1}\times R_p$

For fixed integers $m, k, \mathsf{\mu }, p, q$, the advantage of an adversary $\mathcal{A}$ in distinguishing from samples from a Mod-LWR distribution and that from the uniform distribution are defined as follows:

(3)$Ad{v}_{m,l,\mu ,q,p}^{Mod-LWR}\left(A\right)=\left|\begin{array}{l}\mathrm{Pr}\left(b^{\prime }=1:\begin{array}{c}A\leftarrow \mathcal{U}\left(R_q^{m\times l}\right);s\leftarrow {\beta }_{\mu }\left(R_q^{l\times 1}\right);\\ b^{\prime }=A\left(A,\lfloor \left(p/q\right)A_s\rceil \right);\end{array}\right)\\ -\mathrm{Pr}\left(b^{\prime }=1:\begin{array}{c}A\leftarrow \mathcal{U}\left(R_q^{m\times l}\right);u\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right);\\ b^{\prime }=A\left(A,u\right);\end{array}\right)\end{array}\right|$

2.3. Universally Composable Security Model

To describe and analyze the security of cryptography protocols in parallel concurrency, Canetti proposed the universally composable security framework, which specifies the existence of $\mathcal{A}$(adversary), $\mathcal{S}$(simulator), and $\mathcal{Z}$(environment) in addition to the parties of the protocol. The protocol can prove universally composable security by showing the indistinguishability between the ideal environment and real execution.

In the real execution, $\mathsf{\pi }$ denotes the running protocol, and$\mathcal{A}$denotes the adversary who corrupts the participant to attack the protocol. In the ideal environment, $\mathcal{F}$ is the corresponding function of $\mathsf{\pi }$, and $\mathcal{S}$ is the corresponding simulator of$\mathcal{A}.$ Besides, $\mathcal{Z}$ can be considered as the external environment that can communicate directly with the protocol participants, the adversary, and the simulator except for the ideal function.

Definition 2 (UC-Secure).

If, for any adversary in the real execution, there exists a corresponding simulator in the ideal environment such that the environment cannot distinguish between interacting with a protocol in the real execution or interacting with an ideal function in the ideal environment, and the formula is as follows:

(4) $IDEA{L}_{\mathcal{F},\mathcal{S},\mathit{𝓏}}\begin{array}{c}c\\ \equiv \end{array}EXE{C}_{\mathsf{\pi },\mathcal{A},\mathit{𝓏}}$

Thus, it can be proven that the protocol $\mathsf{\pi }$ can safely simulate the function $\mathcal{F}$.

3. Constitutions of Protocol

In this section, we introduce the constructions of the OT protocol in this paper.

3.1. Key Exchange Protocol

The key exchange protocol used in this paper has two integral roles:

• The parties can finally agree on a unanimous key.

• The final key is indistinguishable from random strings.

The Saber protocol [26] based on the Mod-LWR difficult problem is shown in Table 1. It is one of the candidate algorithms for the post-NIST quantum cryptography competition.

Besides the basic symbols described above, many constants are also used in this protocol that can reduce the probability of failure:$h\in R_q^{l\times 1}$is a constant polynomial vector whose coefficients are equal to$2^{{ϵ}_q-{ϵ}_p-1}$; $h_1,h_2\in R_q$ are constant polynomials; and the efficiencies of$h_1$ and$h_2$ are $2^{{ϵ}_q-{ϵ}_p-1}$ and $2^{{ϵ}_p-2}-2^{{ϵ}_p-{ϵ}_t-2}$, respectively.

Saber uses a function $bits\left(x,i,j\right)$ shown in Figure 1, which is used to obtain the continual $j$ bits of the $x$from the index $i$ to create an integer in ${\mathbb{Z}}_{2^j}.$ We can apply $bits\left(x,i,j\right)$ to a matrix or polynomial by all coefficients. Unless all of the coefficients are divisible by a higher power of 2, the final result can be considered sampled from the uniform distribution. However, in our protocol, the coefficients are generated from a binomial distribution, so the event that causes the result to deviate is that the coefficients are both 0. By analysis, the probability is negligible. Hence, Saber can meet the requirements of the OT protocol.

3.2. Hash Function

The OT protocol also needs a hash function to extend a key of length$l$ bits from a string of $n$ bits. The hash function is simulated by a random oracle machine. However, multiple UC-secure OT protocols should be able to run concurrently, so we use the local random oracle machine. The local random oracle machine can use intermediate values such as $seed\_a,A$ to distinguish different queries. Hence, the hash function is defined as follows:$Hash\left(\left(R_q^{l\times 1}\times R_q^{l\times 1}\right)\times R_t\right)\times R_q^n\to R_2^l.$ This way, the protocol parties can query different results for different instances.

3.3. Symmetric Encryption Function

A standard UC-secure OT function consists of a UC-secure ROT function and an encryption function. To ensure the confidentiality and integrity of the information during the encryption and decryption of the OT protocol, we use an authentication symmetric encryption function. The authentication encryption algorithm [27] can achieve both encryption and authentication.

Like the hash function, we use the intermediate value $\left(\left(R_q^{l\times 1}\times R_q^{l\times 1}\right)\times R_t\right)\times R_q^n$ as an additional input to the authentication symmetric encryption function to distinguish among instances. As a component of UC-secure OT protocol, the authenticated symmetric encryption function has the character of non-committing and robustness. Let $\mathcal{K}$, $\mathcal{M}$, and$\mathcal{C}$ represent the authenticated encryption’s key, plaintext, and ciphertext space, respectively.

Definition 3 (Non-committing).

We say an authentication encryption scheme (Enc, Dec) is non-committing if there exists PPT algorithm${\mathcal{S}}_1. {\mathcal{S}}_2$such that$\left(e,k\right)$and$\left(e^{\prime },k^{\prime }\right)$are distinguishable where$k\leftarrow \mathcal{K}$, $r\leftarrow \mathcal{U}\left( \right)$, $e\leftarrow E\left(k,r,M\right)$, $e^{\prime }\leftarrow {\mathcal{S}}_2\left(1^{\mathcal{K}}\right),$and$k^{\prime }\leftarrow {\mathcal{S}}_2\left(e^{\prime },r,M\right)$.

Definition 4 (Robustness).

Given additional input$r$, $S$is a set of random keys from$\mathcal{K}.$Let$V_{S,r,e}$denote a set of valid keys that satisfies$Dec\left(k,r,e\right)\ne \perp$, for the given ciphertexts$r, e.,$ i.e., We say (Enc, Dec) is robust if, for every ciphertext, the probability of$\left|V_{S,e}\right|>1$is negligible.

As the ciphertexts of common symmetric encryption algorithms do not contain any commitment to the plaintext messages or encryption process, it is impossible to determine whether the key inputted for decryption is correct. However, if the authentication code obtained by decrypting the ciphertext with the inputted key does not match the authentication sequence obtained by encrypting, the algorithm directly outputs “Failure.” and does not output the wrong decryption result. Hence, it has higher security than common symmetric encryption.

The protocol is robust because the probability of getting the same authentication code using different keys and additional inputs is negligible.

4. UC-Secure 1-out-of-2 OT Protocol

A UC-secure OT protocol based on the Mod-LWR problem can be obtained using the above technologies.

In this section, the ROT protocol is described in detail at first. Then, the OT protocol is introduced and, finally, the security of the OT protocol against static attacks is demonstrated under the random oracle model.

4.1. Random Oblivious Transfer

The ROT protocol shown in Table 2 can be divided into three phases: parameter generation, making a choice, and key derivation. After the ROT protocol, the sender can obtain two indistinguishable and uniformly distributed keys, while the receiver only knows the chosen one.

4.1.1. Correctness of the Protocol

The correctness of the protocol can be derived owing to the correctness of the Saber protocol. In other words, if two honest or semi-honest participants interact under the protocol, they can end up with a shared key $s{k}_i$ and $R$ knows nothing about $s{k}_{1-\mathsf{\sigma }}.$

4.1.2. The Privacy of the Receiver

In the protocol, the R only sends$\left(B, c\right)$ to the $\mathrm{S}$, but the $\mathrm{S}$ can get $\left(v_1,v_2,s{k}_1,s{k}_2\right)$ through $\left(B,c\right)$. Therefore, it is required that no information about $\mathsf{\sigma }$ can be obtained from $\left(B,c\right)$ and $\left(v_1,v_2,s{k}_1,s{k}_2\right)$ to ensure that the R’s privacy is not compromised. The following theorem is used to prove the privacy security of the R.

Theorem 1.

Suppose no probabilistic polynomial time adversary can guess $\sigma$ with non-negligible probability from $\left(B,c\right)$ and $\left(v_1,v_2,s{k}_1,s{k}_2\right)$ . In that case, it means that the R’s privacy is guaranteed during the execution. Then, it is necessary to prove the following three points:

• $B_{\mathsf{\sigma } =0}$ and $B_{\mathsf{\sigma } =1}$ are indistinguishable.

• $c$ and $\mathsf{\sigma }$ are independent of each other.

• $v_1$ and $v_2$ are indistinguishable.

Proof of Theorem 1.

• Assuming that the adversary corrupts $\mathrm{S}$, the corrupted sender is denoted as ${\mathrm{S}}^{*}$.

It follows that$b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$and $bits\left(u,{\in }_q,{ϵ}_p\right)$ are indistinguishable because of the Mod-LWR assumption, where $u\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$. Besides, the difference between $B_{\sigma =0}$ and $B_{\sigma =1}$ is$T$, where $T\leftarrow U\left(R_q^{l\times 1}\right)$. Hence, $B_{\sigma =0}=b^{\prime }$ and $B_{\sigma =1}=b^{\prime }+T$ are indistinguishable.

• 2.. $\mathrm{As} \mathrm{c}$sent to the sender is computed by the receiver and the sender can obtain$\mathsf{\sigma }$from$\mathrm{c}.$ Assuming the${ \mathrm{S}}^{*}$can get${\mathrm{s}}^{\prime }$ from$c$, then the${ \mathrm{S}}^{*}$ can distinguish between$B_{\sigma =0}$and$B_{\mathsf{\sigma }=1}$, and finally get$\mathsf{\sigma }$. Therefore, it is necessary to prove that$\mathrm{c}$ and$\mathsf{\sigma }$ are independent of each other by showing that the possibility of obtaining $\mathsf{\sigma }$ from $c$is negligible.

The first step is to prove indistinguishability. It can be shown by the Mod-LWR problem that$c$is indistinguishable from uniformly distributed sampling; thus,$\mathsf{\sigma }$ cannot be obtained directly from$c.$

The second step is to prove independence. A series of games shown in Table 3 show that$c$cannot help the ${\mathrm{S}}^{*}$ to distinguish $B_{\mathsf{\sigma }=0}$ from $B_{\mathsf{\sigma }=1}$. Let $X_i$ denote the event that the${ \mathrm{S}}^{*}$ guesses on$n$in the$i-th$game. Define the advantage of the adversary${ \mathrm{S}}^{*}$ to distinguish c from uniformly distributed sampling as follows:

(5)$AD{V}_{p,q,t}^{Mod-LWR}\left(\mathrm{S}*\right)=\left|Pr\left(\mathrm{S}\ast \left(a,A,T,B,c\right)=1\right)-Pr\left(\mathrm{S}\ast \left(a,A,T,B,c^{\prime }\right)=1\right)\right|$

GAME 0: In this game,$\left(a, s, A\right)$, $\left(a,s^{\prime },b^{\prime }\right),$ and $\left(A,s^{\prime },v^{\prime }\right)$ are Mod-LWR pairs, so

(6)$ADV\left({\mathrm{S}}^{*}\right)=\left|Pr\left(X_0\right)-1/2\right|$

GAME 1: In this game, suppose that${ \mathrm{the} \mathrm{D}}_1$is a probabilistic polynomial-time algorithm with input$\left(a,A\right)$. If the${ \mathrm{D}}_1$ can distinguish between Game 0 and Game 1,${\mathrm{the} \mathrm{S}}^{*}$ can use$\mathrm{the} {\mathrm{D}}_1$ to distinguish between$A=as$and$\mathcal{U}\left(R_q^{l\times 1}\right).$ Hence,

(7)$\left|Pr\left(X_0\right)-Pr\left(X_1\right)\right|\le {\mathrm{ADV}}_{p,q,t}^{\mathrm{Mod}-\mathrm{LWR} }\left({\mathrm{S}}_{{\mathrm{D}}_1}^{*}\right)$

GAME 2: In this game, suppose that t${\mathrm{he} \mathrm{D}}_2$is a probabilistic polynomial-time algorithm with input$\left(\left(a,b^{\prime }\right),\left(A,v^{\prime }\right)\right).$ If the ${\mathrm{D}}_2$ can distinguish between Game 1 and Game 2, then the${ \mathrm{S}}^{*}$ can use the ${\mathrm{D}}_2$ to distinguish between $b^{\prime }=a^T{s}^{\prime }$ and $\mathcal{U}\left(R_q^{l\times 1}\right)$, $v^{\prime }=A^T{s}^{\prime }$, and $\mathcal{U}\left(R_p\right)$. Hence,

(8)$\left|Pr\left(X_1\right)-Pr\left(X_2\right)\right|\le {\mathrm{ADV}}_{p,q,t}^{\mathrm{Mod} -\mathrm{LWR}}\left({\mathrm{S}}_{{\mathrm{D}}_2}^{*}\right)$

In Game 2, the adversary guesses the value of$n$by distinguishing between$c$and$c^{\prime }.$ However,$c$is obtained by scaling and rounding, which is uniformly distributed over$R_p$. Hence,$c$and $c^{\prime }$ are indistinguishable.

If the ${\mathrm{S}}^{*}$ can distinguish between Game 1 and Game 0 or Game 2 and Game 1, the adversary can obtain $\mathsf{\sigma } \mathrm{and} s^{\prime }$. However, the adversary cannot distinguish them because of the Mod-LWR difficult problem. Above all,$c$and$\mathsf{\sigma }$ are independent of each other.

• 3.. 1 and 3 are based on the same assumption, so contradiction can be used. If a PPT adversary can distinguish between$v_1$ and $v_2$ on input $\mathrm{B}$, he can distinguish between $B_0$ and $B_1$ to obtain $\mathsf{\sigma }.$ Assuming the adversary can solve problem 3, the adversary must be able to solve problem 1, which contradicts problem 1. Hence, $v_1$ and $v_2$ are indistinguishable. □

4.1.3. The Privacy of the Sender

Assuming the receiver only can get the chosen message after the protocol and knows nothing about other messages, the protocol can guarantee the sender’s privacy.

In the protocol, the key for encryption and decryption is generated by the hash function. If the receiver knows the sender’s private key$s$, it is possible to obtain $s{k}_{1-\mathsf{\sigma }}$ by computing ${\left(B-\left(1-\mathsf{\sigma }\right)T\right)}^{T}bits\left(s,{\in }_p,{ϵ}_p\right)+h_1$. However, getting$s$from$A$is a difficult problem. Alternatively, if the sender can find a key that satisfies $Hash\left(key\right)=Hash\left(s{k}_{1-\mathsf{\sigma }}\right)$ and $key\ne s{k}_{1-\mathsf{\sigma }}$, the sender can get $m_{1-\mathsf{\sigma }}.$ However, the random oracle machine that runs the hash function is controlled by the simulator and has collision resistance, so this case can also be ignored.

Next, a series of games shown in Table 4 are used to prove that the receiver cannot get $s{k}_{1-\mathsf{\sigma }}$, thus the protocol can guarantee the sender’s privacy. Theorem 2 can prove the security of the sender.

Theorem 2.

Owing to the Mod-LWR difficulty problem, no PPT adversary$R^{*}$can obtain both$v_1$and$v_2$.

Proof of Theorem 2.

The $R^{*}$ determines the value of $\mathrm{n}$ at the end of each game. If the advantage of the $R^{*}$ in judging the value of $\mathrm{n}$ is not negligible, the $R^{*}$ wins the game.

In Game 0, $v^{\prime }$, $\mathrm{c}$, and uniformly distributed samples are indistinguishable, so

(9)$ADV\left({\mathrm{S}}^{*}\right)=\left|Pr\left(X_0\right)-1/2\right|$

Suppose that the${ \mathrm{D}}_3$ is a probabilistic polynomial-time algorithm with input $\left(\left(a,b^{\prime }\right),\left(A,v^{\prime }\right)\right)$. When $b^{\prime }$ and $v^{\prime }$ are computed, the ${\mathrm{D}}_3$ outputs$\left(a, A, T, B, c, sk\right)$; however, when $b^{\prime }$ and $v^{\prime }$ are randomly sampled from a uniform distribution, the ${\mathrm{D}}_3$ outputs $\left(a,A,T,B,c,s{k}^{\prime }\right).$ Owing to Mod-LWR difficulties, Game 0 and Game 1 are indistinguishable.

The next step is to prove that$sk$can be regarded as a uniformly distributed sampling on the ring. In Game 1,$b^{\prime }$, $v$, and $T$ are samples from a uniform distribution, so $B$ is uniformly distributed on $R_q^{l\times 1}$ and$c$is uniformly distributed on$R_t$.

It is necessary to prove that$sk$and$s{k}^{\prime }$ are indistinguishable. Suppose there exists$\overline{b^{\prime }}$, which satisfies $\overline{b^{\prime }}=bits\left(a^T\overline{s^{\prime }}+h,{\in }_q,{\in }_p\right)$ and $\overline{b^{\prime }}\approx B-\mathsf{\sigma }T$, then, for the ${\mathrm{R}}^{*}$, ${\left(B-\mathsf{\sigma }T\right)}^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ and $\overline{b^T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ are distinguishable. Besides, we know that$c$and$\mathsf{\sigma }$are independent of each other from Theorem 1. In addition, $bits\left(v_{1-\mathsf{\sigma }}-2^{{ϵ}_p-{ϵ}_t-1}(\right.bits\left(\left(A^T\right.\right.bits\left.\left.\left.\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1\right),{\in }_p-1,{\in }_t\right)\right)+h_2,\left.{\in }_p,1\right)$ and $bits\left(v_{1-\mathsf{\sigma }}-2^{{ϵ}_p-{ϵ}_t-1}(\right.bits\left(\left(A^T\mathcal{U}\left(R_p\right)+h_1\right),{\in }_p-1\right.,\left.\left.\left.{ϵ}_t\right)\right)+h_2,{ϵ}_p,1\right)$ are distinguishable. In summary, $sk$ and$s{k}^{\prime }$ are indistinguishable for ${\mathrm{R}}^{*}$, and $Pr\left(X_1\right)=1/2$. Therefore, the protocol guarantees the sender’s privacy. □

4.2. Oblivious Transfer Protocol

A standard UC-secure OT protocol can be obtained by combining the random OT mentioned in Section 4.1 and the authentication symmetric encryption algorithm mentioned in Section 3.3. After receiving the key, the S encrypts two messages $M_1$ and $M_2$ with two keys $C_1$and $C_2$, respectively. Then,$\mathrm{the} S$sends them to the $R,$ and$\mathrm{the} R$decrypts the chosen ciphertext.

Theorem 3 demonstrates that the OT protocol can be simulated as an ideal function under the random oracle machine model and can resist static adversary attacks.

Theorem 3.

If the following assumptions hold, then the OT protocol can be simulated as ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}.$

• The adversary only performs static attacks.

• The random oracle machine simulates the hash function.

Proof of Theorem 3.

The static adversary attacks can be divided into four types as follows:

• Neither the $\mathrm{S}$ nor the $R$ is corrupted.

• Only the $\mathrm{S}$ is corrupted.

• Only the $R$ is corrupted.

• Both the $R$ and the $\mathrm{S}$ are corrupted.

Let $\mathcal{A}$ denote the adversary interacting with the honest participant in the real environment. For any $\mathcal{A}$, a simulator $\mathcal{S}$ can be constructed in the ideal environment, which runs the ideal function ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}$ to simulate the interaction with the honest party. It is impossible for the $\mathcal{Z}$ to distinguish between the real execution and the ideal environment. All corruption cases are shown as follows.

• When neither the $S$ nor the $R$ is corrupted, the adversary can attack the procession of data transmission. To demonstrate the universally composable security of the protocol, we build a simulator $\mathcal{S}$. The simulation for the ideal environment is built as follows:

• The $\mathcal{S}$ simulates the $\mathrm{S}$for parameter selection. The $\mathcal{S}$ chooses $see{d}_a\leftarrow \mathcal{U}\left({\{0,1\}}^{256}\right)$, $s\leftarrow {\beta }_{\mu }\left(R_q{}^{l\times 1}\right), \mathrm{and}$ $T\leftarrow \mathcal{U}\left(R_q{}^{l\times 1}\right)$; generates the key $a\leftarrow gen\left(see{d}_a\right)\in R_q^{\mid \times 1};$and then computes$A=bits\left(as+h,{\in }_q,{\in }_p\right)$.

• The $\mathcal{S}$simulates the$R$to make a choice. The$\mathcal{S}$chooses$s\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ and calculates$b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$, $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$,$and c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$.

• The $\mathcal{S}$ generates$\left(C_1,C_2\right)$ by random sampling from the ciphertext space.

• The $\mathcal{S}$ outputs $\left(see{d}_a,A,T\right),$ $\left(B,c\right)$, and $\left(C_1,C_2\right).$

From Theorems 1 and 2, we know that the protocol can guarantee the privacy of the sender$\mathrm{S}$ and the receiver $R,$ so the $\mathcal{Z}$ cannot distinguish whether $\left(see{d}_a,A,T\right)$ and$\left(B, c\right)$are in the real execution or ideal environment. The $\mathcal{Z}$ can also not distinguish between $\left(C_1,C_2\right)$ in the real execution and the ideal environment owing to the authentication symmetric encryption algorithm. Hence, the ideal environment and the real execution are indistinguishable from the perspective of the $\mathcal{Z}$.

• 2.. When the adversary $\mathcal{A}$ corrupts the $\mathrm{S}$, denote$\mathrm{S}$as${ \mathrm{S}}^{*}.$ We build a simulator$\mathcal{S}$to prove that the ideal environment and the real execution are indistinguishable. First, the $\mathcal{S}$ interacts with the ${\mathrm{S}}^{*}$ to get the real input $\left(M_1,M_2\right),$ then plays the role of the $\mathrm{S}$ to interact with the ideal function ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}$, which finally enables the $R$to get $M_{\mathsf{\sigma }}.$ As the $\mathcal{S}$ responds to ${{\mathrm{S}}^{*}}^{\prime }s$ queries using a random oracle machine, it is possible to decrypt the ciphertext using query records and get the sender’s real input. The $\mathcal{S}$ is constructed as follows:

• The $\mathcal{S}$ uses the random oracle machine to answer queries randomly before interacting with the ${\mathrm{S}}^{*}$.

• After receiving $\left(see{d}_a,T,A\right)$ from the ${\mathrm{S}}^{*}$, the $\mathcal{S}$ generates the parameters by seed; chooses$s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$; calculates $b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$, $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1, \mathrm{and}$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$; and sends$\left(b^{\prime },c\right)$ to the ${\mathrm{S}}^{*}$. From this moment on, the $\mathcal{S}$records all queries of the form ${Hash}_{\left(\left(A,T\right){,b}^{\prime },c\right)}$ from the ${\mathrm{S}}^{*}$

• After receiving $\left(C_1,C_2\right)$ from the ${\mathrm{S}}^{*}$, the $\mathcal{S}$ computes $Dec\left(C_i,Has{h}_{record }\right)$ for each$i,$ where$Has{h}_{record }$denotes all the queries records of the ${\mathrm{S}}^{*}$, and records the$M$that can be decrypted successfully from $C$.

• The $\mathrm{S}$ sends$\left(M_1,M_2\right)$ to ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}.$

The next step is to demonstrate the indistinguishability under the$\mathcal{Z}$‘s view. The $\mathcal{Z} \mathrm{only}$can use$\left(B, c\right)$and$M_{\mathsf{\sigma }}$to distinguish the real execution and ideal environment.

From Theorem 1, the protocol can guarantee the receiver’s privacy so that$the \left(B,c\right)$ generated by the $\mathcal{S}$ and$the \left(B^{\prime }, c^{\prime }\right)$caused by the honest $R$ in the protocol are indistinguishable.

In addition, if the adversary can find an $x$ that satisfies $Hash\left(x\right)\ne s{k}_{\mathsf{\sigma }}$ and $Dec\left(C_{\mathsf{\sigma }},Hash\left(x\right)\right)=M$, the $x$ will help$R$ output a different $M$. However, owing to the robustness of the authentication encryption algorithm, the probability is negligible

• 3.. When only the adversary$\mathcal{A}$corrupts the R, denote R as${ R}^{*}$. We build a simulator$\mathcal{S}$ to prove the indistinguishability. The $\mathcal{S}$ needs to play the$\mathrm{S}$‘s role to interact with the $R^{*}$to obtain the $\mathsf{\sigma }$, then uses $\mathsf{\sigma }$ to interact with ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}$to obtain$M_{\mathsf{\sigma }}$ to make the R decrypt correctly, and finally generates $\left(C_1,C_2\right)$based on $M_{\mathsf{\sigma }}$. The $\mathcal{S}$ can obtain the value of$\mathsf{\sigma }$ by the queries records because the $\mathcal{S}$ runs the hash function and the protocol guarantees the sender’s privacy. The $\mathcal{S}$ is constructed as follows:

• The $\mathcal{S}$ chooses $see{d}_a\leftarrow \mathcal{U}\left({\{0,1\}}^{256}\right)$, $s\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right),$ and $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$; then generates key $a\leftarrow gen\left(see{d}_a\right)$; and finally computes$A=bits\left(as+h,{\in }_q,{\in }_p\right)$.

• $\mathrm{The} \mathcal{S}$ uses the random oracle machine to answer the query and records queries of the form$Has{h}_{\left(\left(A,T\right),.,\right)}$ before interacting with $R^{*}$.

• $\mathrm{The} \mathcal{S}$ looks for records of the form $Has{h}_{\left(\left(A,T\right),B,c\right)}$ and judges if the output of the function is equal to$sk$after receiving$\left(B, c\right)$from the${ R}^{*}.$ If equal,$\mathrm{the} \mathcal{S}$ records the value of$i$as$\mathsf{\sigma }$ and interacts with the function${\mathcal{F}}_{\mathcal{O}\mathcal{T}}$ to obtain$M_{\mathsf{\sigma }}$; otherwise, the $\mathcal{S}$fails and sets the value of$\mathsf{\sigma }$ to null.

• The $\mathcal{S}$starts to generate$\left(C_1,C_2\right)$ after interacting with the $R^{*}.$ If the value of$\mathsf{\sigma }$ is null, the$\mathcal{S}$ randomly samples $\left(s{k}_1,s{k}_2\right)$ in the ciphertext space and uses it as $\left(C_1,C_2\right)$; otherwise, the$\mathcal{S}$ sets the value of $s{k}_{\mathsf{\sigma }}$ to the query result and computes$C_{\mathsf{\sigma }}=Enc\left(s{k}_{\mathsf{\sigma }},M_{\mathsf{\sigma }}\right).$ Finally, the$\mathcal{S}$ randomly generates$C_{1-\mathsf{\sigma }}$ and sends $\left(C_1,C_2\right)$ to the $R^{*}$.

• The $\mathcal{S}$ continues to answer queries at random after outputting $\left(C_1,C_2\right)$. If the $R^{*}$ continues with an inquiry of the form$KD{F}_{\left(\left(A,T\right),B,c\right)}$, the answer is as follows. If the value of$\mathsf{\sigma }$ is not null, the $\mathcal{S}$ outputs that the protocol has ended. Otherwise, the $\mathcal{S}$ gets the value of$\mathsf{\sigma }$ like the above method. Finally, the $\mathcal{S}$ encrypts the $M_{\mathsf{\sigma }}$ using the generated key and sends $\left(C_1,C_2\right)$ to the $R^{*}$.

The next step is to prove that the $\mathrm{Z}$ cannot distinguish between the ideal environments and the real execution. It is shown that the$\mathcal{Z}$ only can use$\left(seed, A, T\right)$and$\left(C_1,C_2\right)$to distinguish between the real execution and the simulation.

First, $seed, A, T$are sampled from the distribution. According to Theorem 2, the protocol can guarantee the sender’s privacy, so the $\left(C_1,C_2\right)$ generated during the real execution of the protocol is indistinguishable from the random string. From the construction of the simulator, $C_{1-\mathsf{\sigma }}$ in the simulation is an arbitrary string and $C_{\mathsf{\sigma }}$ is the real ciphertext, which is indistinguishable from a random string. Finally, if the protocol is stopped midway, the $R^{*}$ cannot get $\left(C_1,C_2\right)$, and additional information can be obtained only by asking the random oracle machine. However, getting the value of $\mathrm{c}$ from $\mathrm{v}$ is impossible because of the Mod-LWR difficult problem. In summary, the$\mathcal{Z}$ cannot distinguish between the real execution and ideal environment.

• 4.. When both the $\mathrm{S}$ and the $R$ are corrupted, the simulator directly copies the adversary’s input as its input and outputs the adversary’s output to achieve indistinguishability in $\mathcal{Z}$ view. □

5. UC-Secure 1-out-of-N OT Protocol

In this section, we expand the 1-out-of-2 OT protocol to a 1-out-of-N protocol with a minor tweak. The 1-out-of-N OT protocol is shown in the Table 5. In the 1-out-of-N OT ideal function, the S inputs $\left(M_1,\dots ,M_n\right)$, where$n>2,$ then the R inputs choice bit $\mathsf{\sigma }\in \left[1,n\right]$. Finally, the R outputs$M_{\mathsf{\sigma }}$.

Proof of Security

• The first step is to prove that the protocol can guarantee the parties’ privacy. From Theorem 1, it is clear that$B=b^{\prime }$ and$B=b^{\prime }+T_{\mathsf{\sigma }-1}$ are indistinguishable, so the receiver’s privacy is secure. From Theorem 2, the receiver only gets the information he chooses, so the sender’s privacy is secure.

• The next step is to prove that the protocol can be simulated as ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}$. When the $\mathrm{S}$ is corrupted, the $\mathcal{S}$ records the random oracle machine queries in the specific format. Then, the$\mathcal{S}$ uses these records to obtain the real input from the sender and inputs it into the ideal function. When the $R$ is corrupted, the $\mathcal{S}$ receives the real input$\mathsf{\sigma }$ from the receiver through the records of the random oracle machine. Then, the $\mathcal{S}$ inputs it to the ideal function. Finally, in the same way as Theorem 3, the real execution and the ideal environment from the perspective of $\mathcal{Z}$ are indistinguishable. Hence, the OT protocol can be simulated as ${\mathcal{F}}_{\mathcal{O}\mathcal{T}}.$

6. Discussion

We modified the codes on SABER’s GitHub to simulate the protocol. The CPU is i7-9700f and the memory size is 16 GB. The simulation was repeated 100,000 times and the probability of success was 100%. The average communication cost is 24,576 bits and the average running time is 0.54509 ms. Therefore, the protocol can run efficiently with low communication costs.

Considering that none of the currently available lattice UC-safe OT protocols are based on the Mod-LWR difficulty problem, this protocol is compared to other OT protocols based on the other lattice difficulty problems such as LWE, RLWE, and so on.

The metrics used to judge the efficiency of UC-secure OT protocols are the number of rounds, communication cost, and computation cost. For the lattice OT protocols, the communication cost can be calculated from the size of intermediate amount and the computation cost can be calculated by operations on the lattice, such as multiplication and addition. Comparing the OT protocol proposed with other state-of-the-art protocols in the theoretical aspect, the results are shown in Table 6.

The OT protocol proposed by Peikert is under the common reference string (CRS) model, which needs to interact with the ideal function to obtain the CRS before starting to run. The OT protocol proposed by Quach is also under the CRS model, which uses dual-mode encryption to achieve statistical receiver security. The OT protocol proposed by Liu needs rec(.) and dbl(.) operations, which leads to additional computational costs. Compared with the OT protocol proposed in [16,24], the protocol has advantages for communication and computational costs. Compared with the OT proposed in [22], the protocol reduces the communication cost by reducing the scale and size of the polynomial. In summary, the protocol in this paper has the advantage of high efficiency and low communication.

7. Conclusions

This paper constructs a UC-secure OT protocol on lattice based on the Mod-LWR difficult problem. The protocol obtains universally composable security under the random oracle machine model and can resist static adversary attacks. Besides, the comparison with other UC-secure OT protocols shows that the protocol has constant interaction rounds and low communication costs.

Depending on the attack strategy of the adversary, it can be classified as a static adversary, dynamic adversary, or proactive adversary. Therefore, the following research focuses on an OT protocol that can resist other types of attacks.

Author Contributions

Conceptualization, J.S.; formal analysis and investigation, J.S., D.W., Z.Z., H.D. and Z.L. (Zichen Li); writing—original draft preparation, J.S.; writing—review and editing, D.W.; visualization, J.S.; supervision, D.W.; Z.Z., Z.L. (Zhenzhen Li), H.D. and Z.L. (Zichen Li). All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Data available on request from the authors.

Conflicts of Interest

The authors declare no conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figure and Tables

Figure 1. The schematic of [Forumla omitted. See PDF.] function.

Table 1

Saber key exchange protocol.

Alice		Bob
$see{d}_a\leftarrow \mathcal{U}\left({\{0,1\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)\in R_q^{l\times l}$ $s\leftarrow {\beta }_{\mu }\left(R_q^{l\times 1}\right)$ $A=bits\left(\mathrm{as}+h,{\in }_q,{\in }_p\right)\leftarrow R_q^{l\times 1}$	$\stackrel{see{d}_a,A}{\to }$
	$\stackrel{b,c}{\leftarrow }$	$a\leftarrow gen\left(see{d}_a\right)\in R_q{}^{l\times l}$ $s^{\prime }\leftarrow {\beta }_{\mu }\left(R_q^{l\times 1}\right)$ $b=bits\left(A^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)\in R_q^{l\times 1}$ $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1\in R_p$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)\in R_t$
$v=b^T bit \left(s,{\in }_p,{ϵ}_p\right)+h_1\in R_p$ $k=bits\left(v-2^{{ϵ}_p-{ϵ}_t-1}c+h_2,{\in }_p,1\right)$		$k^{\prime }=bits\left(v^{\prime },{\in }_p,1\right)$

Table 2

Random oblivious transfer protocol.

Alice		Bob
Parameter Generation:$see{d}_a\leftarrow (U\left({\left\{0,1\right\}}^{256}\right)$$a\leftarrow gen\left(see{d}_a\right)$   $s\leftarrow {\beta }_{\mu }\left(R_q^{l\times 1}\right)$$T\leftarrow U\left(R_q^{l\times 1}\right)$ $A=bits\left(as+h,{\in }_q,{\in }_p\right)\leftarrow R_q^{l\times 1}$	$\stackrel{see{d}_a,A,T}{\to }$	$a\leftarrow gen\left(see{d}_a\right)$   $s^{\prime }\leftarrow {\beta }_{\mu }\left(R_q^{l\times 1}\right)$ $b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$$v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$   $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$
Make a choice:	$\stackrel{B,c}{\leftarrow }$	$if\left(\sigma =0\right) B=b^{\prime }$ $if\left(\sigma =1\right) B=b^{\prime }+T$
Key derivation: $v_1=B^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ $v_2={\left(B-T\right)}^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ $s{k}_1=bits\left(v_1-2^{{\in }_p-{\in }_t-1}c+h_2,{\in }_p,1\right)$ $s{k}_2=bits\left(v_2-2^{{\in }_p-{\in }_t-1}c+h_2,{\in }_p,1\right)$		$sk=Hash\left(bits\left(v^{\prime },{\in }_p,1\right)\right)$

Table 3

The games mentioned in Proof of Theorem 1.

Game0:	Game1:	Game2:	${\mathit{D}}_1\left(\mathit{a},\mathit{A}\right):$	${\mathit{D}}_2\left(\left(\mathit{a},{\mathit{b}}^{\prime }\right),\left(\mathit{A},{\mathit{v}}^{\prime }\right)\right):$
$see{d}_a\leftarrow \mathcal{U}\left({\left\{0,1\right\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)$ $s,s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $A=bits\left(as+h,{\in }_q,{\in }_p\right)$ $b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$ $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $c^{\prime }\leftarrow \mathcal{U}\left(R_t\right)$ $n\leftarrow \mathcal{U}\left(\left\{0,1\right\}\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c\right)$ $else$ $return\left(a,A,T,B,c^{\prime }\right)$	$see{d}_a\leftarrow \mathcal{U}\left({\left\{0,1\right\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)$ $s,s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$ $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $c^{\prime }\leftarrow \mathcal{U}\left(R_t\right)$ $n\leftarrow \mathcal{U}\left(\left\{0,1\right\}\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c\right)$ $else$ $return\left(a,A,T,B,c^{\prime }\right)$	$see{d}_a\leftarrow \mathcal{U}\left({\left\{0,1\right\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)$ $s,s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $A\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $c^{\prime }\leftarrow \mathcal{U}\left(R_t\right)$ $n\leftarrow \mathcal{U}\left(\left\{0,1\right\}\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c\right)$ $else$ $return\left(a,A,T,B,c^{\prime }\right)$	$s,s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$ $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $c^{\prime }\leftarrow \mathcal{U}\left(R_t\right)$ $n\leftarrow \mathcal{U}\left(\left\{0,1\right\}\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c\right)$ $else$ $return\left(a,A,T,B,c^{\prime }\right)$	$c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $c^{\prime }=bits\left(\mathcal{U}\left(R_p\right),{\in }_p-1,{\in }_t\right)$ $n\leftarrow \mathcal{U}\left(\left\{0,1\right\}\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c\right)$ $else$ $return\left(a,A,T,B,c^{\prime }\right)$

Table 4

The games mentioned in Proof of Theorem 2.

Game 0:	Game 1:	${\mathit{D}}_3:$
$see{d}_a\leftarrow \mathcal{U}\left({\left\{0,1\right\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)$ $s,s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $A=bits\left(as+h,{\in }_q,{\in }_p\right)$ $b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$ $v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $v_{1-\mathsf{\sigma }}={\left(B-\mathsf{\sigma }T\right)}^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ $sk=bits\left(v_{1-\mathsf{\sigma }}-2^{{\in }_p-{\in }_t-1}c+h_2,{\in }_p,1\right)$ $s{k}^{\prime }\leftarrow \mathcal{U}\left(R\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c,sk\right)$ $else$ $return\left(a,A,T,B,c,s{k}^{\prime }\right)$	$see{d}_a\leftarrow \mathcal{U}\left({\left\{0,1\right\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)$ $s,s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right)$ $A=bits\left(as+h,{\in }_q,{\in }_p\right)$ $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $v_{1-\mathsf{\sigma }}={\left(B-\mathsf{\sigma }T\right)}^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ $sk=bits\left(v_{1-\mathsf{\sigma }}-2^{{\in }_p-{\in }_t-1}c+h_2,{\in }_p,1\right)$ $s{k}^{\prime }\leftarrow \mathcal{U}\left(R\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c,sk\right)$ $else$ $return\left(a,A,T,B,c,s{k}^{\prime }\right)$	$c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$ $B=b^{\prime }+\mathsf{\sigma }T$ $v_{1-\mathsf{\sigma }}={\left(B-\mathsf{\sigma }T\right)}^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ $sk=bits\left(v_{1-\mathsf{\sigma }}-2^{{\in }_p-{\in }_t-1}c+h_2,{\in }_p,1\right)$ $s{k}^{\prime }\leftarrow \mathcal{U}\left(R\right)$ $If\left(n=0\right),then$ $return\left(a,A,T,B,c,sk\right)$ $else$ $return\left(a,A,T,B,c,s{k}^{\prime }\right)$

Table 5

UC-secure 1-out-of-N OT protocol.

Alice		Bob
Parameter Generation: $see{d}_a\leftarrow \mathcal{U}\left({\left\{0,1\right\}}^{256}\right)$ $a\leftarrow gen\left(see{d}_a\right)$ $s\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$ $T_0={\left\{0\right\}}^l$ $T_i\leftarrow \mathcal{U}\left(R_q^{l\times 1}\right),i\in \left[1,n-1\right]$ $A=bits\left(as+h,{\in }_q,{\in }_p\right)$	$\stackrel{see{d}_a,A,T}{\to }$	$a\leftarrow gen\left(see{d}_a\right)$$s^{\prime }\leftarrow {\mathsf{\beta }}_{\mathsf{\mu }}\left(R_q^{l\times 1}\right)$$b^{\prime }=bits\left(a^T{s}^{\prime }+h,{\in }_q,{\in }_p\right)$$v^{\prime }=A^{T}bits\left(s^{\prime },{\in }_p,{\in }_p\right)+h_1$    $c=bits\left(v^{\prime },{\in }_p-1,{\in }_t\right)$
Make a choice:	$\stackrel{B,c}{\leftarrow }$	$B=b^{\prime }+T_{\mathsf{\sigma }-1},\mathsf{\sigma }\in \left[1,n\right]$
Key derivation: $For every i\in \left[1,n\right]:$ $v_i={\left(B-T_i\right)}^{T}bits\left(s,{\in }_p,{\in }_p\right)+h_1$ $s{k}_i=bits\left(v_i-2^{{\in }_p-{\in }_t-1}c+h_2,{\in }_p,1\right)$		$sk=Hash\left(bits\left(v^{\prime },{\in }_p,1\right)\right)$
Encryption: $C_i=Enc\left(Hash\left(s{k}_i\right),M_i\right),i\in \left[1,n\right]$	$\stackrel{C_1,C_2}{\to }$	Decryption: $M_{\mathsf{\sigma }}=Dec\left(C_{\mathsf{\sigma }},sk\right)$

Table 6

Comparison with other OT protocols.

Scheme	Assumption	Model	Security	Strategy	Rounding	Communication Cost	Computational Cost
Peikert [16]	LWE	CRS	UC	Static	At least 2	$O\left(n^2\lg n\right)\left(Z_q\right)$	$O\left(n^3\lg n\right)\left(\times \right)$ $O\left(n^3\lg n\right)\left(+\right)$
Liu [23]	RLWE	ROM	UC	Static	3	$O\left(n^2\right)\left(Z_q\right)$ $O\left(n^2\right)\left(Z_2\right)$	$O\left(n^3\right)\left(\times \right)$ $O\left(n^3\lg n\right)\left(+\right)$
Quach [24]	LWE	CRS	UC	Static	2	$O\left(n^2\lg n\right)\left(Z_q\right)$	$O\left(n^3\lg n\right)\left(\times \right)$ $O\left(n^3\lg n\right)\left(+\right)$
Our	Mod-LWR	ROM	UC	Static	3	$O\left(n\right)\left(R_p\right)$ $O\left(n^2\right)\left(R_t\right)$	$O\left(n^3\right)\left(\times \right)$ $O\left(n^3\lg n\right)\left(+\right)$

References

1. Huang, Z.; Lu, W.; Hong, C.; Ding, J. Cheetah: Lean and fast secure two-party deep neural network inference. Cryptol. ePrint Arch.; 2022; 207, pp. 1-20.

2. Yang, J.; Wang, T.; Li, N.; Cheng, X.; Su, S. Answering Multi-Dimensional Range Queries under Local Differential Privacy. arXiv; 2020; arXiv: 2009.06538[DOI: https://dx.doi.org/10.14778/3430915.3430927]

3. Hong, C.; Katz, J.; Kolesnikov, V.; Lu, W.-J.; Wang, X. Covert Security with Public Verifiability: Faster, Leaner, and Simpler. Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques; Darmstadt, Germany, 19–23 May 2019; pp. 97-121. [DOI: https://dx.doi.org/10.1007/978-3-030-17659-4_4]

4. Pan, J.-S.; Liu, T.; Yan, B.; Yang, H.-M.; Chu, S.-C. Using color QR codes for QR code secret sharing. Multimedia Tools Appl.; 2022; 81, pp. 15545-15563. [DOI: https://dx.doi.org/10.1007/s11042-022-12423-z]

5. Wang, X.; Luo, T.; Li, J. An Efficient Fully Homomorphic Encryption Scheme for Private Information Retrieval in the Cloud. Int. J. Pattern Recognit. Artif. Intell.; 2019; 34, 2055008. [DOI: https://dx.doi.org/10.1142/S0218001420550083]

6. Rackoff, C.; Simon, D.R. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. Advances in Cryptology—CRYPTO ’91; Springer: Berlin/Heidelberg, Germany, 1992; pp. 433-444. [DOI: https://dx.doi.org/10.1007/3-540-46766-1_35]

7. Chailloux, A.; Kerenidis, I. Optimal Bounds for Quantum Bit Commitment. Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science; Washington, DC, USA, 22–25 October 2011; pp. 354-362. [DOI: https://dx.doi.org/10.1109/FOCS.2011.42B]

8. Pinkas, B.; Schneider, T.; Zohner, M.; Segev, G. Phasing: Private Set Intersection using Permutation-based Hashing. Proceedings of the 24th USENIX Security Symposium; Austin, TX, USA, 10–12 August 2012; 17.

9. Weiguo, Z.; Man, S.U.N.; Zhenhua, C.; Wei, C. Secure Multi-party Computation of Spatial Relationship and Its Application. JEIT; 2016; 38, pp. 2294-2300. [DOI: https://dx.doi.org/10.11999/JEIT160102]

10. Rabin, M.O. How to Exchange Secrets with Oblivious Transfer. IACR Cryptol. ePrint Arch.; 2005; 187.Available online: https://www.semanticscholar.org/paper/How-To-Exchange-Secrets-with-Oblivious-Transfer-Rabin/772cdcc8a67cc878b39409230cbf2488a1117e62 (accessed on 15 November 2022).

11. Even, S.; Goldreich, O.; Lempel, A. A Randomized Protocol for Signing Contracts. Commun. ACM; 1983; 28, pp. 637-647. [DOI: https://dx.doi.org/10.1145/3812.3818]

12. Brassard, G.; Crepeau, C.; Robert, J.-M. All-or-nothing disclosure of secrets. Advances in Cryptology—CRYPTO’ 86; Springer: Berlin/Heidelberg, Germany, 1987; pp. 234-238.

13. Tzeng, W.-G. Efficient 1-Out-n Oblivious Transfer Schemes. Public Key Cryptography; Springer: Berlin/Heidelberg, Germany, 2002; pp. 159-171. [DOI: https://dx.doi.org/10.1007/3-540-45664-3_11]

14. Naor, M.; Pinkas, B. Efficient Oblivious Transfer Protocols. 2001; Available online: https://xueshu.baidu.com/usercenter/paper/show?paperid=be727901097ac71cc01239a43ca4e160 (accessed on 5 August 2022).

15. Damgård, I.; Nielsen, J.B.; Orlandi, C. Essentially Optimal Universally Composable Oblivious Transfer. Information Security and Cryptology—ICISC 2008; Springer: Berlin/Heidelberg, Germany, 2009; pp. 318-335.

16. Lindell, A.Y. Efficient fully-simulatable oblivious transfer. Topics in Cryptology—CT-RSA 2008; Springer: Berlin/Heidelberg, Germany, 2008; pp. 52-70.

17. Canetti, R. Universally Composable Security: A New Paradigm for Cryptographic Protocols. Cryptology ePrint Archive. 2000; Available online: https://eprint.iacr.org/2000/067 (accessed on 5 August 2022).

18. Peikert, C.; Vaikuntanathan, V.; Waters, B. A Framework for Efficient and Composable Oblivious Transfer. Advances in Cryptology—CRYPTO 2008; Springer: Berlin/Heidelberg, Germany, 2008; pp. 554-571. [DOI: https://dx.doi.org/10.1007/978-3-540-85174-5_31]

19. Lai, Y.-F.; Galbraith, S.D.; de Saint Guilhem, C.D. Compact, efficient and UC-Secure isogeny-based oblivious transfer. Advances in Cryptology—EUROCRYPT 2021; Springer: Cham, Switzerland, 2021; pp. 213-241.

20. Branco, P.; Ding, J.; Goulão, M.; Mateus, P. A framework for universally composable oblivious transfer from one-round key-exchange. Cryptography and Coding; Springer: Cham, Switzerland, 2019; pp. 78-101.

21. Chou, T.; Orlandi, C. The Simplest Protocol for Oblivious Transfer. Progress in Cryptology—LATINCRYPT 2015; Lauter, K.; Rodríguez-Henríquez, F. Springer: Cham, Switzerland, 2015; Volume 9230, pp. 40-58. [DOI: https://dx.doi.org/10.1007/978-3-319-22174-8_3]

22. Liu, M.; Hu, Y. Universally composable oblivious transfer from ideal lattice. Front. Comput. Sci.; 2018; 13, pp. 879-906. [DOI: https://dx.doi.org/10.1007/s11704-018-6507-4]

23. Xing, Y.; Li, S. An Efficient Implementation of the NewHope Key Exchange on FPGAs. IEEE Trans. Circuits Syst. I: Regul. Pap.; 2020; 67, pp. 866-878. [DOI: https://dx.doi.org/10.1109/TCSI.2019.2956651]

24. Quach, W. UC-Secure OT from LWE, Revisited. Proceedings of the SCN 2020: Security and Cryptography for Networks; Amalfi, Italy, 14–16 September 2020; pp. 192-211. [DOI: https://dx.doi.org/10.1007/978-3-030-57990-6_10]

25. Couteau, G.; Rindal, P.; Raghuraman, S. Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes. Advances in Cryptology—CRYPTO 2021; Springer: Berlin/Heidelberg, Germany, 2021; pp. 502-534. [DOI: https://dx.doi.org/10.1007/978-3-030-84252-9_17]

26. D’Anvers, J.-P.; Karmakar, A.; Roy, S.S.; Vercauteren, F. Saber: Modulo-LWR based key exchange, CPA-Secure encryption and CCA-Secure KEM. Progress in Cryptology—AFRICACRYPT 2018; Springer: Cham, Switzerland, 2018; pp. 282-305.

27. Wu, H.; Preneel, B. AEGIS: A fast authenticated encryption algorithm. Selected Areas in Cryptography—SAC 2013; Springer: Berlin/Heidelberg, Germany, 2014; pp. 185-201.