[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