Title: One-time signatures from Generalized discrete logarithms
| Speaker: | David Jao |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We
initiate
the
study
of
post-quantum
cryptography
based
on
the
generalized
discrete
logarithm
problem
(GDLP)
in
abelian
black-box
semigroups,
which
is
provably
exponentially
hard
for
quantum
computers
in
the
generic
group
setting.
We
introduce
a
one-way
function
that
is
exponentially
hard
to
invert
even
for
quantum
computers,
based
on
this
problem,
along
with
a
post-quantum
one-time
(and
fixed-time)
signature
scheme.
One-time
signature
(OTS)
schemes
are
important
cryptographic
primitives
since
they
can
be
constructed
just
from
one-way
functions,
and
they
have
many
applications
beyond
digital
signatures.
Our
scheme
has
constant-size
short
signatures
(consisting
of
two
positive
integers),
in
contrast
to
schemes
based
on
general
one-way
functions
whose
signature
size
is
linear
in
the
message
size.
Over
suitable
semigroups
with
hard
GDLP
problems,
our
scheme
is
post-quantum,
unlike
those
based
on
DLP
or
factoring
problems
(or
their
variants).
The
signing
algorithm
is
very
fast---it
is
simply
the
usual
addition
of
a
few
positive
integers,
independent
of
the
choice
of
semigroup.
Moreover,
our
scheme
supports
a
number
of
important
properties
(batch
verification,
aggregation,
zero-knowledge
proof
of
knowledge,
etc.)
inherited
from
the
generalized
discrete
logarithm
function.
Joint work with Kassem Kalach.