Message Expansion of Homomorphic Encryption Using Product Pairing

ETRI Journal.
2016.
Mar,
38(1):
123-132

- Received : July 08, 2015
- Accepted : September 25, 2015
- Published : March 01, 2016

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

The Boneh, Goh, and Nissim (BGN) cryptosytem is the first homomorphic encryption scheme that allows additions and multiplications of plaintexts on encrypted data. BGN-type cryptosystems permit very small plaintext sizes. The best-known approach for the expansion of a message size by
t
times is one that requires
t
implementations of an initial scheme; however, such an approach becomes impractical when
t
is large. In this paper, we present a method of message expansion of BGN-type homomorphic encryption using composite product pairing, which is practical for relatively large
t
. In addition, we prove that the indistinguishability under chosen plaintext attack security of our construction relies on the decisional Diffie–Hellman assumption for all subgroups of prime order of the underlying composite pairing group.
e
:
G
×
G
→
G_{T}
with |
G
| = |
G_{T}
| =
N
=
PQ
[1]
. Here, the cyclic group
G
is a subgroup of an elliptic curve group over a finite field. It is proven that the security of the BGN cryptosystem is based on the subgroup decision problem for
G_{P}
in
G
, which is as hard as factoring
N
[2]
. Currently, at the year 2015, it is recommended that
N
be at least 2,048
[3]
,
[4]
. This requires that group
G
in the BGN cryptosystem be larger compared to that of many known elliptic curve–based cryptosystems.
Freeman presented how to convert a BGN cryptosystem of composite pairing to a (+, ×)-homomorphic encryption using a product of prime pairings
[5]
. Therefore, Freeman contributed to reducing the size of the parameters of the original BGN cryptosystem. However, the message size of the Freeman conversion is the same as that of the original BGN cryptosystem. The best-known method of expanding the message size by
t
times while preserving the (+, ×)-homomorphic feature requires
t
implementations of an initial scheme using the Chinese remainder theorem (CRT) directly. However, this method becomes impractical when
t
is large.
In this paper, we present how to expand the message size of the BGN cryptosystem while maintaining efficient parameter sizes. Our idea is to use Freeman’s product pairing with a bilinear group — of composite order
n
. In our scheme, all prime factors of
n
are public, and we use the prime factors to expand the message size. This distinguishes our scheme from many other schemes that use pairing groups of composite order, for such schemes assume that prime factors are private, not public
[6]
,
[7]
.
By using a bilinear group of composite order
n
=
p
_{1}
p
_{2}
⋯
p_{t}
with known prime factors
p_{i}
, we expand the bit size of a message by
t
times. We also prove that the indistinguishability under chosen plaintext attack (IND-CPA) security of our construction relies on the decisional Diffie–Hellman (DDH) assumption on the subgroups of order
p_{i}
of the underlying composite pairing group, for all
i
= 1, … ,
t
.
The rest of the paper is organized as follows. In Section II, we review the BGN cryptosystem and product pairing with projections. We also present a naive message expansion of a (+, ×)-homomorphic cryptosystem using the CRT. In Section III, we describe how to construct a product of composite pairing. In Section IV, we present our scheme with security proof. We also suggest how to select parameters and compare it with the naive approach of
[5]
. In Section V, we conclude our paper.
e
:
G
_{1}
×
G
_{2}
→
G_{T}
with |
G
_{1}
| = |
G
_{2}
| = |
G_{T}
| =
N
=
PQ
and
G_{j}
= <
g_{j}
>, where
N
is difficult to factor. The BGN cryptosystem consists of the following five algorithms:
α
, the size of plaintext, should be chosen to be as small as possible such that a decryption can still be efficiently computed.
Definition 1.
For a pairing
G
_{1}
| = |
G
_{2}
| = |
G_{T}
| =
n
. We note that Freeman only considers
n
to be a prime number in the product pairing; whereas, we consider a composite number
n
in the following.
For
x_{ij}
,
y_{ij}
,
z_{ij}
∈
Z_{n}
,
u
,
v
∈
G_{i}
, and
α
,
β
,
γ
,
v
∈
G_{T}
, we denote
j
= 1, 2, and
π
_{1}
((
g
_{11}
,
g
_{12}
)) = (
g
_{11}
,
g
_{12}
)
^{A}
=
π
_{2}
((
g
_{21}
,
g
_{22}
)) = (
g
_{21}
,
g
_{22}
)
^{B}
=
π_{T}
(
γ
_{1}
,
γ
_{2}
,
γ
_{3}
,
γ
_{4}
) = (
γ
_{1}
,
γ
_{2}
,
γ
_{3}
,
γ
_{4}
)
^{A⊗B}
.
With these projections, we see that (1) below holds.
For all
g
_{11}
,
g
_{12}
∈
G
_{1}
and
g
_{21}
,
g
_{22}
∈
G
_{2}
.
i
= 1, 2,
H_{i}
⊂ ker(
π_{i}
).
Combining with (1), we see that
H_{i}
of
G_{i}
when |
G_{i}
| is prime. Freeman converted the BGN cryptosystem to a scheme using a product of prime pairings with projection. Freeman’s conversion of the BGN to a product pairing is exactly the case
t
= 1 in our construction, which will be described later. The size of the plaintext of Freeman’s conversion of the BGN cryptosystem is the same as that of the original BGN cryptosystem. A simple approach of expanding the message size by
t
times is to perform
t
implementations of the basic scheme and combine them with the CRT.
q
_{1}
, … ,
q_{t}
) and (
p
_{1}
, … ,
p_{t}
), where the
q_{i}
’s are to be used to encode plaintexts and
p_{i}
’s to encrypt the resulting encoded plaintexts.
For
N
=
q
_{1}
q
_{2}
⋯
q_{t}
(
q_{i}
≠
q_{j}
), the CRT provides a ring isomorphism, mod
_{q1,…,qt}
:
Z_{N}
→
Z
_{q1}
× ⋯ ×
Z_{qt}
, defined by mod
_{q1,…,qt}
(
x
) = (
x
mod
q
_{1}
,…,
x
mod
q_{t}
). We see that the inverse of mod
_{q1,…,qt}
is CRT
_{(q1,…,qt)}
.
Remark.
A naive message expansion of a (+, ×)-homomorphic cryptosystem using CRT can be described as follows. Suppose we have a (+, ×)-homomorphic encryption scheme with message space
M
=
Z_{Q}
and ciphertext space
C
.
Set
N
=
q
_{1}
q
_{2}
⋯
q_{t}
(
q_{i}
≠
q_{j}
), where the
q_{i}
’s are primes such that
q_{i}
≤
Q
. The encryption process can then be defined as follows:
For any
m
∈
Z_{N}
, we encode
m_{i}
using the encryption scheme. Then, we obtain a ciphertext
c_{i}
∈
C
and set the ciphertext
c
of
m
as
c
= (
c
_{1}
,…,
c_{t}
) ∈
C^{t}
.
The decryption process is as follows. For a given ciphertext,
c
= (
c
_{1}
,…,
c_{t}
) ∈
C^{t}
, decrypt each
c_{i}
and obtain
m_{i}
∈
Z_{qi}
. Then, we compute
m
= CRT
_{(q1,…,qt)}
(
m
_{1}
,…,
m_{t}
).
Because the CRT is a ring isomorphism, the resulting encryption scheme is (+, ×) homomorphic. Therefore, one can expand the message size of the encryption by
t
times. However, we see that a ciphertext expansion of the same ratio is inevitable in this approach. Therefore, if
t
is large, then it becomes impractical.
n
with |
G
_{1}
| = |
G
_{2}
| =
G_{T}
| =
n
, where
G
_{1}
is a cyclic subgroup of
E
(
F_{q}
), an elliptic curve group over the finite field
F_{q}
,
G
_{2}
is a cyclic subgroup of
E
(
F_{qk}
), an elliptic curve group over the finite field
F_{qk}
, and
G_{T}
is a cyclic subgroup of
G_{T}
is a subgroup of
n
divides
q^{k}
such that (
q^{k}
−1)/
n
has a large enough prime factor to resist discrete logarithm problem solving for
G_{T}
as a subgroup of
G
_{1}
is a subgroup of
E
(
F_{q}
), which implies that
n
divides |
E
(
F_{q}
)|. Note that, we have
q
,
n
, tr,
k
,
D
), where tr =
q
+ 1 − |
E
(
F_{q}
)| is the trace of the elliptic curve,
k
is the embedding degree, and
D
is the discriminant.
Koblitz
[10]
found that an ordinary curve of embedding degree
k
> 2 with composite-order group could leak the factorization of the group order. As in many cryptographic schemes using composite pairings, if the prime factors of a group order are to be kept secret for its security, then an ordinary curve of embedding degree
k
> 2 should not be used. However, in our scheme, we use a composite pairing where all the prime factors are public. Therefore, we can use a higher embedding degree. The security requirement related to prime factors in our scheme is the DDH assumption on the cyclic group of each of the prime factors.
Currently, it is recommended that the prime factor
p
should be of 224 bits to guarantee the DDH assumption on the cyclic groups of order
p
until the year 2030
[3]
,
[4]
.
We present examples of bilinear groups of composite order
n
=
p
_{1}
p
_{2}
p
_{3}
for distinct primes
p
_{1}
,
p
_{2}
,
p
_{3}
of small sizes using the Cocks–Pinch method. In our experiment, we use MAGMA. In the following examples, we choose a generator,
g
_{2}
, from the elliptic curve over the base field since
E
(
F_{q}
) is also a subgroup of
E
(
F_{qk}
), which yields
g
_{2}
,
g_{T}
with the property of non-degeneracy in the pairing evaluation. In general, curves with small ratio of log
_{2}
n
and log
_{2}
q
are desirable to speed up the arithmetic on the elliptic curves
[9]
. On the other hand though, at times, a larger ratio of log
_{2}
n
and log
_{2}
q
is acceptable for the sake of a fast pairing computation. Not many results are known for the generation of pairing-friendly elliptic curves for pairings that are of composite order and public prime factors
[11]
. This necessitates further work on generating pairing-friendly elliptic curves for pairings that are of composite order.
The following are example parameters (
q
,
n
, tr,
k
,
D
), of composite order pairing
G
_{1}
| = |
G
_{2}
| = |
G_{T}
| =
n
.
Example 1.
We provide an example of pairing
n
=
p
_{1}
p
_{2}
p
_{3}
,
k
= 1,
D
= 1. We generate an elliptic curve over
F_{q}
, defined by
y
^{2}
=
x
^{3}
+
x
. We choose the cyclic groups
G
_{1}
= 〈
g
_{1}
〉,
G
_{2}
= 〈
g
_{2}
〉, and
G_{T}
= 〈
g_{T}
〉 as shown in
Table 1
.

Owing to the embedding degree (
k
= 1) in Example 1, the cyclic subgroups,
G_{i}
’s, are two distinct subgroups of elliptic curves over the field
F_{q}
, and
G_{T}
is a cyclic subgroup of the multiplicative group
Example 2.
We provide an example of a pairing,
n
=
p
_{1}
p
_{2}
p
_{3}
,
k
= 2,
D
= 1. We generate an elliptic curve over
F_{q}
, defined by
y
^{2}
=
x
^{3}
+
x
. And we choose the cyclic groups
G
_{1}
= 〈
g
_{1}
〉,
G
_{2}
= 〈
g
_{2}
〉, and
G_{T}
= 〈
g_{T}
〉 as follows (see
Table 2
).
Parameters for Example 2.
Because we consider the embedding degree
k
= 2 in this example,
G
_{2}
is a cyclic subgroup of
E
(
F
_{q2}
) and
G_{T}
is a cyclic subgroup of the multiplicative group
G
_{2}
⊂
E
(
F_{q}
) ⊂
E
(
F
_{q2}
), and
k
= 2 and implementations.
Example 3.
We provide an example of a pairing,
n
=
p
_{1}
p
_{2}
p
_{3}
,
k
= 4,
D
= 1. We consider an elliptic curve over
F_{q}
, defined by
y
^{2}
=
x
^{3}
+ 2
x
. In addition, we choose the cyclic groups
G
_{1}
= 〈
g
_{1}
〉,
G
_{2}
= 〈
g
_{2}
〉, and
G_{T}
= 〈
g_{T}
〉 as shown in
Table 3
.
Parameters for Example 3.
Because we consider the embedding degree
k
= 4 in this example,
G
_{2}
is a cyclic subgroup of
E
(
F
_{q4}
) and
G_{T}
is a cyclic subgroup of the multiplicative group
G
_{2}
⊂
E
(
F_{q}
) ⊂
E
(
F
_{q4}
), and
i
= 1, 2 and
G
of composite order, where the DDHP is infeasible on
G
. There are known results on the hardness of the discrete logarithm problem on a cyclic group of composite order in terms of the subgroups of prime orders
[9]
. However, we cannot find any results on the DDHP on a cyclic group of composite order. In this paper, we present how to assure the hardness of the DDHP on a cyclic group of composite order.
The DDHP on a cyclic group
G
is the problem of deciding if
z
=
g^{ab}
for a given random triple (
g
,
g^{a}
,
g^{b}
,
z
) ∈
G
^{4}
. For our purposes, we define the DDHP on the product of cyclic groups of prime order.
The DDHP for the group
G
_{p1}
×⋯×
G_{pt}
is the problem to decide whether
i
and for a randomly given tuple
G
and
G
_{p1}
×⋯×
G_{pt}
.
Theorem 1.
The DDHP for a cyclic group
G
with |
G
| =
n
=
p
_{1}
⋯
p_{t}
is equivalently hard to the DDHP for a product group
G
_{p1}
×⋯×
G_{pt}
, where
G_{pi}
= 〈
u_{i}
〉 with
u_{i}
=
g^{n/pi}
.
Proof.
It is enough to show that any DDHP instance for
G
can be converted to a DDHP instance for
G
_{p1}
×⋯×
G_{pt}
, which gives the correct answer to the original instance of the DDHP in
G
, and vice versa. Suppose that the DDHP instance (
g
,
g^{a}
,
g^{b}
,
z
) ∈
G
^{4}
is given. We compute an instance of DDHP for the group
G
_{p1}
×⋯×
G_{pt}
as follows:
u_{i}
=
g^{n/pi}
,
z_{i}
=
z^{n/pi}
. It is clear to see that
T
is a DDH tuple for
G
_{p1}
×⋯×
G_{pt}
if and only if (
g
,
g^{a}
,
g^{b}
,
z
) is a DDH tuple for
G
. Therefore, the solution of a DDHP for the instance
T
is the solution of the DDHP instance (
g
,
g^{a}
,
g^{b}
,
z
) in
G
.
Now, we suppose that an instance
S
of the DDHP for the group
G
_{p1}
×⋯×
G_{pt}
is given as
g
,
v
,
w
,
z
) of the DDHP for group
G
as follows:
g
,
v
,
w
,
z
) is a DDH tuple in
G
if and only if
S
is a DDH tuple in
G
_{p1}
×⋯×
G_{pt}
. Because the order of
u_{i}
,
z_{i}
’s is
p_{i}
, we see that
s_{i}
,
ζ_{i}
∈
Z
such that
g
,
v
,
w
,
z
) is a DDH tuple in
G
, then
G_{pi}
for all
i
= 1,…,
t
; that is,
S
is a DDH tuple in
G
_{p1}
×⋯×
G_{pt}
. Conversely, if
S
is a DDH tuple in
G
_{p1}
×⋯×
G_{pt}
, then (
g^{n/pi}
,
v^{n/pi}
,
w^{n/pi}
,
z^{n/pi}
) is a DDH tuple in
G_{pi}
for all
i
, which implies that (
g
,
v
,
w
,
z
) is a DDH tuple in
G
.
Therefore, the solution of the DDHP for the instance (
g
,
v
,
w
,
z
) in
G
is the solution of the DDHP instance
S
in
G
_{p1}
×⋯×
G_{pt}
. ■
By Theorem 1, we see that the DDHP in the cyclic group
G
with |
G
| =
n
=
p
_{1}
⋯
p_{t}
is hard if and only if the DDHP is hard in the cyclic subgroup of
G
of order
p_{i}
, for all
i
= 1, … ,
t
. Therefore, one has to choose
p_{i}
’s as large as the order of the cyclic group where the DDH assumption holds to assure the hardness of the DDHP in
G
. Currently, by taking the size of
p_{i}
’s to be as large as 224 bits, we can assume that the DDHP in
G
is hard.
t
times. In our construction, we set the message space as
Z_{N}
, where
N
=
q
_{1}
⋯
q_{t}
; the
q_{i}
’s are small distinct primes, where the discrete logarithm problem with an exponent less than
q_{i}
is easily solvable. Note the factor
q_{i}
is of the same size as the message size of the original BGN as well as Freeman’s construction. Therefore, our construction expands the plaintext size by up to
t
times compared to the original schemes.
KeyGen: for a given security parameter, proceed with the following:
m
∈
Z_{N}
,
_{×}
: for ciphertexts
_{+}
: for ciphertexts
c
_{1}
,
c
_{2}
, compute
c
, proceed with one of the following:
H_{i}
⊂ ker(
π_{i}
) and
e
(
π
_{1}
(
g
_{1}
),
π
_{2}
(
g
_{2}
)) =
π_{T}
(
e
(
g
_{1}
,
g
_{2}
)). Now, we check the correctness of our construction. First, we want to show that Dec(sk, Enc(pk,
m
)) =
m
. We consider Enc(
pk
,
m
) =
c
, which has the following form:
Therefore, we have
_{×}
in our construction. The input of the algorithm Eval
_{×}
is of the form
c
,
m
) =
c
and Enc(pk,
m'
) =
c
'
for some
m
,
m'
∈
Z_{N}
. Then, we get the following, successively:
The equality (*) above is true from the fact that
_{+}
.
Theorem 2.
If the subgroup decision problems of
H_{j}
are hard, then the new scheme in our construction is IND-CPA secure.
Proof.
It is enough to show that if there is a successful IND-CPA adversary
X
against our encryption scheme, then we can construct a successful solver
D
of the subgroup decisional problem of
j
(= 1 or 2). Without loss of generality, we assume
j
= 1 and the subgroup decision problem for
j
= 2 is hard. For a given instance (
H
_{1}
= 〈
h
_{1}
〉,
j
= 1,
D
acts as the challenger of an IND-CPA security game to the adversary
X
against our encryption with
H
_{2}
= 〈
h
_{2}
〉,
G
_{2}
= 〈
g
_{2}
〉). For the given messages
m
_{0}
,
m
_{1}
, which are arbitrarily chosen by the IND-CPA adversary
X
, the challenger
D
chooses random
b
∈ {0,1} and computes
D
sends
c
_{b}
to adversary
X
and then
X
responds with
b
' ∈ {0,1}. Challenger
D
outputs 1, which means
z
_{1}
∈
H
_{1}
, if and only if
b
' =
b
.
We consider three IND-CPA security games with respect to the same public key,
We note that Game
_{0}
is exactly the same as the IND-CPA security of our encryption scheme. From the hardness of the subgroup decision problem for
X
wins Game
_{1}
] − Pr[
X
wins Game
_{2}
] is negligible. Because
_{2}
] = 1/2.
For challenger
D
, as a solver of the subgroup decision problem, we have
X
is a successful IND-CPA adversary against our scheme, we see that
ϵ
(
n
) − 1/2 is non-negligible; therefore, |
ϵ
(
n
) − 1/2 + negl(
n
)| is non-negligible. Thus,
D
is a successful solver of the subgroup decision problem
G_{i}
| =
n
=
p
_{1}
⋯
p_{t}
for randomly chosen subgroup
H_{j}
.
Theorem 3.
The subgroup decision assumption of
H_{j}
is equivalent to the DDH assumption in the cyclic group
G_{j}
with |
G_{j}
| =
n
for
j
= 1, 2.
Proof.
We prove only the case where
j
= 1; the proof for
j
= 2 is similar. Suppose that one can solve the subgroup decision problem of group
u
,
v
,
y
,
z
)
G
_{1}
is given. We consider a subgroup
H
_{1}
= 〈(
u^{a}
,
v^{b}
)〉 of
H
_{1}
can be considered as a randomly chosen subgroup of
By solving the subgroup decision problem of
H
_{1}
= 〈(
u^{a}
,
v^{b}
)〉 and
u
,
v
,
y
,
z
) is a DDH tuple in
G
_{1}
. Therefore, we see that one can solve the DDHP in
G
_{1}
by using a solver of the subgroup decision problem of
G
_{1}
is solvable with non-negligible probability. We consider the subgroup decision problem of
By solving the DDHP in
G
_{1}
for the random instance (
u^{a}
,
v^{a}
,
y^{a}
,
z^{a}
), one can solve the given instance of the subgroup decision problem of
G
_{1}
. ■
Now, by the results of Theorems 1–3, we see that our construction using the pairing
G_{j}
= 〈
g_{j}
〉 and |
G_{j}
| =
n
=
p
_{1}
p
_{2}
⋯
p_{t}
, is IND-CPA secure if
p_{i}
is large enough to guarantee the DDH assumption on the cyclic group
i
= 1, 2, … ,
t
and
j
= 1, 2.
q^{k}
− 1)/
n
=
ℓ
is of 2,048 bits for the pairing
G
_{1}
| = |
G
_{2}
| = |
G_{T}
| =
n
and embedding degree
k
. Recall that
G
_{2}
is a subgroup of an elliptic curve group over the finite field
F_{q}
, and
G_{T}
is a subgroup of the multiplicative group
G
_{1}
is a subgroup of the elliptic curve group
E
(
F_{q}
), it is assumed that log
n
≤ log
q
. We can expand the message size to
t
times larger than the BGN cryptosystem by using |
G_{i}
| =
p
_{1}
p
_{2}
…
p_{t}
. According to reports
[3]
,
[4]
, to guarantee the DDH assumption on
G_{i}
until the year 2030, it is recommended as log
p_{i}
~ 224.
Table 4
suggests the suitable parameters of our construction for a 112-bit security level.

According to
Table 1
, for a 112-bit security level, using the embedding degree as
k
= 1, 2 expands the message by up to nine times. We note that the ciphertexts belong to either
q
can be used to encrypt a message. However, expanding the size of a message as much as up to
t
times by using the naive approach of direct CRT requires
t
implementations of the initial scheme, which makes it impractical for large
t
, such as
t
= 9. In particular, for any choice of embedding degree, we see that the ciphertext after Eval
_{×}
is an element in

In the case of
k
= 2, we need a pairing-friendly curve with ratio log
q
/log
n
= 1, which is very rare in the construction of the current pairing-friendly elliptic curves of composite order. Finding an efficient pairing-friendly elliptic curve of composite degree with rate log
q
/log
n
= 1 is an interesting subject of future research. Currently, selecting an embedding degree of
k
= 1 in our scheme is the most efficient solution, and it expands the size of a message by up to nine times that achieved by using Freeman’s product pairing of prime order.
This work was supported by the basic science Research Program of Korean Government (Grant number 2012R1A2A1A03006706, Grant number 2013R1A1A2206063268), Priority Research Centers Program of the Ministry of Education of Korea (Grant number 2009-0093827), and Brain Korea 21 plus Mathematical Science Team for Global Women Leaders.
esk9030@gmail.com
Soo Kyung Eom received her PhD degree in mathematics from Ewha Womans University, Seoul, Rep. of Korea, in 2011. She is a post-doctoral scholar at the Institute of Mathematical Sciences, Ewha Womans University. Her main research interests include pairing-based cryptography, such as efficiency and security issues for pairing computation and construction of elliptic curves.
hsl@ewha.ac.kr
Hyang-Sook Lee received her PhD degree in mathematics from Northwestern University, Evanstone, IL, USA, in 1993. She is currently a professor with the Department of Mathematics, Ewha Womans University, Seoul, Rep. of Korea. Her research interests are pairing-based cryptography, especially pairing computations, constructing pairing friendly curves, digital signatures, and public key cryptography.
Corresponding Author seongannym@ewha.ac.kr
Seongan Lim received her PhD degree in mathematics from Purdue University, West Lafayetle, IN, USA, in 1995. She is currently a research professor at the Institute of Mathematical Sciences, Ewha Womans University, Seoul, Rep. of Korea. Her research interests include public key cryptography and privacy preserving protocols.

BGN cryptosystem
;
pairing
;
product pairing
;
homomorphic encryption
;
decisional Diffie–Hellman problem

I. Introduction

Developing an efficient homomorphic encryption scheme is a hot issue in cryptography due to its versatility in providing security in cloud services. Currently, many homomorphic encryption schemes are constructed from lattices. However, a lattice-based homomorphic encryption scheme requires parameters of very large size, which makes such schemes impractical in the near future. On the other hand, pairing-based cryptography is now considered as practical for use with many platforms.
The Boneh, Goh, and Nissim (BGN) cryptosystem is additively homomorphic, but it allows multiplication over ciphertext only once. Such a restriction on a homomorphic evaluation might have limited applications. However, many statistics of numerical data can be expressed as quadratic polynomials and the BGN cryptosystem can be used to evaluate such statistics homomorphically over ciphertexts. The BGN cryptosystem can be used to construct an efficient secure auction protocol. Despite its invaluable contribution as an efficient (+, ×)-homomorphic encryption, the original BGN cryptosystem has, in practice, suffered from two challenging issues: message sizes are required to be very small and it uses larger elliptic curve groups.
The BGN cryptosystem uses a pairing
II. Preliminaries

- 1. BGN Cryptosystem

The original BGN cryptosystem uses a symmetric pairing; however, we present a scheme based on an asymmetric pairing by considering recently announced security issues related to symmetric pairing. The BGN cryptosystem uses a pairing
- 1) KeyGen: for security parameterλ, output

pk=( N,e: G 1 × G 2 → G T , g 1 , g 2 , h 1 = g 1 P , h 2 = g 2 P ), sk=Q

- 2) Enc: for a messagem∈ [0, 2α], outputc=(g1mh1r,g2mh2r')for randomly chosenr,r′∈ZN*
- 3) Eval×: for ciphertextsc1= (c11,c12),c2= (c21,c22) ∈G1×G2, computec×=e(c11,c22)
- 4) Eval+: for ciphertextsc1,c2∈G1×G2⋃GT, compute

c + ={ c 1 ⋅ c 2 c 1 , c 2 ∈ G 1 × G 2 , c 1 ⋅ c 2 if c 1 , c 2 ∈ G T , c 1 ⋅e( g 1 , c 22 ) if c 1 ∈ G T , c 2 ∈ G 1 × G 2 , e( g 1 , c 12 )⋅ c 2 if c 1 ∈ G 1 × G 2 , c 2 ∈ G T .

- 5) Dec: for a ciphertextc∈G1×G2⋃GT, compute

m={ log g 1 Q c 11 Q if c=( c 11 , c 12 )∈ G 1 × G 2 , log e ( g 1 , g 2 ) Q c Q if c∈ G T .

We note that
- 2. Product Pairing with Projections

We begin with a product pairing introduced by Freeman
[5]
for the BGN cryptosystem.
e ^ : G 1 × G 2 → G T ,

we define the product pairing
e: G 1 2 × G 2 2 → G T 4

by
e( ( g 11 , g 12 ),( g 21 , g 22 ) ) =( e ^ ( g 11 , g 21 ), e ^ ( g 11 , g 22 ), e ^ ( g 12 , g 21 ), e ^ ( g 12 , g 22 ) ).

To define the BGN cryptosystem over the product pairing, the following notations are used. Assume that |
X=[ x 11 x 12 x 21 x 22 ], Y=[ y 11 y 12 y 21 y 22 ], Z= [ z ij ] 1≤i,j≤4 .

We also denote
X⊗Y=[ x 11 y 11 x 11 y 12 x 12 y 11 x 12 y 12 x 11 y 21 x 11 y 22 x 12 y 21 x 12 y 22 x 21 y 11 x 21 y 12 x 22 y 11 x 22 y 12 x 21 y 21 x 21 y 22 x 22 y 21 x 22 y 22 ], (u,v) X =( u x 11 v x 21 , u x 12 v x 22 ),

and
(α,β,γ,ν) z = ( α z 11 β z 21 γ z 31 ν z 41 , α z 12 β z 22 γ z 32 ν z 42 , α z 13 β z 23 γ z 33 ν z 43 , α z 14 β z 24 γ z 34 ν z 44 ).

For a randomly chosen
( a j , b j )∈ Z n * × Z n * ,

we consider the subgroups
H 1 = 〈 ( g 1 a 1 , g 1 b 1 ) 〉 ⊂ G 1 2

and
H 2 = 〈 ( g 2 a 2 , g 2 b 2 ) 〉 ⊂ G 2 2 ,

as well as matrices
A=[ − b 1 − b 1 a 1 a 1 ], B=[ − b 2 − b 2 a 2 a 2 ].

We also define projections
π j : G j 2 → G j 2

for
π T : G T 4 → G T 4

as follows:
( g 11 − b 1 g 12 a 1 , g 11 − b 1 g 12 a 1 )

,
( g 21 − b 2 g 22 a 2 , g 21 − b 2 g 22 a 2 )

, and
(1) e( π 1 ( g 11 , g 12 ), π 2 ( g 21 , g 22 ) )= π T ( e( ( g 11 , g 12 ),( g 21 , g 22 ) ) ).

The reason is as follows. First, we have
e( π 1 ( g 11 , g 12 ), π 2 ( g 21 , g 22 ) ) =e( ( g 11 − b 1 g 12 a 1 , g 11 − b 1 g 12 a 1 ),( g 21 − b 2 g 22 a 2 , g 21 − b 2 g 22 a 2 ) ) =(γ,γ,γ,γ),

where
γ = e ^ ( g 11 − b 1 g 12 a 1 , g 21 − b 2 g 22 a 2 ) = e ^ ( g 11 , g 21 ) b 1 b 2 e ^ ( g 12 , g 22 ) a 1 a 2 e ^ ( g 11 , g 22 ) a 2 b 1 e ^ ( g 12 , g 21 ) a 1 b 2 .

We also have,
π T ( e( ( g 11 , g 12 ),( g 21 , g 22 ) ) ) = π T ( e ^ ( g 11 , g 21 ), e ^ ( g 11 , g 22 ), e ^ ( g 12 , g 21 ), e ^ ( g 12 , g 22 ) ) = ( e ^ ( g 11 , g 21 ), e ^ ( g 11 , g 22 ), e ^ ( g 12 , g 21 ), e ^ ( g 12 , g 22 ) ) A⊗B =( γ ˜ , γ ˜ , γ ˜ , γ ˜ ),

where
γ ˜ = e ^ ( g 11 , g 21 ) b 1 b 2 e ^ ( g 12 , g 22 ) a 1 a 2 e ^ ( g 11 , g 22 ) a 2 b 1 e ^ ( g 12 , g 21 ) a 1 b 2 =γ.

Therefore, (1) holds. We also have, for
π i ( ( g i a i , g i b i ) ) =( g i − a i b i + a i b i , g i − a i b i + a i b i ) =( 1 G i , 1 G i ),

or equivalently, we have
H 1 × G 2 2 ∪ G 1 2 × H 2 ⊂ker( π T ).

We also define the canonical projections as follows:
proj 1 : G 1 2 × G 2 2 → G 1 2 by proj 1 ( u 1 , u 2 )= u 1 ,

proj 2 : G 1 2 × G 2 2 → G 2 2 by proj 2 ( u 1 , u 2 )= u 2 ,

Freeman pointed out that the subgroup decision assumption for a subgroup
G i 2

is equivalent to the DDH assumption on
- 3. CRT

Throughout this paper, we use two public tuples of prime numbers, (
m ˜ = mod q 1 ,…, q t ( m )=( m 1 ,…, m t ), m i ≤Q

, and then encrypt each
III. Composite Product Pairing

- 1. Pairings of Composite Order

Boneh and others
[8]
constructed ordinary curves with composite-order bilinear groups using the Cocks–Pinch method. As a result, one can construct a pairing
e ^ : G 1 × G 2 → G T

of composite order
F q k *

.
Because
F q k *

, we see that
q k −1=| F q k * |

. By the Pohlig–Hellman algorithm
[9]
, it is necessary to choose
F q k *

. Currently, it is recommended to have a prime factor of 2,048 bits. We also note that
e ^ ( P 1 , P 2 )= f n, P 1 ( P 2 ) q k −1 n ,

where
f n, P 1 (*)

is a rational map, which is usually computed by using the Miller algorithm.
A bilinear map is parameterized by (
g T =e( g 1 , g 2 )∈ F q *

. Next, we should set generators
e ^ : G 1 × G 2 → G T

with |
e ^ : G 1 × G 2 → G T

with
Parameters for Example 1.

Values | |
---|---|

tr | 2 |

2054962877509987980780288079839124242750761599408078234952147994867614170371943383, where log_{2} | |

Curves | ^{2} = ^{3} + |

_{1}_{2}_{3} | 3777641531202213662745286501136101531862152453, where log_{2} _{2} _{1} = 49, log_{2} _{2} = 50, log_{2} _{3} = 52 |

_{1} | (154074463401954681164008506675678730231295984929127689069027356830329316305557358253327964255: 238551455294957387415182340779234776554140378987694308567900564272120457108798531248453486858) |

_{2} | (1282733480099721371687324949832027341047277751562377469778305621408877866761332660985780396938: 477971295518231100142302118752341259223360125489186662436028545037124158159908757895761682282) |

_{T} | 1983145573174149296524812391988656054182664195896827913997840764888507889682408512084900532019 |

F q *

.
e ^ : G 1 × G 2 → G T

with
Parameters for Example 2.

PPT Slide

Lager Image

F q 2 *

. For simplicity, we present the case
G T ⊂ F q * ⊂ F q 2 *

. In
[12]
, Scott presents an efficient setup for some choice of curves with
e ^ : G 1 × G 2 → G T

with
Parameters for Example 3.

PPT Slide

Lager Image

F q 4 *

. For simplicity, we present the case
G T ⊂ F q * ⊂ F q 4 *

.
For a given pairing,
e ^ : G 1 × G 2 → G T

, of composite order, we can define the product pairing
e: G 1 2 × G 2 2 → G T 4

as in Definition 1 with the projections
π i : G i 2 → G i 2

for
π T : G T 4 → G T 4

, where (1) holds.
- 2. DDH Problem (DDHP) on Cyclic Groups of Composite Order

In our paper, we consider a bilinear group
z i = u i a i b i

, for all
(( u 1 , u 2 ,…, u t ); u 1 a 1 ,…, u t a t , u 1 b 1 ,…, u t b t ; z 1 ,…, z t )

.
Now, we prove the following theorem on the equivalences of the hardness of the DDHP for the groups
T=( ( u 1 ,…, u t );( u 1 a 1 ,…, u t a t ),( u 1 b 1 ,… u t b t );( z 1 ,…, z t ) ),

where
u i a i = ( g a ) n/ p i , u i b i = ( g b ) n/ p i

, and
S= ( ( u 1 ,…, u t ); u 1 a 1 ,…, u t a t , u 1 b 1 ,…, u t b t ; z 1 ,…, z t ).

We compute an instance (
{ g= u 1 u 2 ⋯ u t , v= u 1 a 1 u 2 a 2 ⋯ u t a t , w= u 1 b 1 u 2 b 2 ⋯ u t b t , z= z 1 z 2 ⋯ z t .

Now, we show that (
{ g n p i = u i n p i , v n p i = u i a i n p i , w n p i = u i b i n p i , z n p i = z i n p i , or equivalently { ( g n p i ) ζ i = u i , ( v n p i ) ζ i = u i a i , ( w n p i ) ζ i = u i b i , ( z n p i ) ζ i = z i .

Here, we use the fact that there are
s i p i + ζ i ⋅ n p i =1

from
gcd( p i , n p i )=1

.
Therefore, we see that if (
( u i , u i a i , u i b i , z i )

is a DDH tuple in
IV. Our Construction

- 1. Proposed Scheme

We now present our message expansion of the BGN cryptosystem by using a product of composite pairing. We present how to expand the message size by up to
- 1) Generate a bilinear mape^:G1×G2→GTof a composite order |Gi| = |GT| =n=p1⋯pt, whereGj= 〈gj〉 forj= 1, 2 andp1, … ,ptare distinct primes ofλbits. And construct the composite product pairinge:G12×G22→GT4as in Definition 1.
- 2) Generategj∈Gj2at random.
- 3) Generate(a1,b1),(a2,b2)∈Zn*×Zn*at random and set

h 1 =( g 1 a 1 , g 1 b 1 ), h 2 =( g 2 a 2 , g 2 b 2 ), A=[ − b 1 − b 1 a 1 a 1 ], B=[ − b 2 − b 2 a 2 a 2 ].

- We denoteHi=〈hi〉⊂Gi2.
- 4) Set

{ π 1 ( u 1 , v 1 )= ( u 1 , v 1 ) A , π 2 ( u 2 , v 2 )= ( u 2 , v 2 ) B , π T ( γ 1 , γ 2 , γ 3 , γ 4 )= ( γ 1 , γ 2 , γ 3 , γ 4 ) A⊗B .

- 5) Set the message spaceZN, whereN=q1…qtandqi’s are small distinct primes, as described above.
- 6) Output

pk= ( N,( p i ) 1≤i≤t , g 1 , g 2 , h 1 , h 2 ,e: G 1 2 × G 2 2 → G T 4 ), sk=( π 1 , π 2 , π t ).

Enc: for a message
- a) for the prime factorsqiofN, compute modq1,…,qt(m) = (m1,…,mt) ∈Zq1×⋯×Zqt.
- b) compute the ciphertext, forn=p1⋯pt, and randomly chooser,r'∈Zn*.

c=( ( g 1 ) m 1 n p 1 +⋯+ m t n p t ( h 1 ) r , ( g 2 ) m 1 n p 1 +⋯+ m t n p t ( h 2 ) r ′ ).

Eval
c 1 , c 2 ∈ G 1 2 × G 2 2

, compute
c × =e( proj 1 ( c 1 ), proj 2 ( c 2 ) )∈ G T 4 .

Eval
c + ={ c 1 ⋅ c 2 Case( i ), c 1 ⋅ c 2 Case( ii ), c 2 ⋅e( g 1 , proj 2 ( c 1 ) ) Case( iii ), c 1 ⋅e( g 1 , proj 2 ( c 2 ) ) Case( iv ).

Here, we set
Case (i):
c 1 , c 2 ∈ G 1 2 × G 2 2

,
Case (ii):
c 1 , c 2 ∈ G T 4 ,

Case (iii):
c 1 ∈ G 1 2 × G 2 2 , c 2 ∈ G T 4 ,

Case (iv):
c 2 ∈ G 1 2 × G 2 2 , c 1 ∈ G T 4 .

Dec: for a ciphertext
- 1) Case 1:c∈GT4. Computew=πT(c)∈GT4. Fori= 1, 2, … ,t, computeyi=wn/pi, computezi = πT(e(g1,g2))n3/pi3,computeαi=logziyi. Computeα=CRT(q1,…,qt)(α1,…,αt). Outputαas the plaintext.
- 2) Case 2:c =((c11, c12), (c21, c22))∈G12 ×G22. Computew=π1(proj1(c))∈G12. Fori= 1, 2, … ,t, computeyi=wn/pi, computezi=(π1(g1))n2/pi2, computeαi=logziyi. Computeα=CRT(q1,…,qt)(α1,…,αt). Outputαas the plaintext.

- 2. Correctness of Our Construction

Recall the fact that
c=( g 1 m 1 n p 1 +⋯+ m t n p t ⋅ h 1 r , g 2 m 1 n p 1 +⋯+ m t n p t ⋅ h 2 r ′ ).

Then, we have the following, successively:
- 1)w=π1(proj1(c))=π1(g1)m1np1+⋯+mtnpt.
- 2)yi=wnpi=π1(g1)mi⋅n2pi2,
- 3)αi= logzi yi=mi, wherezi=(π1(g1))n2pi2.

α= CRT q 1 ,…, q t ( m 1 ,…, m t )=m.

Now, we check the correctness of Eval
c ' ∈ G 1 2 × G 2 2

such that Enc(pk,
- 1)c×=Eval×(pk,(c,c'))
- =e(proj1(c),proj2(c')) =e(g1m1np1+⋯+mtnpth1r,g2m'1np1+⋯+m'tnpth2r′).
- 2)w=πT(c×)
- =e(π1(g1)m1np1+⋯+mtnpt,π2(g2)m'1np1+⋯+m'tnpt).
- 3)yi=wnpi=e(π1(g1)minpi,π2(g2)m′inpi)npi….....(*)
- =e(π1(g1),π2(g2))mim′in3pi3 =πT(e(g1, g2))mim′n3pi3.
- 4)αi=logziyi=mimi' for zi=πT(e(g1,g2))n3pi3.

e( π 1 ( g 1 ) m i n p i , π 2 ( g 2 ) m ′ j n p j )=1 if i≠j.

Therefore, we have
α= CRT q 1 ,…, q t ( m 1 m ′ 1 ,…, m t m ′ t )=m m ′ .

Because the multiplications of the group elements correspond to the addition of the exponents, one can similarly show the correctness of Eval
- 3. Security Analysis

As in Freeman’s BGN cryptosystem, the IND-CPA security of our scheme is based on the hardness of the subgroup decision for
H j ⊂ G j 2

.
H j ⊂ G j 2

for randomly chosen subgroups
H j ⊂ G j 2

for some
G 1 2 =〈 g 1 〉, z 1 ∈ G 1 2

) of the subgroup decision problem for
pk=( e, g j ∈ G j 2 , h j ∈ H j ,j =1,2 )

for randomly chosen (
c b =( g 1 ϕ( m b ) z 1 r 1 , g 2 ϕ( m b ) h 2 r 2 ),

where
ϕ( m b )= ∑ m b,i n p i with mod q 1 ,…, q t ( m b )=( m b,1 ,…, m b,t ).

Challenger
pk=( e, g j ∈ G j 2 , h j ∈ H j ,j=1,2 )

. The differences of each game are from the construction of the ciphertext to be challenged in the following way:
- 1) Game0:c′b=(g1ϕ(mb)h1r1,g2ϕ(mb)h2r2),
- 2) Game1:c″b=(g1ϕ(mb)w1→r1,g2ϕ(mb)h2r2)
- for randomly chosenw1→∈G12,
- 3) Game2:c‴b=(g1ϕ(mb)w1→r1,g2ϕ(mb)w2→r2)
- for randomly chosenw1∈G12 and w1∈G22.

H 2 ⊂ G 2 2

,
c ″ b and c ‴ b

are indistinguishable for any probabilistic polynomial time adversary; therefore, we see that Pr[
c ‴ b

is uniformly distributed in
G 1 2 × G 2 2 ,

we see that Pr[X wins Game
Pr[D( H 1 =〈 h 1 〉, G 1 2 =〈 g 1 〉, z → 1 ∈ H 1 )=1] =Pr[X wins Game 0 ] =ϵ(n),

Pr[D( H 1 =〈 h 1 〉, G 1 2 =〈 g 1 〉, z 1 ∈ rand G 1 2 )=1] =Pr[X wins Game 1 ] =Pr[X wins Game 2 ]+negl(n) =1/2+negl(n).

Therefore, we see that
|Pr[D( H 1 =〈 h 1 〉, G 1 2 =〈 g 1 〉, z 1 ∈ H 1 )=1] −Pr[D( H 1 =〈 h 1 〉, G 1 2 =〈 g 1 〉, z 1 ∈ rand G 1 2 )=1]| =|ϵ(n)− 1 2 +negl(n)|.

Because
( H 1 =〈 h 1 〉, G 1 2 =〈 g 1 〉, z 1 ∈ G 1 2 )

. ■
Now, we analyze the strength of the subgroup decision assumption of
H j ⊂ G j 2

with |
H j ⊂ G j 2

for randomly chosen subgroup
G 1 2

for a randomly chosen subgroup with non-negligible probability. Suppose that an instance (
∈ G 1 4

of DDHP in
G 1 2

for randomly chosen
a,b∈ Z n *

so that
G 1 2

. Now, consider a tuple
w ′ =( y a , z b )∈ G 1 2

. We see that the following hold:
- 1)w'∈H1
- 2) (y,z) ∈ 〈(u,v)〉
- 3) (u,v,y,z) is a DDH tuple inG1.

G 1 2

for the randomly given subgroup
w ′ =( y a , z b )∈ G 1 2

, one can correctly decide whether (
G 1 2

. For the proof of the converse, suppose that the DDHP in
G 1 2

for
H 1 =〈( u,v) 〉⊂ G 1 2

and
(y,z)∈ G 1 2

. We see that the following are equivalent for randomly chosen
a∈ Z n * :

- 1) (ua,va,ya,za) is a DDH tuple inG1,
- 2) (ya,za) ∈H1
- 3) (y,z) ∈H1

G 1 2

. Therefore, we see that one can solve the subgroup decision problem of
G 1 2

by using a solver of the DDHP in
e ^ : G 1 × G 2 → G T

, where
G j, p i =〈 g j n/ p i 〉

for all
- 4. Selection of Parameters for Current Security Level

For the current security level (that is, 112-bit security until the year 2030
[3]
,
[4]
), it is required that (
e ^ : G 1 × G 2 → G T

with |
F q k *

. Because
Selecting parameters for 112-bit security.

1 | 2 | 4 | 6 | 12 | |
---|---|---|---|---|---|

log | 4,096 | 2,048 | 1,024 | 683 | 342 |

log | 2,048 | 2,048 | 1,024 | 683 | 342 |

9 | 9 | 4 | 3 | 1 |

G 1 2 × G 2 2

or
G T 4 ⊂ ( F q k ) 4

. Therefore, the bit-size of ciphertext in our scheme is at most 16,384.
Table 5
presents selection parameters for a 112-bit security level in Freeman’s construction using prime product pairing
[5]
. In the prime case as in
Table 2
, a relatively small
( G T 4 ) 9 ⊂ ( F q k ) 36

, which means that its bit-size is about 73,728. We also note that this is 4.5 times larger than our construction using composite pairing.
Prime (n) order case of 112-bit security.

1 | 2 | 4 | 6 | 12 | |
---|---|---|---|---|---|

log | 2,048 | 1,024 | 512 | 342 | 224 |

log | 224 | 224 | 224 | 224 | 224 |

V. Conclusion

In this paper, we presented how to expand the message size of the BGN cryptosystem using a product pairing of composite order. We use composite order not to provide the security of the scheme but to expand the message size. The security of our scheme is based on the DDH assumption on the subgroups of prime order of the underlying composite pairing group. We also presented how to select parameters that expand the message size more efficiently.
BIO

Boneh D.
,
Goh E.-J.
,
Nissim K.
2005
“Evaluating 2-DNF Formulas on Ciphertexts,”
Theory of Cryptography-TCC 2005, Springer Verlag, LNCS
3378
325 -
341

Tibor J.
,
Jorg S.
2013
“On the Analysis of Cryptographic Assumptions in the Generic Ring Model,”
J. Cryptology
26
(2)
225 -
245
** DOI : 10.1007/s00145-012-9120-y**

Fact Sheet Suite B Cryptography, NSA
https://www.nsa.gov/ia/programs/suiteb_cryptography/

2013
Algorithms for Qualified Electronic Signatures, BNetzA
BSI
updated with BSI Draft, Oct. 2013

Freeman D.
2010
“Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups,”
Proc. Int. Conf. Theory Appl. Cryptographic Techn.
44 -
61

Guillevix A.
2013
“Comparing the Pairing Efficiency over Composite Order and Prime Order Elliptic Curves,”
Appl. Cryptography Netw. Security, Springer LNCS
7954
357 -
372

Lee H.-S.
,
Lim S.
2015
“A Depth Specific Description of Somewhat Homomorphic Encryption and its Applications,”
Appl. Math. Inf. Sci.
9
(3)
1345 -
1353

Boneh D.
,
Rubin K.
,
Silverberg A.
2011
“Finding Composite Order Ordinary Elliptic Curves Using the Cocks-Pinch Method,”
J. Number Theory
131
832 -
841
** DOI : 10.1016/j.jnt.2010.05.001**

Pohlig S.
,
Hellman M.
1978
“An Improved Algorithm for Computing Logarithms over GF(P) and its Cryptographic Significance,”
IEEE Trans. Inf. Theory
24
(1)
106 -
110
** DOI : 10.1109/TIT.1978.1055817**

Koblitz N.
2010
“A Security in Composite-Order Pairing-Based Protocols with Embedding Degree K>2,” Cryptology ePrint Archive Report
227 -

Zhang X.
,
Lin D.
2011
“Efficient Pairing Computation on Ordinary Elliptic Curve of Embedding Degree 1 and 2,”
Cryptography Coding, LNCS
7089
309 -
326

Scott M.
2005
“Computing the Tate Pairing,”
Topic Cryptography, LNCS
3376
293 -
304

Citing 'Message Expansion of Homomorphic Encryption Using Product Pairing
'

@article{ HJTODO_2016_v38n1_123}
,title={Message Expansion of Homomorphic Encryption Using Product Pairing}
,volume={1}
, url={http://dx.doi.org/10.4218/etrij.16.0115.0630}, DOI={10.4218/etrij.16.0115.0630}
, number= {1}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Eom, Soo Kyung
and
Lee, Hyang-Sook
and
Lim, Seongan}
, year={2016}
, month={Mar}