General Information

The Quantum-Safe Crypto Workshop, was held at CQT Level 3 Seminar Room, S15-03-15, Centre for Quantum Technologies, National University of Singapore on October 3, 2016.


03 Oct, Mon
9:45 - 10:00hr Coffee/Tea Reception
10:00 - 10:10hr Welcome
10:10 - 11:00hr Leo Ducas, Centrum Wiskunde & Informatica (CWI), Amsterdam
NewHope, Frodo, in Between and Beyond
Arrow Abstract

We start by a brief presentation of NewHope, an instantiation of a post-quantum Key-Exchange scheme based on the Ring-LWE assumption with a few new trick toward, simplicity, efficiency and security in the wild.

We then summarize recent developments in quantum algorithms for algebraic lattices which incite the use of weaker assumption. This was done in the scheme Frodo (take off the ring!), using the much weaker LWE assumption, but with a significant loss of bandwidth efficiency.

Finally, we will discuss intermediate solution, that could swipe fears of algebraic attacks while maintaining acceptable bandwidth. If time allows, we will mention natural ideas from the theory of codes and lattice-packing to improve bandwidth further.

| Slides
11:10 - 12:00hr Sze Ling Yeo, Institute for Infocomm Research (I2R), A*STAR Singapore
On Semaev polynomials and ECDLP Attacks
Arrow Abstract

In this talk, we will review the approach of using Semaev polynomials to solve the elliptic curve discrete logarithm problem (ECDLP). In particular, we will outline how these polynomials can be used in an index-calculus attack to solve ECDLP instances. We will demonstrate some specific instances where these attacks lead to sub-exponential attacks. On the other hand, we will discuss why sub-exponential claims on general instances using this approach can be controvertial.

| Slides
12:00 - 14:00hr Lunch
14:00 - 14:50hr Kai-Min Chung, Academia Sinica, Taiwan
Computational Notions of Quantum Entropy
Arrow Abstract

Computational entropies, such as HILL (min-)entropy, metric (min-)entropy, and guessing pseudoentropy, are fundamental concepts in cryptography and complexity theory. These notions measure how much (min-)entropy a source $X$ has from the eyes of a computationally bounded party who may hold certain leakage information $B$ about $X$. In this work, we initiate the study of these notions in the quantum setting, where $X$ and/or $B$ may become quantum states. We first observe that these notions generalize naturally in the quantum setting, though some notions only generalize for classical $X$ with quantum $B$. We then explore whether classical theorems extend to the quantum setting. The results turn out to be quite intriguing, as summarized below:

- On the positive side, we show that the leakage chain rule remains to hold when the leakage B becomes quantum (the source X remains classical). Precisely, if $X$ has HILL entropy at least $k$ and $B$ is an $\ell$ qubit leakage, then $X$ conditioned on $B$ has HILL entropy at least $k -\ell$. We prove the result by extending several classical techniques, such as leakage simulation lemma and non-uniform min-max theorem, to the quantum setting, which leads to a new variant of POVM tomography problem for quantum circuits that may be of independent interests. As an immediate application, some known applications of leakage chain rule in leakage resilient crypto can be extended to handle quantum leakage.

- On the negative side, we point out a general *barrier* to extend the proof of several classical results to the quantum setting: We observe that common in essentially all these proofs is a ``gap-amplification'' procedure invoked by the reduction, which we show is *impossible* to achieve when the input consists of unknown quantum states. The impossibility can be viewed as a generalization of the no-cloning theorem. Our result does not imply that quantum analogues of these statements are false, but that different techniques are required from existing classical proofs.

- We further show that quantum analogues of certain classical theorem are provably *false*. Specifically, we investigate the dense model theorem, which can be interpreted as the equivalence of two notions of computational min-relative entropy. We show that such an equivalence (as well as the quantum analogue of the dense model theorem) becomes false in the quantum setting. At the core, we observe that a uniformly sampled pure state (according to the Haar measure) is pseudorandom to efficient quantum circuits with high probability, a property that may find other applications.

Joint work with Yi-Hsiu Chen, Ching-Yi Lai, Salil Vadhan, and Xiaodi Wu

| Slides
14:50 - 15:40hr Divesh Aggarwal, Centre for Quantum Technologies, NUS, Singapore
Algorithms for Lattice Problems via Discrete Gaussians
Arrow Abstract

I will present a randomized 2^{n+o(n)}-time and space algorithm for solving the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on n-dimensional Euclidean lattices.

In fact, I will present a conceptually simple algorithm that solves the perhaps even more interesting problem of discrete Gaussian sampling (DGS). Prior work only solved DGS for very large parameters. Our SVP/CVP results follow from a natural reduction from SVP to DGS.

This talk is based on joint works with Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz.

| Slides
15:40 - 16:00hr Coffee/Tea Break
16:00 - 16:50hr Khoa Nguyen, Nanyang Technological University, Singapore
Some recent uses of Stern-like protocols in lattice-based cryptography
Arrow Abstract

At CRYPTO 1993, Stern introduced a zero-knowledge protocol for the Syndrome Decoding problem, which later became one of the most prominent tools in code-based cryptography. The protocol was first adapted into the lattice setting by Kawachi, Tanaka and Xagawa (ASIACRYPT 2008). A recent body of work has developed Stern's protocol into a relatively strong tool for designing privacy-preserving lattice-based schemes (e.g., group signatures, logarithmic-size ring signatures, group encryption, compact e-cash). In this talk, I will survey these recent developments.

| Slides

Centre for quantum technologies National University of Singapore