An MLWE-Based Cut-and-Choose Oblivious Transfer Protocol

Abstract

The existing lattice-based cut-and-choose oblivious transfer protocol is constructed based on the learning-with-errors (LWE) problem, which generally has the problem of inefficiency. An efficient cut-and-choose oblivious transfer protocol is proposed based on the difficult module-learning-with-errors (MLWE) problem. Compression and decompression techniques are introduced in the LWE-based dual-mode encryption system to improve it to an MLWE-based dual-mode encryption framework, which is applied to the protocol as an intermediate scheme. Subsequently, the security and efficiency of the protocol are analysed, and the security of the protocol can be reduced to the shortest independent vector problem (SIVP) on the lattice, which is resistant to quantum attacks. Since the whole protocol relies on the polynomial ring of elements to perform operations, the efficiency of polynomial modulo multiplication can be improved by using fast Fourier transform (FFT). Finally, this paper compares the protocol with an LWE-based protocol in terms of computational and communication complexities. The analysis results show that the protocol reduces the computation and communication overheads by at least a factor of n while maintaining the optimal number of communication rounds under malicious adversary attacks.

1. Introduction

In today’s digital and Internet era, with the rapid development of big data technology, the demand for collaborative computing by individuals or organisations using their respective private data is rapidly increasing. However, due to the sensitivity and privacy of data, many data holders are reluctant to share their private information directly with other participants. Therefore, the design of protocols that enable secure joint computation by multiple parties is an urgent problem. Further in-depth study of oblivious transfer [1] (OT), a core building block of secure computing protocols, will play an important role in data security and privacy protection in the digital era.

OT, as an important and fundamental cryptographic primitive, was first proposed by Rabin [2] in 1981. In oblivious transfer, the sender inputs two secret values $(m_0,m_1)$, and the receiver inputs a choice bit ($\delta \in \{0,1\}$). After both parties run the OT protocol, the receiver obtains the value ($m_{\delta }$) corresponding to his choice bit ($\delta$) and knows nothing about $m_2$; the sender obtains nothing and knows nothing about the receiver’s choice bit ($\delta$). A brief model of the OT protocol is shown in Figure 1. The OT protocol has been used as a high-frequency building block in secure multi-party computation (SMPC) protocols [3,4,5,6] since it was proposed. The main goal of SMPC is to enable two or more participants to jointly compute an agreed-upon function based on their own private inputs and, ultimately, to obtain their respective computation results without compromising privacy.

The efficiency and security of the OT protocol affect both the utility and security of the external high-level protocols that call the OT protocol. In order to make their outer layer protocols more efficient or secure, researchers have started to focus on designing more functional OT variants [7,8,9,10,11]. The cut-and-choose method, as a tool in secure two-party computation, can be used to normalise and constrain parties that honestly execute protocols in garbled circuits and can prevent circuit constructors from cheating by constructing faulty circuits. This technique can reduce the use of zero-knowledge proof techniques and can thus increase the efficiency of secure computation protocols. The literature [3,12] states that separating the cut-and-choose technique from the OT protocol may lead to selective failure attacks. Notably, in 2011, Lindell et al. [3] combined cut-and-choose technology with OT and first proposed a new primitive: namely, cut-and-choose oblivious transfer (CCOT). Subsequently, CCOT was applied to Yao’s secure two-party computation protocol [13] based on garbled circuits to complete key transfer and efficiently solved the selective failure attacks pointed out by Kiraz et al. [14]. In 2015, Zhao et al. [15] further extended the idea of CCOT by proposing cut-and-choose bilateral oblivious transfer (CCBOT), which is capable of transmitting the garbled keys of all participants at once in the key transmission phase. In 2016, Wei et al. [16] extended the CCBOT protocol again based on the DDH assumption, which is more efficient than the previous protocol. Subsequently, in 2022, Wang et al. [17] proposed a secure two-party computation protocol framework in [16] by integrating Yao’s protocol [13]. This protocol only requires two rounds of contact to complete key transfer, which leads to improvements in protocol efficiency.

The security of most previous OT protocols and their variants is based on classical number-theory problem assumptions, such as large integer decomposition and discrete logarithm problems. With quantum algorithms such as those proposed by Shor [18] and Grover [19] pointing out that the above classical number-theory problems can be solved efficiently in polynomial time, cryptographic regimes constructed based on these problems are no longer secure against the threat of future quantum computers. OT protocols constructed based on the special linear structure of the lattice have attracted the attention of researchers because they are not only resistant to quantum attacks and have worst-case security but also are efficient in execution.

Our Contributions

With the advent of the post-quantum era, in this paper, we consider the construction of an efficient CCOT protocol based on the hard MLWE problem assumption that can be applied to two-party computation protocols in the future to resist the threat of quantum attacks while reducing the computation and communication overheads of the protocols. The protocol uses the MLWE-based dual-mode encryption framework as an intermediate scheme to meet the security requirements and introduces compression and decompression techniques to reduce the size of the key and ciphertext to further optimise the communication overhead. The main contributions of this paper are summarized as follows:

• Based on the LWE-based dual-mode encryption system, the MLWE-based dual-mode encryption framework is constructed based on the difficult MLWE problem, and compression and decompression functions are introduced to further reduce the size of the public key and ciphertext. The MLWE-based CCOT protocol is proposed by using this dual-mode encryption framework as an intermediate scheme. Compared with the CCOT protocol based on classical number-theory assumptions, this protocol is not only secure under malicious adversary attacks but is also resistant to quantum attacks.
• The correctness of the proposed MLWE-based CCOT protocol is analysed in this paper, and the security of the protocol under malicious adversary attacks is demonstrated based on the simulation proof approach.
• The approximate efficiency of each phase of the proposed protocol is evaluated, and the computational and communication complexities are compared with those of the LWE-based CCOT protocol. The analysis results show that the proposed protocol is more computationally efficient and that the communication overhead is reduced by a factor of n under malicious adversary attacks.

The structure of this paper is outlined as follows. In Section 2, we introduce relevant previous work. In Section 3, we introduce the symbols used in this paper as well as the concepts of the lattice, compression, and decompression functions, the rounding function, and other definitions. In Section 4, we introduce the MLWE-based dual-mode encryption framework and propose the MLWE-based CCOT protocol. A security analysis is presented in Section 5. Section 6 presents the efficiency analysis. The last section comprises a summary of the paper.

2. Relative Work

2.1. Relative References

One of the appealing features of the LWE problem is its provable security, which ensures that solving the average-case LWE problem is at least as hard as solving the certain worst-case lattice problem [20]. In 2008, Peikert et al. [21] first constructed an LWE-based dual-mode encryption system [20] and designed a generic OT protocol framework under the common reference string (CRS) model. However, this public-key lattice-based encryption OT protocol requires high communication and computation overheads. Subsequently, several OT protocols for lattice public-key cryptosystems have been proposed [22,23,24,25]. The OT protocols in [22,23] are based on the hard lattice problem assumption, which is equivalent to the hardness of the LWE problem, while the security of the OT protocols in [24,25] relies on the hard LWE problem assumption. In 2019, Liu et al. [26] constructed a novel OT protocol based on the hard LWE problem assumption, which is more efficient than the protocols in [21,25]. However, the OT protocols in [22,23,24,25,26] are based on the hard LWE problem assumption and are not resistant to selective failure attacks [3,12] launched by malicious attackers in secure two-party computation. In 2020, Quach [27] improved the dual-mode cryptosystem in [21] to make the common reference string reusable in any number of executions between the sender and the receiver, achieving statistical security for both parties involved. In 2021, Ding et al. [28] constructed the first LWE-based CCOT protocol using the dual-mode encryption framework in [27] by introducing the cut-and-choose technique.

The OT and CCOT protocols constructed based on the LWE problem require a large number of matrix operations and can only encrypt a single bit, leading to low computation overhead and large key and ciphertext sizes. In 2017, Liu et al. [29] constructed an OT protocol with relatively low computation and communication overheads based on the ring-learning-with-errors (RLWE) assumption. However, the security assumptions of the RLWE problem can only be reduced to difficult problems on an ideal lattice, and a larger number of ring dimensions are required to ensure security, which improves the computational efficiency. To further reduce the computation overhead, in 2019, Liu et al. [26] proposed another ideal-lattice-based OT protocol. It uses the RLWE key exchange mechanism and provides input privacy for both parties, but it requires high communication overhead. To minimize communication overhead, in 2020, Yadav et al. [30] proposed an RLWE-based OT protocol, but it still requires high communication overhead. The literature [31,32] proposed the MLWE problem assumptions, which guarantee the same level of security as general lattice-based schemes while providing efficient encryption with smaller key and ciphertext sizes. Since then, many works [33,34,35,36] have been constructed based on the hard MLWE problem assumption, verifying the security and feasibility of this assumption.

2.2. Summary of Related Protocols

As shown in

Table 1. Comparison of related protocols.

Scheme	[25]	[21]	[26]	[28]	Our Protocol
Assumption	LWE	LWE	LWE	LWE	MLWE
Model	CRS	CRS	ROM	CRS	CRS
Quantum attack	YES	YES	YES	YES	YES
Communication round	≥3	≥2	3	1	1
Selective failure attack	NO	NO	NO	YES	YES
Computation overhead	$O(n_1^{2c_1+1}{n}_{2}log{q}_{1}log{q}_2+n_2^{2}log{q}_2)(\odot )$, $O(n_1^{2c_1+1}{n}_{2}log{q}_{1}log{q}_2+n_2^{2}log{q}_2)(+)$, $O\left(n_{2}log{q}_2\right)(\oplus )$	$O\left({\mathit{n}}^{3}logn\right)(\odot )$, $O\left({\mathit{n}}^{3}logn\right)(+)$	$O\left({\mathit{n}}^3\right)(\odot )$, $O\left({\mathit{n}}^{3}logn\right)(+)$	$O\left({\mathit{n}}^3\right)(\odot )$, $O\left({\mathit{n}}^2\right)(+)$, $O\left({\mathit{n}}^2\right)(\oplus )$	$O\left({\mathit{n}}^{2}logn\right)(\odot )$, $O\left(\mathit{n}\right)(+)$, $O\left(\mathit{n}\right)(\oplus )$
Communication overhead	$O(n_1^{2c_1+1}log{q}_1+n_1^{c_1+1}{n}_{2}log{q}_{1}log{q}_2)\left({\mathbb{Z}}_{q_1}\right)$, $O\left(n_2^{2}log{q}_2\right)\left({\mathbb{Z}}_{q_2}\right)$, $O(n_1+n_{2}log{q}_2)\left({\mathbb{Z}}_2\right)$	$O\left(n^{2}logn\right)\left({\mathbb{Z}}_q\right)$	$O\left({\mathit{n}}^2\right)\left({\mathbb{Z}}_q\right)$, $O\left({\mathit{n}}^2\right)\left({\mathbb{Z}}_2\right)$	$O\left({\mathit{n}}^2\right)\left({\mathbb{Z}}_q\right)$, $O\left({\mathit{n}}^2\right)\left({\mathbb{Z}}_2\right)$	$O\left({\mathit{n}}^2\right)\left({\mathbb{Z}}_q\right)$, $O\left(n\right)\left({\mathbb{Z}}_2\right)$

, OT protocols [24,25,26] are based on the LWE problem assumption, which is theoretically resistant to quantum attacks. However, these protocols cannot defend against selective failure attacks launched by malicious adversaries in secure two-party computation [3,12]. Moreover, the protocols in [21,25,28] are standard universal composability secure under the CRS model, while the protocol in [26] is provably secure under the random oracle model (ROM). Among these, the instantiated protocol in [26] is more efficient compared to the instantiated protocols in [21,25].

At the present stage, a lattice-based CCOT protocol is constructed only based on the hard LWE problem assumption [28]. The CCOT protocol [28] designed based on the hard LWE problem assumption and incorporating the cut-and-choose technique is capable of resisting quantum attacks in secure two-party communication, in contrast to OT protocols [21,25,26] constructed based on the hard LWE problem assumption. The LWE-based CCOT protocol [28] not only has fewer communication rounds but also can resist selective failure attacks. According to Table 1, our MLWE-based CCOT protocol is able to reduce the computation and communication overheads by at least n times compared to the LWE-based CCOT protocol [28] while maintaining the optimal number of communication rounds and guaranteeing protocol security.

3. Preliminaries

3.1. Symbol Descriptions

In

Table A1. Description of the main parameters in this paper.

Parameter Symbol	Meaning
$\mathbb{Z}$	The set of integers
${\mathbb{Z}}_q$	The ring of residue classes of modulo q
R	$R=\mathbb{Z}\left[X\right]/\left(X^n+1\right)$ denotes a polynomial ring
$R_q$	$R_q={\mathbb{Z}}_q\left[X\right]/\left(X^n+1\right)$ denotes a polynomial ring modulo q
${\chi }_B$	${\chi }_B=\left\{e\in {\chi }_B|{∥e∥}_{\infty }\le B\right\}$ denotes a probability distribution bounded by B
$m\in R$	A polynomial in the polynomial ring R
$\mathit{s}/{\mathit{s}}^T$	$\mathit{s}$ vector/the transpose of the vector
$\mathit{A}/{\mathit{A}}^T$	A matrix/the transpose of the matrix
${∥\mathit{s}∥}_{\infty }$	The infinite norm of a vector $\mathit{s}$
$\mathit{s}\stackrel{\$}{\leftarrow }{R}_q^k$	Uniform random sample of a k-dimensional polynomial vector $\mathit{s}$
$\mathit{e}\leftarrow {\chi }_B^m$	Sample of an m-dimensional polynomial vector $\mathit{e}$ from the probability distribution ${\chi }_B$
$poly\left(n\right)$	A polynomial function of n
$negl\left(n\right)$	A negligible function of n
$\lceil ·\rfloor$	Rounding the element ·

, the symbols used in the paper and their meanings are described.

3.2. The Lattice Assumption

Definition 1

(MLWE problem (${\mathrm{MLWE}}_{n,m,k,q,\chi }$ [32])). Let the positive integer n be a power of 2, and let $m,k,B\ge 1$ be any positive integers. Given a prime q satisfying $q\equiv 1mod2n$, the ring of polynomials modulo q is defined as $R_q={\mathbb{Z}}_q\left[X\right]/(X^n+1)$. The error distribution ${\chi }_B$ is the probability distribution (usually the central binomial distribution) over $R_q$ bounded by B. For $\mathit{A}$$\stackrel{\$}{\leftarrow }{R}_q^m$ and $\mathit{s}\stackrel{\$}{\leftarrow }{\chi }_B^k,\mathit{e}\stackrel{\$}{\leftarrow }{\chi }_B^m$, define the distribution consisting of $\left(\mathit{A},\mathit{v}=\mathit{As}+\mathit{e}\right)$ as $A_{\mathit{s},{\chi }_B^m}^M$. The search ${MLWE}_{n,m,k,q,\chi }$ problem is defined as: given a sample $\left(\mathit{A},\mathit{V}=\mathit{As}+\mathit{e}\right)\in R_q^{m\times k}\times R_q^m$, solve for $\mathit{s}\in R_q^k$. The decision ${MLWE}_{n,m,k,q,\chi }$ problem is defined as: determine whether multiple samples $\left(\mathit{A},\mathit{V}=\mathit{As}+\mathit{e}\right)$ are drawn from the distribution $A_{\mathit{s},{\chi }_B^m}^M$ or from the distribution $U\left(R_q^{m\times k}\times R_q^m\right)$. For $\epsilon >0,\alpha \in \left(0,1\right),q\ge 2$, and $\gamma =\sqrt{8nk}·\omega (\sqrt{logn}/\alpha )·\sqrt{ln\left(2n\left(1+1/\epsilon \right)/\pi \right)}$, it has been proven in the literature [32] that the ${MLWE}_{n,m,k,q,\chi }$ problem is at least as difficult as approximating the shortest-independent-vector problem (${SIVP}_{\gamma }$).

3.3. Compression and Decompression Functions

To reduce the size of the public key and ciphertext and improve algorithm efficiency, this paper adopts the compression and decompression functions used in the Kyber algorithm [33]. These functions discard certain low-order bits from the values being compressed without affecting the correctness of decryption as long as appropriate parameters are used.

Compression function: ${\mathrm{Compress}}_{p_1\to p_2}\left(x\right)=\lceil p_2/p_1\rfloor mod{p}_2$;

Decompression function: ${\mathrm{Decompress}}_{p_2\to p_1}\left(x\right)=\lceil p_1/p_2\rfloor$.

As described in the literature [33], for any $x\in {\mathbb{Z}}_{q}with{p}_1>p_2$, $x^{\prime }={\mathrm{Decompress}}_{p_2\to p_1}\left({\mathrm{Compress}}_{p_1\to p_2}\left(x\right)\right)$ is a value close to x: specifically, $\left|x^{\prime }-xmod{p}_1\right|\le p_1/2p_2$. When the inputs are $x\in R_q\mathrm{or}\mathit{x}\in R_q^m$, these functions operate separately on each coefficient of each polynomial element.

3.4. Other Definitions and Citations

Lemma 1

(Noise flooding [37]). Given two integers $B,B^{\prime }\in \mathbb{Z}$ satisfying $B^{\prime }/B=negl\left(n\right)$ and assuming $\mathit{e}\in \left[-B^{\prime },B^{\prime }\right]$, the two distributions $U\left(-B,B\right)$ and $U\left(-B,B\right)+\mathit{e}$ are statistically indistinguishable.

Lemma 2

(Smoothing parameter [38]). Given a positive real number $\epsilon >0$, a lattice $\Lambda \left(\mathit{A}\right)$, and a Gaussian weight function defined as ${\rho }_{1/\sigma }\left(\mathit{x}\right)=exp\left(-\pi ∥{\mathit{x}}^2∥{\sigma }^2\right),for \mathit{x}\in {\Lambda }^{*}\left(\mathit{A}\right)\setminus \left\{0\right\}$, the smoothing parameter ${\eta }_{\epsilon }\left(\Lambda \left(\mathit{A}\right)\right)$ is defined as the smallest $\sigma >0$ that satisfies ${\rho }_{1/\sigma }\left(\mathit{x}\right)<\epsilon$.

Lemma 3

([38,39,40]). Given a positive real number $\epsilon >0$ and any k-dimensional lattice Λ, it follows that:

$${\eta }_{\epsilon }\left(\Lambda \right)={\displaystyle \frac{\sqrt{log\left(2m/\left(1+1/\epsilon \right)\right)/\pi }}{{\lambda }_1^{\infty }\left({\Lambda }^{*}\right)}}.$$

(1)

For any $\omega \left(\sqrt{logk}\right)$ function, there exists a negligible $\epsilon \left(k\right)$ such that either ${\eta }_{\epsilon }\left(\Lambda \left(\mathit{A}\right)\right)\le \omega \left(\sqrt{logk}\right){\lambda }_1\left({\Lambda }^{*}\left(\mathit{A}\right)\right)$ or ${\eta }_{\epsilon }\left({\Lambda }^{\perp }\left(\mathit{A}\right)\right)\le \omega \left(\sqrt{logk}\right)$.

3.5. The Rounding Function

Lemma 4

([41]). Given $m=\Theta \left(klogq\right)$, the rounding function $\mathcal{R}:{\mathbb{Z}}_q\to \left\{0,1\right\}$ is defined as follows:

$$\mathcal{R}\left(x\right)=⌊{\displaystyle \frac{2x}{q}}⌋mod2=\left\{\begin{array}{c}1,Pr:{\displaystyle \frac{1}{2}}+{\displaystyle \frac{cos(2\pi x/q)}{2}}\\ 0,Pr:{\displaystyle \frac{1}{2}}-{\displaystyle \frac{cos(2\pi x/q)}{2}}\end{array}\right..$$

(2)

Assume that $\mathit{A}\in R_q^{m\times k},\mathit{p}\in R_q^k$, and $\sigma \ge {\eta }_{\epsilon }\left({\Lambda }^{\perp }\left(\mathit{A}\right)\right)$ (where $\epsilon =negl\left(n\right)$). Then the following properties hold for the rounding function $\mathcal{R}$:

• Approximate correctness: Given $\mathit{s}\in R_q^k,\mathit{e}\in {\chi }_B^m$, where $B=o\left(q\right)/\sigma ·\sqrt{m}$, for all $\mathit{v}=\mathit{As}+\mathit{e}$, the following equation holds:

  $$\underset{\mathcal{R},\mathit{r}\leftarrow D_{R_q,\sigma }^m}{Pr}\left[\mathcal{R}\left({\mathit{r}}^T\mathit{As}\right)=\mathcal{R}\left({\mathit{r}}^T\mathit{v}\right)\right]\ge {\displaystyle \frac{2}{3}}.$$

  (3)
• Statistical smoothness: Given a full-rank matrix $\mathit{A}\in R_q^{m\times k}$, for all vectors $\mathit{v}\in R_q^m$ satisfying $d\left(\mathit{v},{\Lambda }^{\perp }\left(\mathit{A}\right)\right)\ge q\sqrt{m}/\sigma$, the following equation holds for $\mathit{r}\leftarrow D_{R_q,\sigma }^m$:

$$\left|\underset{\mathcal{R},\mathit{r}\leftarrow D_{R_q,\sigma }^m}{Pr}\left[\mathcal{R}\left({\mathit{r}}^T\mathit{v}\right)=1\left|{\mathit{r}}^T\mathit{A}={\mathit{P}}^T\right.\right]-1/2\right|\le negl\left(n\right).$$

(4)

4. The Cut-and-Choose Oblivious Transfer Protocol

The MLWE-based CCOT protocol essentially builds on the dual-mode encryption framework described in [21,27], with the key difference being the use of different hard problems and parameter selection methods. To facilitate understanding, we first present the MLWE-based dual-mode encryption framework.

4.1. The MLWE-Based Dual-Mode Encryption Framework

This section presents the MLWE-based dual-mode encryption framework, which builds the dual-mode encryption system described in the literature [27]. The key differences include the integration of compression and decompression techniques from the Kyber algorithm, which further reduce the size of the public key and ciphertext. Additionally, the framework uses the difficult MLWE problem and incorporates polynomial elements in the encryption and decryption processes. This allows for the encryption and decryption of multi-bits at a time, ensuring security while improving encryption efficiency.

The MLWE-based dual-mode encryption framework consists of the following seven probabilistic polynomial time (PPT) algorithms (the message space of the encryption framework is $\mathcal{M}$, where each message $m\in \mathcal{M}$ is considered a polynomial with coefficients in $\left\{0,1\right\}$ over the polynomial ring R):

SetupMessy$\left(1^{\lambda }\right)$: Given a security parameter $\lambda$, the execution of Algorithm 1 outputs a common reference string $cr{s}_M$ and a trapdoor $t{d}_M$.

Algorithm 1: SetupMessy$\left(1^{\lambda }\right)\to \left(cr{s}_M,t{d}_M\right)$

1: $\left({\mathit{A}}_0,\mathit{T}\right)\leftarrow TrapGen\left(1^k,1^m,q\right)$; 2: ${\mathit{v}}_0\stackrel{\$}{\leftarrow }{R}_q^m$; 3: return $cr{s}_M:=\left({\mathit{A}}_0,{\mathit{v}}_0\right),t{d}_M:=T$

SetupDec$\left(1^{\lambda }\right)$: Given the security parameter $\lambda$, the execution of Algorithm 2 outputs a common reference string $cr{s}_D$ and a trapdoor $t{d}_D$.

Algorithm 2: SetupDec   $\left(1^{\lambda }\right)\to \left(cr{s}_D,t{d}_D\right)$

1: ${\mathit{A}}_1\stackrel{\$}{\leftarrow }{R}_q^{m\times k},\overline{\mathit{s}}\stackrel{\$}{\leftarrow }{\chi }_B^k,\overline{\mathit{e}}\stackrel{\$}{\leftarrow }{\chi }_B^m$; 2: ${\mathit{v}}_1={\mathit{A}}_1\overline{\mathit{s}}+\overline{\mathit{e}}$; 3: return $cr{s}_D:=\left({\mathit{A}}_1,{\mathit{v}}_1\right),t{d}_D:=\overline{\mathit{s}}$

KeyGen$\left(crs,\delta \right)$: Given a public reference string $crs$ and a choice bit $\delta \in \left\{0,1\right\}$, the execution of Algorithm 3 outputs a base public key ${pk}_{base}$ after passing through the compression function and a private key $s{k}_{\delta }$ corresponding to the choice bit $\delta$.

Algorithm 3: KeyGen   $\left(crs,\delta \right)\to \left({pk}_{base},s{k}_{\delta }\right)$

1: ${\mathit{s}}_j\stackrel{\$}{\leftarrow }{\chi }_B^k,{\mathit{e}}_j\stackrel{\$}{\leftarrow }{\chi }_B^m,{\mathit{f}}_j\stackrel{\$}{\leftarrow }{\left[-B^{\prime },B^{\prime }\right]}^m$; 2: $p{k}_{base}:={\mathit{A}}_j{\mathit{s}}_j+{\mathit{e}}_j+{\mathit{f}}_j-\delta ·{\mathit{v}}_j,s{k}_{\delta }:={\mathit{s}}_j$; 3: ${pk}_{base}:={\mathrm{Compress}}_{q\to p_1}\left(p{k}_{base}\right)$; 4: $p{k}_1=p{k}_0+{\mathit{v}}_j$; 5: return $\left({pk}_{base},s{k}_{\delta }:=\mathit{s}\right)$

Enc$\left(crs,{pk}_{base},\mu \in \left\{0,1\right\},{\mathit{m}}_{\mu }\right)$: Given the common reference string $crs$, the base public key ${pk}_{base}$, and two messages $m_{\mu },\mu \in \left\{0,1\right\}$, the execution of Algorithm 4 outputs the ciphertext $c{t}_{\mu }$ after passing through the compression function.

Algorithm 4: Enc   $\left(crs,{pk}_{base},\mu \in \left\{0,1\right\},m_{\mu }\right)\to c{t}_{\mu }$

1: $p{k}_{base}:={\mathrm{Decompress}}_{p_1\to q}\left({pk}_{base}\right)$; 2: $p{k}_{\mu }:=p{k}_{base}+\mu ·{\mathit{v}}_j$; 3: ${\mathit{r}}_{\mu }\stackrel{\$}{\leftarrow }{D}_{R_q,\sigma }^m$, ${\mathit{p}}_{\mu }^T={\mathit{r}}_{\mu }^T·{\mathit{A}}_j$; 4: $c_{\mu }=\mathcal{R}\left({\mathit{r}}_{\mu }^T·p{k}_{\mu }\right)\oplus m_{\mu }$; 5: ${\widehat{c}}_{\mu }={\mathrm{Compress}}_{q\to p_2}\left(c_{\mu }\right)$; 6: return $c{t}_{\mu }:={\left(\left\{{\mathit{p}}_{\mu },{\widehat{c}}_{\mu }\right\}\right)}_{\mu \in \left\{0,1\right\}}$

Dec$\left(crs,s{k}_{\delta },c{t}_{\mu }\right)$: Given the common reference string $crs$, the private key $s{k}_{\delta }$, and the ciphertext $c{t}_{\mu }$, the execution of Algorithm 5 outputs the message $m_{\delta }$ or the messages $\left(m_0,m_1\right)$ corresponding to the choice bit $\delta$.

Algorithm 5: Dec   $\left(crs,s{k}_{\delta },c{t}_{\mu }\right)\to m_{\delta }or\left(m_0,m_1\right)$

1: Parse: $c{t}_{\mu }\mapsto {\left(\left\{{\mathit{p}}_{\mu },{\widehat{c}}_{\mu }\right\}\right)}_{\mu \in \left\{0,1\right\}}$; 2: $c_{\mu }={\mathrm{Decompress}}_{p_2\to q}\left({\widehat{c}}_{\mu }\right)$; 3: $\mathcal{R}({\mathit{p}}_{\mu }^T·s{k}_{\delta })\oplus c_{\mu }\to m_{\delta }or\left(m_0,m_1\right)$; 4: return $j=0:m_{\delta };j=1:\left(m_0,m_1\right)$

FindMess${\mathit{y}}^{*}\left(crs,t{d}_M,p{k}_{\delta }\right)$: Given the common reference string $crs$, the trapdoor $t{d}_M$, and a public key $p{k}_{\delta }$, the execution of Algorithm 6 outputs the bit $\overline{\delta }\in \left\{0,1\right\}$, which determines whether the public key is in Messy mode. This algorithm is used only in security proofs.

Algorithm 6: FindMess   $y^{*}\left(crs,t{d}_M,p{k}_{\delta }\right)\to \overline{\delta }$

1: Invoke: $IsMessy\left(t{d}_M,p{k}_{\delta }\right)$; 2: Invoke: $Invert\left(t{d}_M,p{k}_{\delta }\right)\to \mathrm{event}$; 3: if $∥\mathit{e}∥>q/6\sqrt{m}$ then 4:      return event: messy; 5: else 6:      return event: not sure; 7: end if 8: if event: messy then 9:      return $\overline{\delta }:=0$ 10: else 11:    return $\overline{\delta }:=1$ 12: end if

TKeyGe${\mathit{n}}^{*}\left(crs,t{d}_D\right)$: Given the common reference string $crs$ and the trapdoor $t{d}_D$, the execution of Algorithm 7 outputs the base public $p{k}_{\delta }$ and two private keys $\left(s{k}_{\delta },s{k}_{1-\delta }\right)$. This algorithm is used only in security proofs.

Algorithm 7: ${\mathit{TKeyGen}}^{*}\left(crs,t{d}_D\right)\to \left(p{k}_{\delta },s{k}_{\delta },s{k}_{1-\delta }\right)$

1: $\mathit{s}\stackrel{\$}{\leftarrow }{\chi }_B^k,\mathit{e}\stackrel{\$}{\leftarrow }{\chi }_B^m,\mathit{f}\stackrel{\$}{\leftarrow }{\left[-B^{\prime },B^{\prime }\right]}^m$; 2: $p{k}_{\delta }:=\mathit{As}+\mathit{e}+\mathit{f}$ 3: $s{k}_{\delta }:=\mathit{s},s{k}_{1-\delta }:=\mathit{s}+\overline{\mathit{s}}$ 4: return $\left(p{k}_{\delta },s{k}_{\delta },s{k}_{1-\delta }\right)$

Lemma 5

(Correctness). The above framework ensures correct decryption if the parameters satisfy $\sigma \ge \omega \left(\sqrt{logm}\right)$ and $\left(B+B^{\prime }\right)·\sigma ·\sqrt{m}=o\left(q\right)$.

Proof. 

From Lemma 3, there exist some negligible positive real numbers $\epsilon =negl\left(n\right)$ such that $\sigma \ge {\eta }_{\epsilon }\left({\Lambda }^{\perp }\left(\mathit{A}\right)\right)$ holds with non-negligible probability in the choice of matrix $\mathit{A}$. According to the approximate correctness of the rounding function R in Lemma 4, given internal randomness ${\mathit{r}}_{\mu }\stackrel{\$}{\leftarrow }{D}_{R_q,\sigma }^m$ and $\mathcal{R}$, the following equation holds:

$$\underset{\mathcal{R},{\mathit{r}}_{\mu }\stackrel{\$}{\leftarrow }{D}_{R_q,\sigma }^m}{Pr}\left[\mathcal{R}\left({\mathit{r}}_{\mu }^T·{pk}_{\mu }\right)=\mathcal{R}({\mathit{p}}_{\mu }^T·{sk}_{\delta })\right]\ge {\displaystyle \frac{2}{3}}.$$

(5)

Thus, it follows that the framework ensures decryption correctness. This concludes the proof. □

Lemma 6

(Indistinguishability of the Messy and Dec modes). The framework satisfies the indistinguishability of two modes if the decision ${MLWE}_{n,m,k,q,p,\chi }$ assumption holds.

Proof. 

The common reference string $cr{s}_M:=\left({\mathit{A}}_0,{\mathit{v}}_0\right)\leftarrow SetupMessy\left(1^{\lambda }\right)$ generated in Messy mode is a nearly uniform distribution over $R_q^{m\times k}\times R_q^m$. According to the ${\mathrm{MLWE}}_{n,m,k,q,p,\chi }$ assumption, $\left(\mathit{A},\mathit{v}=\mathit{A}\overline{\mathit{s}}+\overline{\mathit{e}}\right)$ and $\left(\mathit{A},\mathit{v}\right)\stackrel{\$}{\leftarrow }{R}_q^{m\times k}\times R_q^m$ are computationally indistinguishable if sampled by $\mathit{A}\stackrel{\$}{\leftarrow }{R}_q^m,\overline{\mathit{s}}\stackrel{\$}{\leftarrow }{R}_q^k,\overline{\mathit{e}}\stackrel{\$}{\leftarrow }{\mathcal{X}}_B^m$. Thus, the distribution of $cr{s}_M:=\left({\mathit{A}}_0,{\mathit{v}}_0\right)$ obtained in Messy mode is indistinguishable from the distribution of $cr{s}_D:=\left({\mathit{A}}_1,{\mathit{v}}_1\right)$ obtained in Dec mode. This concludes the proof. □

Lemma 7

(A sufficient condition for Messy mode keys [27]). Given $\mathit{A}\stackrel{\$}{\leftarrow }{R}_q^{m\times k}$, $\mathit{v}\in R_q^m$, and $\epsilon =negl\left(n\right)$, let $\sigma \ge {\eta }_{\epsilon }\left(\Lambda \left(\mathit{A}\right)\right)$. If the matrix $\mathit{A}$ is full-rank and $d\left(\mathit{v},\Lambda \left(\mathit{A}\right)\right)\ge q\sqrt{m}/\sigma$, then the public key $pk=\left(\mathit{A},\mathit{v}\right)$ is in Messy mode, i.e., it satisfies the following equation:

$$Enc\left(crs,pk,m_0\right){\approx }_{s}Enc\left(crs,pk,m_1\right).$$

(6)

Lemma 8

(Most public keys are in Messy mode [27]). Given $m\ge 2\left(k+1\right)logq,\sigma \ge 4\sqrt{m}$ and $(\mathit{A},\mathit{v})\stackrel{\$}{\leftarrow }{R}_q^{m\times k}\times R_q^m$, then there exists a non-negligible probability that $d\left(\mathit{v},\Lambda \left(\mathit{A}\right)\right)\ge q/4$ holds, and $\left(\mathit{A},\mathit{v}\right)$ is in Messy mode.

Lemma 9

(Identifying Messy keys [27]). Given $\left(\mathit{A},\mathit{T}\right)\leftarrow TrapGen\left(1^k,1^m,q\right)$, if $\mathit{A}$ is full-rank and $\sigma \ge 6m$, then there exists a polynomial-time algorithm $IsMessy$ that computes the distance between $\mathit{v}$ and $\Lambda \left(\mathit{A}\right)$ for input $\mathit{v}\in R_q^m$. If $d\left(\mathit{v},\Lambda \left(\mathit{A}\right)\right)\ge q\sqrt{m}/\sigma$, the public key $\left(\mathit{A},\mathit{v}\right)$ is recognised as a Messy public key.

Lemma 10

(Security in Messy mode). Given $\sigma \ge 6m$ and $m\ge 2\left(k+1\right)logq$, the framework is secure in Messy mode, i.e., the following equation holds:

$$Enc\left(crs,pk,j,m_0\right){\approx }_{s}Enc\left(crs,pk,j,m_1\right).$$

(7)

Proof. 

First, we prove that in Messy mode, for any public key, there is a non-negligible probability that at least one public key $p{k}_0={\mathit{v}}_0$ or $p{k}_1={\mathit{v}}_1$ satisfies $d\left({\mathit{v}}_j,\Lambda \left(\mathit{A}\right)\right)\ge q/6\sqrt{m}$, and by Lemma 8, it is in Messy mode. It is straightforward to show that if either $p{k}_0={\mathit{v}}_0$ or $p{k}_1={\mathit{v}}_1$ is close to $\Lambda \left(\mathit{A}\right)$, then by the triangle inequality, $\mathit{v}={\mathit{v}}_1-{\mathit{v}}_0$ will also be close to $\Lambda \left(\mathit{A}\right)$. Specifically, if there exists $d\left({\mathit{v}}_j,\Lambda \left(\mathit{A}\right)\right)\le q/6\sqrt{m}$ when $j\in \left\{0,1\right\}$, then it follows from Lemma 8 that there must be $d\left(\mathit{v},\Lambda \left(\mathit{A}\right)\right)\le q/3\sqrt{m}$, which occurs only with negligible probability based on the randomness of $(\mathit{A},\mathit{v})\stackrel{\$}{\leftarrow }{R}_q^{m\times k}\times R_q^m$. Thus, by Lemma 9, for all public keys $p{k}_{\delta }$, the output $\overline{\delta }$ of the $FindMess{y}^{*}\left(crs,t{d}_M,p{k}_{\delta }\right)$ algorithm is in Messy mode. This concludes the proof. □

Lemma 11

(Security in Dec mode). The framework is secure in Dec mode if the relation between the boundaries B and $B^{\prime }$ of the noise distribution satisfies $B^{\prime }/B=negl\left(n\right)$.

Proof. 

Since there exists a relationship $p{k}_1=p{k}_0+\mathit{v}$ between the two public keys, we have $\left(cr{s}_D,t{d}_D\right)\leftarrow SetupDec\left(1^{\lambda }\right)$ in Dec mode, where $cr{s}_D=\left(\mathit{A},{\mathit{v}}_1=\mathit{A}\overline{\mathit{s}}+\overline{\mathit{e}}\right)$ and $t{d}_D=\overline{\mathit{s}}$. When $\delta =0$, the output of the algorithm $TKeyGe{n}^{*}\left(crs,t{d}_D\right)$ gives $p{k}_0=\mathit{As}+\mathit{e}+\mathit{f},s{k}_0=\mathit{s}$, and $p{k}_1=p{k}_0+{\mathit{v}}_1=\mathit{A}\left(\mathit{s}+\overline{\mathit{s}}\right)+\left(\mathit{e}+\overline{\mathit{e}}\right)+\mathit{f},s{k}_1=\left(\mathit{s}+\overline{\mathit{s}}\right)$. According to Lemma 1, the statistical distribution of $\left(p{k}_1,s{k}_1\right)$ is close to $p{k}_1=\mathit{A}\left(\mathit{s}+\overline{\mathit{s}}\right)+\left(\mathit{e}\right)+\mathit{f},s{k}_1=\left(\mathit{s}+\overline{\mathit{s}}\right)$. The conventional key for the branch j is generated by $KeyGen\left(crs,\delta \right)$: ${\overline{pk}}_j=\mathit{A}{\mathit{s}}_j+{\mathit{e}}_j$, ${\overline{sk}}_{\delta }={\mathit{s}}_j$, where ${\mathit{s}}_j\stackrel{\$}{\leftarrow }{R}_q^k,{\mathit{e}}_j\leftarrow {\mathcal{X}}_B^m,and\mathit{f}\stackrel{\$}{\leftarrow }\left[-B^{\prime },B^{\prime }\right]$, with the relation ${\overline{pk}}_1={\overline{pk}}_0+{\mathit{v}}_j$. For $j\in \left\{0,1\right\}$, the respective joint distributions of $(cr{s}_D,p{k}_j,s{k}_j)$ and $(cr{s}_D,p{k}_j,s{k}_j)$ are statistically indistinguishable. This concludes the proof. □

4.2. The MLWE-Based CCOT Protocol

The CCOT protocol is commonly used in secure two-party computation to achieve key transfer. Before detailing the MLWE-based CCOT protocol construction, we first briefly review the functional function of the CCOT protocol. In a secure two-party computation protocol, the circuit constructor $P_1$ constructs s garbled circuits. The circuit evaluator $P_2$ then randomly selects half of these circuits as check circuits and the other half as evaluation circuits. During the key transfer phase, $P_2$ obtains the garbled keys based on the circuit index bit $j\in \left\{0,1\right\}$. When $j=0$ (corresponding to the evaluation circuit), $P_2$ obtains one garbled key on each input wire, and when $j=1$ (corresponding to the check circuit), $P_2$ obtains two garbled keys on each input wire. A brief model of the CCOT protocol is given in Figure 2.

The MLWE-based CCOT protocol is built upon the MLWE-based two-mode encryption framework. Given the inputs $m_0,m_1\in \mathcal{M}$ of the sender $P_1$, where $\mathcal{M}$ denotes the set of polynomials with coefficients in $\left\{0,1\right\}$ over the polynomial ring R, and the index bit $\delta \in \left\{0,1\right\}$ and the choice bit $\delta \in \left\{0,1\right\}$ for the receiver $P_2$. The protocol is divided into the setup and transmission phases:

4.2.1. The Setup Phase

• SetupMessy$\left(1^{\lambda }\right)$: When the receiver $P_2$’s index bit is $j=0$, $P_2$ calls Algorithm 1.

  (1)

  $P_2$ executes the algorithm $TrapGen\left(1^k,1^m,q\right)\to \left({\mathit{A}}_0,\mathit{T}\right)$ and uniformly randomly samples $v_0\stackrel{\$}{\leftarrow }{R}_q^m$.

  (2)

  $P_2$ generates $cr{s}_M=\left({\mathit{A}}_0,{\mathit{v}}_0\right)\mathrm{and}t{d}_M=\mathit{T}$, where $cr{s}_M$ is publicly available and the trapdoor $t{d}_M$ associated with the evaluation circuit is known only to $P_2$.

• SetupDec$\left(1^{\lambda }\right)$: When the receiver $P_2$’s index bit is $j=1$, $P_2$ calls Algorithm 2.

  (1)

  $P_2$ uniformly randomly samples ${\mathit{A}}_1\stackrel{\$}{\leftarrow }{R}_q^{m\times k},\mathit{s}\stackrel{\$}{\leftarrow }{\chi }_B^k,\mathrm{and}\mathit{e}\stackrel{\$}{\leftarrow }{\chi }_B^m$, and computes ${\mathit{v}}_1={\mathit{A}}_1\overline{\mathit{s}}+\overline{\mathit{e}}$.

  (2)

  $P_2$ generates $cr{s}_D=\left({\mathit{A}}_1,{\mathit{v}}_1\right)\mathrm{and}t{d}_D=\overline{\mathit{s}}$, where $cr{s}_D$ is publicly available and the trapdoor $t{d}_D$ associated with the check circuit is known only to $P_2$.

4.2.2. The Transmission Phase

• KeyGen$\left(crs,\delta \right)$: The receiver $P_2$ calls Algorithm 3 based on its choice bit $\delta \in \left\{0,1\right\}$.

  (1)

  $P_2$ samples ${\mathit{s}}_j\stackrel{\$}{\leftarrow }{\chi }_B^k,{\mathit{e}}_j\stackrel{\$}{\leftarrow }{\chi }_B^m,\mathrm{and}{f}_j\stackrel{\$}{\leftarrow }\left[-B^{\prime },B^{\prime }\right]$, and computes $p{k}_{base}={\mathit{A}}_j{\mathit{s}}_j+{\mathit{e}}_j+{\mathit{f}}_j-\delta ·{\mathit{v}}_j,\mathrm{and}s{k}_{\delta }={\mathit{s}}_j$. Additionally, $P_2$ sets $p{k}_1-p{k}_0={\mathit{v}}_j$.

  (2)

  $P_2$ processes the base public key $p{k}_{base}$ with the compression function to obtain ${pk}_{base}={\mathrm{Compress}}_{q\to p_1}\left(p{k}_{base}\right)$ and sends it to $P_1$.

• Enc$\left(crs,{pk}_{base},\mu \in \left\{0,1\right\},m_{\mu }\right)$: The sender $P_1$ calls Algorithm 4 based on ${pk}_{base}$ and two messages $m_{\mu },\mu \in \left\{0,1\right\}$.

  (1)

  $P_1$ processes ${pk}_{base}$ through the decompression function to obtain the original $p{k}_{base}={\mathrm{Decompress}}_{p_1\to q}\left({pk}_{base}\right)$.

  (2)

  $P_1$ computes two derived public keys $p{k}_0=p{k}_{base}\mathrm{and}p{k}_1=p{k}_{base}+{\mathit{v}}_j$ based on $p{k}_{\overline{\delta }}=p{k}_{base}+\overline{\delta }·{\mathit{v}}_j,\overline{\delta }\in \left\{0,1\right\}$.

  (3)

  $P_1$ encrypts $m_0\mathrm{and}{m}_1$ using $p{k}_0\mathrm{and}p{k}_1$, respectively. $P_1$ samples ${\mathit{r}}_{\overline{\delta }}\leftarrow D_{R_q,\sigma }^m$ and computes $c_{\overline{\delta }}=\mathcal{R}\left({\mathit{r}}_{\overline{\delta }}^T·p{k}_{\overline{\delta }}\right)\oplus m_{\overline{\delta }}$ as well as ${\mathit{p}}_{\overline{\delta }}^T={\mathit{r}}_{\overline{\delta }}^T·{\mathit{A}}_j$.

  (4)

  $P_1$ processes $c_{\overline{\delta }}$ through the compression function to obtain ${\widehat{c}}_{\overline{\delta }}={\mathrm{Compress}}_{q\to p_2}\left(c_{\overline{\delta }}\right)$ and finally sends the ciphertext $c{t}_{\overline{\delta }}={\left(\left\{{\mathit{P}}_{\overline{\delta }},{\widehat{c}}_{\overline{\delta }}\right\}\right)}_{\overline{\delta }\in \left\{0,1\right\}}$ to $P_2$.

• Dec$\left(crs,s{k}_{\delta },c{t}_{\mu }\right)$: The receiver $P_2$ calls Algorithm 5 based on $c{t}_{\overline{\delta }\in \left\{0,1\right\}}$.

  (1)

  $P_2$ parses $c{t}_{\overline{\delta }\in \left\{0,1\right\}}$ to obtain $c{t}_{\overline{\delta }}\mapsto {\left(\left\{{\mathit{p}}_{\overline{\delta }},{\widehat{c}}_{\overline{\delta }}\right\}\right)}_{\overline{\delta }\in \left\{0,1\right\}}$ and processes ${\widehat{c}}_{\overline{\delta }\in \left\{0,1\right\}}$ through the decompression function to obtain $c_{\overline{\delta }}={\mathrm{Decompress}}_{p_2\to q}\left({\widehat{c}}_{\overline{\delta }}\right)$.

  (2)

  $P_2$ computes $\mathcal{R}({\mathit{p}}_{\overline{\delta }}^T·s{k}_{\delta })\oplus c_{\overline{\delta }}$ using the private key $s{k}_{\delta }$. If $P_2$’s index bit $j=0$, then $P_2$ obtains the value $m_{\delta }$ corresponding to its selection bit $\delta \in \left\{0,1\right\}$ from the evaluation circuit. If $P_2$’s index bit $j=1$, then $P_2$ obtains both values $m_0\mathrm{and}{m}_1$ from the checking circuit.

5. Security Analysis

5.1. Correctness Analysis

Theorem 1.

Assume that the parameters satisfy $\left(B+B^{\prime }\right)·\sigma ·\sqrt{m}=o\left(q\right)$ and $\sigma \ge \omega \left(\sqrt{logm}\right)$. If the MLWE-based dual-mode encryption framework satisfies decryption correctness, then the MLWE-based CCOT protocol is correct.

Proof. 

When the receiver $P_2$’s index bit is $j=0$ and the choice bit is $\delta =0$, $P_2$ sets the base public key to $p{k}_{base}={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+{\mathit{f}}_0$ and the private key to $s{k}_{\delta }=s{k}_0={\mathit{s}}_0$ in the key generation phase. The sender $P_1$ can calculate $p{k}_0={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+{\mathit{f}}_0$ and $p{k}_1={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+{\mathit{f}}_0+{\mathit{v}}_0$ based on $p{k}_{base}$. According to Lemma 5, $P_2$ can correctly decrypt the message $m_0$ with the choice bit $\delta =0$ using $p{k}_0$ and $s{k}_0={\mathit{s}}_0$. Since ${\mathit{v}}_0$ in $p{k}_1$ is sampled uniformly at random by $P_2$, the receiver $P_2$ cannot know the private key $s{k}_1$ corresponding to $p{k}_1$, and thus $P_2$ cannot decrypt $m_1$. When the choice bit $\delta =1$, $P_2$ sets the base public key to $p{k}_{base}={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+f_0-{\mathit{v}}_0$, and $P_1$ computes $p{k}_1={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+f_0$, $p{k}_0={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+{\mathit{f}}_0-{\mathit{v}}_0$, and $s{k}_{\delta }=s{k}_1={\mathit{s}}_0$. Similarly, $P_2$ can only decrypt the message $m_1$ corresponding to its choice bit $\delta =1$ based on $p{k}_1$ and $s{k}_1={\mathit{s}}_0$.

When the receiver $P_2$’s index bit is $j=1$ and the choice bit $\delta =0$, the sender $P_1$ can compute $p{k}_0={\mathit{A}}_1{\mathit{s}}_1+{\mathit{e}}_1+{\mathit{f}}_1$ and $p{k}_1={\mathit{A}}_1{\mathit{s}}_1+{\mathit{e}}_1+{\mathit{f}}_1+{\mathit{v}}_1$ according to $p{k}_{base}={\mathit{A}}_1{\mathit{s}}_1+{\mathit{e}}_1+{\mathit{f}}_1$. Since $P_2$ knows ${\mathit{v}}_1={\mathit{A}}_1\overline{\mathit{s}}+\overline{\mathit{e}}$ and $p{k}_1={\mathit{A}}_1\left({\mathit{s}}_1+\overline{\mathit{s}}\right)+\left({\mathit{e}}_1+\overline{\mathit{e}}\right)+{\mathit{f}}_1$, $P_2$ not only knows $s{k}_{\delta }=s{k}_0={\mathit{s}}_0$ but also knows the private key $s{k}_1=\left({\mathit{s}}_1+\overline{\mathit{s}}\right)$ corresponding to the public key $p{k}_1$. From Lemma 5, $P_2$ can correctly decrypt both messages $m_0$ and $m_1$. Similarly, if $P_2$’s choice bit is $\delta =1$, $P_2$ can decrypt both messages according to the trapdoor ${\mathit{v}}_1$. □

5.2. Security Analysis

Theorem 2.

Given the security parameter λ, the encryption parameter $n=n\left(\lambda \right)=\lambda$ (where n is a power of 2), the modulus $q=q\left(\lambda \right)\equiv 1mod2n$, matrix dimensions $m=m\left(\lambda \right)andk=k\left(\lambda \right)$, and $m\ge 2\left(k+1\right)logq$. Set $\sigma \ge 6m$ and the boundary $B=\tilde{\Omega }\left(\sqrt{k}\right)$ of the probability distribution ${\chi }_B$. Assuming that the decision ${MLWE}_{n,m,k,q,p,\chi }$ problem is hard, the CCOT protocol described in Section 4.2 achieves security against static malicious adversary attacks under the CRS model.

Proof. 

The security proof of the protocol is conducted under two corruption scenarios: when the sender $P_1$ is corrupted and when the receiver $P_2$ is corrupted.

When the sender $P_1$ is corrupted: First, define a static malicious adversary $\mathcal{A}$ that corrupts the sender $P_1$ in the real protocol. Then, construct a simulator $\mathcal{S}$ that invokes the adversary $\mathcal{A}$ in the ideal world to simulate the interaction between the adversary $\mathcal{A}$ and the honest receiver $P_2$. The exact workflow of simulator $\mathcal{S}$ is as follows:

${\mathcal{S}}_1$: When the honest receiver $P_2$’s index bit is $j=0$, the simulator $\mathcal{S}$ calls the SetupMessy$\left(1^{\lambda }\right)$ algorithm to generate $cr{s}_M=\left({\mathit{A}}_0,{\mathit{v}}_0\right)$ and $t{d}_M$; it then sends $cr{s}_M$ from inside to the adversary $\mathcal{A}$ while keeping $t{d}_M$ secret. Similarly, when $j=1$, simulator $\mathcal{S}$ calls the SetupMessy$\left(1^{\lambda }\right)$ algorithm to generate $cr{s}_D=\left({\mathit{A}}_1,{\mathit{V}}_1={\mathit{A}}_1\overline{\mathit{s}}+\overline{\mathit{e}}\right)$ and $t{d}_D=\overline{\mathit{s}}$. It then sends $cr{s}_D$ from the inside to the adversary $\mathcal{A}$, while $\mathcal{S}$ keeping $t{d}_D$ secret.

${\mathcal{S}}_2$: The simulator $\mathcal{S}$ sets the choice bit ${\delta }^{\prime }=0$, consistent with the choice bit of the honest receiver $P_2$. When the honest receiver $P_2$’s index bit is $j=0$, simulator $\mathcal{S}$ calls the KeyGen$\left(crs,\delta \right)$ algorithm to generate $p{k}_{base}={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+{\mathit{f}}_0$ and the private key $s{k}_{{\delta }^{\prime }}=s{k}_0={\mathit{s}}_0$. When $j=1$, $\mathcal{S}$ calls the KeyGen$\left(crs,\delta \right)$ algorithm to generate $p{k}_{base}={\mathit{A}}_1{\mathit{s}}_1+{\mathit{e}}_1+{\mathit{f}}_1$ and the private key $s{k}_{{\delta }^{\prime }}=s{k}_0$. $\mathcal{S}$ then sends $p{k}_{base}$ from inside to the adversary $\mathcal{A}$.

${\mathcal{S}}_3$: When $P_2$’s index bit is $j=0$, the simulator $\mathcal{S}$ instructs the adversary $\mathcal{A}$ to run the FindMess$y^{*}\left(crs,t{d}_M,p{k}_{\delta }\right)$ algorithm to obtain the hidden message branch. The adversary $\mathcal{A}$ then computes the two derived public keys $p{k}_1={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+f_0+{\mathit{v}}_0$ and $p{k}_0={\mathit{A}}_0{\mathit{s}}_0+{\mathit{e}}_0+{\mathit{f}}_0$ based on the received $p{k}_{base}$. Similarly, when $j=1$, the adversary $\mathcal{A}$ encrypts the two messages $m_0\mathrm{and}{m}_1\in \mathcal{M}$ using $p{k}_0\mathrm{and}p{k}_1$, respectively, and sends the ciphertexts to the simulator $\mathcal{S}$.

${\mathcal{S}}_4$: The simulator $\mathcal{S}$ executes the Dec$\left(crs,s{k}_{\delta },c{t}_{\mu }\right)$ algorithm in the same manner as the honest receiver $P_2$ to decrypt the message. When $j=0$, based on the hard decision ${\mathrm{MLWE}}_{n,m,k,q,p,\chi }$ problem assumption, $\mathcal{S}$ can only obtain the message $m_0$ corresponding to ${\delta }^{\prime }=0$. When $j=1$, the simulator $\mathcal{S}$ can decrypt all messages correctly because it knows the private keys corresponding to both public keys.

When the receiver $P_2$ is corrupted: First, define a static malicious adversary $\mathcal{A}$ that corrupts the receiver $P_2$ in the real protocol. Then, construct a simulator $\mathcal{S}$ that invokes the adversary $\mathcal{A}$ in the ideal world to simulate the interaction between $\mathcal{A}$ and the honest sender $P_1$. The specific workflow of simulator $\mathcal{S}$ is as follows:

${\mathcal{S}}_1$: The simulator $\mathcal{S}$ invokes the adversary $\mathcal{A}$ to generate $\left(crs,td\right)$, which involves uniformly randomly sampling the matrix $\mathit{A}$ and the vector $\mathit{v}$. When the honest participant $P_1$ initiates an inquiry, the simulator $\mathcal{S}$ returns the corresponding $crs$ to the inquired party while keeping the trapdoor $td$ secret.

${\mathcal{S}}_2$: The simulator $\mathcal{S}$ invokes the adversary $\mathcal{A}$ to run the TKeyGe${\mathit{n}}^{*}\left(crs,td\right)$ algorithm to generate $\left(pk,s{k}_0,s{k}_1\right)$ and then sends $pk$ to the honest participant $P_1$. Finally, $\mathcal{S}$ keeps $\left(pk,s{k}_0,s{k}_1\right)$.

${\mathcal{S}}_3$: The simulator $\mathcal{S}$ invokes the Enc$\left(crs,pk,\mu \in \left\{0,1\right\},m_{\mu }\right)$ algorithm to encrypt the message and obtain the ciphertext $c{t}_{\mu \in \left\{0,1\right\}}$. It then sends $c{t}_{\mu \in \left\{0,1\right\}}$ to the adversary $\mathcal{A}$.

${\mathcal{S}}_4$: The simulator $\mathcal{S}$ invokes the adversary $\mathcal{A}$ to decrypt the ciphertext $c{t}_{\mu \in \left\{0,1\right\}}$ using the saved $\left(s{k}_0,s{k}_1\right)$. According to the ${\mathrm{MLWE}}_{n,m,k,q,p,\chi }$ assumption, the simulator $\mathcal{S}$ can only decrypt the ciphertext corresponding to the ${\mathcal{A}}^{\prime }s$ choice bit when $j=0$. Conversely, when $j=1$, the simulator $\mathcal{S}$ can decrypt all messages correctly. □

By using the corresponding parameters $\sigma \ge \omega \left(\sqrt{logm}\right)$ and $(B+B^{\prime })·\sigma ·\sqrt{m}=O\left(q\right)$ [38,39,40,41] and relying on the approximate correctness property [41] of the rounding function, we ensure that the CCOT protocol constructed with the dual-mode encryption framework based on the difficult MLWE problem satisfies the decryption correctness. The literature [32] reduces the MLWE problem with a polynomial ring algebra structure, which is more complex than the standard-form LWE problem, to the (approximate) shortest independent vector problem (SIVP) on the module lattice. Compared to the standard-form LWE problem, the MLWE problem has a stricter security assumption based on the module lattice. Because the module lattice combines the properties of the standard and ideal lattices, it makes the MLWE problem more difficult to solve. Therefore, our CCOT protocol, based on the hard MLWE problem assumption, offers a higher security level and performance advantages compared to the CCOT protocol based on the hard standard form LWE problem assumption [28].

6. Efficiency Analysis

For a single execution of the protocol transmitting two messages $m_0,m_1\in \mathcal{M}$, this section analyses the approximate efficiency of the protocol in terms of the approximate counts of all of the participants’ computational complexity (including the modulo multiplication ⊙, addition +, and XOR ⊕ operations) and communication complexity (based on the number of elements sent). When analysing the complexity, $z=s$ is set, and according to the literature [33], the dimension k is typically set to 2, which is sufficient to ensure security under $2^{100}$ attacks by the adversary. The literature [34] states that the computational complexity of the fast Fourier transform (FFT) for one polynomial multiplication is $O\left(3nlogn+n\right)$. The specific efficiency analysis of the protocol is shown in

Table 2. Complexities of the protocol phases.

Phases of the Protocol	Computational Complexity	Communication Complexity
The setup phase	$O\left(m\left(3nlogn+n\right)\right)\left(\odot \right),O\left(m\right)\left(+\right)$	$O\left(mn\right)\left({\mathbb{Z}}_q\right)$
Key generation	$O\left(m\left(3nlogn+n\right)\right)\left(\odot \right),O\left(m\right)\left(+\right)$	$O\left(mn\right)\left({\mathbb{Z}}_q\right)$
Encryption operation	$O\left(m\left(3nlogn+n\right)\right)\left(\odot \right),O\left(m\right)\left(+\right),$ $O\left(n\right)\left(\oplus \right)$	$O\left(n\right)\left({\mathbb{Z}}_q\right),$  $O\left(n\right)\left({\mathbb{Z}}_2\right)$
Decryption operation	$O\left(3nlogn+n\right)\left(\odot \right),O\left(n\right)\left(\oplus \right)$	-

.

The computational complexity is as follows: In the setup phase, the receiver $P_2$ generates the CRS, which requires a total of $km$ times ⊙ and m times + operations. In the transmission phase, $P_2$ generates the key, requiring $km$ times ⊙ and $3m$ times + operations. During the encryption phase, the sender $P_1$ encrypts the two messages, which requires $2m\left(k+1\right)$ times ⊙, m times +, and $2n$ times ⊕ operations. In the decryption phase, $P_2$ decrypts the messages with $2k$ times ⊙ and $2n$ times ⊕ operations. Therefore, the computational complexity of the protocol is $O\left(m\left(3nlogn+n\right)\right)\left(\odot \right),O\left(m\right)\left(+\right),\mathrm{and}O\left(n\right)\left(\oplus \right)$.

The communication complexity is as follows: In a single execution of the protocol, during the setup phase, the receiver $P_2$ sends $mn\left(k+1\right)$ elements of ${\mathbb{Z}}_q$ to the sender $P_1$. In the transmission phase, $P_2$ needs to send $mn$ elements of ${\mathbb{Z}}_q$ to $P_1$ during key generation, and in the encryption process, $P_1$ sends a total of $2kn$ elements of ${\mathbb{Z}}_q$ and $2n$ bits of ${\mathbb{Z}}_2$ to $P_2$. Therefore, the communication complexity of the protocol is $O\left(n\left(m+1\right)\right)\left({\mathbb{Z}}_q\right),\mathrm{and}O\left(n\right)\left({\mathbb{Z}}_2\right)$.

At present, the lattice-based CCOT protocol is constructed solely based on the hard LWE problem assumption, as seen in the protocol proposed in the literature [28]. Therefore, the comparative efficiency analysis focuses only on the protocol in this paper and the protocol presented in the literature [28], as shown in

Table 3. Comparison summary for different protocols.

Protocol	The Literature [28]	Ours
Problem	LWE	MLWE
Security model	CRS	CRS
Communication round	1	1
Computational complexity	$O\left(\left(m+1\right)n^2+mn\right)\left(\odot \right),$  $O\left(mn\right)\left(+\right),O\left(n^2\right)\left(\oplus \right)$	$O\left(m\left(3nlogn+n\right)\right)\left(\odot \right),$  $O\left(m\right)\left(+\right),O\left(n\right)\left(\oplus \right)$
Communication complexity	$O\left(n^2+mn\right)\left({\mathbb{Z}}_q\right),$  $O\left(n^2\right)\left({\mathbb{Z}}_2\right)$	$O\left(n\left(m+1\right)\right)\left({\mathbb{Z}}_q\right),$  $O\left(n\right)\left({\mathbb{Z}}_2\right)$

.

Both the protocol of this paper and the protocol in the literature [28] achieve security under the CRS model. Maintaining optimal one-round communication, the protocol of this paper, based on the MLWE assumption, reduces security to the SIVP problems on the modular lattice, compared to the LWE-based protocol in the literature [28]. Our protocol guarantees security for the transmission of messages $m_0,m_1\in \mathcal{M},\mathcal{M}\subseteq {\left\{0,1\right\}}^n$ and demonstrates better computational efficiency and lower communication cost, saving at least a factor of n in computation and communication overheads compared to the LWE-based CCOT protocol in the literature [28].

7. Conclusions

In this paper, we propose an MLWE-based CCOT protocol the security of which relies on the hard MLWE problem assumption, which can resist quantum attacks. The protocol demonstrates superior computational efficiency and lower communication overhead. We enhance the original dual-mode encryption system by leveraging the MLWE problem and introducing compression and decompression techniques to further reduce the size of the public key and ciphertext. This results in the construction of a new MLWE-based dual-mode encryption framework, which replaces the LWE-based dual-mode encryption system as an intermediate scheme for the MLWE-based CCOT protocol. Compared to the LWE-based CCOT protocol, due to the MLWE-based problem, our protocol allows for smaller encryption parameters while maintaining security and performs multi-bit encryption on messages, thereby improving the communication efficiency. Additionally, the polynomial modulo multiplication operation can be optimized using FFT, enhancing the computational efficiency of the protocol.