Approach of the value of a rent when non-central moments of the capitalization factor are known: an R application with interest rates following normal and beta distributions
Ratio Mathematica ISSN: 1592-7415
Vol. 34, 2018, pp. 49-65 eISSN: 2282-8214
49
A New Provably Secure Cryptosystem
Using Dedekind Domain Direct Product
Approach
Amir Hassani Karbasi1
Received: 27-02-2018. Accepted: 01-06-2018. Published: 30-06-2018
doi: 10.23755/rm.v34i0.404
©Amir Hassani Karbasi
Abstract
We would like to prevent, detect, and protect communication and
information systems' attacks, which include unauthorized reading of a
message of file and traffic analysis or active attacks, such as modification
of messages or files, and denial of service by providing cryptographic
techniques. If we prove that an encryption algorithm is based on
mathematical NP-hard problems, we can prove its security. In this paper,
we present a new NTRU-Like public-key cryptosystem with security
provably based on the worst-case hardness of the approximate lattice
problems (NP-hard problems) in some structured lattices (ideal lattices) in
order to attain the applicable objectives of preserving the confidentiality
of communication and information system resources (includes hardware,
software, firmware, information/data, and telecommunications). Our
proposed scheme is an improvement of ETRU cryptosystem. ETRU is an
NTRU-Like public-key cryptosystem based on the Eisenstein integers
1 Department of Mathematics, University of Guilan, Rasht, Iran.
karbasi@phd.guilan.ac.ir
Amir Hassani Karbasi
50
where is a primitive cube root of unity. ETRU has heuristic security and it
has no proof of security. We show that our cryptosystem has security
stronger than that of ETRU, over Cartesian product of Dedekind domains
and extended cyclotomic polynomials. We prove the security for our main
algorithm from the R-SIS and R-LWE problems as NP-hard problems.
Keywords: Lattice-based cryptography; Ideal lattices; ETRU; Provable
security; Dedekind domain.
2010 subject classification: 94A60; 11T71; 14G50; 68P25.
1. Introduction
Public-key cryptography has many exciting applications for web browsers,
e-mail programs, cell phones, bank cards, RFID tags, smart cards, government
communications, banking systems, and so on. The users to communicate over
non-secure channels without any prior communication can use public-key
cryptography. The idea of public-key cryptography was first proposed by Diffie
and Hellman in 1976 [1]. Lattice-based cryptography as a field of public-key
cryptography has attracted considerable interest and it has been categorized into
post-quantum cryptography [6]. Lattice-based cryptography enjoys efficient
implementations, very strong security proofs based on worst-case hardness, as
well as great simplicity. Our focus here will be mainly on the theoretical aspects
of lattice-based cryptography.
The NTRU cryptosystem which is a famous lattice-based crypto scheme
devised by Hoffstein, Pipher and Silverman, was first presented at the Crypto’96
rump session [2]. Although its structure relies on arithmetic over the quotient
polynomial ring [ ]/ 1
N
q
x x − Z for N prime and q a small integer, it was quickly
shown that breaking it could be reflected as a problem over Euclidean lattices
[3]. At the ANTS’98 conference, the NTRU authors presented an improved
variant including a thorough assessment of its practical security against lattice
attacks [4]. The NTRU cryptosystem standard number and version is IEEE
P1363.1 [5]. The NTRU encryption (NTRUEncrypt) system is also often
considered as the most practical post-quantum public-key crypto scheme [6] and
this scheme uses the properties of structured lattices to achieve high efficiency
but its security remains heuristic and it was an important open challenge to
provide a provably secure scheme with comparable efficiency. For example, an
8-dimensional lattice in 2D view is shown in Figure 1.
By rising number of attacks and practical variants of NTRU, provable
security in lattice-based cryptography is developed. The first provably secure
lattice-based cryptosystem and its variant of GapSVP in arbitrary lattices were
presented by Ajtai and Dwork [8, 9]. Ajtai’s average-case problem is now
reflected to as the Small Integer Solution problem (SIS). Another major
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
51
achievement in this field was the introduction in 2005 of the Learning with
Errors problem (LWE) by Regev [13]. Micciancio [10] presented an alternative
based on the worst-case hardness of the restriction of Poly(n)-SVP to cyclic
lattices and succeeded in restricting SIS to structured matrices while preserving
a worst-case to average-case reduction, which correspond to ideals in
polynomial ring [ ]/ 1
n
x x − Z . Subsequently, Lyubashevsky and Micciancio
[11] and independently Peikert and Rosen [12] showed how to modify
Micciancio's function to construct an efficient and provably secure collision
resistant hash function. So, they introduced the more general class of ideal
lattices, which correspond to ideals in polynomial rings [ ]/
q
x Z with a
that is irreducible cyclotomic polynomial, also is sparse (e.g., 1
n
x = + for n
a power of 2). Their system relies on the hardness of the restriction of Poly(n)-
SVP to ideal lattices (called Poly(n)-Ideal-SVP). The average-case collision-
finding problem is a natural computational problem called Ideal-SIS, which has
been reflected to be as hard as the worst-case instances of Ideal-SVP. In 2011,
Stehlé and Steinfeld [14] proposed a structured variant of the NTRU, which they
proved as hard as CPA security from the hardness of a variant of R-SIS and R-
LWE (Ring Learning with Errors problem). R-LWE has great efficiency and
provides more natural and flexible cryptographic constructions. The current
paper was motivated by [14], in which the integers were replaced with the ring
of Cartesian product of Eisenstein integers.
Figure 1. An 8-dimensional lattice in 2D view.
The ETRU is obtained from the NTRU by replacing Z with the ring of
Eisenstein integers [7]. It is faster and has smaller size of keys for the same or
better level of security than that of NTRU. Both division algorithm for
Eisenstein integers and the choice of lattice embedding are integral, thus
significantly improving their efficiency over the complex-valued versions
Amir Hassani Karbasi
52
proposed in [15]. Note that the ETRU security is based on both SVP and then
CVP so its security remains heuristic. The other author's lattice-based schemes
are [20 – 28] which are suitable for application to WSNs and IoT [29-31].
In this paper, our proposed cryptosystem based on extended ideal lattices
over
3 3
: ( [ ] [ ])[ ]/R xz z= ´ < F >Z Z (for
1
(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + +
with n+1 a prime) exploits the properties of the ETRU structured lattice to
achieve high efficiency and it has IND-CPA security based on ideal lattices with
established hardness of R-SIS and R-LWE problems. We prove that our
modification of ETRU is provably secure, assuming the quantum hardness of
standard worst-case problems over extended ideal lattices.
The rest of this paper is structured as follows: In section 2, we shortly review
the ETRU system and explain the security related to the computational
problems. In section 3, we study ideal lattices, R-SIS and R-LWE problems. In
section 4, we suggest a key generation algorithm, where the generated public
key follows a distribution for which Ideal-SVP reduces to R-LWE. In section 5,
we make our modified ETRU cryptosystem as secure as worst-case problems
over ideal lattices. Finally, the paper concludes in section 6.
2. ETRU Cryptosystem
2.1. Parameters Creation
We denote by
3
a complex cube root of unity, that is
3
3
1 = where
3
31 / 2( 1 )i = − + since
3
3
2
3 33
1 ( 1)( 1) 0 − = − + + = , we have
2
3 3
1 0 + + =
and hence
2
3 3
1 = − − . The ring of Eisenstein integers, denoted
3
[ ]Z , is the set
of complex numbers of the form
3
a b = + with ,a b Z . For
3
a b = + we will
define
22
( )d a b ab = = + − which is the square of the usual analytic complex
norm | | . Note that ( )d is a positive integer for 0 since ( )d is the square
of a norm and ,a b Z . For any complex numbers , we have that | | | | . | | =
hence it follows that ( ) ( ). ( )d d d = . The Eisenstein integers
3
[ ]Z form a
lattice in generated by the basis
3
{1, }B = . Note that the two basis vectors 1
and
3
, represented by the vectors (1, 0) and ( 1 / 2, 3 / 2)− in 2, have 120
degrees with equal length. Let be an Eisenstein integer. We define the ideal
3
( ) { }| ,L a b a b = + Z . Therefore ( )L is a lattice generated by the basis
3
{ , } . According to [7], we deduce that the Eisenstein integers are an
Euclidean domain that the units and Eisenstein primes exist. For each matrix B
with entries that are Eisenstein integers we will set < B > to be the 2n by 2n
matrix. We choose an prime n and set
3
[ 1, ]/
n
R x x= − Z , we also choose p
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
53
and q in
3
[ ]Z relatively prime, with |q| much larger than |p|. Since each ETRU
coefficient is a pair of integers, an element of ETRU at degree n is comparable
with an element of NTRU of degree n' = 2n.
2.2. Key Generation
Private key consists of two randomly chosen polynomials f, g in R. We
define the inverses Fq = f -1 in Rq and Fp = f -1 in Rp. Hence public key is
generated by h = Fq * g. The public key h is a polynomial with n coefficients
which are reduced modulo q. Each coefficient consists of two integers which by
Theorem 3 in [7] can be stored as binary strings of length
2
log (4 | | /3)q , hence
the size of the ETRU public key is
2
2 log (4 | | /3)K n q= . An NTRU public key,
corresponding to polynomials with n' = 2n coefficients reduced modulo an
integer q', has size
2
' ' log ( ')K n q= . Therefore to maintain the same key size as
NTRU with n' = 2n and q' = 2k , we should choose | | (3 / 4) 'q q so that
2 2
log (4 | | /3) log ( ')q q .
2.3. Encryption
Each encryption requires the user to compute * mod e ph m q= + where m
is a plaintext and is a ephemeral key. In total one counts
22
' ' ~ 4 2n n n n+ +
operations for NTRU encryption at ' ~ 2n n in contrast to only
2
3 27n n+
operations for ETRU encryption.
2.4. Decryption
Each decryption requires the user to compute both * mod a f e q= and
* mod
p
m F a p= . For decryption, we have
22
2 ' 2 ' ~ 8 4n n n n++ operations for
NTRU and only
2
6 29n n+ operations for ETRU.
2.5. Decryption Failure and Security
In [7] is shown that in fact | |~ (3 / 8) 'q q is an optimal choice in view of
security against decryption failure and lattice attacks. Based on this choice the
public key size for ETRU will be smaller than that of the NTRU public key.
3. Ideal Lattices and Their Hard Problems
Our results are restricted to the sequence of rings
3 3
: ( [ ] [ ])[ ]/R xz z= ´ < F >Z Z
with 1(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + + where n+1 is a prime
Amir Hassani Karbasi
54
that is irreducible cyclotomic polynomial. We can refer to [19] for
irreducibility of cyclotomic polynomials
n
F in
3
[ ][ ]xzZ where n is prime in
3
[ ]zZ
The R-LWE problem is known to be hard when is cyclotomic [16]. The
security analysis for our proposed scheme allows encrypting and decrypting
( )n plaintext bits for ( )O n bit operations, while achieving security against
( )
2
g n
-time attacks, for any g(n) that is (log )n and o(n), assuming the worst-case
hardness of poly(n)-Ideal-SVP against
( ( ))
2
O g n
-time quantum algorithms for
each element component-wise in complex pair-wise system because note that
each polynomial in R has its coefficients of the form
3 3
(( , ), ( , ))
i i i i
a b c dz z (ai, bi 3 )
where , , ,
i i ii
a b c d Z , so in this paper, all operations execute for ai's, bi's, ci's and
di's separately, that is,
2 component-wise. The latter assumption is believed
to be valid for any g(n)=o(n). Also we can define £ and ³ as poset orders.
3.1. Notation
Similar to [14] we denote by
1 2 3 4( , , , ) 1 2 3 4
( ), , ,x x x x
(respectively
1 2 3 4( , , , )
) the standard n-dimensional Gaussian function (respectively
distribution) with center (0,0,0,0) and variance
1 2 3 4
( ), , , . We denote by
( )Exp the exponential distribution on
4n with mean and by U(E) the uniform
distribution over a finite set E . If D1 and D2 are two distributions on discrete
oracle E, their statistical distance is
2 1 21 1 2 3 4 1 2 3 4
( ; ) 1 / 2 | ( ) ( ) |, , , , , ,
x E
D D D x x x x D x x x x
= − . We write z D when the
random variable z is chosen from the distribution D. The integer n is called the
lattice dimension. Note that in our proposed scheme with pairwise components
and coefficients in vectors, the dimension increases four times without
increasing n. The minimum
1
( )L (respectively 1 ( )L
) is the Euclidean
(respectively infinity) norm of any shortest vector of L \ (0,0,0,0).
The dual of lattice L is the lattice
1 2 3 4
4 4
1 2 3 4 1 2 3 4
ˆ {( ) }: , ( ), (, , , , , , , , , )
i i i i
n
L c c c c R c c c ci b b b b= Z where the bij’s
are a basis of L. For a lattice L,
1 2 3 4
( ) (0, 0, 0, 0), , , and (c1,c2,c3,c4)
4n,
we define the lattice Gaussian distribution of support L, deviation
1 2 3 4
( ), , ,
and center (c1,c2,c3,c4) by
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
( , , , ),( , , , ) ( , , , ),( , , , )1 2 3 4 1 2 3 4,( , , , ),( , , , ) 1 2 3 4 1 2 3 4
( ) ( ) / ( ), , , , , ,
c c c c c c c cL c c c c
D b b b b b b b b L
= , for any
1 2 3 4
( ), , ,b b b b L .
We extend the definition of
1 2 3 4 1 2 3 4,( , , , ),( , , , )L c c c c
D
to any M L
(not necessarily a sub-lattice), by setting
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
55
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
( , , , ),( , , , ) ( , , , ),( , , , )1 2 3 4 1 2 3 4,( , , , ),( , , , ) 1 2 3 4 1 2 3 4
( ) ( ( )) / ( ( )), , , , , ,
c c c c c c c cM c c c c
D b b b b b b b b M
=
and for
1 2 3 4
( ) (0, 0, 0, 0), , , , we denote the smoothing parameter
1 2 3 4( , , , )
( )L
as the smallest
1 2 3 4
( ) (0, 0, 0, 0), , , such that
1 2 3 4(1,1,1,1)/( , , , ) 1 2 3 4
ˆ( \ (0, 0, 0, 0)) ( ), , ,L
.
It quantifies how large
1 2 3 4
( ), , , needs to be for
1 2 4 1 2 3 4,( , , 3, ),( , , , )L c c c c
D
to
behave like a continuous Gaussian. We will typically consider 2
n
i
−
= .
3.2. Definition
Let n+1 be a prime and 1(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + +
which is irreducible over
3 3
[ ] [ ]z z´Q Q also let
3 3
: ( [ ] [ ])[ ]/R xz z= ´ < F >Z Z . An
(integral) ideal I of R is a subset of R closed under addition and multiplication by
arbitrary elements of R. By mapping polynomials to the vectors of their
coefficients, we see that an ideal (0, 0, 0, 0)I corresponds to a full-rank sub-
lattice of 4n. Thus we can view I as both a lattice and an ideal. An ideal lattice
for is a sub-lattice of (*)2n that corresponds to a non-zero ideal I R . The
algebraic norm N(I) is equal to det I, where I is regarded as a lattice. In the
following, an ideal lattice will implicitly refer to a -ideal lattice.
By restricting SVP (respectively -SVP) to instances that are ideal lattices,
we obtain Ideal-SVP (respectively -ideal-SVP). The latter is implicitly
parameterized by the polynomial
1
(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + + . No algorithm is known to
perform non-negligibly better for -ideal-SVP than for -SVP [14].
3.3. Properties of The Ring of Cartesian Product
For 1 2 3 4( ), , ,v v v v R we define by ||(v1, v2, v3, v4)|| its Euclidean norm. We
denote the multiplicative expansion factor by
, 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
( ) max (|| ( ) ( ) ||) / (|| ( ) || . || ( ) ||), , , , , , , , , , , ,
u v Ri i
R u u u u v v v v u u u u v v v v
= .
Since is the n+1-th cyclotomic polynomial, the ring R is exactly the maximal
order of the cyclotomic field 3 3( [ ] [ ])[ ]: [ , ']
x
K
z z
z z
´
= @
F
Q Q
Q . We denote by
1 2 3 4
( ), , ,
i i i i i n
the complex embeddings. We can choose
2 1 2 1 2 1 2 1
1 2 3 4 1 2 3 4
( : ( ), , , ) , , ,
i i i i
i i i i
K K
+ + + +
→ for i n .
Lemma 3.1. The norm of as an element in
3
( ) is a2 + b2 - ab. This is
also
2
| | , where is denoted as an element of .
Amir Hassani Karbasi
56
Proof. The minimal polynomial of
3
over is the cyclotomic polynomial
2
3
1x x = + + . Thus, there exist exactly two monomorphisms (isomorphisms
in this case) from to fixing and permuting the roots of
3
. Since
3
has
two roots
3
and
2
3
, the embeddings are
3 31
( )a b a b + = + and
3
2
2 3
( )a b a b + = + , where ,a b . By definition, the algebraic norm of
3
a b = + is
2
2
3
1
3
( ) ( ) ( )
( )( )
N
a b a b
=
= + +
Note that
3
2
3
= and
33
1 = −+ . So we have
2
2
3 3
3 3
2
2
( ) ( )( )
( )
N a b a b
a b ab
a b ab
= + +
= + + +
= + −
Now we show that
2
( ) ( ) | |d N = = .
2
3
2
2
2
2 2
2
1 3
2
3
2 2
| | | |
| ( ) |
| |
3
2 2
b b
a b
i
a b
i
a
b b
a
a b ab
− +
= +
= +
= − +
= − +
= + −
□
In rest of the paper, all of computations are done component-wise for each
complex element as an integer. We define T2-norm by
2 2 2 22
1 1 2 2 3 3 4 42 1 2 3 4
( ) ( | ( ) | | ( ) | | ( ) | | ( ) |, , , , , , )
i i i i
i n i n i n i n
T
= . We also
use the fact that for any 1 2 3 4( ), , , R , we have |N 1 2 3 4( ), , , | = det <
1 2 3 4
( ), , , >, where < 1 2 3 4( ), , , > is the ideal of R generated by
1 2 3 4
( ), , , . Let (q1, q2, q3, q4) be a prime element such that has n distinct
linear factors modulo (q1, q2, q3, q4), that is,
1 2 3 41 2 3 4 1 2 3 4
( (( ) ( )) mod ( ), , , , , , , , ,
i i i i
i n
x x x x q q q q
= − where i 's are primitive
n+1-th root of unity modulo (q1, q2, q3, q4) component-wise. Also we know that
1 2 3 4
( , , , ) 1 2 3 4
/ ( ) / ( ) / ( ) / ( )
q q q q
R R q R R q R R q R R q R= ´ ´ ´ .
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
57
3.4. Adaptation of Ideal Lattice Problems
Definition 3.1. The ring small integer solution problem with parameters
1 2 3 4 1 2 3 4
( , , , ), , ( , , , ),q q q q m b b b b F is: Given m polynomials
11 21 31 41 1 1 1 1
( , , , ), ..., ( , , , )
m m m m
a a a a a a a a chosen uniformly and independently in
1 2 3 4( , , , )q q q q
R , find
1 2 3 4
( , , , )t t t t in assumed R-module such that
1 2 3 4 1 2 3 4
|| ( , , , ) || ( , , , )t t t t b b b b£ .
In [14] is shown that R-SIS and R-LWE are dual. For
1 2 3 41 2 3 4 ( , , , )
( ), , ,
q q q q
s s s s R and 1 2 3 4( ), , , some distributions in 1 2 3 4( , , , )q q q qR , we
have
1 2 3 4 1 2 3 4( , , , ),( , , , )s s s s
A
as the distribution obtained by sampling the pair
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
(( ), ( )( ) ( )), , , , , , , , , , , ,a a a a a a a a s s s s e e e e+ with
1 2 3 41 2 3 4 1 2 3 4 ( , , , ) 1 2 3 4
(( ), ( )) ( ) ( ), , , , , , , , ,
q q q q
a a a a e e e e U R . The Ring Learning With
Errors problem (R-LWE) was introduced by Lyubashevsky et al.[16] and shown
hard for specific error distributions . The error distributions 1 2 3 4( ), , , that
we use are an adaptation of those introduced in [16].
Definition 3.2.
1 2 3 4 1 2 3 4( , , , ),( , , , )
( )
q q q q
R LWE
− : Let
1 2 3 41 2 3 4 ( , , , )
( ), , ,
and
( )1 2 3 41 2 3 4 , , ,
( ) ( ), , ,
q q q q
s s s s U R where
1 2 3 4( , , , )
is a family of distributions.
Given access to an oracle O that produces samples in
1 2 3 4
( , , , )1 2 3 4( , , , ) q q q qq q q q
R R
, distinguish whether O outputs samples from
1 2 3 4 1 2 3 4( , , , ),( , , , )s s s s
A
or from
1 2 3 4
( , , , )1 2 3 4( , , , )
( )
q q q qq q q q
U R R . The distinguishing advantage should be
( )
1 / ( ) ( . 2 )
o n
poly n resp
− over the randomness of the input, the randomness of the
samples and the internal randomness of the algorithm, component-wise [14].
Theorem 1 in [14] indicates that R-LWE is hard, assuming that the worst-
case -Ideal-SVP cannot be efficiently solved using quantum computers, for
small . It was recently improved by Lyubashevsky et al. [18] if the number of
samples that can be chosen to the oracle O is bounded by a constant (which is
the case in our application), then the result also holds with simpler errors than
1 2 3 41 2 3 4 1 2 3 4 ( , , , )
( ) ( ), , , , , ,e e e e
, and with an even smaller Ideal-SVP
approximation factor . This should allow to both simplify the proposed
scheme and to strengthen its security guarantee.
3.5. Our Proposed Variants of R-LWE
For
1 2 3 41 2 3 4 ( , , , )
( ), , ,
q q q q
s s s s R and
1 2 3 4
( ), , , some distributions in
1 2 3 4
( , , , )q q q q
R ,
we denote
1 2 3 4 1 2 3 4, , , , , ,( ),( )s s s s
A
as the distribution obtained by sampling
Amir Hassani Karbasi
58
the pair 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4(( ), ( )( ) ( )), , , , , , , , , , , ,a a a a a a a a s s s s e e e e+ with
1 2 3 41 2 3 4 1 2 3 4 ( , , , ) 1 2 3 4
(( ), ( )) ( ) ( ), , , , , , , , ,
q q q q
a a a a e e e e U R
, where
1 2 3 4( , , , )q q q q
R
is
the set of invertible elements of
1 2 3 4( , , , )q q q q
R . This variant is hard and called
R LWE
++
− as [14]. Furthermore, as explained in [18], the nonce 1 2 3 4( , , , )s s s s
can also be sampled from the error distribution without incurring any security
loss. We call this variant
HNF
R LWE
++
− . According to adaptation of lemmas 7, 8
and 9 as well as Theorem 2 in [14] the problems R LWE
++
− and
HNF
R LWE
++
−
are dual to -Ideal-SVP and are defined some families of R-modules for I, an
arbitrary ideal of
1 2 3 4( , , , )q q q q
R as a lattice, also short vectors exist in ideal and
statistical distance (regularity bound) is exactly appropriate and reliable.
4. The Proposed Key Generation Algorithm
We now use the results of the previous section on modular ideal lattice to
derive a key generation algorithm for the ETRU for each component in vectors,
where the generated public key follows a distribution for which Ideal-SVP
reduces to R-LWE. Algorithm 1 is as follows.
Input:
1 2 3 41 2 3 4 1 2 3 4 ( , , , ) 1 2 3 4
, , , ( ), , , , , , , , ,
q q q q
n q q q q p p p p R
Z R .
Output:
1 2 3 4( , , , )
A key pair ( , )
q q q q
sk pk R R
.
Sample
1 2 3 4
( , , , ) 'f f f f from 4
1 2 3 4,( , , , )
nD
Z
; let
1 2 3 4 1 2 3 4 1 2 3 4
( , ) ( , ).( , ) ' (1,1,1,1), , , , , ,f f f f p p p p f f f f= + ; if (
1 2 3 4
( , , , )f f f f mod
1 2 3 4
( , , , )q q q q )
1 2 3 4( , , , )q q q q
R
, resample. Sample
1 2 3 4
( , , , )g g g g from
4
1 2 3 4,( , , , )
nD
Z
; if (
1 2 3 4
( , , , )g g g g mod
1 2 3 4
( , , , )q q q q )
1 2 3 4( , , , )q q q q
R
, resample.
Return secret key sk =
1 2 3 4
( , , , )f f f f and public key pk =
1 2 3 4
( , , , )h h h h =
1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 ( , , , )
( , , , )( , , , ) / ( , , , )
q q q q
p p p p g g g g f f f f R
´
Î .
The following Theorem ensures that for some appropriate choice of
parameters, the key generation algorithm terminates in expected polynomial
time.
Theorem 4.1[Adapted from 14]. Let 8n and n+1 be a prime such that
1
(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + + splits into n linear factors
modulo prime 1 2 3 4( ) (5, 5, 5, 5), , ,q q q q component-wise. Let
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
59
1/
ln(2 (1 1 / )) / .
n
i i i
n n q + , or an arbitrary (0,1 / 2)i . Let 1 2 3 4( , ), ,a a a a R and
1 2 3 41 2 3 4 ( , , , )
( , ), ,
q q q q
p p p p R
Then
component-wise.
The following Lemma ensures that the generated secret key is small.
Lemma 4.1[Adapted from 14]. Let 8n and n+1 be a prime such that
1
(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + + splits into n linear factors
modulo prime 1 2 3 4( ) (8, 8, 8, 8), , ,q q q q n . Let
1/
2 ln(6 ) / .
n
i i
n n q . The secret
key polynomials
1 2 3 4 1 2 3 4
( , , , ), ( , , , )f f f f g g g g returned by the algorithm 1 satisfy,
with probability
3
1 2
n− +
− :
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
|| ( , ) || (2, 2, 2, 2) || ( , ) || ( ) || ( , ) || ( ) , , , , , , , , , , , ,f f f f n p p p p and g g g g n .
If deg
1 2 3 4
( , , , )p p p p (1,1,1,1) , then
1 2 3 4 1 2 3 4 1 2 3 4
|| ( , ) || (4, 4, 4, 4) || ( , ) || ( ), , , , , , ,f f f f n p p p p with probability
3
1 2
n− +
− component-wise.
Theorem 3 in [14] shows that the public key can be uniformly distributed in
the whole ring and this satisfy cryptographic pseudo randomness for our
Algorithm 1, which seems necessary for exploiting the established hardness of
R-LWE (and R-SIS). Now we can construct the proposed cryptosystem over
ideal lattices with high efficiency and provable security (CPA-secure).
5. The Proposed New Cryptosystem
Using our new results above, we describe our proposed cryptosystem for
which we can provide a security proof under a worst-case hardness assumption.
5.1. Decryption Failure
The correctness condition for each pairwise coefficient in the proposed
cryptosystem is as follows.
Lemma 5.1 [Adapted from 14]. If
21.5
( log ) deg(( )) || ( ) || (1,1,1,1)
i i i i
n n p p (resp.
20.5
( log ) || ( ) || (1,1,1,1) deg( ) (1,1,1,1)
i i i i
n n p if p ) and
0.5
i i
q n , then the
decryption algorithm of the proposed cryptosystem recovers
1 2 3 4
( , , , )M M M M
with probability
(1)
1 n
−
− over the choice of si, ei, fi and gi component-wise.
Amir Hassani Karbasi
60
Proof. In the decryption algorithm, we have
and let
computed in R (not modulo
1 2 3 4
( , , , )q q q q ). If
1 2 3 4 1 2 3 4
|| ( , ) " || ( ) / 2, , , , ,C C C C q q q q
then we have
1 2 3 4 1 2 3 4
( , ) ' ( , ) ", , , ,C C C C C C C C= in R and hence, since
( ) (1,1,1,1) mod ( ), ( ) ' mod ( ) ( ) " mod ( ) ( ) mod ( )
i i i i i i i i
f p C p C p M p = = , i.e., the
decryption algorithm succeeds. It thus suffices to give an upper bound on the
probability that 1 2 3 4 1 2 3 4|| ( , ) " || ( ) / 2, , , , ,C C C C q q q q . From Lemma 2, we know
that with probability
3
1 2
n− +
− both
1 2 3 4
( , , , )f f f f and
1 2 3 4
( , , , )g g g g have
Euclidean norms 2 || ( ) || ( . (4, 4, 4, 4) || ( ) || deg( ) (1,1,1,1))
i i i i i
n p resp n p if p this
implies that, 2 21.5|| ( )( ) ||, || ( )( ) || (2, 2, 2, 2) || ( ) || ( . (8, 8, 8, 8) || ( ) || )n
i i i i i i i i
p f p g n p resp p
with probability
3
1 2
n− +
− . From Lemma 6 in [14], both
1 2 3 4 1 2 3 4 1 2 3 4
( , , , )( , , , )( , , , )p p p p f f f f e e e e and
1 2 3 4 1 2 3 4 1 2 3 4
( , , , )( , , , )( , , , )p p p p g g g g s s s s
have infinity norm
(resp.
21.5
(2, 2, 2, 2) (log ). || ( ) ||
i i i i
q n n p
2
(8, 8, 8, 8) (log ). || ( ) ||
i i i i
q n n p
), with probability
(1)
1 n
−
− . Independently:
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
61
Proposed Encryption Scheme
Parameters Creation:
1. We use
1
(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + + with 8n
and n+1 a prime,
3 3
: ( [ ] [ ])[ ]/R xz z= ´ < F >Z Z and
1 2 3 4( , , , ) 1 2 3 4
/ ( ) / ( ) / ( ) / ( )
q q q q
R R q R R q R R q R R q R= with
1 2 3 4
( ) (5, 5, 5, 5), , ,q q q q prime such that
1
n
k
k
=
= in
1 2 3 4( , , , )q q q q
R with distinct
k
's component-wise.
Key Generation:
2. We use the algorithm 1 and return
1 2 3 41 2 3 4 ( , , , )
( , ), ,
q q q q
sk f f f f R
= with
1 2 3 4 1 2 3 4
( , ) (1,1,1,1) mod ( , ), , , ,f f f f p p p p , and pk =
1 2 3 4
( , , , )h h h h =
1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 ( , , , )
( , , , )( , , , ) / ( , , , )
q q q q
p p p p g g g g f f f f R
´
Î , component-wise.
Encryption:
3. Given message 1 2 3 4( , ), ,M M M M P , set
1 2 3 41 2 3 4 1 2 3 4 ( , , , )
( ), ( ), , , , , ,s s s s e e e e
and return ciphertext
1 2 3 41 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 ( , , , )
( , ) ( , )( ) ( , )( ) ( , ), , , , , , , , , , , , , ,
q q q q
C C C C h h h h s s s s p p p p e e e e M M M M R= + +
Decryption:
4. Given ciphertext
1 2 3 4
( , , , )C C C C and secret key
1 2 3 4
( , , , )f f f f , compute
1 2 3 41 2 3 4 1 2 3 4 1 2 3 4 ( , , , )
( , ) ' ( , ).( , ), , , , , ,
q q q q
C C C C f f f f C C C C R= and return
1 2 3 4
( , , , ) 'C C C C mod
1 2 3 4
( , , , )p p p p .
2 2
|| ( )( ) || || ( )( ) || || ( ) || . || ( ) || (2, 2, 2, 2).(deg( ) (1,1,1,1). || ( ) ||
i i i i i i i i i
nf M f M f M p n p
+
(resp.
2
(8, 8, 8, 8) || ( ) ||
i i
n p ). Since i iq n , we conclude that
1.5 2
|| ( ) " || ((6, 6, 6, 6) (2, 2, 2, 2) deg( )). (log ). || ( ) ||
i i i i i i
C p q n n p
+ (resp.
20.5
(24, 24, 24, 24) (log ). || ( ) ||
i i i i
q n n p ), with probability
(1)
1 n
−
− ,
component-wise.
□
Amir Hassani Karbasi
62
5.2. Security
The security of the proposed cryptosystem follows by an elementary
reduction from the decisional
HNF
R LWE
++
− , exploiting the uniformity of the
public key in
1 2 3 4( , , , )q q q q
R
(adaptation of Theorem 3 in [14]), and the invertibility
of
1 2 3 4
( , , , )p p p p in
1 2 3 4( , , , )q q q q
R .
Lemma 5.2 [adapted from 7]. Suppose n+1 is a prime such that
1
(1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
nn
x x x
−
= + + + + splits into n linear factors
modulo prime (1)iq = . Let
(1/ 2,1/ 2,1/ 2,1/ 2)
(2, 2, 2, 2) ln(8 ). i
i i i
n nq q
+
and
1 2 3 41 2 3 4 1 2 3 4 1 2 3 4 ( , , , )
( ), ( ) (0, 0, 0, 0), ( ), , , , , , , , ,
q q q q
p p p p R
. If there exists
an IND-CPA attack against the proposed cryptosystem that runs in time T and
has success probability (1 / 2,1 / 2,1 / 2,1 / 2) i+ with parameters i and qi, then
there exists an algorithm solving
HNF
R LWE
++
− that runs in time T' = T + O(n)
and has success probability
( )
'
n
i i i
q
−
= − .
Proof. Let A denote the given IND-CPA attack algorithm. We construct an
algorithm B against
HNF
R LWE
++
− that runs as follows, given oracle O that
samples from either ( )
qi iq
U R R
or ,i is
A
for some previously chosen i is and
ii
.Algorithm B first calls O to get a sample ((hi)', (Ci)') from qi iq
R R
.
Then, algorithm B runs A with public key ( ) ( ).( ) '
ii i i q
h p h R= . When A outputs
challenge messages
10
( , () )
ii
M M P , algorithm B picks ({0,1})b U , computes
the challenge ciphertext ( ) ( ).( ) ' ( )
qii i i bi
C p C M R= + , and returns (Ci) to A.
Eventually, when A outputs its guess b' for b, algorithm B outputs 1 if b' = b and
0 otherwise. The (hi)' used by B is uniformly random in
iq
R
and therefore so is
the public key (hi) given to A, thanks to the invertibility of (pi) modulo (qi). Thus,
by Theorem 3 in [14], the public key given to A is within statistical distance
( )n
q
−
of the public key distribution in the genuine attack, component-wise.
Moreover, since ( ) ' ( ).i i i iC h s e= + with ,i i is e , the ciphertext (Ci) given to A
has the right distribution as in the IND-CPA attack. Overall, if O outputs
samples from ,i is
A
then A succeeds and B returns 1 with probability
( )
(1 / 2,1 / 2,1 / 2,1 / 2)
n
i i
q
−
+ − . Now, if O outputs samples from ( )
qi iq
U R R
,
then, since
ii q
p R
, the value of (pi)(Ci)' and hence (Ci), is uniformly random in
Rqi and independent of b. It follows that B outputs 1 with probability 1/2,
component-wise. The claimed advantage of B follows. □
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
63
By combining lemmata 3 and 4 (with adaptation of Theorem 1 in [14]) we
obtain main result.
6. Conclusions
In this paper, we provided a new cryptosystem that uses the properties of the ETRU
cryptosystem and its structured lattice to achieve high efficiency by providing a
provable security (CPA-secure) based on ideal lattices and a variant of R-LWE
problem. Also we showed that each polynomial in
1
3 3
( [ ] [ ])[ ]/ (1,1,1,1) (1,1,1,1) ... (1,1,1,1) (1,1,1,1)
n n
R x x x x
−
= + + + + Z Z has its
coefficients of the form
3 3
(( , ), ( , ))
i i i i
a b c dz z where , , ,
i i ii
a b c d Z , so we made both
lemmata and theorems here for ai's, bi's, ci's and di's separately, that is, we reflected
2 2
( , ) ( , )@C C R R . Hence, we could enhance the dimension of lattice 4-times without
increasing n.
References
[1] W. Diffie and M.E. Hellman, "New directions in cryptography," In IEEE
Trans. On Information Theory, (1976), 22, 644-654.
[2] J. Hoffstein, J. Pipher, and J.H. Silverman, "NTRU: a new high speed
public-key cryptosystem," Preprint; presented at the rump session of Crypto
(1996).
[3] D. Coppersmith and A. Shamir, "Lattice attacks on NTRU," In Fumy,
W. (ed.) EUROCRYPT, LNCS, (1997), 1233, 52–61.
[4] J. Hoffstein, J. Pipher, and J.H. Silverman, "NTRU: A ring-based public-
key cryptosystem," In Buhler, J.P. (ed.) ANTS, LNCS, (1998), 1423, 267–288.
[5] IEEE P1363. Standard specifications for public-key cryptography,
http://grouper.ieee.org/groups/1363/
[6] R.A. Perlner and D.A. Cooper, "Quantum resistant public-key
cryptography: a survey," In Proc. of IDtrust, ACM, New York, (2009), 85–93.
[7] K. Jarvis and M. Nevins, "ETRU: NTRU over the Eisenstein Integers,"
Designs, Codes and Cryptography, DOI: 10. 1007/s10623-013-9850-3, (2013).
[8] M. Ajtai and C. Dwork, "A public-key cryptosystem with worst-
case/average-case equivalence," In Proceedings of STOC, ACM, (1997), 284-
293.
Amir Hassani Karbasi
64
[9] V. Lyubashevsky and D. Micciancio, "On bounded distance decoding,
unique shortest vectors, and the minimum distance problem," In Proceedings of
Crypto, (2009), 5677, 450-461.
[10] D. Micciancio, "Generalized compact knapsacks, cyclic lattices, and
efficient oneway functions," Computational Complexity, (2007), 16, 4, 365-411.
[11] V. Lyubashevsky and D. Micciancio, "Generalized compact knapsacks
are collision resistant," In Proceedings of ICALP, (2006), 4052, 144-155.
[12] C. Peikert and A. Rosen, "Efficient collision-resistant hashing from
worst-case assumptions on cyclic lattices," In Proceedings of TCC, (2006), 145-
166.
[13] O. Regev, "On lattices, learning with errors, random linear codes, and
cryptography," Journal of ACM, (2009), 56, 6.
[14] D. Stehle and R. Steinfeld, "Making NTRU as Secure as Worst-Case
Problems over Ideal Lattices," In Eurocrypt, (2011), 6632, 27-47.
[15] M. Nevins, C. Karimianpour, and A. Miri, "NTRU over rings beyond
Z," Des. Codes Cryptogr., (2010), 56, 1, 65–78.
[16] V. Lyubashevsky, C. Peikert, and O. Regev, "On ideal lattices and
learning with errors over rings," In Gilbert, H. (ed.) EUROCRYPT, (2010),
6110, 1–23.
[17] C. Gentry, "Fully homomorphic encryption using ideal lattices," In
Proc. of STOC, (2009), 169–178.
[18] V. Lyubashevsky, C. Peikert, and O. Regev, "On ideal lattices and
learning with errors over rings," Draft version, dated 01/02/2011.
[19] P. Garrett, "Abstract Algebra," University of Minnesota, (2007), 211-
217.
[20] R.E. Atani, S.E. Atani, and A.H. Karbasi, "EEH: A GGH-Like Public
Key Cryptosystem Over The Eisenstein Integers Using Polynomial
Representation," The ISC International Journal of Information Security
(IseCure), (2015), 7, 2, 115-126.
[21] A.H. Karbasi and R.E. Atani, "ILTRU: An NTRU-Like Public Key
Cryptosystem Over Ideal Lattices," IACR Cryptology ePrint Archive, (2015),
549.
[22] A.H. Karbasi and R.E. Atani, "PSTRU: A provably secure variant of
NTRUEncrypt over extended ideal lattices," The 2nd National Industrial
Mathematics Conference, Tabriz, Iran, (2015).
A New Provably Secure Cryptosystem Using Dedekind Domain Direct
Product Approach
65
[23] A.H. Karbasi and R.E. Atani, "A Survey on Lattice-based
Cryptography," (in Persian), Biannual Journal for Cyberspace Security (Monadi
AFTA), (2015), 3, 1, 3-14.
[24] A.H. Karbasi, M.A. Nia, and R.E. Atani, "Designing of An Anonymous
Communication System Using Lattice-based Cryptography," (in Persian),
Journal of Electronic and Cyber Defence, (2014), 2, 3, 13-22.
[25] S.E. Atani, R.E. Atani, and A.H. Karbasi, "A Provably Secure Variant
of ETRU Based on Extended Ideal Lattices over Direct Product of Dedekind
domains," Submitted.
[26] A.H. Karbasi, R.E. Atani, and S.E. Atani, "A New Ring-Based SPHF
and PAKE Protocol On Ideal Lattices," Submitted.
[27] S.E. Atani, R.E. Atani, and A.H. Karbasi, "PairTRU: Pairwise Non-
commutative Extension of The NTRU Public key Cryptosystem," International
Journal of Information Security Science, (2018), 7, 1, 11-19.
[28] S.E. Atani, R.E. Atani, and A.H. Karbasi, "NETRU: A Non-
Commutative and Secure Variant of CTRU Cryptosystem," The ISC
international journal of information security (IseCure), (2018), 10, 1, 1-9.
[29] A.H. Karbasi and R.E. Atani, "Application of dominating sets in
wireless sensor networks," Int. J. Security and its Application, (2013), 7, 4.
[30] A.H. Karbasi and R.E. Atani. "Projective plane-based key pre-
distribution by key copying and exchanging based on connected dominating set
in distributed wireless sensor networks," International Journal of Information
and Communication Technology, (2016), 9, 4, 438-462.
[31] S. Tahouri, R.E. Atani, A.H. Karbasi, and Y. Deldjou, "Application of
connected dominating sets in wildfire detection based on wireless sensor
networks," International Journal of Information Technology, Communications
and Convergence, (2015), 3, 2, 139-160.