Advanced
Message Expansion of Homomorphic Encryption Using Product Pairing
Message Expansion of Homomorphic Encryption Using Product Pairing
ETRI Journal. 2016. Mar, 38(1): 123-132
Copyright © 2016, Electronics and Telecommunications Research Institute (ETRI)
  • Received : July 08, 2015
  • Accepted : September 25, 2015
  • Published : March 01, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Soo Kyung Eom
Hyang-Sook Lee
Seongan Lim

Abstract
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.
Keywords
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 e : G × G GT with | G | = | GT | = 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 GP 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 pt with known prime factors pi , 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 pi 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.
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 e : G 1 × G 2 GT with | G 1 | = | G 2 | = | GT | = N = PQ and Gj = < gj >, where N is difficult to factor. The BGN cryptosystem consists of the following five algorithms:
  • 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 α , the size of plaintext, should be chosen to be as small as possible such that a decryption can still be efficiently computed.
- 2. Product Pairing with Projections
We begin with a product pairing introduced by Freeman [5] for the BGN cryptosystem.
Definition 1. For a pairing
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 | G 1 | = | G 2 | = | GT | = 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 xij , yij , zij Zn , u , v Gi , and α , β , γ , v GT , we denote
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 j = 1, 2, and
π T : G T 4 → G T 4
as follows: π 1 (( g 11 , g 12 )) = ( g 11 , g 12 ) A =
( g 11 − b 1 g 12 a 1 ,  g 11 − b 1 g 12 a 1 )
, π 2 (( g 21 , g 22 )) = ( g 21 , g 22 ) B =
( g 21 − b 2 g 22 a 2 ​, g 21 − b 2 g 22 a 2 )
, and πT ( γ 1 , γ 2 , γ 3 , γ 4 ) = ( γ 1 , γ 2 , γ 3 , γ 4 ) AB .
With these projections, we see that (1) below holds.
For all g 11 , g 12 G 1 and g 21 , g 22 G 2 .
(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 = 1, 2,
π 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 Hi ⊂ ker( πi ).
Combining with (1), we see that
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 Hi of
G i 2  
is equivalent to the DDH assumption on Gi when | Gi | 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.
- 3. CRT
Throughout this paper, we use two public tuples of prime numbers, ( q 1 , … , qt ) and ( p 1 , … , pt ), where the qi ’s are to be used to encode plaintexts and pi ’s to encrypt the resulting encoded plaintexts.
For N = q 1 q 2 qt ( qi qj ), the CRT provides a ring isomorphism, mod q1,…,qt : ZN Z q1 × ⋯ × Zqt , defined by mod q1,…,qt ( x ) = ( x mod q 1 ,…, x mod qt ). 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 = ZQ and ciphertext space C .
Set N = q 1 q 2 qt ( qi qj ), where the qi ’s are primes such that qi Q . The encryption process can then be defined as follows:
For any m ZN , we encode
m ˜ = mod q 1 ,…, q t ( m )=( m 1 ,…, m t ), m i ≤Q
, and then encrypt each mi using the encryption scheme. Then, we obtain a ciphertext ci C and set the ciphertext c of m as c = ( c 1 ,…, ct ) ∈ Ct .
The decryption process is as follows. For a given ciphertext, c = ( c 1 ,…, ct ) ∈ Ct , decrypt each ci and obtain mi Zqi . Then, we compute m = CRT (q1,…,qt) ( m 1 ,…, mt ).
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.
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 n with | G 1 | = | G 2 | = GT | = n , where G 1 is a cyclic subgroup of E ( Fq ), an elliptic curve group over the finite field Fq , G 2 is a cyclic subgroup of E ( Fqk ), an elliptic curve group over the finite field Fqk , and GT is a cyclic subgroup of
F q k *
.
Because GT is a subgroup of
F q k *
, we see that n divides
q k −1=| F q k * |
. By the Pohlig–Hellman algorithm [9] , it is necessary to choose qk such that ( qk −1)/ n has a large enough prime factor to resist discrete logarithm problem solving for GT as a subgroup of
F q k *
. Currently, it is recommended to have a prime factor of 2,048 bits. We also note that G 1 is a subgroup of E ( Fq ), which implies that n divides | E ( Fq )|. Note that, we have
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 ( q , n , tr, k , D ), where tr = q + 1 − | E ( Fq )| 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 ( Fq ) is also a subgroup of E ( Fqk ), which yields
g T =e( g 1 , g 2 )∈ F q *
. Next, we should set generators g 2 , gT 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
e ^ : G 1 × G 2 → G T
with | G 1 | = | G 2 | = | GT | = n .
Example 1. We provide an example of pairing
e ^ : G 1 × G 2 → G T
with n = p 1 p 2 p 3 , k = 1, D = 1. We generate an elliptic curve over Fq , defined by y 2 = x 3 + x . We choose the cyclic groups G 1 = 〈 g 1 〉, G 2 = 〈 g 2 〉, and GT = 〈 gT 〉 as shown in Table 1 .
Parameters for Example 1.
Values
tr 2
q 2054962877509987980780288079839124242750761599408078234952147994867614170371943383, where log2q= 309
Curves y2 = x3 + x
n = p1p2p3 3777641531202213662745286501136101531862152453, where log2 n = 151 with log2 p1 = 49, log2 p2 = 50, log2 p3 = 52
g1 (154074463401954681164008506675678730231295984929127689069027356830329316305557358253327964255: 238551455294957387415182340779234776554140378987694308567900564272120457108798531248453486858)
g2 (1282733480099721371687324949832027341047277751562377469778305621408877866761332660985780396938: 477971295518231100142302118752341259223360125489186662436028545037124158159908757895761682282)
gT 1983145573174149296524812391988656054182664195896827913997840764888507889682408512084900532019
Owing to the embedding degree ( k = 1) in Example 1, the cyclic subgroups, Gi ’s, are two distinct subgroups of elliptic curves over the field Fq , and GT is a cyclic subgroup of the multiplicative group
F q *
.
Example 2. We provide an example of a pairing,
e ^ : G 1 × G 2 → G T
with n = p 1 p 2 p 3 , k = 2, D = 1. We generate an elliptic curve over Fq , defined by y 2 = x 3 + x . And we choose the cyclic groups G 1 = 〈 g 1 〉, G 2 = 〈 g 2 〉, and GT = 〈 gT 〉 as follows (see Table 2 ).
Parameters for Example 2.
PPT Slide
Lager Image
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 GT is a cyclic subgroup of the multiplicative group
F q 2 *
. For simplicity, we present the case G 2 E ( Fq ) ⊂ E ( F q2 ), and
G T ⊂ F q * ⊂ F q 2 *
. In [12] , Scott presents an efficient setup for some choice of curves with k = 2 and implementations.
Example 3. We provide an example of a pairing,
e ^ : G 1 × G 2 → G T
with n = p 1 p 2 p 3 , k = 4, D = 1. We consider an elliptic curve over Fq , defined by y 2 = x 3 + 2 x . In addition, we choose the cyclic groups G 1 = 〈 g 1 〉, G 2 = 〈 g 2 〉, and GT = 〈 gT 〉 as shown in Table 3 .
Parameters for Example 3.
PPT Slide
Lager Image
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 GT is a cyclic subgroup of the multiplicative group
F q 4 *
. For simplicity, we present the case G 2 E ( Fq ) ⊂ E ( F q4 ), and
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 i = 1, 2 and
π 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 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 = gab for a given random triple ( g , ga , gb , 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 ×⋯× Gpt is the problem to decide whether
z i = u i a i b i
, for all i and for a randomly given tuple
(( 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 G and G p1 ×⋯× Gpt .
Theorem 1. The DDHP for a cyclic group G with | G | = n = p 1 pt is equivalently hard to the DDHP for a product group G p1 ×⋯× Gpt , where Gpi = 〈 ui 〉 with ui = gn/pi .
Proof. It is enough to show that any DDHP instance for G can be converted to a DDHP instance for G p1 ×⋯× Gpt , which gives the correct answer to the original instance of the DDHP in G , and vice versa. Suppose that the DDHP instance ( g , ga , gb , z ) ∈ G 4 is given. We compute an instance of DDHP for the group G p1 ×⋯× Gpt as follows:
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 ui = gn/pi ,
u i a i  = ( g a ) n/ p i ​,   u i b i  = ( g b ) n/ p i
, and zi = zn/pi . It is clear to see that T is a DDH tuple for G p1 ×⋯× Gpt if and only if ( g , ga , gb , 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 , ga , gb , z ) in G .
Now, we suppose that an instance S of the DDHP for the group G p1 ×⋯× Gpt is given as
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 , v , w , z ) of the DDHP for group G as follows:
{ 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 , v , w , z ) is a DDH tuple in G if and only if S is a DDH tuple in G p1 ×⋯× Gpt . Because the order of ui , zi ’s is pi , we see 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 si , ζi Z such that
s i p i + ζ i ⋅ n p i =1
from
gcd( p i , n p i )=1
.
Therefore, we see that if ( g , v , w , z ) is a DDH tuple in G , then
( u i , u i a i , u i b i , z i )
is a DDH tuple in Gpi for all i = 1,…, t ; that is, S is a DDH tuple in G p1 ×⋯× Gpt . Conversely, if S is a DDH tuple in G p1 ×⋯× Gpt , then ( gn/pi , vn/pi , wn/pi , zn/pi ) is a DDH tuple in Gpi 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 ×⋯× Gpt .                                       ■
By Theorem 1, we see that the DDHP in the cyclic group G with | G | = n = p 1 pt is hard if and only if the DDHP is hard in the cyclic subgroup of G of order pi , for all i = 1, … , t . Therefore, one has to choose pi ’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 pi ’s to be as large as 224 bits, we can assume that the DDHP in G is hard.
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 t times. In our construction, we set the message space as ZN , where N = q 1 qt ; the qi ’s are small distinct primes, where the discrete logarithm problem with an exponent less than qi is easily solvable. Note the factor qi 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:
  • 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 m ZN ,
  • 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 × : for ciphertexts
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 + : for ciphertexts c 1 , c 2 , compute
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 c , proceed with one of the following:
  • 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 Hi ⊂ 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:
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.
Therefore, we have
α= CRT q 1 ,…, q t ( m 1 ,…, m t )=m.
Now, we check the correctness of Eval × in our construction. The input of the algorithm Eval × is of the form c ,
c ' ∈ G 1 2 × G 2 2
such that Enc(pk, m ) = c and Enc(pk, m' ) = c ' for some m , m' ZN . Then, we get the following, successively:
  • 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.
The equality (*) above is true from the fact that
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
.
Theorem 2. If the subgroup decision problems of
H j ⊂ G j 2
for randomly chosen subgroups Hj 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
H j ⊂ G j 2
for some 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 〉,
G 1 2 =〈 g 1 〉, z 1 ∈ G 1 2
) of the subgroup decision problem for j = 1, D acts as the challenger of an IND-CPA security game to the adversary X against our encryption with
pk=( e, g j ∈ G j 2 ,   h j ​∈  H j ​,j =1,2 )
for randomly chosen ( 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
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 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,
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.
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
H 2 ⊂ G 2 2
,
c ″ b  and  c ‴ b
are indistinguishable for any probabilistic polynomial time adversary; therefore, we see that Pr[ X wins Game 1 ] − Pr[ X wins Game 2 ] is negligible. Because
c ‴ b
is uniformly distributed in
G 1 2 × G 2 2 ,
we see that Pr[X wins Game 2 ] = 1/2.
For challenger D , as a solver of the subgroup decision problem, we have
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 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
( 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 | Gi | = n = p 1 pt for randomly chosen subgroup Hj .
Theorem 3. The subgroup decision assumption of
H j ⊂ G j 2
for randomly chosen subgroup Hj is equivalent to the DDH assumption in the cyclic group Gj with | Gj | = 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
G 1 2
for a randomly chosen subgroup with non-negligible probability. Suppose that an instance ( u , v , y , z )
∈ G 1 4
of DDHP in G 1 is given. We consider a subgroup H 1 = 〈( ua , vb )〉 of
G 1 2
for randomly chosen
a,b∈ Z n *
so that H 1 can be considered as a randomly chosen subgroup of
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.
By solving the subgroup decision problem of
G 1 2
for the randomly given subgroup H 1 = 〈( ua , vb )〉 and
w ′ =( y a , z b )∈ G 1 2
, one can correctly decide whether ( 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 2
. For the proof of the converse, suppose that the DDHP in G 1 is solvable with non-negligible probability. We consider the subgroup decision problem of
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
By solving the DDHP in G 1 for the random instance ( ua , va , ya , za ), one can solve the given instance of the subgroup decision problem of
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 G 1 .                                      ■
Now, by the results of Theorems 1–3, we see that our construction using the pairing
e ^ : G 1 × G 2 → G T
, where Gj = 〈 gj 〉 and | Gj | = n = p 1 p 2 pt , is IND-CPA secure if pi is large enough to guarantee the DDH assumption on the cyclic group
G j, p i =〈 g j n/ p i 〉
for all i = 1, 2, … , t and j = 1, 2.
- 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 ( qk − 1)/ n = is of 2,048 bits for the pairing
e ^  : G 1 × G 2 → G T
with | G 1 | = | G 2 | = | GT | = n and embedding degree k . Recall that G 2 is a subgroup of an elliptic curve group over the finite field Fq , and GT is a subgroup of the multiplicative group
F q k *
. Because G 1 is a subgroup of the elliptic curve group E ( Fq ), it is assumed that log n ≤ log q . We can expand the message size to t times larger than the BGN cryptosystem by using | Gi | = p 1 p 2 pt . According to reports [3] , [4] , to guarantee the DDH assumption on Gi until the year 2030, it is recommended as log pi ~ 224. Table 4 suggests the suitable parameters of our construction for a 112-bit security level.
Selecting parameters for 112-bit security.
k 1 2 4 6 12
log q 4,096 2,048 1,024 683 342
log n 2,048 2,048 1,024 683 342
t 9 9 4 3 1
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
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 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
( 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.
k 1 2 4 6 12
log q 2,048 1,024 512 342 224
log n 224 224 224 224 224
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.
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.
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.
BIO
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.
References
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