In this talk, we will first give an introduction on multivariate public key cryptography with the emphasis on the fundamental cryptanalysis tools. We will then discuss a new quantum attack algorithm developed by Gao etc against the multivariate schemes using the HHL quantum algorithm. The complexity of this algorithm depends on the so-called condition numbers.
The work of Gao etc claims that there is a possibility such an algorithm is polynomial asymptotically. If it is indeed true, then we will have a quantum algorithm to solve a NP-complete problem in polynomial time. We will present a proof we developed recently that in general this new algorithm is actually exponential in terms of its complexity in solving a set of quadratic equations over a finite field. This second part of the talk is a joint work with Vlad Gheorghiu from University of Waterloo.
The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor’s celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms. The latest successful generalization (Eisenträger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space R^m , even for large dimensions m. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices. The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits. This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction.
Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.
We will review recent work on quantum Machine Learning with a focus on longer-term quantum algorithms. We will discuss challenges and prospects for such algorithms and ways of bringing them closer to practical solutions.
Variational Quantum Circuits, which include examples of quantum approximate optimization algorithms (QAOA), variational quantum eigensolver (VQE), and quantum neural-networks (QNN), are predicted to be one of the most important near-term quantum applications, not only because of their potential promises as classical neural-networks but also because of their feasibility on near-term noisy intermediate size quantum (NISQ) machines.
This talk reports some progress toward a principled understanding of the training of variational quantum circuits. First, I will demonstrate the difficulty of training by constructing an example with exponentially many local optima, however, due to a differential nature from classical neural-networks. Second, I will explain how to facilitate the training by incorporating the optimal-transport norm in the context of quantum generative adversarial networks (GANs), as well as its application in compressing quantum circuits in practical uses.
A small random sample of rows/columns of any matrix is a decent proxy for the matrix, provided sampling probabilities are proportional to squared lengths. Since the early theorems on this from the 90’s, there has been a substantial body of work using sampling (random projections and probabil-ties based on leverage scores are two examples) to reduce matrix sizes for Linear Algebra computations. The talk will describe theorems, applications and challenges in the area.
We discuss a classical analogue to the singular value transformation framework for quantum linear algebra algorithms developed by Gilyén et al. The proofs underlying this classical framework have natural connections to well-known ideas in randomized numerical linear algebra. Namely, our proofs are based on one key observation: approximating matrix products is easy in the quantum-inspired input model. This primitive's simplicity makes finding classical analogues to quantum machine learning algorithms straightforward and intuitive. We present sketches of the key proofs of our sketches as well as of its applications to dequantizing low-rank quantum machine learning.
Joint work with Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang.
https://eprint.iacr.org/2020/292
Dana Dachman-Soled and Léo Ducas and Huijing Gong and Mélissa Rossi
Abstract: We propose a framework for cryptanalysis of lattice-based schemes, when side information---in the form of ``hints''--- about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information.
While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU), that were previously not known to (slightly) benefit from lattice attacks.
We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al (SAC 2018). Contrary to ad-hoc practical attacks exploiting side-channel leakage, our work is a generic way to estimate security loss even given very little side-channel information.
Category / Keywords: public-key cryptography / LWE, NTRU, Lattice reduction, Cryptanalysis, Side-channels analysis, decryption failures.
Date: received 5 Mar 2020, last revised 6 Mar 2020
Contact author: danadach at ece umd edu,l ducas@cwi nl,gong@cs umd edu,melissa rossi@ens fr
Available format(s): PDF | BibTeX Citation
Version: 20200306:193806 (All versions of this report)
Short URL: ia.cr/2020/292
In the context of the NIST competition, the last three years have seen a lot of research to be invested in the construction of public-key primitives that remain actively secure even in the presence of quantum adversaries. All current NIST proposals follow the approach to achieve active security by first constructing a weaker primitive, and then applying a variant of the Fujisaki-Okamoto transformation.
The Fujisaki-Okamoto transformation and its variants turns any scheme with a weak security level into a scheme with the desired active security level, in a generic way. All of its variants, however, are constructed relative to hash functions, and quantum attackers might interact with these hash functions in a more sophisticated way than classical attackers would be capable of. This possibility is reflected in the security bounds that have been proven for quantum adversaries: They are less tight than in the classical setting.
In this context, tight bounds mean that the derived scheme is as secure as the underlying building block, whereas less tight results relate the derived scheme's security to the weaker building block in a less immediate manner. To still achieve a sufficent level of security for the derived scheme, the underlying primitive's level of security would have to be scaled up, leading to less efficient schemes. Gradual progress towards tighter security bounds has been made within the last years, but it comes at the price of additional restrictions for the weaker building block. This talk offers a survey of knowledge with regards to how directly active security can be derived from the weaker building block, when assuming attackers that are quantum.