IEEE Circuits and Systems Magazine - Q1 2021 - 35

postquantum cryptography and Fully Homomorphic Encryption (FHE), respectively.
A lattice can be seen as a vector space generated by
all linear combinations with integer coefficients of a set
R = " rv0, f, rvn - 1 ,, with rvi ! R m, of linearly independent
vectors, as defined in (46); the rank of the lattice is n,
and its dimension is m. Two vectors in span ^ R h are congruent if their difference is in L ^ R h .
L ^R h = ) / z i rvi : z i ! Z 3
n-1

(46)

i=0

Each basis is associated with the parallelepiped:
P ^ R h = ) / w i rvi : w i ! ` - 1 , 1 B3
2 2
i=0
n-1

(47)

v ! L^ Rh
v + xv ! span ^ R h, where w
For any point yv = w
and xv ! P ^ Rh, the reduction in the yv modulo P ^ R h is
defined as xv = yv mod P ^ Rh . The modular reduction has
a different meaning for each basis, since they are associated with different parallelepipeds. An example of this is
featured in Fig. 25, where the point cv is reduced modulo
both P ^ Rh and P ^ Bh, producing two different points,
which are represented as triangles, while L ^ Rh = L ^ Bh .
Lattice Based Cryptography (LBC) is supported
by the Closest Vector Problem (CVP). This problem
consists of a given base R ! R n # m, and yv ! R m, finding
xv ! L ^ Rh such that < yv - xv < = min zv ! L^ Bh < yv - zv <. The private basis is produced as a rotated nearly orthogonal
basis, such that Babai's round-off [146] provides accurate solutions to the CVP. Rose's cryptosystem uses
bases of an Optimal Hermite Normal Form (OHNF) as
the public key, a subclass of Hermite Normal Forms
(HNFs), where all but the first column are trivial. The
decryption algorithm is modified for its implementation
v -1@ ( 6 $ @ denotes roundwith the RNS. The operation 6cR
ing to the nearest integer) can be replaced by the apv -1@ through an RNS Montgomery
proximation nv of 6ccR
reduction [139], where cv = ^c, 0, f, 0 h and the scaling by
c enables the detection and correction of the errors resulting from the approximate RNS Montgomery reducv -1@ is rewritten using integer arithmetic as in
tion. 6ccR
t = R -1 d is an integer and d = det ^ R h .
(48), where R
v -1@ =
6ccR

vt
v t - ccR
ccR
d

d

(48)

It is shown that the usage of RNS enables parallelizing
the decryption in Rose's cryptosystems to significantly
speed up its computation in both CPUs and GPUs [147].
Homomorphic encryption allows performing computations directly on ciphertexts, generating encrypted
results as if the operations had been performed on the
plaintext and then encrypted. FHE provides malleable ciphertexts, such that given two ciphertexts representing
FIRST QUARTER 2021

the operands, it will be possible to produce a ciphertext
encrypting its product or sum [166]. Structured lattices
underpin classes of cryptosystems supporting FHE [148].
There is noise associated with the ciphertexts that grows
as homomorphic operations are applied; thus, bootstrapping has been proposed, a technique in which ciphertexts are homomorphically decrypted [148]. Modern
FHE systems rely on Ring Learning with Errors (RLWE),
for which techniques have been proposed that limit the
need for bootstrapping [147].
Batching [149] improves the performance of FHE
based on the CRT by allowing multiple bits to be encrypted in a single ciphertext so that one can carry out
AND and XOR sequences of bits using a single homomorphic multiplication or addition. For example, in an
RLWE cryptosystem, binary polynomials are homomorphically processed in a cyclotomic ring. By noticing that
certain cyclotomic polynomials factor modulo two onto
a set of polynomials with the same degree, one may take
advantage of the CRT to associate a plaintext bit with
each one of these polynomials. Homomorphic additions
and multiplications then add and multiply the bits modulo their respective polynomial, achieving coefficientwise XOR and AND operations. Rotations of these bits
may be accomplished with [150].
The operations that arise from FHE are evaluated,
and efficient algorithm-hiding systems are designed for
applications that take advantage of those operations in

S

b0

S

c
S

S

c mod P (B )

S

b1 = r1
S

r0

S

P (R ) c mod P (R )
P (B )

v 0, b
v 1 of the same lattice,
Figure 25. Two basis vr0, vr1 and b
along with the corresponding parallelepipeds in red and grey,
v is reduced modulo the two parallelepiare represented; c
peds [147].

IEEE CIRCUITS AND SYSTEMS MAGAZINE

35
IEEE Circuits and Systems Magazine - Q1 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2021
