# Lattice Based Mix Network for Location Privacy in Mobile System

Authors: Kunwar Singh; C. Pandu Rangan; A. K. Banerjee
Journal: Mobile Information Systems
 (2015)

---

## Abstract

In 1981, David Chaum proposed a cryptographic primitive for privacy calledmix network (Mixnet). A mixnet is cryptographic construction that establishes anonymous communication channel through a set of servers. In 2004, Golle et al. proposed a new cryptographic primitive called universal reencryption which takes the input as encrypted messages under the public key of the recipients not the public key of the universal mixnet. In Eurocrypt 2010, Gentry, Halevi, and Vaikunthanathan presented a cryptosystem which is an additive homomorphic and a multiplicative homomorphic for only one multiplication. In MIST 2013, Singh et al. presented a lattice based universal reencryption scheme under learning with error (LWE) assumption. In this paper, we have improved Singh et al.’s scheme using Fairbrother’s idea. LWE is a lattice hard problem for which till now there is no polynomial time quantum algorithm. Wiangsripanawan et al. proposed a protocol for location privacy in mobile system using universal reencryption whose security is reducible to Decision Diffie-Hellman assumption. Once quantum computer becomes a reality, universal reencryption can be broken in polynomial time by Shor’s algorithm. In postquantum cryptography, our scheme can replace universal reencryption scheme used in Wiangsripanawan et al. scheme for location privacy in mobile system.


---

## Body

## 1. Introduction

In 1981, Chaum [1] proposed a cryptographic primitive for privacy calledmix network (Mixnet). A mixnet is cryptographic construction that establishes anonymous communication channel through a set of servers. One type of mixnets accepts encrypted messages under the public keys of all intermediate mixnet nodes and outputs randomly permuted corresponding plaintexts. Sender encrypts the message using public keys of the mixnet nodes in some order. Ciphertext is concatenation of n-encryptions which can be seen as building up of a n layered onion. Mixnet receives these ciphertexts from many senders. Mixnet nodes decrypt the ciphertexts using its private keys (remove outer layer of the onion) in reverse order of the encryption and permute them before forwarding to the next mixnet node. Finally, the nth mixnet node sends the messages to the respective receivers. In this way, adversary like eavesdropper (external) and mail server (internal) will find it hard to guess who is communicating. Mixnet preserves anonymous communication even with one honest mixnet node. A drawback of decryption type of mixnet is that if one server fails then mixnet fails.Choonsik et al. [2] proposed a reencryption mixnet which is robust. A reencryption mixnet accepts the encrypted massages under the public key of the mixnet. Mixnet node reencrypts the encrypted message and broadcasts this reencrypted to other mixnet nodes. There is no order of reencryption. Any mixnet node can reencrypt first and broadcast reencrypted to other nodes. Also it is not required that reencryption has to be done by all the mixnet nodes. The private key corresponding to the public key of the mixnet is distributed among all reencryption mixnet nodes [3]. Set of ciphertexts produced by last reencryption mixnet node is decrypted by group of t nodes using a (
t
,
n
) threshold scheme [3]. For privacy, it is required that adversary cannot distinguish between the reencrypted ciphertext and a random ciphertext with size being the same as the size of the reencrypted ciphertext.Both the mixnets discussed above accept encrypted messages under the public key of the mixnet. In 2004, Golle et al. [4] proposed a new cryptographic primitive called universal reencryption which takes the input as encrypted messages under the public key of the recipients not the public key of the universal mixnet. So it dispenses with the complexities of the key generation, key distribution, and key maintenance of the public key of mixnet. A mixnet based on universal reencryption is called universal mixnet. Universal mixnet takes the input as encrypted messages under the public key of the recipients. These encrypted messages are universally reencrypted and permuted by each universal mixnet node before forwarding them to the next node. Finally the output from a universal mixnet is set of universal reencrypted ciphertexts. Potential recipient must perform to decrypt all the ciphertexts to identify messages sent for them. This is a disadvantage of the universal reencryption.Lattice based cryptography has bloomed in recent years because of the following advantages.(i)
Once quantum computer comes into reality, all the cryptosystem based on prime factorization and discrete logarithm problem can be solved in polynomial time by Shor’s algorithm [5]. But till now there is no polynomial time quantum algorithm for lattice hard problems.
(ii)
Security of the cryptosystem depends on the hardness of the problem in the average case. Ajtai in his seminal result [6] has shown that lattice based cryptosystems are secure on the assumption of lattice based hard problems in the worst case. It gives strong hardness guarantee.
(iii)
Lattice based cryptosystems are efficient and parallelizable.
(iv)
Powerful primitives like fully homomorphic encryption [7] and multilinear maps [8] are realized using lattices.A drawback of lattice based cryptosystem is that it has large key size and ciphertext size. Recently Regev [9] defined the learning with error (LWE) problem and proved that it also enjoys similar average case/worst case equivalence hardness properties under a quantum reduction.Location privacy is the ability to prevent adversaries from knowing one’s current or past location [10]. Advances in mobile networks have made location information a useful information in many applications. However location information can be used to know about person’s medical condition, alternating lifestyle, and so forth. This information can be used for blackmail by malicious user. Wiangsripanawan et al. [11] proposed a protocol for location privacy in mobile system using universal reencryption [4] whose security is reducible to Decision Diffie-Hellman assumption. Once quantum computer becomes a reality, universal reencryption can be broken in polynomial time by Shor’s algorithm [5].Our Contributions. Universal reencryption has simple idea. In an additive homomorphic cryptosystem, a new ciphertext (encryption of zero) can be appended to the ciphertext. The new ciphertext can be used to reencrypt (change the encryption factor) the ciphertext such that the reencrypted ciphertext and the ciphertext decrypt to the same plaintext because, in an additive homomorphic, E
(
M
+
0
)
=
E
(
M
)
+
E
(
0
).In Eurocrypt 2010 Gentry, Gentry et al. [12] presented a cryptosystem which is an additive homomorphic and a multiplicative homomorphic for only one multiplication. In MIST 2013, Singh et al. [13] presented lattice based universal reencryption scheme using learning with error (LWE) problem based on [12]. In this paper, we have improved Singh et al.’s scheme [13] in terms of ciphertext size and computational cost using Fairbrother’s idea [14]. The idea is simple: ciphertext in scheme [13] has two parts and second part of the ciphertext is encryption of zero. Larger files can be split into many segments and the second part of the ciphertext (encryption of zero) can be made the same for all the segments. By this way, size of the ciphertext is reduced by approximately half and it also reduces the computational cost.In post quantum cryptography, our scheme can replace universal reencryption scheme used in Wiangsripanawan et al. [11] protocol for location privacy in mobile system.Paper Outline. Rest of the paper is organized as follows. In Section 2, we give some preliminaries including security models and hard problems. In Section 3, we describe different types of mixnet. We describe GHV public key cryptosystem [12] in Section 4. In Section 5, we review Singh et al.’s scheme [13]. In Section 6, we give our improved construction and in Section 7 we give conclusion and related open problems.


## 2. Preliminaries

### 2.1. Notation

We denote[
j
]
=
{
0,1
,
…
,
j
}, set of real numbers by R and the set of integers by Z. We assume vectors to be in column form which are written using small letters, for example, x. Matrices are written as capital letters, for example, X. We denote R
←
ψ
β
(
q
)
q
m
×
m as matrix R whose elements are chosen from the Gaussian distribution ψ
β over Z
q and S
←
Z
q
n
×
m as matrix S whose elements are chosen uniformly over Z
q. S denotes the Euclidean norm of the longest (maximum Euclidean norm) vector in matrix S; that is, S
∶
=
ma
x
i
s
i for 1
≤
i
≤
k.We say thatnegl
(
n
) is a negligible function in n if it is smaller than the inverse of any polynomial function in n for sufficiently large n.


### 2.2. Universal Reencryption Scheme (URe)

Universal Reencryption Scheme consists of four algorithms [4]. We denote M, C, and R as message space, ciphertext space, and set of encryption factors, respectively.Universal KeyGen
(
n
). On the input of a security parameter n, this algorithm outputs the public key pk and secret key sk pair.Universal Encryption
(
pk
,
m
,
r
). On the input of public key pk, a message m
∈
M, and an encryption factor r
∈
R, this algorithm outputs a ciphertext C
∈
C.Universal Decryption
(
C
,
sk
). On the input of a secret key sk and a ciphertext C, this algorithm outputs message m.Universal Reencryption
(
C
,
r
). On the input of a ciphertext C and reencryption factor r
∈
R, but no public key, this algorithm outputs ciphertext C
′ where C
′
∈
C.


### 2.3. Universal Semantic Security Model for Universal Reencryption Scheme (IND-URe-CPA)

Universal security model is variant of semantic security model and is adapted from [4]. In this model, adversary is allowed to construct universal ciphertexts under randomly generated public key pk. The challenger reencrypts the ciphertext. The goal of the adversary is to distinguish between the reencrypted ciphertext and the random ciphertext with the size of the random ciphertext being the same as size of the universally reencrypted ciphertext. Here, security model is defined using the following game played between the challenger and an active adversary.KeyGen. The challenger runs the key generation algorithm and gives public parameters to the adversary.Challenger. The adversary submits messages m
∈
M and r
∈
R (adversary can construct ciphertext). Challenger sets C
←
Universal
Encryption
(
m
,
r
,
pk
) and chooses a random bit b
∈
{
0,1
} and a random ciphertext C with the size of the random ciphertext being the same as size of the universally reencrypted ciphertext. If b
=
0, it assigns the challenge ciphertext to C
*
=
Universal
Reencryption
(
C
,
r
′
). If b
=
1, it assigns the challenge ciphertext to C
*
=
C. Challenger sends challenge ciphertext C
* to the adversary.Guess. The adversary outputs a guess b
′
∈
{
0,1
} and wins the game if b
′
=
b.An IND-URe-CPA adversary is referred to as an adversaryA. We define the advantage of the adversary A in attacking universal reencryption scheme ξ as Ad
v
ξ
,
A
(
n
)
=
|
Pr
⁡
[
b
=
b
′
]
-
1
/
2
|.Definition 1.
One says that universal reencryption schemeξ is universal semantic secure if for all probabilistic polynomial time adversaries A, one has Ad
v
ξ
,
A
(
n
) which is a negligible function.


#### 2.3.1. Semantically Secure Elgamal Cryptosystem [15]

Semantically secure Elgamal cryptosystem consists of three algorithms.Setup. Two primes p and q are randomly selected such that p
=
2
q
+
1. Pick a random generator h
∈
Z
p and set g
=
h
2
(
mod
⁡
p
). g is generator of subgroup G (Schnorr group) of size q. Message m is also element of subgroup G. Since g
∈
Q
R
p so m
∈
Q
R
p (Quadratic residue modulo p). Pick a random number x
∈
Z
p
-
1 as private key and public key y
=
g
x
(
mod
⁡
p
).Encryption. To encrypt a message m
∈
G, sender picks a random number r
∈
Z
p
-
1 and computes a ciphertext pair as follows:c
1
=
g
r
mod
⁡
p
andc
2
=
y
r
m
(
mod
⁡
p
). Output ciphertext C
=
(
c
1
,
c
2
).Decryption. To decrypt a ciphertext (
c
1
,
c
2
), receiver computes m
=
c
2
/
c
1
x
(
mod
⁡
p
).


#### 2.3.2. Homomorphic Encryption

A encryption scheme is multiplicative homomorphic encryption scheme if encryption ofx
y is equal to encryption of x into encryption of y; that is, E
(
x
y
)
=
E
(
x
)
E
(
y
).A encryption scheme is additive homomorphic encryption scheme ifE
(
x
+
y
)
=
E
(
x
)
+
E
(
y
).It can be easily proved that Elgamal encryption scheme is multiplicative homomorphic encryption.


### 2.4. Integer Lattices [16, 17]

LetB
=
{
b
1
,
…
,
b
n
}
⊂
R
n consist of n linearly independent m-dimensional vectors as column vectors; the lattice generated by the matrix B is(1)
∧
=
L
(
B
)
=
{
B
x
:
x
∈
Z
n
}
.The column vectors of matrixB
=
{
b
1
,
…
,
b
n
} are called a basis for the lattice. n and m are called the rank and dimension of the lattice, respectively. When n
=
m, the lattice is called full-rank lattice but generally n
≤
m. The determinant of a lattice is the absolute value of the determinant of the basis matrix det
⁡
(
L
(
B
)
)
=

det
⁡
⁡
(
B
).q
-Ary Lattices. Generally cryptographic constructions based on lattices use q-ary lattices. Lattice L which satisfies the condition q
Z
n
⊆
L
⊆
Z
n for some prime q is called q-ary lattices. In other words, any vector x
∈
L
′ if and only if x
mod
⁡
q
∈
L
′, where L
′ is a q-ary lattices.For primeq, A
∈
Z
q
n
×
m, and u
∈
Z
q
n, three m-dimensional q-ary lattices are defined as follows:(2)
Λ
q
A
∶
=
e
∈
Z
m
s
.
t
.
∃
s
∈
Z
q
n
where
A
T
s
=
e
mod
⁡
q
Λ
q
⊥
A
∶
=
e
∈
Z
m
s
.
t
.
A
e
=
0
mod
⁡
q
Λ
q
u
A
∶
=
e
∈
Z
m
s
.
t
.
A
e
=
u
mod
⁡
q
.Since first q-ary lattices are generated by rows of matrix A and second is set of vectors orthogonal to rows of matrix A so these two q-ary lattices are dual to each other:(3)
Λ
q
⊥
A
=
q
·
Λ
q
A
*
,
Λ
q
A
=
q
·
Λ
q
⊥
A
*
.


### 2.5. Gram Schmidt Orthogonalization

S
~
∶
=
{
s
1
~
,
…
,
s
k
~
}
⊂
R
m denotes the Gram-Schmidt orthogonalization of the set of linearly independent vectors S
=
{
s
1
,
…
,
s
k
}
⊂
R
m, which is defined as follows:(4)
s
i
~
=
s
i
-
∑
j
=
1
i
-
1
‍
μ
i
,
j
s
j
~
where
μ
i
,
j
=
s
i
,
s
i
~
s
j
~
,
s
j
~
.In other words, s
1
~
=
s
1 and s
i
~ is the component of s
i orthogonal to span(
s
1
,
…
,
s
i
) where 2
≤
i
≤
k. Since s
i
~ is the component of s
i so s
i
~
≤
s
i for all i.We refer toS
~ as the Gram-Schmidt norm of S.


### 2.6. Discrete Gaussians

LetL be a subset of Z
m. For any vector c
∈
R
m and any positive parameter σ
∈
R
>
0, define:ρ
σ
,
c
(
x
)
=
exp
⁡
(
-
π
(
x
-
c
/
σ
2
)
): a Gaussian-shaped function on R
m with center c and parameter σ,
ρ
σ
,
c
(
L
)
=
∑
x
∈
L
‍
ρ
σ
,
c
(
x
): over L,
D
L
,
σ
,
c: the discrete Gaussian distribution over L with parameters σ and c,(5)
∀
y
∈
L
,
D
L
,
σ
,
c
(
y
)
=
ρ
σ
,
c
y
ρ
σ
,
c
L
.Theorem 2 (see [6, 18]).
Letq
≥
3 be odd and m
∶
=
⌈
6
n
log
⁡
⁡
q
⌉.
There is PPT algorithm TrapGen(q
,
n) that generates a pair (A
∈
Z
q
n
×
m
,
T
∈
Z
n
×
m) such that T is a basis for Λ
q
⊥
(
A
) and A is statistically close to a uniform matrix in Z
q
n
×
m satisfying(6)
T
~
≤
O
n
log
⁡
⁡
q
,
T
≤
O
(
n
log
⁡
⁡
q
)with overwhelming probability in n.


### 2.7. Decision Diffie-Hellman Problem

Let us consider a finite cyclic groupZ
p with generator g, where p is a prime number. g
a, g
b, and g
c are given for some random a
,
b
,
c
∈
Z
p. The goal of the adversary is to decide whether c
=
a
b or not.


### 2.8. The LWE Hardness Assumption [9, 19]

In 2004, Regev [9] proposed the LWE hard problem.Definition 3.
For a security parametern, let m
=
poly
(
n
), modulus q
=
poly
(
n
), and a Gaussian distribution χ
m over Z
q
m. For a uniformly chosen vector s
∈
Z
q
n, let A
s
,
χ be the distribution on Z
q
n
×
Z
q of the variable (
a
,
a
,
s
+
e
) where a vector a
∈
Z
q
n is chosen uniformly at random and e
∈
Z
q is chosen according to χ.
Search LWE. The search LW
E
q
,
χ problem is to find s
∈
Z
q
n with probability exponentially close to one, given m samples from A
s
,
χ.
Decision LWE. Decision LWE is to distinguish with nonnegligible probability between the distribution A
s
,
χ for some uniform s
∈
Z
q
n and a random distribution on Z
q
n
×
Z
q.In above,s is uniformly chosen from the random distribution. Even, if s is chosen from the Gaussian distribution still decision LWE is hard [20, 21].Gaussian Distribution
ψ
α. For α
∈
R
+, the distribution ψ
α on T
=
[
0,1
) is obtained by sampling a Gaussian distribution with mean 0 and variance α
2
/
2
π and reducing the result modulo 1. The probability density function is given by the following equation:(7)
ψ
α
(
x
)
=
∑
k
∈
Z
‍
1
α
exp
⁡
-
π
x
-
k
α
2
.In other words, distribution is obtained by “folding” a Gaussian distributionN
(
0
,
α
2
/
2
π
) on R into the interval T
=
[
0,1
) [22].Discrete Gaussian Distribution
ψ
¯
α. This distribution is obtained by “folding” a Gaussian distribution ψ
α on T
=
[
0,1
) into the interval Z
q. It is a discrete distribution over Z
q of the random variable ⌊
q
X
⌉
mod
⁡
q where the random variable X
∈
T has distribution ψ
α.The following theorem shows that LWE problem is reducible to some lattice problems in the worst case using the quantum algorithm.Theorem 4 (see [9]).
For security parametern, Let α
=
α
(
n
)
∈
(
0,1
) and q
=
p
o
l
y
(
n
) be a prime integer such that α
·
q
>
2
n. If there exists an efficient, possibly quantum algorithm for deciding the (
Z
q
,
n
,
ψ
¯
α
)-LWE problem for q
>
2
n
/
α, then there exists an efficient quantum algorithm for approximating the SIVP and GapSVP problems, to within O
(
n
/
α
) factors in the l
2 norm, in the worst case.


## 2.1. Notation

We denote[
j
]
=
{
0,1
,
…
,
j
}, set of real numbers by R and the set of integers by Z. We assume vectors to be in column form which are written using small letters, for example, x. Matrices are written as capital letters, for example, X. We denote R
←
ψ
β
(
q
)
q
m
×
m as matrix R whose elements are chosen from the Gaussian distribution ψ
β over Z
q and S
←
Z
q
n
×
m as matrix S whose elements are chosen uniformly over Z
q. S denotes the Euclidean norm of the longest (maximum Euclidean norm) vector in matrix S; that is, S
∶
=
ma
x
i
s
i for 1
≤
i
≤
k.We say thatnegl
(
n
) is a negligible function in n if it is smaller than the inverse of any polynomial function in n for sufficiently large n.


## 2.2. Universal Reencryption Scheme (URe)

Universal Reencryption Scheme consists of four algorithms [4]. We denote M, C, and R as message space, ciphertext space, and set of encryption factors, respectively.Universal KeyGen
(
n
). On the input of a security parameter n, this algorithm outputs the public key pk and secret key sk pair.Universal Encryption
(
pk
,
m
,
r
). On the input of public key pk, a message m
∈
M, and an encryption factor r
∈
R, this algorithm outputs a ciphertext C
∈
C.Universal Decryption
(
C
,
sk
). On the input of a secret key sk and a ciphertext C, this algorithm outputs message m.Universal Reencryption
(
C
,
r
). On the input of a ciphertext C and reencryption factor r
∈
R, but no public key, this algorithm outputs ciphertext C
′ where C
′
∈
C.


## 2.3. Universal Semantic Security Model for Universal Reencryption Scheme (IND-URe-CPA)

Universal security model is variant of semantic security model and is adapted from [4]. In this model, adversary is allowed to construct universal ciphertexts under randomly generated public key pk. The challenger reencrypts the ciphertext. The goal of the adversary is to distinguish between the reencrypted ciphertext and the random ciphertext with the size of the random ciphertext being the same as size of the universally reencrypted ciphertext. Here, security model is defined using the following game played between the challenger and an active adversary.KeyGen. The challenger runs the key generation algorithm and gives public parameters to the adversary.Challenger. The adversary submits messages m
∈
M and r
∈
R (adversary can construct ciphertext). Challenger sets C
←
Universal
Encryption
(
m
,
r
,
pk
) and chooses a random bit b
∈
{
0,1
} and a random ciphertext C with the size of the random ciphertext being the same as size of the universally reencrypted ciphertext. If b
=
0, it assigns the challenge ciphertext to C
*
=
Universal
Reencryption
(
C
,
r
′
). If b
=
1, it assigns the challenge ciphertext to C
*
=
C. Challenger sends challenge ciphertext C
* to the adversary.Guess. The adversary outputs a guess b
′
∈
{
0,1
} and wins the game if b
′
=
b.An IND-URe-CPA adversary is referred to as an adversaryA. We define the advantage of the adversary A in attacking universal reencryption scheme ξ as Ad
v
ξ
,
A
(
n
)
=
|
Pr
⁡
[
b
=
b
′
]
-
1
/
2
|.Definition 1.
One says that universal reencryption schemeξ is universal semantic secure if for all probabilistic polynomial time adversaries A, one has Ad
v
ξ
,
A
(
n
) which is a negligible function.


### 2.3.1. Semantically Secure Elgamal Cryptosystem [15]

Semantically secure Elgamal cryptosystem consists of three algorithms.Setup. Two primes p and q are randomly selected such that p
=
2
q
+
1. Pick a random generator h
∈
Z
p and set g
=
h
2
(
mod
⁡
p
). g is generator of subgroup G (Schnorr group) of size q. Message m is also element of subgroup G. Since g
∈
Q
R
p so m
∈
Q
R
p (Quadratic residue modulo p). Pick a random number x
∈
Z
p
-
1 as private key and public key y
=
g
x
(
mod
⁡
p
).Encryption. To encrypt a message m
∈
G, sender picks a random number r
∈
Z
p
-
1 and computes a ciphertext pair as follows:c
1
=
g
r
mod
⁡
p
andc
2
=
y
r
m
(
mod
⁡
p
). Output ciphertext C
=
(
c
1
,
c
2
).Decryption. To decrypt a ciphertext (
c
1
,
c
2
), receiver computes m
=
c
2
/
c
1
x
(
mod
⁡
p
).


### 2.3.2. Homomorphic Encryption

A encryption scheme is multiplicative homomorphic encryption scheme if encryption ofx
y is equal to encryption of x into encryption of y; that is, E
(
x
y
)
=
E
(
x
)
E
(
y
).A encryption scheme is additive homomorphic encryption scheme ifE
(
x
+
y
)
=
E
(
x
)
+
E
(
y
).It can be easily proved that Elgamal encryption scheme is multiplicative homomorphic encryption.


## 2.3.1. Semantically Secure Elgamal Cryptosystem [15]

Semantically secure Elgamal cryptosystem consists of three algorithms.Setup. Two primes p and q are randomly selected such that p
=
2
q
+
1. Pick a random generator h
∈
Z
p and set g
=
h
2
(
mod
⁡
p
). g is generator of subgroup G (Schnorr group) of size q. Message m is also element of subgroup G. Since g
∈
Q
R
p so m
∈
Q
R
p (Quadratic residue modulo p). Pick a random number x
∈
Z
p
-
1 as private key and public key y
=
g
x
(
mod
⁡
p
).Encryption. To encrypt a message m
∈
G, sender picks a random number r
∈
Z
p
-
1 and computes a ciphertext pair as follows:c
1
=
g
r
mod
⁡
p
andc
2
=
y
r
m
(
mod
⁡
p
). Output ciphertext C
=
(
c
1
,
c
2
).Decryption. To decrypt a ciphertext (
c
1
,
c
2
), receiver computes m
=
c
2
/
c
1
x
(
mod
⁡
p
).


## 2.3.2. Homomorphic Encryption

A encryption scheme is multiplicative homomorphic encryption scheme if encryption ofx
y is equal to encryption of x into encryption of y; that is, E
(
x
y
)
=
E
(
x
)
E
(
y
).A encryption scheme is additive homomorphic encryption scheme ifE
(
x
+
y
)
=
E
(
x
)
+
E
(
y
).It can be easily proved that Elgamal encryption scheme is multiplicative homomorphic encryption.


## 2.4. Integer Lattices [16, 17]

LetB
=
{
b
1
,
…
,
b
n
}
⊂
R
n consist of n linearly independent m-dimensional vectors as column vectors; the lattice generated by the matrix B is(1)
∧
=
L
(
B
)
=
{
B
x
:
x
∈
Z
n
}
.The column vectors of matrixB
=
{
b
1
,
…
,
b
n
} are called a basis for the lattice. n and m are called the rank and dimension of the lattice, respectively. When n
=
m, the lattice is called full-rank lattice but generally n
≤
m. The determinant of a lattice is the absolute value of the determinant of the basis matrix det
⁡
(
L
(
B
)
)
=

det
⁡
⁡
(
B
).q
-Ary Lattices. Generally cryptographic constructions based on lattices use q-ary lattices. Lattice L which satisfies the condition q
Z
n
⊆
L
⊆
Z
n for some prime q is called q-ary lattices. In other words, any vector x
∈
L
′ if and only if x
mod
⁡
q
∈
L
′, where L
′ is a q-ary lattices.For primeq, A
∈
Z
q
n
×
m, and u
∈
Z
q
n, three m-dimensional q-ary lattices are defined as follows:(2)
Λ
q
A
∶
=
e
∈
Z
m
s
.
t
.
∃
s
∈
Z
q
n
where
A
T
s
=
e
mod
⁡
q
Λ
q
⊥
A
∶
=
e
∈
Z
m
s
.
t
.
A
e
=
0
mod
⁡
q
Λ
q
u
A
∶
=
e
∈
Z
m
s
.
t
.
A
e
=
u
mod
⁡
q
.Since first q-ary lattices are generated by rows of matrix A and second is set of vectors orthogonal to rows of matrix A so these two q-ary lattices are dual to each other:(3)
Λ
q
⊥
A
=
q
·
Λ
q
A
*
,
Λ
q
A
=
q
·
Λ
q
⊥
A
*
.


## 2.5. Gram Schmidt Orthogonalization

S
~
∶
=
{
s
1
~
,
…
,
s
k
~
}
⊂
R
m denotes the Gram-Schmidt orthogonalization of the set of linearly independent vectors S
=
{
s
1
,
…
,
s
k
}
⊂
R
m, which is defined as follows:(4)
s
i
~
=
s
i
-
∑
j
=
1
i
-
1
‍
μ
i
,
j
s
j
~
where
μ
i
,
j
=
s
i
,
s
i
~
s
j
~
,
s
j
~
.In other words, s
1
~
=
s
1 and s
i
~ is the component of s
i orthogonal to span(
s
1
,
…
,
s
i
) where 2
≤
i
≤
k. Since s
i
~ is the component of s
i so s
i
~
≤
s
i for all i.We refer toS
~ as the Gram-Schmidt norm of S.


## 2.6. Discrete Gaussians

LetL be a subset of Z
m. For any vector c
∈
R
m and any positive parameter σ
∈
R
>
0, define:ρ
σ
,
c
(
x
)
=
exp
⁡
(
-
π
(
x
-
c
/
σ
2
)
): a Gaussian-shaped function on R
m with center c and parameter σ,
ρ
σ
,
c
(
L
)
=
∑
x
∈
L
‍
ρ
σ
,
c
(
x
): over L,
D
L
,
σ
,
c: the discrete Gaussian distribution over L with parameters σ and c,(5)
∀
y
∈
L
,
D
L
,
σ
,
c
(
y
)
=
ρ
σ
,
c
y
ρ
σ
,
c
L
.Theorem 2 (see [6, 18]).
Letq
≥
3 be odd and m
∶
=
⌈
6
n
log
⁡
⁡
q
⌉.
There is PPT algorithm TrapGen(q
,
n) that generates a pair (A
∈
Z
q
n
×
m
,
T
∈
Z
n
×
m) such that T is a basis for Λ
q
⊥
(
A
) and A is statistically close to a uniform matrix in Z
q
n
×
m satisfying(6)
T
~
≤
O
n
log
⁡
⁡
q
,
T
≤
O
(
n
log
⁡
⁡
q
)with overwhelming probability in n.


## 2.7. Decision Diffie-Hellman Problem

Let us consider a finite cyclic groupZ
p with generator g, where p is a prime number. g
a, g
b, and g
c are given for some random a
,
b
,
c
∈
Z
p. The goal of the adversary is to decide whether c
=
a
b or not.


## 2.8. The LWE Hardness Assumption [9, 19]

In 2004, Regev [9] proposed the LWE hard problem.Definition 3.
For a security parametern, let m
=
poly
(
n
), modulus q
=
poly
(
n
), and a Gaussian distribution χ
m over Z
q
m. For a uniformly chosen vector s
∈
Z
q
n, let A
s
,
χ be the distribution on Z
q
n
×
Z
q of the variable (
a
,
a
,
s
+
e
) where a vector a
∈
Z
q
n is chosen uniformly at random and e
∈
Z
q is chosen according to χ.
Search LWE. The search LW
E
q
,
χ problem is to find s
∈
Z
q
n with probability exponentially close to one, given m samples from A
s
,
χ.
Decision LWE. Decision LWE is to distinguish with nonnegligible probability between the distribution A
s
,
χ for some uniform s
∈
Z
q
n and a random distribution on Z
q
n
×
Z
q.In above,s is uniformly chosen from the random distribution. Even, if s is chosen from the Gaussian distribution still decision LWE is hard [20, 21].Gaussian Distribution
ψ
α. For α
∈
R
+, the distribution ψ
α on T
=
[
0,1
) is obtained by sampling a Gaussian distribution with mean 0 and variance α
2
/
2
π and reducing the result modulo 1. The probability density function is given by the following equation:(7)
ψ
α
(
x
)
=
∑
k
∈
Z
‍
1
α
exp
⁡
-
π
x
-
k
α
2
.In other words, distribution is obtained by “folding” a Gaussian distributionN
(
0
,
α
2
/
2
π
) on R into the interval T
=
[
0,1
) [22].Discrete Gaussian Distribution
ψ
¯
α. This distribution is obtained by “folding” a Gaussian distribution ψ
α on T
=
[
0,1
) into the interval Z
q. It is a discrete distribution over Z
q of the random variable ⌊
q
X
⌉
mod
⁡
q where the random variable X
∈
T has distribution ψ
α.The following theorem shows that LWE problem is reducible to some lattice problems in the worst case using the quantum algorithm.Theorem 4 (see [9]).
For security parametern, Let α
=
α
(
n
)
∈
(
0,1
) and q
=
p
o
l
y
(
n
) be a prime integer such that α
·
q
>
2
n. If there exists an efficient, possibly quantum algorithm for deciding the (
Z
q
,
n
,
ψ
¯
α
)-LWE problem for q
>
2
n
/
α, then there exists an efficient quantum algorithm for approximating the SIVP and GapSVP problems, to within O
(
n
/
α
) factors in the l
2 norm, in the worst case.


## 3. Mix Network

A mix network is a multistage system that offers anonymous communication. Here, we describe three types of mixnets: decryption mixnet, reencryption mixnet, and universal reencryption mixnet.


### 3.1. Decryption Mixnet [1, 23]

Each mixnet node has its own public key and private key. We denote public and private key ofith mixnet node by (
p
k
i
,
s
k
i
).Encryption. Sender first encrypts the message using public key of the nth mixnet node. First encryption is(8)
C
n
=
E
P
K
n
m
∥
B
∥
r
n
,where B is the address of the receiver and r is the random number concatenated with the encryption. Similarly, sender again encrypts C
n with the public key of (
n
-
1
)th mixnet node. Second encryption is(9)
C
n
-
1
=
E
P
K
n
-
1
C
n
∥
r
n
-
1
.Finally, sender sends the ciphertext C to the mixnet as(10)
C
=
E
P
K
1
E
P
K
2
E
P
K
3
,
…
,
∥
r
3
∥
r
2
∥
r
1
.Above ciphertext is concatenation of n-encryptions which can be seen as building up of a n layered onion.Decryption. First mixnet node receives ciphertext from many senders. It will decrypt all the ciphertexts using its private key (remove outer layer of the onion) and permute them before forwarding to the second mixnet node. Finally, the nth mixnet node sends the messages to the respective receivers.Chaum’s mixnet [1] preserves anonymous communication even with one honest mixnet node. But it has the following disadvantages.(1)
Mixnet is not robust because if one mixnet node fails, whole mixnet fails.
(2)
Encryption cost is very high which grows with the number of mixnet nodes.
(3)
Decryption has to be performed in reverse order of the encryption.


### 3.2. Reencryption Mixnet [2, 23]

All three weaknesses of the decryption mixnet are removed in reencryption mixnet. Reencryption mixnet node is based on Elgamal cryptosystem [24] and Shamir’s secret sharing [3].Secret key of the mixnet isd and public key is K
=
g
d. Secret key d is distributed among n mixnet nodes in such a way that, at least, t mixnet nodes are required to compute secret key d but no group of t
-
1 nodes can compute secret key d.Encryption. Sender encrypts the using public key K of the mixnet. Ciphertext is(11)
C
=
E
K
m
,
r
=
g
r
∥
B
∥
m
k
r
.Sender sends the ciphertext C to the mixnet.Reencryption. Mixnet node j reencrypts the encrypted message as follows:(12)
Reencryption
=
E
K
C
,
r
j
=
g
r
j
g
r
∥
B
∥
m
K
r
K
r
j
=
g
r
+
r
j
∥
B
∥
m
K
r
+
r
j
,where r
j is random number. Mixnet node broadcasts this reencrypted to other mixnet nodes. There is no order of reencryption. Any mixnet node can reencrypt first and broadcast reencrypted to other nodes. It is also not required that reencryption has to be done by all the mixnet nodes.Decryption. Now, in decryption phase, any t mixnet nodes can participate to compute secret key d:(13)
D
d
g
r
+
r
1
+
r
2
+
⋯
+
r
m
∥
B
∥
m
K
r
+
r
1
+
r
2
+
⋯
+
r
m
=
(
B
∥
m
)
K
r
+
r
1
+
r
2
+
⋯
+
r
m
g
r
+
r
1
+
r
2
+
⋯
+
r
m
d
=
B
∥
m
,where m
≤
n and B is address of the receiver.


### 3.3. Universal Reencryption Mixnet [4]

In 2004, Golle et al. [4] presented a new primitive called universal reencryption based on the Elgamal public key cryptosystem [24]. Universal mixnet is a mixnet based on universal reencryption which takes the input as encrypted messages under the public key of the recipients not the public key of the universal mixnet. Even, there is no term like the public key of the universal mixnet. So it dispenses with cost of establishing public key infrastructure for mixnet nodes.The idea for universal reencryption is simple. In an additive homomorphic cryptosystem, we append a second ciphertext (encryption of zero) to the ciphertext. Since, in an additive homomorphic,E
(
M
+
0
)
=
E
(
M
)
+
E
(
0
), we can use the second ciphertext to reencrypt (change the encryption factor) the first ciphertext such that the reencrypted ciphertext and the ciphertext decrypt the same plaintext.Key Generation. It is the same as key generation algorithm in Elgamal cryptosystem.Universal Encryption. On the input of a message m, a public key y, and a random encryption factor r
=
(
k
0
,
k
1
)
∈
Z
q
2, ciphertext C is computed as follows:(14)
C
=
c
0
,
c
1
;
c
2
,
c
3
=
m
y
k
0
,
g
k
0
;
y
k
1
,
g
k
1
.Here ciphertext (
c
2
,
c
3
) is for message m.Universal Decryption. Here, the decryption is done by the receiver. Compute m
0
=
c
0
/
c
1
x and m
1
=
c
2
/
c
3
x. If m
1
=
1, then the output is m
=
m
0. Otherwise, decryption fails.Universal Reencryption. On the input of a C
=
[
(
c
0
,
c
1
)
;
(
c
2
,
c
3
)
] and a random reencryption factor r
′
=
(
k
0
′
,
k
1
′
)
∈
Z
q
2, reencrypted ciphertext C
′ is computed as follows:(15)
C
′
=
c
0
′
,
c
1
′
;
c
2
′
,
c
3
′
=
c
0
c
2
k
0
′
,
c
1
c
3
k
0
′
;
c
2
k
1
′
,
c
3
k
1
′
.


## 3.1. Decryption Mixnet [1, 23]

Each mixnet node has its own public key and private key. We denote public and private key ofith mixnet node by (
p
k
i
,
s
k
i
).Encryption. Sender first encrypts the message using public key of the nth mixnet node. First encryption is(8)
C
n
=
E
P
K
n
m
∥
B
∥
r
n
,where B is the address of the receiver and r is the random number concatenated with the encryption. Similarly, sender again encrypts C
n with the public key of (
n
-
1
)th mixnet node. Second encryption is(9)
C
n
-
1
=
E
P
K
n
-
1
C
n
∥
r
n
-
1
.Finally, sender sends the ciphertext C to the mixnet as(10)
C
=
E
P
K
1
E
P
K
2
E
P
K
3
,
…
,
∥
r
3
∥
r
2
∥
r
1
.Above ciphertext is concatenation of n-encryptions which can be seen as building up of a n layered onion.Decryption. First mixnet node receives ciphertext from many senders. It will decrypt all the ciphertexts using its private key (remove outer layer of the onion) and permute them before forwarding to the second mixnet node. Finally, the nth mixnet node sends the messages to the respective receivers.Chaum’s mixnet [1] preserves anonymous communication even with one honest mixnet node. But it has the following disadvantages.(1)
Mixnet is not robust because if one mixnet node fails, whole mixnet fails.
(2)
Encryption cost is very high which grows with the number of mixnet nodes.
(3)
Decryption has to be performed in reverse order of the encryption.


## 3.2. Reencryption Mixnet [2, 23]

All three weaknesses of the decryption mixnet are removed in reencryption mixnet. Reencryption mixnet node is based on Elgamal cryptosystem [24] and Shamir’s secret sharing [3].Secret key of the mixnet isd and public key is K
=
g
d. Secret key d is distributed among n mixnet nodes in such a way that, at least, t mixnet nodes are required to compute secret key d but no group of t
-
1 nodes can compute secret key d.Encryption. Sender encrypts the using public key K of the mixnet. Ciphertext is(11)
C
=
E
K
m
,
r
=
g
r
∥
B
∥
m
k
r
.Sender sends the ciphertext C to the mixnet.Reencryption. Mixnet node j reencrypts the encrypted message as follows:(12)
Reencryption
=
E
K
C
,
r
j
=
g
r
j
g
r
∥
B
∥
m
K
r
K
r
j
=
g
r
+
r
j
∥
B
∥
m
K
r
+
r
j
,where r
j is random number. Mixnet node broadcasts this reencrypted to other mixnet nodes. There is no order of reencryption. Any mixnet node can reencrypt first and broadcast reencrypted to other nodes. It is also not required that reencryption has to be done by all the mixnet nodes.Decryption. Now, in decryption phase, any t mixnet nodes can participate to compute secret key d:(13)
D
d
g
r
+
r
1
+
r
2
+
⋯
+
r
m
∥
B
∥
m
K
r
+
r
1
+
r
2
+
⋯
+
r
m
=
(
B
∥
m
)
K
r
+
r
1
+
r
2
+
⋯
+
r
m
g
r
+
r
1
+
r
2
+
⋯
+
r
m
d
=
B
∥
m
,where m
≤
n and B is address of the receiver.


## 3.3. Universal Reencryption Mixnet [4]

In 2004, Golle et al. [4] presented a new primitive called universal reencryption based on the Elgamal public key cryptosystem [24]. Universal mixnet is a mixnet based on universal reencryption which takes the input as encrypted messages under the public key of the recipients not the public key of the universal mixnet. Even, there is no term like the public key of the universal mixnet. So it dispenses with cost of establishing public key infrastructure for mixnet nodes.The idea for universal reencryption is simple. In an additive homomorphic cryptosystem, we append a second ciphertext (encryption of zero) to the ciphertext. Since, in an additive homomorphic,E
(
M
+
0
)
=
E
(
M
)
+
E
(
0
), we can use the second ciphertext to reencrypt (change the encryption factor) the first ciphertext such that the reencrypted ciphertext and the ciphertext decrypt the same plaintext.Key Generation. It is the same as key generation algorithm in Elgamal cryptosystem.Universal Encryption. On the input of a message m, a public key y, and a random encryption factor r
=
(
k
0
,
k
1
)
∈
Z
q
2, ciphertext C is computed as follows:(14)
C
=
c
0
,
c
1
;
c
2
,
c
3
=
m
y
k
0
,
g
k
0
;
y
k
1
,
g
k
1
.Here ciphertext (
c
2
,
c
3
) is for message m.Universal Decryption. Here, the decryption is done by the receiver. Compute m
0
=
c
0
/
c
1
x and m
1
=
c
2
/
c
3
x. If m
1
=
1, then the output is m
=
m
0. Otherwise, decryption fails.Universal Reencryption. On the input of a C
=
[
(
c
0
,
c
1
)
;
(
c
2
,
c
3
)
] and a random reencryption factor r
′
=
(
k
0
′
,
k
1
′
)
∈
Z
q
2, reencrypted ciphertext C
′ is computed as follows:(15)
C
′
=
c
0
′
,
c
1
′
;
c
2
′
,
c
3
′
=
c
0
c
2
k
0
′
,
c
1
c
3
k
0
′
;
c
2
k
1
′
,
c
3
k
1
′
.


## 4. Gentry, Halevi, and Vaikunthanathan (GHV) Cryptosystem [12]

GHV cryptosystem [12] is an additive homomorphic and multiplicative homomorphic for only one multiplication. Here, message space M
∈
Z
2
m
×
m (the set of binary m-by-m matrices) and ciphertex space C
∈
Z
q
m
×
m (the set of m-by-m matrices). Here, we briefly describe the GHV homomorphic cryptosystem because our scheme is based on it.KeyGen
(
n
). On the input of a security parameter n, set the parameters q
=
poly
(
n
) and m
=
O
(
n
log
⁡
q
) and a Gaussian distribution ψ
β
(
q
)
q
m
×
m with Gaussian error parameter β
=
1
/
poly
(
n
). Uniform matrix A
∈
Z
q
m
×
n together with the trapdoor T
∈
Z
m
×
m is obtained by running algorithm TrapGen of Theorem 2. The public key is A and the secret key is T.Encrypt
(
A
,
M
∈
{
0,1
}
m
×
m
). To encrypt message M
∈
{
0,1
}
m
×
m, do the following steps.(1)
A random matrixS
←
Z
q
n
×
m and an error matrix X
←
ψ
β
(
q
)
q
m
×
m are chosen uniformly.
(2)
Output the ciphertext(16)
C
=
A
S
+
2
X
+
M
mod
⁡
q
.Decrypt
(
T
,
C
). To decrypt C, do the following steps.(1)
SetE
=
T
C
T
t
mod
⁡
q.
(2)
Output the matrixB
=
T
-
1
E
(
T
t
)
-
1
mod
⁡
q.Correctness. Since T
·
A
=
0, therefore E
=
T
C
T
t
=
T
(
2
X
+
M
)
T
t
mod
⁡
q. Now, if T
(
2
X
+
M
)
T
t
mod
⁡
q is equal to T
(
2
X
+
M
)
T
t, then T
-
1
E
T
mod
⁡
q
=
M. So for correct decryption, one has to set the parameter β small enough so that all the entries of T
(
2
X
+
M
)
T
t are smaller than q
/
2 with high probability.Additive Homomorphic. Let C
1
=
A
S
1
+
2
X
1
+
M
1 and C
2
=
A
S
2
+
2
X
2
+
M
2 be ciphertexts for messages M
1 and M
2 under public key A. Then,(17)
C
=
C
1
+
C
2
=
A
(
S
1
+
S
2
)
+
2
(
X
1
+
X
2
)
+
M
1
+
M
2would be decrypted to M
1
+
M
2 as long as all the entries in T
(
2
(
X
1
+
X
2
)
+
M
1
+
M
2
)
T
t are smaller than q
/
2.Multiplicative Homomorphic. The product of C
1 and C
2 is(18)
C
=
C
1
·
C
2
t
=
(
A
S
1
+
2
X
1
+
M
1
)
·
A
S
2
+
2
X
2
+
M
2
t
=
A
·
(
S
1
C
2
t
)
+
2
·
X
1
2
X
2
+
M
2
+
M
1
X
2
t
+
M
1
M
2
t
+
2
X
1
+
M
1
S
2
t
·
A
t
.Product ciphertext C has the form A
S
+
2
X
+
M
+
S
′
A
t. Ciphertext would be decrypted to M
1
·
M
2
T as long as all the entries in T
(
2
X
+
M
)
T
t are smaller than q
/
2.For our scheme, we will use variant of GHV cryptosystem which is only additive homomorphic. For this variant, decryption algorithm will not have right multiplication ofT
t.


## 5. Lattice Based Universal Reencryption [13]

Singh et al.’ scheme [13] is based on GHV cryptosystem which is explained in Section 4 (Table 1).Table 1
We compare our scheme with Singh et al.’ scheme [13] for plaintext size of k
(
m
×
m
) bits.
Plaintext size
Ciphertext size
Singh et al.’ scheme [13]
k
(
m
×
m
) bits
2
k
(
m
×
m
) bits
Our scheme
k
(
m
×
m
) bits
(
k
+
1
)
(
m
×
m
) bitsThe idea for universal reencryption is to append a new ciphertext (encryption of zero) to the GHV cryptosystem ciphertext. The new ciphertext can be used to reencrypt (change the encryption factor) the ciphertext such that the reencrypted ciphertext and the ciphertext decrypt the same plaintext because the GHV public key cryptosystem is additive homomorphic; that is, (E
(
M
+
0
)
=
E
(
M
)
+
E
(
0
)).Universal KeyGen
(
n
). On the input of a security parameter n, we set the parameters q
=
poly
(
n
) and m
=
O
(
n
log
⁡
⁡
q
) and a Gaussian distribution ψ
β
(
q
)
q
m
×
m with Gaussian error parameter β
=
1
/
poly
(
n
). Uniform matrix A
∈
Z
q
m
×
n together with the trapdoor T
∈
Z
m
×
m is obtained by running algorithm TrapGen of Theorem 2. The public key is A and the secret key is T.Universal Encryption
(
A
,
M
). To encrypt message M
∈
{
0,1
}
m
×
m, we do the following steps.(i)
We choose random matricesS
1
,
S
2
←
Z
q
n
×
m and error matrices X
1
,
X
2
←
ψ
β
(
q
)
q
m
×
m.
(ii)
ComputeC
1
=
A
S
1
+
2
X
1
+
M
∈
Z
q
m
×
m and C
2
=
A
S
2
+
2
X
2
+
0
m
×
m
(
zero
matrix
)
∈
Z
q
m
×
m.
(iii)
Output the ciphertextC
=
(
C
1
,
C
2
).Universal Decryption
(
T
,
C
=
(
C
1
,
C
2
)
). To decrypt C, we do the following steps.(i)
SetE
1
=
T
C
1.
(ii)
ComputeM
1
=
T
-
1
E
1
mod
⁡
2.
(iii)
Similarly, setE
2
=
T
C
2.
(iv)
ComputeM
2
=
T
-
1
E
2
mod
⁡
2.
(v)
If (M
2
=
0
m
×
m), then output message M
=
M
1. Otherwise, decryption fails and output is ⊥.Universal Reencryption
(
C
=
(
C
1
,
C
2
)
). To reencrypt ciphertext C
=
(
C
1
,
C
2
) without using public key, we do the following steps.(i)
Choose two matricesR
1
,
R
2
←
ψ
β
(
q
)
q
m
×
m. We also choose error matrices X
3
,
X
4
←
ψ
β
(
q
)
q
m
×
m.
(ii)
Compute(19)
C
1
′
=
C
1
+
C
2
R
1
+
2
X
3
=
A
S
1
+
2
X
1
+
M
+
A
S
2
+
2
X
2
+
0
m
×
m
R
1
+
2
X
3
=
A
(
S
1
+
S
2
R
1
)
+
(
2
(
X
1
+
X
2
R
1
)
+
2
X
3
)
+
M
.
(iii)
Compute(20)
C
2
′
=
C
2
R
2
+
2
X
4
=
(
A
S
2
+
2
X
2
+
0
m
×
m
)
R
2
+
2
X
4
=
A
S
2
R
2
+
2
X
2
R
2
+
0
m
×
m
+
2
X
4
.
(iv)
Output the ciphertextC
′
=
(
C
1
′
,
C
2
′
).It is required that above universal reencryption scheme has the correctness property; that is, decryption ofC
′ and decryption of C give the same message M. It is only possible when all the entries in T
2
(
X
1
+
X
2
R
1
)
+
2
X
3
+
M and 2
X
2
R
2
+
2
X
4
+
0
m
×
m are less than q
/
2. Since X
1
,
X
2
,
X
3
,
X
4
,
R
1, and R
2 are small, we can set parameter β small enough so that, with the probability exponentially close to 1, all the entries in T
2
(
X
1
+
X
2
R
1
)
+
2
X
3
+
M and 2
X
2
R
2
+
2
X
4
+
0
m
×
m are less than q
/
2.Theorem 5.
Lattice based universal reencryption scheme is IND-URe-CPA (semantic) secure assuming that theL
W
E
q
,
χ is hard or A
d
v
B
,
L
W
E
q
,
χ
(
n
)
=
A
d
v
χ
,
A
(
n
).Proof.
It is the same as proof of [13].


## 6. Lattice Based Efficient Universal Reencryption

We use Fairbrother’s idea [14] to reduce the size of the ciphertext by half. It also reduces the computational cost. The idea is that larger files can be split into k segments and size of each segment is m
×
m bits. In Singh et al.’s universal reencryption scheme [13], size of the plaintext is (
m
×
m
) and second part of the ciphertext is encryption of zero. In this scheme, size of the plaintext is k
(
m
×
m
) and, for all these k segments, second part of the ciphertext (encryption of zero) is made the same.In [13], size of the ciphertext for plaintext of size k
(
m
×
m
) bits is 2
k
(
m
×
m
) bits. With our efficient universal reencryption scheme size of the ciphertext for plaintext of size k
(
m
×
m
) bits is (
k
+
1
)
(
m
×
m
) bits. Since second part of the ciphertext is same for all the segments, there is also some improvement in computation cost. Now, we describe our efficient scheme which is similar to [13].Universal KeyGen
(
n
). It is same as Universal KeyGen(
n
) algorithm of our scheme given in Section 5.Universal Encryption
(
A
,
M
). To encrypt message M
=
(
M
1
,
M
2
,
…
,
M
k
)
∈
{
0,1
}
k
(
m
×
m
), we do the following steps.(i)
We choose random matricesS
1
,
S
2
,
…
,
S
k
+
1
←
Z
q
n
×
m and error matrices X
1
,
X
2
,
…
,
S
k
+
1
←
ψ
β
(
q
)
q
m
×
m.
(ii)
Fori
=
1 to k, compute C
i
=
A
S
i
+
2
X
i
+
M
i
∈
Z
q
m
×
m.
(iii)
ComputeC
k
+
1
=
A
S
k
+
1
+
2
X
k
+
1
+
0
m
×
m
(
zero
matrix
)
∈
Z
q
m
×
m.
(iv)
Output the ciphertextC
=
(
C
1
,
C
2
,
…
,
C
k
+
1
).Universal Decryption
(
T
,
C
=
(
C
1
,
C
2
,
…
,
C
k
+
1
)
). To decrypt C, we do the following steps.(i)
Fori
=
1 to k, set E
i
=
T
C
i.
(ii)
Fori
=
1 to k, compute M
i
=
T
-
1
E
i
mod
⁡
2.
(iii)
Similarly, setE
k
+
1
=
T
C
k
+
1.
(iv)
ComputeM
k
+
1
=
T
-
1
E
k
+
1
mod
⁡
2.
(v)
If (M
k
+
1
=
0
m
×
m), then output message M
=
M
1
⋯
M
k. Otherwise, decryption fails and output is ⊥.Universal Reencryption
(
C
=
(
C
1
,
C
2
,
…
,
C
k
+
1
)
). To reencrypt ciphertext C
=
(
C
1
,
C
2
) without using public key, we do the following steps.(i)
Choose matricesR
1
,
R
2
,
…
,
R
k
+
1
←
ψ
β
(
q
)
q
m
×
m. We also choose error matrices Y
1
,
Y
2
,
…
,
Y
k
+
1
←
ψ
β
(
q
)
q
m
×
m.
(ii)
Compute(21)
For
i
=
1
to
k
,
C
i
′
=
C
i
+
C
k
+
1
R
i
+
2
Y
i
=
(
A
S
i
+
2
X
i
+
M
i
)
+
(
A
S
k
+
1
+
2
X
k
+
1
+
0
m
×
m
)
R
i
+
2
Y
i
=
A
(
S
i
+
S
k
+
1
R
i
)
+
2
X
i
+
X
k
+
1
R
i
+
2
Y
i
+
M
i
.
(iii)
Compute(22)
C
k
+
1
′
=
C
k
+
1
R
k
+
1
+
2
Y
k
+
1
=
(
A
S
k
+
1
+
2
X
k
+
1
+
0
m
×
m
)
R
k
+
1
+
2
Y
k
+
1
=
A
S
k
+
1
R
k
+
1
+
2
X
k
+
1
R
k
+
1
+
0
m
×
m
+
2
Y
k
+
1
.
(iv)
Output the ciphertextC
′
=
(
C
1
′
,
C
2
′
,
…
,
C
k
+
1
′
).Correctness property is similar to correctness of previous scheme [13].Theorem 6.
The lattice based improved universal reencryption scheme is IND-URe-CPA (semantic) secure assuming that theL
W
E
q
,
χ is hard or A
d
v
B
,
L
W
E
q
,
χ
(
n
)
=
A
d
v
χ
,
A
(
n
).Proof.
We now show universal semantic security of the universal reencryption scheme. We will show that if there exists a PPT adversaryA that breaks universal reencryption scheme with nonnegligible probability then there must exist a PPT challenger B that solves decision LWE hard problem with nonnegligible probability by simulating views of A.
AdversaryA constructs the ciphertext C
=
(
C
1
,
C
2
,
…
,
C
k
,
C
k
+
1
) for message m and sends to the challenger B. Ciphertext C
k
+
1 is statistically close to uniform.
Fori
=
1 to k,{challengerB obtains m
LWE samples (for vector r
i
,
1), m
LWE samples (for vector r
i
,
2),
…
,
m
LWE samples (for vector r
i
,
m) where vectors r
i
,
1
,
r
i
,
2
,
…
,
r
i
,
m are from Gaussian (error) distribution ψ
m and matrix R
i
=
[
r
i
,
1
⋯
r
i
,
m
]. It parsed as C
k
+
1
R
i
+
2
X
3
,
i and then challenger computes C
i
′
=
C
k
+
1
R
i
+
2
X
3
,
i
+
C
i
}.
Similarly, challenger again obtainsm
LWE samples (for vector r
1
′), m
LWE samples (for vector r
2
′)⋯
m
LWE samples (for vector r
m
′) where vectors r
1
′
,
r
2
′
,
…
,
r
m
′ are from Gaussian (error) distribution ψ
m and matrix R
k
+
1
=
[
r
1
′
⋯
r
m
′
]. It parsed as C
k
+
1
R
k
+
1
+
2
X
4, and then challenger assigns C
k
+
1
′
=
C
k
+
1
R
k
+
1
+
2
X
4. Here, matrices X
3,1
,
…
,
X
3
,
k
,
X
4
←
ψ
β
(
q
)
q
m
×
m.
ChallengerB sends C
*
=
(
C
1
′
,
…
,
C
k
′
,
C
k
+
1
′
) to the adversary A.
When OracleO is a pseudorandom LWE oracle, then C
* is a valid universal reencryption of ciphertext C. When Oracle O is a random oracle, then C
* is a uniform. Finally, adversary A terminates with some output; challenger B terminates with same output and ends the simulation. So if adversary A breaks the scheme, then there exists challenger B which solves decision LWE hard problem.
Ad
v
B
,
LW
E
q
,
χ
(
n
)
=
Ad
v
χ
,
A
(
n
). Hence, our scheme is universal semantic secure.


## 7. Conclusion

We have presented an improved construction for lattice based universal reencryption. Disadvantage of universal reencryption is that receiver has to decrypt all the ciphertexts to identify message for him. A lattice based universal reencryption scheme improving this cost in the receiver side is an open problem.



---

*Source: 963628-2015-03-23.xml*