ECE Seminar
Julien Eynard
Title
A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes
Invited by Professor Anwar Hasan
All are welcome!
Abstract
Homomorphic
encryption
(HE)
enables
arithmetic
operations
in
the
encrypted
domain
and
hence
makes
it
possible
to
secure
outsourced
computations.
Gentry's
breakthrough
work
in
2009
opened
the
way
to
the
development
of
fully
HE
schemes,
allowing
the
possibility
of
unlimited
number
of
additions
and
multiplications
on
encrypted
data.
However,
practicality
of
such
schemes
still
remains
severely
restricted
due
to
their
poor
performance.
For
this
reason,
somewhat
homomorphic
encryption
(SHE)
schemes,
which
support
only
a
limited
number
of
operations
but
offer
much
better
performance,
are
considered
suitable
for
a
variety
of
practical
applications.
Many
of
the
leading
SHE
schemes
proposed
so
far
rely
on
Ring
Learning
With
Errors
(RLWE)
problems.
For
such
schemes
the
underlying
operations
occur
on
high-degree
polynomials
with
large
coefficients.
Various
techniques
are
applied
to
improve
the
performance
of
polynomial
and
integer
arithmetic.
For
instance,
the
Residue
Number
Systems
(RNS)
can
be
applied
to
large
coefficients.
In
SHE
schemes
like
that
of
Fan
and
Vercauteren
(FV),
such
a
representation
has
been
exploited
to
a
limited
extent
only,
since
RNS
is
hardly
compatible
with
coefficient-wise
division
and
rounding
required
in
decryption
and
homomorphic
multiplication.
Thus,
costly
switching
between
RNS
and
classical
positional
representation
is
still
used
for
such
operations.
In
our
recent
work,
we
show
how
to
entirely
eliminate
the
need
for
multi-precision
arithmetic
in
FV
like
schemes.
We
present
a
full
RNS
implementation
of
FV.
For
realistic
parameters,
we
report
speedups
from
5x
to
20x
(resp.
2x
to
4x)
for
software
implementation
of
decryption
(resp.homomorphic
multiplication).
Biography:
Dr.
Julien
Eynard
is
a
post-doctoral
fellow
in
the
Department
of
Electrical
and
Computer
Engineering
at
the
University
of
Waterloo,
and
hosted
by
Prof.
Anwar
Hasan.
Dr.
Eynardreceived
his
MSc
(2011)
at
University
Joseph
Fourier
(Grenoble,
France),
and
obtained
a
PhD
(2015)
from
University
Pierre
and
Marie
Curie
(Paris,
France).
His
interests
are
related
to
applied
cryptography
focussing
on
acceleration
of
cryptographic
algorithms
and
their
protection
against
side
channel
attacks.