# Oblivious Transfer via Lossy Encryption from Lattice-Based Cryptography

Authors: Zengpeng Li; Can Xiang; Chengyu Wang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Authentication is the first defence line to prevent malicious entities to accesssmart mobile devices (or SMD). Essentially, there exist many available cryptographic primitives to design authentication protocols.Oblivious transfer (OT) protocol is one of the important cryptographic primitives to design authentication protocols. The first lattice-based OT framework under universal composability (UC) model was designed by dual mode encryption and promoted us to find an alternative efficient scheme. We note that “lossy encryption” scheme is an extension of the dual mode encryption and can be used to design UC-secure OT protocol, but the investigations of OT via lossy encryption over the lattice are absent. Hence, in order to obtain an efficient authentication protocol by improving the performance of the UC-secure OT protocol, in this paper, we first design a multibit lossy encryption under the decisional learning with errors (LWE) assumption and then design a new variant of UC-secure OT protocol for authenticated protocol via lossy encryption scheme. Additionally, our OT protocol is secure against semihonest (static) adversaries in the common reference string (CRS) model and within the UC framework.


---

## Body

## 1. Introduction

Oblivious transfer (OT) is an important cryptographic primitive which can be used for designing secure multiparty computing and privacy-preserving schemes, such as authenticated key exchange and password-based authentication key exchange (PAKE) [1]. Apparently, authentication is the first line of defence to prevent unauthorized access from illegitimate entities (including both devices and users). Very recently, the issues of privacy-preserving forsmart mobile devices (SMD),Internet of things (IoTs),wireless sensor networks (WSNs), andcloud storage auditing are arousing the public attention [2–4]. In this case, it is becoming more important to protect the private information for mobile computing environments by utilizing the technique of authentication [5, 6]. However, the literature which focuses on the problem of how to use the basic cryptographic primitive to design authentication protocols is relatively few and the research of improving the performance of the primitives is fewer. Thus, to design the efficient authentication protocols in the future, this paper focuses on how to improve the performance of universal composable- (UC-) secure OT protocol via lattice-based cryptography.To our knowledge,OT protocol was originally proposed by Rabin [7]. Since then various cryptography schemes and protocols are designed by using OT, e.g., [1, 8]. Informally speaking, there exist two players (the sender S and the receiver R) in OT protocol. On the one hand, the sender can send two (or more) values to the receiver. However, the sender does not know which value will be received by the receiver, and the receiver only knows the received value and remains oblivious to the other values. In a word, they are oblivious to other’s true behaviour.Importantly, Gertner et al. [9] pointed out the relationship between the public key encryption (PKE) scheme and the OT protocol at FOCS’00. In some indistinguishability against chosen plaintext attack (IND-CPA) secure PKE schemes, if the public key generated by the key generation algorithm is indistinguishable from the public key sampled from a uniform distribution, then we can use the PKE scheme to design an OT protocol [9]. In this setting, Peikert-Vaikuntanathan-Waters (PVW) [10] has constructed anefficient, universally composability and generally realizableOT via “dual mode encryption” underworst-case lattice assumption (LWE) at CRYPTO’08. Loosely speaking, there are two types of public key in “dual mode encryption”. One type is injective keys; it is real public key and behaves normally. The other one is “lossy” or “messy” key, it is lossy public key, and it loses some information of the plaintext. Moreover, there exist two important properties for the dual mode encryption. The first one is statistically close; namely, the distributions of ciphertext for any two plaintexts under a lossy key are statistically close. The second one computationally indistinguishable; namely, the injective key is computationally indistinguishable from the lossy key. (Importantly, no efficient adversary can tell the difference between normal keys and lossy keys.)Along with this line, the notation of “lossy encryption” was proposed by Bellare, Hofheinz, and Yilek (BHY) [11] on EUROCRYPT’09. Actually, the lossy encryption is an extension of the meaningful/meaningless encryption [12] and dual mode encryption [10]. In a nutshell, a “lossy” (or “messy” in [10]) cryptosystem is one which also has two modes according to two types of public keys. Concretely,(1) In the normal mode, the ciphertext is generated by encrypting the plaintext under an injective key.(2) In the lossy (or “messy”) mode, the ciphertext is independent of the plaintext. Actually, the operability property was proposed by [11]; they basically can open a ciphertext generated under a lossy key for any plaintext by adopting a possibly inefficient algorithm. Meanwhile, the injective key is computationally indistinguishable from the lossy key. Actually, our work is along this line and we embark on this question:How to design a (string)OTprotocol via multibit lattice-based “lossy encryption” rather than “dual mode encryption”?To solve this issue, we note that, after the polynomial time solvers in the nonclassical quantum computation model was pointed out by Shor [13] for discrete logarithm and integer factorization, most researchers seek to find the various alternative computational assumption; thus lattice-based (e.g., learning with errors, LWE) cryptography draws attention. Over the last decade, lattice has emerged as a very attractive foundation separately for cryptography. Specially, Regev scheme [14] and Gentry-Peikert-Vaikutanathan (GPV, a.k.a., dual Regev) scheme [15] are important lattice-based schemes to remain secure even against quantum computer attacks.From the above observations and inspired by the work of Peikert et al. [10], we still work along this line and construct a multibit LWE-based lossy encryption scheme which has two types of public keys.


### 1.1. Our Contributions and Techniques Overview

Although many would considerOT protocol a breakthrough for multiparty computation, nowadays, OT protocols are plagued by several well-known pain-points among which performance (string OT) and security (postquantum attacks) are perhaps the most visible and most often debated points. However, most existing OT protocols adopt a variety of standard number-theoretic assumptions; only a few works focus on designing the protocol underworst-case lattice assumption such as [10, 16, 17]. Here we fill in some of the missing details in the high-level description.(1)
We use the lossy encryption scheme to replace the dual mode encryption, then we design theOT protocol via lossy encryption over the lattice. More concretely, we note that, Peikert et al. [10] proposed the framework of OT protocol by using dual mode cryptography. Actually, the lossy encryption is an extension of the meaningful/meaningless encryption [12] and dual mode encryption [10] and has the obvious property of two types of public keys. The crux of this issue is how to obtain multibit lossy encryption scheme. In this paper, we constructlossy encryption via multibit Gentry-Peikert-Vaikuntanathan (GPV, a.k.a., dual Regev scheme), i.e., MGPV scheme. In particular, the public key in MGPV with many LWE instances rather than a simple matrix of LWE instance.(2)
Moreover, we design a multibit public key encryption scheme (i.e.,MGPV scheme) by following the methodology of Li et al. [18]. Actually, the semantically secure multibit public key encryption scheme via subset sum problem (SSP) proposed by Lyubashevsky et al. [16] and multiple secrets Gentry-Sahai-Waters scheme via LWE assumption proposed by Li et al. [19] promoted us to explore the functions of the public key with a sequence of LWE instances. Importantly, the public matrix A contains many LWE instances, each one is used to protect the secret key. In this setting, the decrypter can decrypt the plaintext in a bit-by-bit manner.(3)
Lastly, we attempt to explore the potential application of our UC-secure OT protocol for PAKE in SMDs. To our knowledge, PAKE is an important tool to design authentication protocol, which can help SMDs to enable adequate user authentication and prevent unauthorized use of an unattended and lost, etc. Inspired by the OT-based PAKE [1], extending our multibit OT protocol via lossy encryption to multibit PAKE is a natural result. This solution is aimed at helping us apply SMDs for authentication and other security services.


### 1.2. Paper Organization

In Section2 we formally define and present some related notations. In Section 3 we describe our multibit encryption scheme (hereafter MGPV) via LWE assumption. In Section 4 we describe our lossy encryption scheme (hereafter LE) via MGPV scheme. In Section 5 we describe a oblivious transfer protocol via the constructed LE scheme. In Section 6, we explore the potential application PAKE in SMDs. Finally, we give a conclusion in Section 7.


## 1.1. Our Contributions and Techniques Overview

Although many would considerOT protocol a breakthrough for multiparty computation, nowadays, OT protocols are plagued by several well-known pain-points among which performance (string OT) and security (postquantum attacks) are perhaps the most visible and most often debated points. However, most existing OT protocols adopt a variety of standard number-theoretic assumptions; only a few works focus on designing the protocol underworst-case lattice assumption such as [10, 16, 17]. Here we fill in some of the missing details in the high-level description.(1)
We use the lossy encryption scheme to replace the dual mode encryption, then we design theOT protocol via lossy encryption over the lattice. More concretely, we note that, Peikert et al. [10] proposed the framework of OT protocol by using dual mode cryptography. Actually, the lossy encryption is an extension of the meaningful/meaningless encryption [12] and dual mode encryption [10] and has the obvious property of two types of public keys. The crux of this issue is how to obtain multibit lossy encryption scheme. In this paper, we constructlossy encryption via multibit Gentry-Peikert-Vaikuntanathan (GPV, a.k.a., dual Regev scheme), i.e., MGPV scheme. In particular, the public key in MGPV with many LWE instances rather than a simple matrix of LWE instance.(2)
Moreover, we design a multibit public key encryption scheme (i.e.,MGPV scheme) by following the methodology of Li et al. [18]. Actually, the semantically secure multibit public key encryption scheme via subset sum problem (SSP) proposed by Lyubashevsky et al. [16] and multiple secrets Gentry-Sahai-Waters scheme via LWE assumption proposed by Li et al. [19] promoted us to explore the functions of the public key with a sequence of LWE instances. Importantly, the public matrix A contains many LWE instances, each one is used to protect the secret key. In this setting, the decrypter can decrypt the plaintext in a bit-by-bit manner.(3)
Lastly, we attempt to explore the potential application of our UC-secure OT protocol for PAKE in SMDs. To our knowledge, PAKE is an important tool to design authentication protocol, which can help SMDs to enable adequate user authentication and prevent unauthorized use of an unattended and lost, etc. Inspired by the OT-based PAKE [1], extending our multibit OT protocol via lossy encryption to multibit PAKE is a natural result. This solution is aimed at helping us apply SMDs for authentication and other security services.


## 1.2. Paper Organization

In Section2 we formally define and present some related notations. In Section 3 we describe our multibit encryption scheme (hereafter MGPV) via LWE assumption. In Section 4 we describe our lossy encryption scheme (hereafter LE) via MGPV scheme. In Section 5 we describe a oblivious transfer protocol via the constructed LE scheme. In Section 6, we explore the potential application PAKE in SMDs. Finally, we give a conclusion in Section 7.


## 2. Preliminaries

Below, we introduce some necessary notations.


### 2.1. Notation

Throughout our paper, vectors is denoted by bold lower-case letters, e.g.,a, and matrices were denoted by upper-case letters, e.g., A. The matrix B={b1,⋯,bn}∈Rn contains n linearly independent vectors. The basis B can be used to generate the n-dimensional lattice Λ as follows:(1)Λ=LB=Bc=∑i∈nci·bi:c∈Zqn.Below we give a variant of leftover hash lemma.Lemma 1 (see [20] Lemma 2.1).
We first denote the statistical distance between the distributionA and B by Δ(A,B). If the parameters satisfy the following conditions, i.e., λ∈Z, n∈N, q∈N, m≥nlog⁡q+2λ, A is a uniform random matrix over Zqm×n, r←R{0,1}m and y←RZqn. Then we have that (2)ΔA,AT·r,A,y≤2-λ


### 2.2. Gaussian Distribution

We denote the truncated discrete Gaussian distribution overZm with parameter σ by DZqm,σ and let DZm,σ be m·σ-bounded.Remark 2.
If defineDσ←Z⇒e←Dσ,e≤σ, then Dσm←Zm⇒e←Dσm,e≤m·σ. Throughout the paper, we suppose σ≥2m. Therefore, if e←Dσm then we have, on average, that e≈m·σ.


### 2.3. Learning with Errors

Definition 3 (LWE distribution).
TheLWE distribution As,χ over Zqn×Zq is sampled by sampling a∈Zqn uniformly, choosing e←χ, and outputting (a,b=〈s,a〉+e(modq)) for a secret vector s∈Zqn.Below we describe the decision version.Definition 4 (decision-LWEn,q,χ,m).
Sampledm samples (ai,bi) independently over Zqn×Zq. For every sample (ai,bi) the following distributions are indistinguishable (with nonnegligible advantage). (1)(ai,bi)←As,χ, (2)(ai,bi) sampled from the uniform distribution.


### 2.4. Inhomogeneous Short Integer Solution

In this subsection, we review the Inhomogeneous Short Integer Solution (ISIS) problem as follows.Definition 5 (ISIS).
Given an integerq, a public matrix A∈Zqn×m, a vector b∈Zqn, and a real β, then find an integer vector e∈Zm such that Ae=b(modq) and e2≤β.


### 2.5. Lossy Encryption

Definition 6 ((perfectly) lossy encryption [21]).
An encryption scheme(KeyGen,Enc,Dec) is called “lossy” if there exists a probabilistic polynomial time (PPT) algorithm KeyGenlossy that takes 1λ as input and outputs pklossy such that (i)
the distributionpklossy is computationally indistinguishable from a public key pk generated by Gen(1λ);(ii)
for every two equal-length messagesm0 and m1, the distributions Enc(pklossy,m0) and Enc(pklossy,m1) are identically distributed for every pklossy←KeyGenlossy(1λ).Remark 7.
If an encryption scheme is lossy then it is semantically secure.It is given by a tuple ofPPT algorithms (3)KeyGenreal,KeyGenlossy,Enc,Dec.The details are as follows:(i)
KeyGenreal(1λ,inj) takes as input a security parameter λ and outputs either the real public key along with the secret key (pkreal,sk) or the injective key.(ii)
KeyGenlossy(1λ,lossy) takes as input λ and outputs a lossy public key and ⊥ instead of sk, i.e., (pklossy,⊥).(iii)
Enc(pk,m) takes as input either pkreal or pklossy and message m and outputs a ciphertext C.(iv)
Dec(sk,C) takes as input a secret key sk and a ciphertext C and outputs either a message m or ⊥.Lemma 8 (see [15]).
If consider all but a2q-n fraction of all matrix A over Zqm×n along with any s≥ω(log⁡m) and m≥2nlog⁡q, then the distribution of uT=eT·A(modq) is statistically close to uniform over Zqn, where e~DZ,sm.Lemma 9 (see [22]).
We first denote the distributionD over Zqn with min-entropy k. If C←Zql×n is a uniform matrix and s∈Zqn×n is sampled from the distribution D for any ε>0 and l≤(k-2log⁡1/ε-O(1))/log⁡q, then the joint distribution of (C,C·s) is ε-close to the uniform distribution over Zql×n×Zql.Lemma 10 (see [22]).
Consider a distribution “Lossy” forA¯←Lossy≈cU←Zqm×n. If given s←Zqn and e←AZ,β·qm×n, there exists H~∞ε(s∣A¯,A¯·s+x)≥n for ε=negl(λ). Then the Lossy distribution is as follows:(i)
ChooseD←Zqm×k, C←Zqk×n, and Z←Dαqm×n, where α/β=negl(λ) and k·log⁡q≤n-2λ+2.(ii)
LetA¯=DC+Z.(iii)
OutputA¯.


### 2.6. The Universal Composability (UC) Framework

The UC framework first defines aPPT environment machine Z and then uses the machine to oversee the execution of a protocol in one of two worlds. The detailed description of the executions was presented by Canetti [23], and there exist two world ensembles EXECπ,A,Z and IDEALF,S,Z for real world and ideal world, respectively.Definition 11 (see [10] Def.2.1).
If there exists a simulatorS for any adversary A such that for all environments Z(4)IDEALF,S,Z≈cEXECπ,A,Z,then we can say that a protocol π is UC-realize a functionality F.


## 2.1. Notation

Throughout our paper, vectors is denoted by bold lower-case letters, e.g.,a, and matrices were denoted by upper-case letters, e.g., A. The matrix B={b1,⋯,bn}∈Rn contains n linearly independent vectors. The basis B can be used to generate the n-dimensional lattice Λ as follows:(1)Λ=LB=Bc=∑i∈nci·bi:c∈Zqn.Below we give a variant of leftover hash lemma.Lemma 1 (see [20] Lemma 2.1).
We first denote the statistical distance between the distributionA and B by Δ(A,B). If the parameters satisfy the following conditions, i.e., λ∈Z, n∈N, q∈N, m≥nlog⁡q+2λ, A is a uniform random matrix over Zqm×n, r←R{0,1}m and y←RZqn. Then we have that (2)ΔA,AT·r,A,y≤2-λ


## 2.2. Gaussian Distribution

We denote the truncated discrete Gaussian distribution overZm with parameter σ by DZqm,σ and let DZm,σ be m·σ-bounded.Remark 2.
If defineDσ←Z⇒e←Dσ,e≤σ, then Dσm←Zm⇒e←Dσm,e≤m·σ. Throughout the paper, we suppose σ≥2m. Therefore, if e←Dσm then we have, on average, that e≈m·σ.


## 2.3. Learning with Errors

Definition 3 (LWE distribution).
TheLWE distribution As,χ over Zqn×Zq is sampled by sampling a∈Zqn uniformly, choosing e←χ, and outputting (a,b=〈s,a〉+e(modq)) for a secret vector s∈Zqn.Below we describe the decision version.Definition 4 (decision-LWEn,q,χ,m).
Sampledm samples (ai,bi) independently over Zqn×Zq. For every sample (ai,bi) the following distributions are indistinguishable (with nonnegligible advantage). (1)(ai,bi)←As,χ, (2)(ai,bi) sampled from the uniform distribution.


## 2.4. Inhomogeneous Short Integer Solution

In this subsection, we review the Inhomogeneous Short Integer Solution (ISIS) problem as follows.Definition 5 (ISIS).
Given an integerq, a public matrix A∈Zqn×m, a vector b∈Zqn, and a real β, then find an integer vector e∈Zm such that Ae=b(modq) and e2≤β.


## 2.5. Lossy Encryption

Definition 6 ((perfectly) lossy encryption [21]).
An encryption scheme(KeyGen,Enc,Dec) is called “lossy” if there exists a probabilistic polynomial time (PPT) algorithm KeyGenlossy that takes 1λ as input and outputs pklossy such that (i)
the distributionpklossy is computationally indistinguishable from a public key pk generated by Gen(1λ);(ii)
for every two equal-length messagesm0 and m1, the distributions Enc(pklossy,m0) and Enc(pklossy,m1) are identically distributed for every pklossy←KeyGenlossy(1λ).Remark 7.
If an encryption scheme is lossy then it is semantically secure.It is given by a tuple ofPPT algorithms (3)KeyGenreal,KeyGenlossy,Enc,Dec.The details are as follows:(i)
KeyGenreal(1λ,inj) takes as input a security parameter λ and outputs either the real public key along with the secret key (pkreal,sk) or the injective key.(ii)
KeyGenlossy(1λ,lossy) takes as input λ and outputs a lossy public key and ⊥ instead of sk, i.e., (pklossy,⊥).(iii)
Enc(pk,m) takes as input either pkreal or pklossy and message m and outputs a ciphertext C.(iv)
Dec(sk,C) takes as input a secret key sk and a ciphertext C and outputs either a message m or ⊥.Lemma 8 (see [15]).
If consider all but a2q-n fraction of all matrix A over Zqm×n along with any s≥ω(log⁡m) and m≥2nlog⁡q, then the distribution of uT=eT·A(modq) is statistically close to uniform over Zqn, where e~DZ,sm.Lemma 9 (see [22]).
We first denote the distributionD over Zqn with min-entropy k. If C←Zql×n is a uniform matrix and s∈Zqn×n is sampled from the distribution D for any ε>0 and l≤(k-2log⁡1/ε-O(1))/log⁡q, then the joint distribution of (C,C·s) is ε-close to the uniform distribution over Zql×n×Zql.Lemma 10 (see [22]).
Consider a distribution “Lossy” forA¯←Lossy≈cU←Zqm×n. If given s←Zqn and e←AZ,β·qm×n, there exists H~∞ε(s∣A¯,A¯·s+x)≥n for ε=negl(λ). Then the Lossy distribution is as follows:(i)
ChooseD←Zqm×k, C←Zqk×n, and Z←Dαqm×n, where α/β=negl(λ) and k·log⁡q≤n-2λ+2.(ii)
LetA¯=DC+Z.(iii)
OutputA¯.


## 2.6. The Universal Composability (UC) Framework

The UC framework first defines aPPT environment machine Z and then uses the machine to oversee the execution of a protocol in one of two worlds. The detailed description of the executions was presented by Canetti [23], and there exist two world ensembles EXECπ,A,Z and IDEALF,S,Z for real world and ideal world, respectively.Definition 11 (see [10] Def.2.1).
If there exists a simulatorS for any adversary A such that for all environments Z(4)IDEALF,S,Z≈cEXECπ,A,Z,then we can say that a protocol π is UC-realize a functionality F.


## 3. Multibit GPV Scheme

This paper aims to obtain an efficient multibit OT protocol via the multibit lossy encryption. But before designing the multibit lossy encryption scheme, we first present how to obtain the building block multibit GPV scheme of the lossy encryption scheme. Below, we follow the multibit FHE framework of Li et al. [22], and we first develop the multibit GPV (MGPV) scheme. Notably, most of existing LWE-based encryption schemes focus on how to enrich the functions of the single-bit encryption that was originally proposed by Regev [14], such as chosen-plaintext-attacker (CPA) secure schemes [10, 24], chosen-ciphertext-attacker (CCA) secure schemes [25, 26], fully homomorphic encryption (FHE) schemes [20], and oblivious transfer [10, 17].Notably several recent works (such as [10, 27]) have formally shown the properties of multibit encryption. Fortunately, a multibit Regev [14] scheme was provided by Peikert et al. [10], which is called “pack ciphertext method” and was used as a crux tool to construct multibit FHE schemes [27]. Similarly, many works extended the work of Gentry-Peikert-Vaikutanathan (GPV) to the multibit scheme in the same way [18]. Along with this line, Lindner and Peikert [24] considered a new scheme under the multibit setting, where it is possible to encrypt multiple bits at one-time and makes PKE even more efficient. However, all of the mentioned schemes are constructed by a straightforward concatenation method with the inefficient performance. An important question is raised naturally.Is it possible to explore a new method to design the multiple bitsGPVencryption under theLWEassumption instead of the method of straightforward concatenation?We formally explore this important question in this section and we believe that the multibit GPV based on the public key with a sequence ofLWE instances might offer many advantages over other approaches. The main ideas behind our method to design the MGPV scheme is described in following sections.


### 3.1.MGPV Scheme

Below we describe theMGPV scheme and its properties.(i)
params←MGPV.Setup(1λ):
(1)
Takeλ as input and output the common parameter params=(n,q,χ,m,t), and let l=⌊log⁡q⌉+1. We remark that this Setup algorithm is identical to the GPV [15] scheme except that we let a parameter t be the number of secret keys.(ii)
(pk,sk)←MGPV.KeyGen(params):
(1)
Sampleei←χn×1, i∈[t] and output ski≔ei′←(Ii,-eiT)T=(0,⋯,1,⋯,0∣-ei,1,⋯,-ei,n)∈χn+t, and the i-th position is 1.(2)
Choose a matrixB←Zqm×n and compute ui=Bei∈Zqm×1, then we set A=[u1∣⋯∣ut∣B]∈Zqm×(n+t).(3)
Outputpk←A and sk←{e1′,⋯,et′}.(iii)
c←MGPV.Enc(params,pk,m):
(1)
Setm≔(m1,⋯,mt), mi∈{0,1} and define m′≔(m∣0)∈Zq1×(n+t).(2)
SamplexT=(x1T∣x2T)=(x1,1,⋯,x1,t∣x2,1,⋯,x2,n)=(x1T←χ1×t,x2T←χ1×n)∈DZ1×(n+t), then choose r←Zqm×1.(3)
Computec=AT·r+⌊q/2⌋·mT+x∈Zq(n+t)×1, where the size of ciphertext is O((n+t)log2q).(iv)
m′←MGPV.Dec(params,sk,c):
(1)
In order to make the reader understand the structure of the secret ky matrixS=(sk1,⋯,skt)∈{0,1}(n+t)×t, the detailed form of the matrix is as follows: (5)
S
=
e
1
′
,
⋯
,
e
t
′
=
1
⋯
0
⋮
⋱
⋮
0
⋯
1
-
e
1,1
⋯
-
e
t
,
1
⋮
⋱
⋮
-
e
1
,
n
⋯
-
e
t
,
n
.(2)
Then compute and output(6)c,S=AT·r+q2·mT+xT,S=q2·mT·S+xT·S=q2·m′+x1,1-x2e1,⋯,x1,t-x2etmodq.We note that the magnitude of the vector(x1,1-x2e1,⋯,x1,t-x2et) can be regarded as the form of t·(x1,i+x2T·ei) for i∈[t]. If 〈c,S〉≤t(n+1)B<q/4, then set mi=1 and otherwise set mi=0. Output m′=(m1,⋯,mt).Remark 12.
We stress that the ciphertext can be decrypted in a bit-by-bit manner. Once we have the secret key matrixS, we can choose the i-th column of S to recover the i-th bit of the plaintext. In more detail,(1)
we usei-th column vector si from S to get the i-th position bit of message;(2)
compute and output〈c,s〉=〈ATr+⌊q/2⌋m+xT,s〉=⌊q/2⌋mi+(x1,i+x2T·ei)(modq).
If〈c,S〉≤(n+1)B<q/4, then set mi=1 and otherwise set mi=0. Output m′.


### 3.2. Correctness

In this subsection, we analyze the magnitude of the noise.Lemma 13 (correctness).
Consider the decryption algorithm decrypts in a bit-by-bit manner. If the ciphertext isc=AT·r+⌊q/2⌋·mT+xT(modq)∈Zq(m+t)×1 under the i-th column secret key ski=ei′∈Zq(m+t)×1, then we have that (7)c,ei=q2·mi+x1,i+x2T·ei=q2·mi+errormodq,with error<E≤⌊q/2⌋/2. Hence, for the secret key matrix sk=S∈Zq(m+t)×t, we get the following result: (8)c,S=q2·m′+xT·S=q2·m′+t·errormodq,with t·error<t·E≤⌊q/2⌋/2. Hence, there exists m′←Dec(sk,m).Proof.
Consider the following parametersxT=(x1T←χ1×t,x2T←χ1×m) and ∀xi←χ, xi≤B (where B≪q). Thus, we can get (9)c,ei′=rT·AT·ei′+q2mT·ei′+xT·ei′=0+q2·mi+x1,i+x2T·ei=q2·mi+errorDmodq,with errorD≤x1,i+x2T·ei≤B+mB≤ED; the norm of x1,i+x2T·ei is bounded by (m+1)B, where ED is denoted as the norm of error elements.
Hence, we can easily obtain the resultt·errorD≤t·ED for 〈c,S〉=⌊q/2⌋·m′+t·errorD(modq).


### 3.3. Security

Theorem 14.
Regarding the following two distributionsX and Y, (i)
the distributionX is denoted as matrices [u1∣⋯∣ut∣B] on m×(t+n), where B∈Zqm×n is a uniform matrix for all 1≤i≤t, ui=Bei(modq), and ei is sampled from χn.(ii)
the distributionY is denoted as the uniform on Zqm×(t+n).
If the(n,q,χ,m)-ISIS assumption is hard for the parameters m>n∈N, q∈N, χ←Z, and t=O(log⁡(n)) being an integer, then the distribution X is computationally indistinguishable from Y.The following theorem formalizes the key result used to show the security ofMGPV scheme. We show the scheme is IND-CPA secure by using Theorem 14.Theorem 15.
If theISIS assumption and LWE assumption hold for the parameters params=(n,q,χ,m,t), then the MGPV scheme is IND-CPA-secure.Proof.
The high-level proof is as follows:(i)
Firstly, armed with theISIS assumption, the matrix A=[u1,⋯,ut∣B]∈Zqn×(m+t) is computationally indistinguishable from a uniform random matrix by applying the Theorem 14.(ii)
Secondly, the matrixAr+e is indistinguishable from uniform under the LWE assumption and the leftover hash lemma.
This concludes the proof of the theorem.


### 3.4. Oblivious Transfer viaMGPV

In this subsection, we instantiate theOT protocol under the LWE assumption that provides security for the sender against an honest-but-curious receiver and security for the receiver against a cheating sender.OT protocol contains two phases, as shown in Figure 1, the initialization phase (i.e., Setup) and the transfer phase (i.e., Transfer) [10].(i)
TheSetup phase: thesenderS owns 2 elements m0 and m1. Thereceiver samples a choice bit b∈{0,1}.(ii)
TheTransfer phase:
(1)
At the beginning of each transfer, thereceiverR has an input choice bit b, and he invokes the KeyGen(·) algorithm and outputs a pair (pkb,skb), then he draws a vector as pk1-b from the distribution Zqn×(n+t), then R sends the pair (pk0,pk1) to thesenderS.(2)
Upon receiving the pair(pk0,pk1), thesenderS inputs 2 elements m0 and m1 and invokes the Enc(·) algorithm to encrypt them under the pk0,pk1, respectively, then outputs the ciphertext c0 and c1 and sends back to the receiver R.(3)
Upon receiving the pairc0,c1, the receiver invokes the Dec(·) algorithm and outputs mb.Figure 1
FunctionFCRSD, ∗ [10].


### 3.5. Security

TheOT protocol is a simple application of MGPV scheme.Theorem 16 (see [16] Theorem 5.2).
We say that theOT protocol is secure for the receiver if the LWEn,q,m,χ problem is hard.Proof.
The above security proof is simple, so we omit further details and recommend the reader to find further details from the proof of Theorem 5.2 in Lyubashevsky et al. at TCC’10 [16].Theorem 17 (see [16] Theorem 5.3).
We say that the aboveOT protocol is secure for the sender against an honest-but-curious receiver, if the LWEn,q,m,χ assumption is hard for the input message length t of the sender.Proof.
The detailed proof can be found from the Theorem 5.3 in Lyubashevsky et al. at TCC’10 [16].


## 3.1.MGPV Scheme

Below we describe theMGPV scheme and its properties.(i)
params←MGPV.Setup(1λ):
(1)
Takeλ as input and output the common parameter params=(n,q,χ,m,t), and let l=⌊log⁡q⌉+1. We remark that this Setup algorithm is identical to the GPV [15] scheme except that we let a parameter t be the number of secret keys.(ii)
(pk,sk)←MGPV.KeyGen(params):
(1)
Sampleei←χn×1, i∈[t] and output ski≔ei′←(Ii,-eiT)T=(0,⋯,1,⋯,0∣-ei,1,⋯,-ei,n)∈χn+t, and the i-th position is 1.(2)
Choose a matrixB←Zqm×n and compute ui=Bei∈Zqm×1, then we set A=[u1∣⋯∣ut∣B]∈Zqm×(n+t).(3)
Outputpk←A and sk←{e1′,⋯,et′}.(iii)
c←MGPV.Enc(params,pk,m):
(1)
Setm≔(m1,⋯,mt), mi∈{0,1} and define m′≔(m∣0)∈Zq1×(n+t).(2)
SamplexT=(x1T∣x2T)=(x1,1,⋯,x1,t∣x2,1,⋯,x2,n)=(x1T←χ1×t,x2T←χ1×n)∈DZ1×(n+t), then choose r←Zqm×1.(3)
Computec=AT·r+⌊q/2⌋·mT+x∈Zq(n+t)×1, where the size of ciphertext is O((n+t)log2q).(iv)
m′←MGPV.Dec(params,sk,c):
(1)
In order to make the reader understand the structure of the secret ky matrixS=(sk1,⋯,skt)∈{0,1}(n+t)×t, the detailed form of the matrix is as follows: (5)
S
=
e
1
′
,
⋯
,
e
t
′
=
1
⋯
0
⋮
⋱
⋮
0
⋯
1
-
e
1,1
⋯
-
e
t
,
1
⋮
⋱
⋮
-
e
1
,
n
⋯
-
e
t
,
n
.(2)
Then compute and output(6)c,S=AT·r+q2·mT+xT,S=q2·mT·S+xT·S=q2·m′+x1,1-x2e1,⋯,x1,t-x2etmodq.We note that the magnitude of the vector(x1,1-x2e1,⋯,x1,t-x2et) can be regarded as the form of t·(x1,i+x2T·ei) for i∈[t]. If 〈c,S〉≤t(n+1)B<q/4, then set mi=1 and otherwise set mi=0. Output m′=(m1,⋯,mt).Remark 12.
We stress that the ciphertext can be decrypted in a bit-by-bit manner. Once we have the secret key matrixS, we can choose the i-th column of S to recover the i-th bit of the plaintext. In more detail,(1)
we usei-th column vector si from S to get the i-th position bit of message;(2)
compute and output〈c,s〉=〈ATr+⌊q/2⌋m+xT,s〉=⌊q/2⌋mi+(x1,i+x2T·ei)(modq).
If〈c,S〉≤(n+1)B<q/4, then set mi=1 and otherwise set mi=0. Output m′.


## 3.2. Correctness

In this subsection, we analyze the magnitude of the noise.Lemma 13 (correctness).
Consider the decryption algorithm decrypts in a bit-by-bit manner. If the ciphertext isc=AT·r+⌊q/2⌋·mT+xT(modq)∈Zq(m+t)×1 under the i-th column secret key ski=ei′∈Zq(m+t)×1, then we have that (7)c,ei=q2·mi+x1,i+x2T·ei=q2·mi+errormodq,with error<E≤⌊q/2⌋/2. Hence, for the secret key matrix sk=S∈Zq(m+t)×t, we get the following result: (8)c,S=q2·m′+xT·S=q2·m′+t·errormodq,with t·error<t·E≤⌊q/2⌋/2. Hence, there exists m′←Dec(sk,m).Proof.
Consider the following parametersxT=(x1T←χ1×t,x2T←χ1×m) and ∀xi←χ, xi≤B (where B≪q). Thus, we can get (9)c,ei′=rT·AT·ei′+q2mT·ei′+xT·ei′=0+q2·mi+x1,i+x2T·ei=q2·mi+errorDmodq,with errorD≤x1,i+x2T·ei≤B+mB≤ED; the norm of x1,i+x2T·ei is bounded by (m+1)B, where ED is denoted as the norm of error elements.
Hence, we can easily obtain the resultt·errorD≤t·ED for 〈c,S〉=⌊q/2⌋·m′+t·errorD(modq).


## 3.3. Security

Theorem 14.
Regarding the following two distributionsX and Y, (i)
the distributionX is denoted as matrices [u1∣⋯∣ut∣B] on m×(t+n), where B∈Zqm×n is a uniform matrix for all 1≤i≤t, ui=Bei(modq), and ei is sampled from χn.(ii)
the distributionY is denoted as the uniform on Zqm×(t+n).
If the(n,q,χ,m)-ISIS assumption is hard for the parameters m>n∈N, q∈N, χ←Z, and t=O(log⁡(n)) being an integer, then the distribution X is computationally indistinguishable from Y.The following theorem formalizes the key result used to show the security ofMGPV scheme. We show the scheme is IND-CPA secure by using Theorem 14.Theorem 15.
If theISIS assumption and LWE assumption hold for the parameters params=(n,q,χ,m,t), then the MGPV scheme is IND-CPA-secure.Proof.
The high-level proof is as follows:(i)
Firstly, armed with theISIS assumption, the matrix A=[u1,⋯,ut∣B]∈Zqn×(m+t) is computationally indistinguishable from a uniform random matrix by applying the Theorem 14.(ii)
Secondly, the matrixAr+e is indistinguishable from uniform under the LWE assumption and the leftover hash lemma.
This concludes the proof of the theorem.


## 3.4. Oblivious Transfer viaMGPV

In this subsection, we instantiate theOT protocol under the LWE assumption that provides security for the sender against an honest-but-curious receiver and security for the receiver against a cheating sender.OT protocol contains two phases, as shown in Figure 1, the initialization phase (i.e., Setup) and the transfer phase (i.e., Transfer) [10].(i)
TheSetup phase: thesenderS owns 2 elements m0 and m1. Thereceiver samples a choice bit b∈{0,1}.(ii)
TheTransfer phase:
(1)
At the beginning of each transfer, thereceiverR has an input choice bit b, and he invokes the KeyGen(·) algorithm and outputs a pair (pkb,skb), then he draws a vector as pk1-b from the distribution Zqn×(n+t), then R sends the pair (pk0,pk1) to thesenderS.(2)
Upon receiving the pair(pk0,pk1), thesenderS inputs 2 elements m0 and m1 and invokes the Enc(·) algorithm to encrypt them under the pk0,pk1, respectively, then outputs the ciphertext c0 and c1 and sends back to the receiver R.(3)
Upon receiving the pairc0,c1, the receiver invokes the Dec(·) algorithm and outputs mb.Figure 1
FunctionFCRSD, ∗ [10].


## 3.5. Security

TheOT protocol is a simple application of MGPV scheme.Theorem 16 (see [16] Theorem 5.2).
We say that theOT protocol is secure for the receiver if the LWEn,q,m,χ problem is hard.Proof.
The above security proof is simple, so we omit further details and recommend the reader to find further details from the proof of Theorem 5.2 in Lyubashevsky et al. at TCC’10 [16].Theorem 17 (see [16] Theorem 5.3).
We say that the aboveOT protocol is secure for the sender against an honest-but-curious receiver, if the LWEn,q,m,χ assumption is hard for the input message length t of the sender.Proof.
The detailed proof can be found from the Theorem 5.3 in Lyubashevsky et al. at TCC’10 [16].


## 4. Lossy Encryption (LE Scheme)

The notation of “lossy encryption” was proposed by Bellare-Hofheinz-Yilek (BHY) [11]. Actually, the lossy encryption is an extension of the meaningful/meaningless encryption [12] and dual mode encryption [10]. At a high level, a “lossy” (or “messy” in [10]) cryptosystem is one which also has two modes according to two types of public keys. Concretely,(1) in the normal mode, the ciphertext is generated by encrypting the plaintext under an injective key.(2) In the lossy (or “messy”) mode, the ciphertext is independent of the plaintext. Actually, the operability property was proposed by [11]; they basically allow a possibly inefficient algorithm to open a ciphertext generated under a lossy key to any plaintext. Meanwhile, the injective key is computationally indistinguishable from the lossy key.


### 4.1. Multibit Lossy Encryption Scheme

Gentry et al. [15] proposed the dual Regev scheme to design the identity-based encryption (IBE) with the random oracle. Then, Agrawal et al. [28] used it to design the IBE scheme in the standard model. In this paper, we construct the LWE-based lossy encryption from multiple bits GPV. However, the process of encryption is different from GPV. In our construction, we only sample the noise vector e one-time rather than twice AS in the GPV scheme. The concrete construction is as follows:(i)
(crs,params)←Setup(1λ):
(1)
Setm≥2n·log⁡q and secure parameter λ. Since Lemma 10, we set k·log⁡q≤n-2·λ+2, l≤(k-2log⁡1/ε-O(1))/log⁡q, q≥5rm, r≥ω(log⁡m), β≤1/(rm·ω(log⁡m), β·q>O(2·n), and α/β=negl(λ). To satisfy these requirements, q should be superpolynomial of the secure parameter λ, moreover, t as described in MGPV scheme.(2)
Outputparams≔(m,n,q,χ,k,l,t) and crs≔B, where B←Zqm×n.(ii)
(pkreal,sk)←KeyGenreal(params):
(1)
Fori∈[t], ei←χn×1, then we have that ui≔Aei∈Zqm×1. Compose all ei together, then we have that E=[e1,⋯,et]∈DZ,rn×t.(2)
Hence,pkreal≔A=[u1,⋯,ut∣B]∈Zqm×(n+t).(3)
Outputsk≔S=[I∣E] as described above.(iii)
(pklossy,⊥)←KeyGenlossy(params):
(1)
ChooseD←Zqm×k, C←Zqk×n, Z←DZ,α·qm×n, and U∈Zqm×t≔[ui′,…,ut′], where ui′←Zqm×1.(2)
Outputsk≔⊥, pklossy≔(u1′,⋯,ut′∣DC+Z).(iv)
c←Enc(pk,m):
(1)
Denotem′=[m∣0]∈{0,1}1×(n+t).(2)
Choose random vectorsr←Zqm×1, x←DZ,β·q(n+t)×l.(3)
Compute and output ciphertexts:c≔AT·r+q/2m′T+x∈Zq(n+t)×1.(v)
m′←Dec(sk,c): Compute and output: 〈c,S〉=⌊q/2⌋m+xT·S.In order to construct the oblivious transfer, we need to design a verification algorithmVerify(·) for the sender S, who is similar to the FindMessy(·) in [10], and will use the Verify(·) to verify that the public key pkσ from the receiver R is pkreal or pklossy, in more detail:(i)
b←Verify(pkσ,σ): for σ∈{0,1}≔{real,lossy}, the key generation takes a chosen decryptable branch σ∈{0,1} as a parameter, and the resulting secret key skσ corresponds to branch σ of public key pkσ. Then, we use b∈{0,1} to distinguish the two messages. Actually, messages encrypted on branch b=σ can be decrypted using skσ, while those on the other branch cannot.Below, we show that this scheme fulfills the properties of lossy encryption.Proposition 18.
Correctness on Real Keys. For all (pkreal,sk) generated by KeyGenreal(1λ) and all message m, (10)Decsk,Encpkreal,m=DecS,EncA,m′=DecS,ATr+q2m′T+x=q2·m+error the algorithm Dec(·) will get the correct message with overwhelming probability.We need to remark that, considering the parametersq≥5rm and β≤1/(rm·ω(logq)) which were denoted in [15]. Then Dec(sk,c) decrypts correctly with overwhelming probability (over the random choices of KeyGenreal(1λ) and Enc(pk,m)).Proposition 19.
Lossiness of Encryption with Lossy Keys. In more detail (11)Encpklossy,m=Encu1,…,ut∣DC+Z_,m′=u1,…,ut∣DC+Z_T·r+q2·m′+xmodq Parse public key A as pk1≔(u1,…,ut) and pk2≔B, by Lemma 10, H~∞ε(r∣B¯,B¯·r+x)≥m since m≤(λ-2log⁡1/ε-O(1))/log⁡q, and by Lemma 9, given (DC+Z)·r+x, (u1,…,ut)_T·r is ε-close to U(Zqt×1). When ε=negl(λ), (u1,…,ut)_T·r≈sU(Zqt×1) given (DC+Z)·r+x. Therefore, ∀m∈M, given (DC+Z)r+x, i.e., (12)u1,…,ut_T·r+q2·m≈sUZqt×1 for any lossy keys pklossy generated by KeyGenlossy(1λ) and any two messages m0≠m1, holds (13)Encpklossy,m0≈sEncpklossy,m1Proposition 20.
Indistinguishability between Real Public Key and Lossy Public Key. pkreal is (u1,…,ut_∣B), and pklossy is (u1′,…,ut′_∣(DC+Z)). Since m≥2nlog⁡q, by Lemma 8, sample U1←Zqm×t and U2←Zqm×n. (14)B·e1,…,B·et_∣B≈sU1,U2
Under the hardness of LWE,(U1,U2)≈c(u1,…,ut_∣DC+Z), (15)∴u1,…,ut_∣DC+Z≈cB·e1,…,B·et_∣B.i.e., pkreal and pklossy are computationally indistinguishable.


## 4.1. Multibit Lossy Encryption Scheme

Gentry et al. [15] proposed the dual Regev scheme to design the identity-based encryption (IBE) with the random oracle. Then, Agrawal et al. [28] used it to design the IBE scheme in the standard model. In this paper, we construct the LWE-based lossy encryption from multiple bits GPV. However, the process of encryption is different from GPV. In our construction, we only sample the noise vector e one-time rather than twice AS in the GPV scheme. The concrete construction is as follows:(i)
(crs,params)←Setup(1λ):
(1)
Setm≥2n·log⁡q and secure parameter λ. Since Lemma 10, we set k·log⁡q≤n-2·λ+2, l≤(k-2log⁡1/ε-O(1))/log⁡q, q≥5rm, r≥ω(log⁡m), β≤1/(rm·ω(log⁡m), β·q>O(2·n), and α/β=negl(λ). To satisfy these requirements, q should be superpolynomial of the secure parameter λ, moreover, t as described in MGPV scheme.(2)
Outputparams≔(m,n,q,χ,k,l,t) and crs≔B, where B←Zqm×n.(ii)
(pkreal,sk)←KeyGenreal(params):
(1)
Fori∈[t], ei←χn×1, then we have that ui≔Aei∈Zqm×1. Compose all ei together, then we have that E=[e1,⋯,et]∈DZ,rn×t.(2)
Hence,pkreal≔A=[u1,⋯,ut∣B]∈Zqm×(n+t).(3)
Outputsk≔S=[I∣E] as described above.(iii)
(pklossy,⊥)←KeyGenlossy(params):
(1)
ChooseD←Zqm×k, C←Zqk×n, Z←DZ,α·qm×n, and U∈Zqm×t≔[ui′,…,ut′], where ui′←Zqm×1.(2)
Outputsk≔⊥, pklossy≔(u1′,⋯,ut′∣DC+Z).(iv)
c←Enc(pk,m):
(1)
Denotem′=[m∣0]∈{0,1}1×(n+t).(2)
Choose random vectorsr←Zqm×1, x←DZ,β·q(n+t)×l.(3)
Compute and output ciphertexts:c≔AT·r+q/2m′T+x∈Zq(n+t)×1.(v)
m′←Dec(sk,c): Compute and output: 〈c,S〉=⌊q/2⌋m+xT·S.In order to construct the oblivious transfer, we need to design a verification algorithmVerify(·) for the sender S, who is similar to the FindMessy(·) in [10], and will use the Verify(·) to verify that the public key pkσ from the receiver R is pkreal or pklossy, in more detail:(i)
b←Verify(pkσ,σ): for σ∈{0,1}≔{real,lossy}, the key generation takes a chosen decryptable branch σ∈{0,1} as a parameter, and the resulting secret key skσ corresponds to branch σ of public key pkσ. Then, we use b∈{0,1} to distinguish the two messages. Actually, messages encrypted on branch b=σ can be decrypted using skσ, while those on the other branch cannot.Below, we show that this scheme fulfills the properties of lossy encryption.Proposition 18.
Correctness on Real Keys. For all (pkreal,sk) generated by KeyGenreal(1λ) and all message m, (10)Decsk,Encpkreal,m=DecS,EncA,m′=DecS,ATr+q2m′T+x=q2·m+error the algorithm Dec(·) will get the correct message with overwhelming probability.We need to remark that, considering the parametersq≥5rm and β≤1/(rm·ω(logq)) which were denoted in [15]. Then Dec(sk,c) decrypts correctly with overwhelming probability (over the random choices of KeyGenreal(1λ) and Enc(pk,m)).Proposition 19.
Lossiness of Encryption with Lossy Keys. In more detail (11)Encpklossy,m=Encu1,…,ut∣DC+Z_,m′=u1,…,ut∣DC+Z_T·r+q2·m′+xmodq Parse public key A as pk1≔(u1,…,ut) and pk2≔B, by Lemma 10, H~∞ε(r∣B¯,B¯·r+x)≥m since m≤(λ-2log⁡1/ε-O(1))/log⁡q, and by Lemma 9, given (DC+Z)·r+x, (u1,…,ut)_T·r is ε-close to U(Zqt×1). When ε=negl(λ), (u1,…,ut)_T·r≈sU(Zqt×1) given (DC+Z)·r+x. Therefore, ∀m∈M, given (DC+Z)r+x, i.e., (12)u1,…,ut_T·r+q2·m≈sUZqt×1 for any lossy keys pklossy generated by KeyGenlossy(1λ) and any two messages m0≠m1, holds (13)Encpklossy,m0≈sEncpklossy,m1Proposition 20.
Indistinguishability between Real Public Key and Lossy Public Key. pkreal is (u1,…,ut_∣B), and pklossy is (u1′,…,ut′_∣(DC+Z)). Since m≥2nlog⁡q, by Lemma 8, sample U1←Zqm×t and U2←Zqm×n. (14)B·e1,…,B·et_∣B≈sU1,U2
Under the hardness of LWE,(U1,U2)≈c(u1,…,ut_∣DC+Z), (15)∴u1,…,ut_∣DC+Z≈cB·e1,…,B·et_∣B.i.e., pkreal and pklossy are computationally indistinguishable.


## 5. OT via Lossy Encryption

In this section, inspired by David et al. [21] UC-secure OT protocol via lossy encryption using the McEliece assumption over code-based cryptography, we present an UC-secure OT protocol via lattice-based lossy encryption using LWE and ISIS assumption.


### 5.1. Our Construction: UC-SecureOT for Ideal Functionalities

Before describing our construction, we first denote the ideal functionalitiesFCRSD and FOT. In more detail, the CRS functionality FCRSD outputs a string with a fixed distribution as depicted in Algorithm 1.Algorithm 1:The CRS functionality FCRSD from [10].
F C R S D is parameterized by an algorithm D, and FCRSD can interact with parities P1,⋯,Pn. (i) Upon receiving a command (sid,Pi,Pj) from the party Pi, first let crs←D(1λ), then send the message (sid,crs) to Pi and send the message (crs,Pi,Pj) to the adversary; (ii) Upon receiving a command (sid,Pi,Pj) from the party Pj (and only Pj), then send Pj and the adversary the message (sid,crs), and halt.As shown in Algorithm2, the two-party functionality OT contains a sender S with input x0,x1 and receiver R with an input σ∈{0,1}. Importantly, the OT functionality FOT captures requirement of OT specification.Algorithm 2:The oblivious transfer functionality FOT.
F O T interacts with a receiver R and a sender S. (i) Upon receiving a command (sid,sender,x0,x1) from S, store the pair (x0,x1) for x i ∈ 0,1 l. (Notably, the length of the string l is fixed and all parties know); (ii) Upon receiving a command (sid,receiver,σ) from R, then check if (sid,sender,⋯) was previously sent and send the message (sid,xσ) to R, and send the adversary S the message (sid) and halt. Otherwise, send nothing to R.


### 5.2. Our Construction:OT from Lossy Encryption

Below we describe our main contribution, a variousOT protocol from lossy encryption in Figure 2.Figure 2
ProtocolLEmode for oblivious transfer ∗.Simulating the communication with Z : the simulator S writes every input value from Z into the input tape of the adversary A. S copies every output value written by A to his output tape. The environment Z can read the output tap.Simulating R is corrupted: S simulates the view of the receiver without considering which mode of the protocol and does the following: running the Setup algorithm in messy mode and letting (crs,t)←SetupLossy(1λ). If the parties query the FCRSmode, then it obtains the feedback (sid,crs).(i)
Once the adversaryA generates a message (sid,ssid,pkreal,pklossy), S extracts the choice bit b of the corrupted receiver and lets b←{0,1}, then S sends the command (sid,ssid,receiver,1-b) to the FOT, then FOT returns the output (sid,ssid,m1-b) to S, and S then stores it along with b.(ii)
Once the dummy simulatorS is activated by the command (sid,ssid), S then simulates the S’s behaviour, and looks up the corresponding bit b for mb and m1-b and then computes cb←Enc(pk,0t) and c1-b←Enc(pk,m1-b) and sends (sid,ssid,c0,c1) to A.Simulating S is corrupted: S does the following without considering which mode of the protocol: running the real (injective) mode KeyGen algorithm and letting (crs)←Setup(1λ). If the parties query the ideal functionality FCRSmode, then FCRSmode returns (sid,crs) to them.(i)
Once the dummyR is activated on by the command (sid,ssid), S then simulates the behaviour of R and computes (pkreal,skreal)←KeyGen(1λ,inj) and (pklossy,sklossy)←KeyGen(1λ), and then S sends (sid,ssid,pkreal,pklossy) to A and stores (sid,ssid,pkreal,skreal,sklossy).(ii)
WhenA replies with a message (sid,ssid,c0,c1), the S looks up the corresponding (pkreal,skreal) and (pklossy,sklossy), computes mb←Dec(skb,cb) for each b∈{0,1}, and returns (sid,ssid,sender,m0,m1) to F^OT.Simulating the remaining cases: once both parties are corrupted by the adversary, then S runs A. More concretely, S internally runs the S on input (sid,ssid,m0=0t,m1=0t); meanwhile, it runs the honest R on input (sid,ssid,σ=0) and honest no matter which party is corrupted. When the corresponding dummy party is activated in the ideal execution, S activates the appropriate algorithm and delivers A all messages between its internal R and S.Caim. If A corrupts R in an execution of LElossy, i.e., S in lossy mode, then we have(16)IDEALF^OT,S,Z≈sEXECLElossy,A,ZProof.
Below we give a formal proof, in more detail:(i)
The real world execution can be viewed as the proceed of the following game.
(a)
Firstly, obtaincrs by invoking the algorithm Setup1lossy(1λ).(b)
Secondly, the environmentZ can schedule subsessions arbitrarily. Notably, in each subsession,
(1)
Z can choose an arbitrary message (m0,m1) for the honest sender S;(2)
the honest senderS sends the ciphertext cb←Enc(pk,0t) for each b∈{0,1} to Z.(ii)
The ideal world execution can be viewed as the proceed of the following game:
(a)
Firstly, obtaincrs by running the algorithm Setuplossy(1λ).(b)
Secondly, the environmentZ schedules subsessions arbitrarily, in each subsession,
(1)
Z can input an arbitrary pk and the arbitrary input message (m0,m1) for the dummy sender S;(2)
S can run the verification algorithm b←Verify(crs,pkσ,σ) to Z and learn m1-b from F^OT. It then sends Z the cb←Enc(crs,pk,1-b,0t) and c1-b←Enc(crs,pk,1-b,m1-b).
We stress that the only difference between the ideal world execution and the real world execution is the generation ofcb in each subsession. But by lossy key generation in Proposition 19, hence the above two games are statistically indistinguishable.Claim. If, in an execution of LEreal (i.e., S in real mode), A corrupts S then we have(17)IDEALF^OT,S,Z≈sEXECLEreal,A,Z.Proof.
Below we give a formal proof, in more detail:(i)
The real world execution can be viewed as the proceed of the following game:
(a)
Firstly,crs←Setup1real(1λ).(b)
Secondly, the environment arbitrarily schedules some number of subsessions. In each subsession,
(1)
Z chooses an input σ for the honest R, who generates (pkσ,skσ)←KeyGen(crs,σ), and sends pkreal, pklossy to Z;(2)
thenD proceeds arbitrarily (c1,c2) to the honest R outputs Dec(crs,skσ,cσ).(ii)
The ideal world execution can be viewed as the proceed of the following game:
(a)
Firstly,(crs,t)←SetupDec(1λ).(b)
Secondly, the environment arbitrarily schedules subsessions, in each subsession,
(1)
Z outputs arbitrary σ which is not known to S;(2)
S then runs (pkreal,skreal)←KeyGen(crs,σ) and (pklossy,sklossy)←KeyGen(crs,1-σ) and sends pkreal, pklossy to Z;(3)
lastly,S receives the arbitrary ciphertext tuple (c0,c1) from Z.Remark 21.
Actually, the dummy entityR queries the value of Dec(crs,skσ,cσ) from the ideal functionality, then the simulator S provides the messages mb←Dec(crs,skb,cb).The only difference between the two games is method of the public and secret keys. The above two games are statistically indistinguishable by the lossy key generation in Proposition20.Claim. There exists the following result:(18)EXECπlossy,A,Z≈cEXECπreal,A,Z for any protocol πmode in the FCRSmode-hybrid model.Proof.
In the lossy encryption, the output ofFCRSlossy is computationally indistinguishable from FCRSreal since the indistinguishability of modes. Moreover, Z can run the protocol πmode and can receive a polynomial number of samples from either FCRSlossy or FCRSreal. Thus, the above two executions are indistinguishable by a standard hybrid argument.


### 5.3. Performance

Lattice-based cryptography has been subjecting of intense research appearing recently, bringing groundbreaking advance to the understanding of the subjacent questions. One of the main characteristics of lattice-based cryptography is worst-case to average-case reductions, which provides stronger security against quantum computer attacks. In this paper, we construct a lossy encryption scheme via a variant of multibitGPV scheme, then we construct the universal composable secure OT protocols based on LWE assumption by utilizing the lossy encryption as the building block. Below, a comparison of some related works with our scheme is provided in the Table 1.Table 1
The comparison of some related works with our scheme.
Scheme assumption message size bit Dec one-time Dec applications GPV [15] LWE/SIS 1 ✔ ✘ PKE&IBE PVW [10] LWE 1 ✘ ✔ PKE&OT LPS [16] SSP t ✔ ✔ PKE&OT  Our scheme LWE t ✔ ✔ PKE&OTAs shown in the Table1, we can easily obtain the following conclusion. We follow the methodology of Li et al. [18] and design a multibit public key encryption scheme, i.e., MGPV scheme. Importantly, the public matrix A contains many LWE instances; each one is used to protect the secret key. In this setting, the decrypter can decrypt the plaintext either in a bit-by-bit manner or in a one-time manner. Meanwhile, compared the magnitude of ciphertext of PVW scheme [10] with ours, it is easy to see the two schemes with the same magnitude of ciphertext O(logqmn). Although the public key size of PVW depends on the parameter n and our scheme’s public key size depends on m, the bit decryption of our scheme implies flexible decryption (i.e., multibit decryption), which means that our scheme is more practical in reality.


## 5.1. Our Construction: UC-SecureOT for Ideal Functionalities

Before describing our construction, we first denote the ideal functionalitiesFCRSD and FOT. In more detail, the CRS functionality FCRSD outputs a string with a fixed distribution as depicted in Algorithm 1.Algorithm 1:The CRS functionality FCRSD from [10].
F C R S D is parameterized by an algorithm D, and FCRSD can interact with parities P1,⋯,Pn. (i) Upon receiving a command (sid,Pi,Pj) from the party Pi, first let crs←D(1λ), then send the message (sid,crs) to Pi and send the message (crs,Pi,Pj) to the adversary; (ii) Upon receiving a command (sid,Pi,Pj) from the party Pj (and only Pj), then send Pj and the adversary the message (sid,crs), and halt.As shown in Algorithm2, the two-party functionality OT contains a sender S with input x0,x1 and receiver R with an input σ∈{0,1}. Importantly, the OT functionality FOT captures requirement of OT specification.Algorithm 2:The oblivious transfer functionality FOT.
F O T interacts with a receiver R and a sender S. (i) Upon receiving a command (sid,sender,x0,x1) from S, store the pair (x0,x1) for x i ∈ 0,1 l. (Notably, the length of the string l is fixed and all parties know); (ii) Upon receiving a command (sid,receiver,σ) from R, then check if (sid,sender,⋯) was previously sent and send the message (sid,xσ) to R, and send the adversary S the message (sid) and halt. Otherwise, send nothing to R.


## 5.2. Our Construction:OT from Lossy Encryption

Below we describe our main contribution, a variousOT protocol from lossy encryption in Figure 2.Figure 2
ProtocolLEmode for oblivious transfer ∗.Simulating the communication with Z : the simulator S writes every input value from Z into the input tape of the adversary A. S copies every output value written by A to his output tape. The environment Z can read the output tap.Simulating R is corrupted: S simulates the view of the receiver without considering which mode of the protocol and does the following: running the Setup algorithm in messy mode and letting (crs,t)←SetupLossy(1λ). If the parties query the FCRSmode, then it obtains the feedback (sid,crs).(i)
Once the adversaryA generates a message (sid,ssid,pkreal,pklossy), S extracts the choice bit b of the corrupted receiver and lets b←{0,1}, then S sends the command (sid,ssid,receiver,1-b) to the FOT, then FOT returns the output (sid,ssid,m1-b) to S, and S then stores it along with b.(ii)
Once the dummy simulatorS is activated by the command (sid,ssid), S then simulates the S’s behaviour, and looks up the corresponding bit b for mb and m1-b and then computes cb←Enc(pk,0t) and c1-b←Enc(pk,m1-b) and sends (sid,ssid,c0,c1) to A.Simulating S is corrupted: S does the following without considering which mode of the protocol: running the real (injective) mode KeyGen algorithm and letting (crs)←Setup(1λ). If the parties query the ideal functionality FCRSmode, then FCRSmode returns (sid,crs) to them.(i)
Once the dummyR is activated on by the command (sid,ssid), S then simulates the behaviour of R and computes (pkreal,skreal)←KeyGen(1λ,inj) and (pklossy,sklossy)←KeyGen(1λ), and then S sends (sid,ssid,pkreal,pklossy) to A and stores (sid,ssid,pkreal,skreal,sklossy).(ii)
WhenA replies with a message (sid,ssid,c0,c1), the S looks up the corresponding (pkreal,skreal) and (pklossy,sklossy), computes mb←Dec(skb,cb) for each b∈{0,1}, and returns (sid,ssid,sender,m0,m1) to F^OT.Simulating the remaining cases: once both parties are corrupted by the adversary, then S runs A. More concretely, S internally runs the S on input (sid,ssid,m0=0t,m1=0t); meanwhile, it runs the honest R on input (sid,ssid,σ=0) and honest no matter which party is corrupted. When the corresponding dummy party is activated in the ideal execution, S activates the appropriate algorithm and delivers A all messages between its internal R and S.Caim. If A corrupts R in an execution of LElossy, i.e., S in lossy mode, then we have(16)IDEALF^OT,S,Z≈sEXECLElossy,A,ZProof.
Below we give a formal proof, in more detail:(i)
The real world execution can be viewed as the proceed of the following game.
(a)
Firstly, obtaincrs by invoking the algorithm Setup1lossy(1λ).(b)
Secondly, the environmentZ can schedule subsessions arbitrarily. Notably, in each subsession,
(1)
Z can choose an arbitrary message (m0,m1) for the honest sender S;(2)
the honest senderS sends the ciphertext cb←Enc(pk,0t) for each b∈{0,1} to Z.(ii)
The ideal world execution can be viewed as the proceed of the following game:
(a)
Firstly, obtaincrs by running the algorithm Setuplossy(1λ).(b)
Secondly, the environmentZ schedules subsessions arbitrarily, in each subsession,
(1)
Z can input an arbitrary pk and the arbitrary input message (m0,m1) for the dummy sender S;(2)
S can run the verification algorithm b←Verify(crs,pkσ,σ) to Z and learn m1-b from F^OT. It then sends Z the cb←Enc(crs,pk,1-b,0t) and c1-b←Enc(crs,pk,1-b,m1-b).
We stress that the only difference between the ideal world execution and the real world execution is the generation ofcb in each subsession. But by lossy key generation in Proposition 19, hence the above two games are statistically indistinguishable.Claim. If, in an execution of LEreal (i.e., S in real mode), A corrupts S then we have(17)IDEALF^OT,S,Z≈sEXECLEreal,A,Z.Proof.
Below we give a formal proof, in more detail:(i)
The real world execution can be viewed as the proceed of the following game:
(a)
Firstly,crs←Setup1real(1λ).(b)
Secondly, the environment arbitrarily schedules some number of subsessions. In each subsession,
(1)
Z chooses an input σ for the honest R, who generates (pkσ,skσ)←KeyGen(crs,σ), and sends pkreal, pklossy to Z;(2)
thenD proceeds arbitrarily (c1,c2) to the honest R outputs Dec(crs,skσ,cσ).(ii)
The ideal world execution can be viewed as the proceed of the following game:
(a)
Firstly,(crs,t)←SetupDec(1λ).(b)
Secondly, the environment arbitrarily schedules subsessions, in each subsession,
(1)
Z outputs arbitrary σ which is not known to S;(2)
S then runs (pkreal,skreal)←KeyGen(crs,σ) and (pklossy,sklossy)←KeyGen(crs,1-σ) and sends pkreal, pklossy to Z;(3)
lastly,S receives the arbitrary ciphertext tuple (c0,c1) from Z.Remark 21.
Actually, the dummy entityR queries the value of Dec(crs,skσ,cσ) from the ideal functionality, then the simulator S provides the messages mb←Dec(crs,skb,cb).The only difference between the two games is method of the public and secret keys. The above two games are statistically indistinguishable by the lossy key generation in Proposition20.Claim. There exists the following result:(18)EXECπlossy,A,Z≈cEXECπreal,A,Z for any protocol πmode in the FCRSmode-hybrid model.Proof.
In the lossy encryption, the output ofFCRSlossy is computationally indistinguishable from FCRSreal since the indistinguishability of modes. Moreover, Z can run the protocol πmode and can receive a polynomial number of samples from either FCRSlossy or FCRSreal. Thus, the above two executions are indistinguishable by a standard hybrid argument.


## 5.3. Performance

Lattice-based cryptography has been subjecting of intense research appearing recently, bringing groundbreaking advance to the understanding of the subjacent questions. One of the main characteristics of lattice-based cryptography is worst-case to average-case reductions, which provides stronger security against quantum computer attacks. In this paper, we construct a lossy encryption scheme via a variant of multibitGPV scheme, then we construct the universal composable secure OT protocols based on LWE assumption by utilizing the lossy encryption as the building block. Below, a comparison of some related works with our scheme is provided in the Table 1.Table 1
The comparison of some related works with our scheme.
Scheme assumption message size bit Dec one-time Dec applications GPV [15] LWE/SIS 1 ✔ ✘ PKE&IBE PVW [10] LWE 1 ✘ ✔ PKE&OT LPS [16] SSP t ✔ ✔ PKE&OT  Our scheme LWE t ✔ ✔ PKE&OTAs shown in the Table1, we can easily obtain the following conclusion. We follow the methodology of Li et al. [18] and design a multibit public key encryption scheme, i.e., MGPV scheme. Importantly, the public matrix A contains many LWE instances; each one is used to protect the secret key. In this setting, the decrypter can decrypt the plaintext either in a bit-by-bit manner or in a one-time manner. Meanwhile, compared the magnitude of ciphertext of PVW scheme [10] with ours, it is easy to see the two schemes with the same magnitude of ciphertext O(logqmn). Although the public key size of PVW depends on the parameter n and our scheme’s public key size depends on m, the bit decryption of our scheme implies flexible decryption (i.e., multibit decryption), which means that our scheme is more practical in reality.


## 6. Potential Application: Password-Based Authenticated Key Exchange for Smart Mobile Devices

Nowadays, SMDs, IoTs, and WSNs within the workplace are expanding rapidly. Obliviously, these devices are becoming important tools that offer competitive advantages for the mobile workforce. But they also might be endangered by the information they can access remotely. In this case, enabling user authentication for SMDs is the first line of defence to prevent the malicious unauthorized user.Most of related works [5, 29] focus on how to use PAKE as the basic tool to achieve the authentication for SMDs. In particular, Wei et al. [5] proposed a PAKE protocol for wireless body area networks. He et al. [29] proposed an authentication protocol for mobile wireless networks with conditional privacy preservation. However, to our knowledge, related works of lattice-based PAKE for SMDs authentication are limited. Hence, in this section, we explore how to implement PAKE via our OT protocol. Because details of the design and implementation are beyond the scope of the discussion of this paper, thus, we just give a brief of description for the technical line as follows. In more detail, following the technical line of Canetti et al. [1], we first realize OT-based PKAE via LWE assumption instead of computational Diffie-Hellman (CDH) assumption and the hardness of factoring. Next, we can extend the PAKE protocol for privacy-preserving authentication schemes for SMDs.


## 7. Conclusion

In this paper, we have investigated one of the hot but hard topics in authentication of SMDs, IoTs, and WSNs. As an important building block,OT can be used for designing privacy-preserving authentication protocols. Thus, we focus on an important question how to design on an efficient UC-secure OT protocol for PAKE which can be used to achieve authentication for SMDs. However, an important question that remain is how to implement OT-based PAKE under the LWE assumption following our presented brief technical line. Meanwhile, we believe that this result enriched the postquantum OT protocols. However, it remains open to be secure against adaptive adversaries under the lossy encryption and its variants. We leave these topics for future research.



---

*Source: 5973285-2018-09-02.xml*