[crypto] Fwd: PROGRAM Crypto Working Group, November 9, 2018
R. Hirschfeld
ray at unipay.nl
Mon Nov 5 17:17:29 CET 2018
-------- Original Message --------
Subject: PROGRAM Crypto Working Group, November 9, 2018
Date: 2018-11-05 15:39
From: Secretariaat DM <secdm at tue.nl>
To: Secretariaat DM <secdm at tue.nl>
Dear all,
Herewith I send you the program of the CWG-meeting on Friday, November
9, 2018.
With kind regards / Met vriendelijke groeten,
Anita Klooster
secretary of the section Discrete Mathematics
[cid:image001.gif at 01CB8FB5.88A9C0F0]
Dept. of Mathematics and Computer Science
MF 4.058
Office hours: Monday and Friday 08.30-12.30 h / Tuesday and Wednesday
08.30-17.00 h
Telephone: +31 (0)40 2472254
Email: secdm at tue.nl<mailto:secdm at tue.nl>
CRYPTO WORKING GROUP
Friday, November 9, 2018
De Kargadoor (http://www.kargadoor.nl/utrecht/zaalverhuur.html)
Oudegracht 36, Utrecht
Program
10.45 – 11.30 hrs. Leo Ducas (CWI),
The General Sieve Kernel
and New Records in Lattice Reduction
11.30 - 11.45 hrs. Coffee / tea break
11.45 - 12.30 hrs. Stacey Jeffery (CWI and QuSoft),
On
non-adaptive quantum chosen-ciphertext attacks and Learning with Errors
12.30 - 14.00 hrs. Lunch break (lunch not included)
14.00 - 14.45 hrs. Christian Majenz (CWI, QuSoft, UvA),
Quantum-secure message
authentication via blind-unforgeability
14.45 - 15.00 hrs. Coffee / tea break
15.00 - 15.45 hrs Matthias Kannwischer (RU),
Faster
multiplication in $Z_{2^m}[x]$ on Cortex-M4 to speed up NIST PQC
candidates
Abstract talk Leo Ducas: The General Sieve Kernel and New Records in
Lattice Reduction
Sieving algorithms are asymptotically the fastest heuristic algorithms
for solving the shortest vector problem, and therefore for solving other
problems such as LWE or SIS, due to the Block-Korkine-Zolotarev lattice
reduction algorithm (BKZ).
Until recently, sieving was considered as a function to be used as a
blackbox SVP oracle inside BKZ. The works of Ducas (Eurocrypt 2018), and
of Laarhoven and Mariano (PQCrypto 2018), however, proposed improvements
to lattice reduction that go beyond this blackbox use of Sieve-style
algorithms.
To formalise and generalise these new strategies, we propose the General
Sieve Kernel (G6K, pronounced /ȝe.si.ka/), an abstract machine
supporting a wide variety of lattice reduction strategies based on
sieving algorithms. It is designed to minimise the sieving computation
effort per reduction quality, and achieves this via mechanisms such as
recycling and on-the-fly lifting. We provide a highly optimised,
multi-threaded, tweakable, and open-source implementation of this
stateful machine.
Finally, we apply G6K to various lattice challenges (SVP, LWE). Our work
demonstrates that sieving significantly outperforms enumeration in
dimensions achievable in practice.
Joint work with Martin R. Albrecht, Gottfried Herold, Elena Kirshanova,
Eamonn Postlethwaite and Marc Stevens.
Abstract talk Stacey Jeffery: On non-adaptive quantum chosen-ciphertext
attacks and Learning with Errors
Large-scale quantum computing is a significant threat to classical
public-key cryptography. In strong "quantum access" security models,
numerous symmetric-key cryptosystems are also vulnerable. We consider
classical encryption in a model which grants the adversary quantum
oracle access to encryption and decryption, but where the latter is
restricted to non-adaptive (i.e., pre-challenge) queries only. We define
this model formally using appropriate notions of ciphertext
indistinguishability and semantic security (which are equivalent by
standard arguments) and call it QCCA1 in analogy to the classical CCA1
security model. Using a bound on quantum random-access codes, we show
that the standard PRF- and PRP-based encryption schemes are QCCA1-secure
when instantiated with quantum-secure primitives.
We then revisit standard IND-CPA-secure Learning with Errors (LWE)
encryption and show that leaking just one quantum decryption query (and
no other queries or leakage of any kind) allows the adversary to recover
the full secret key with constant success probability. In the classical
setting, by contrast, recovering the key uses a linear number of
decryption queries, and this is optimal. The algorithm at the core of
our attack is a (large-modulus version
of) the well-known Bernstein-Vazirani algorithm.
This is joint work with Gorjan Alagic, Maris Ozols, and Alexander
Poremba.
Abstract talk Christian Majenz: Quantum-secure message authentication
via blind-unforgeability
Formulating and designing unforgeable authentication of classical
messages in the presence of quantum adversaries has been a challenge, as
the familiar notions like EUF-CMA do not directly translate into
meaningful notions in the quantum setting. A particular difficulty is
how to fairly capture the notion of ``predicting an unqueried value''
when the adversary can query in quantum superposition.
In this talk I will begin by presenting a counterexample that the
peviously proposed notion of Boneh and Zhandry (BZ-unforgeability) is
insufficient. More precisely, we construct a MAC that is obviously
completely broken, but BZ-unforgeable. The proof of BZ-unforgeability
for this MAC is based on the recent superposition oracle technique by
Zhandry.
Subsequently, I will introduce a candidate replacement, blind
unforgeability, and some characterization results about it that support
its viability as a quantum-access generalization of EUF-CMA.
Joint work with Gorjan Alagic, Alexander Russell and Fang Song,
https://arxiv.org/abs/1803.03761 (to be updated and eprinted)
Abstract talk Matthias Kannwischer: Faster multiplication in
$Z_{2^m}[x]$ on Cortex-M4 to speed up NIST PQC candidates
In this talk we present optimized polynomial multiplication in
$Z_{2^m}[x]$ on the ARM Cortex-M4 microprocessor. We use these optimized
multiplication routines to speed up the NIST post-quantum candidates
RLizard, NTRU-HRSS, NTRUEncrypt, Saber, and Kindi. For most of those
schemes the only previous implementation that executes on the Cortex-M4
is the reference implementation submitted to NIST; for some of those
schemes our optimized software is more than factor of 20 faster. One of
the schemes, namely Saber, has been optimized on the Cortex-M4 in a CHES
2018 paper; the multiplication routine for Saber we present here
outperforms the multiplication from that paper by 37%, yielding speedups
of 17% for key generation, 15% for encapsulation and 18% for
decapsulation. Out of the five schemes optimized in this paper, the best
performance for encapsulation and decapsulation is achieved by
NTRU-HRSS.
Specifically, encapsulation takes just over 430 000 cycles, which is
more than twice as fast as for any other NIST candidate that has
previously been optimized on the ARM Cortex-M4.
More information about the crypto
mailing list