I am a dealmaker, investor, director and legal advisor, focusing on technology, green business and China.
I am very interested in use of artificial and machine intelligence to solve business problems. I have invested in five UK start-ups that broadly fit this model: Sparrho, Qlearsite, CognitionX, Lexoo and Contego. I write novels about international dealmaking under the pen name David Zen. I am an enthusiastic sailor, husband and father.
Challenges to digital encryption from quantum computing, and potential solutions
Quantum computing may pose substantial challenges to the security of digital cryptography using public key encryption, primarily because Shor's algorithm (and possibly other methods) running on a sufficiently advanced quantum computer can theoretically solve the "hard problems" on which many public key cryptography are based (e.g. integer factorization, discrete logarithms in a finite field or over an elliptic curve) much faster than a digital computer can do so. There are also some theoretical speed-ups by quantum computing to "brute force" attacks on symmetric and hash algorithms.
This pinboard explores those threats and attacks, and the digital encryption methods that are resistant to them.
I am leading a report on these issues as part of the Distributed Futures project (http://www.longfinance.net/programmes/distributed-futures-menu.html).
Abstract: These lectures notes were written for a summer school on Mathematics for post-quantum cryptography in Thi\`es, Senegal. They try to provide a guide for Masters' students to get through the vast literature on elliptic curves, without getting lost on their way to learning isogeny based cryptography. They are by no means a reference text on the theory of elliptic curves, nor on cryptography; students are encouraged to complement these notes with some of the books recommended in the bibliography. The presentation is divided in three parts, roughly corresponding to the three lectures given. In an effort to keep the reader interested, each part alternates between the fundamental theory of elliptic curves, and applications in cryptography. We often prefer to have the main ideas flow smoothly, rather than having a rigorous presentation as one would have in a more classical book. The reader will excuse us for the inaccuracies and the omissions.
Pub.: 10 Nov '17, Pinned: 28 Nov '17
Abstract: The Ring Learning-With-Errors (RLWE) problem shows great promise for post-quantum cryptography and homomorphic encryption. We describe a new attack on the non-dual search RLWE problem with small error widths, using ring homomorphisms to finite fields and the chi-squared statistical test. In particular, we identify a "subfield vulnerability" (Section 5.2) and give a new attack which finds this vulnerability by mapping to a finite field extension and detecting non-uniformity with respect to the number of elements in the subfield. We use this attack to give examples of vulnerable RLWE instances in Galois number fields. We also extend the well-known search-to-decision reduction result to Galois fields with any unramified prime modulus q, regardless of the residue degree f of q, and we use this in our attacks. The time complexity of our attack is O(nq2f), where n is the degree of K and f is the residue degree of q in K. We also show an attack on the non-dual (resp. dual) RLWE problem with narrow error distributions in prime cyclotomic rings when the modulus is a ramified prime (resp. any integer). We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.
Pub.: 10 Oct '17, Pinned: 28 Nov '17
Abstract: The security of several post-quantum cryptosystems is based on the assumption that solving a system of multivariate (quadratic) polynomial equations $p_1=\dots=p_m=0$ over a finite field is hard. Such a system can be solved by computing a lexicographic Gr\"obner basis of the ideal $(p_1,\dots,p_m)$. The most efficient algorithms for computing Gr\"obner bases, such as $F_4$ and $F_5$, transform the problem into several instances of Gaussian elimination. The computational complexity of these algorithms is not completely understood, especially when the polynomials $p_1,\dots,p_m$ are non-homogeneous. In this paper, we prove that this complexity is bounded by a function of the Castelnuovo-Mumford regularity of the ideal $(p_1^h,\dots,p_m^h)$ obtained by homogenizing the input polynomials. This allows us to bound the complexity of solving a system of polynomial equations when the associated ideal is zero-dimensional, a common situation in cryptography. More precisely, we show that the degree of the polynomials involved in the computation a Gr\"obner basis of a zero-dimensional ideal grows at most linearly in the number of variables. In combination with some theorems in commutative algebra, our results also allow us to bound the complexity of some instances of the MinRank Problem.
Pub.: 20 Jun '17, Pinned: 28 Nov '17
Abstract: The performance of superconducting qubits has improved by several orders of magnitude in the past decade. These circuits benefit from the robustness of superconductivity and the Josephson effect, and at present they have not encountered any hard physical limits. However, building an error-corrected information processor with many such qubits will require solving specific architecture problems that constitute a new field of research. For the first time, physicists will have to master quantum error correction to design and operate complex active systems that are dissipative in nature, yet remain coherent indefinitely. We offer a view on some directions for the field and speculate on its future.
Pub.: 09 Mar '13, Pinned: 09 Dec '17
Join Sparrho today to stay on top of science
Discover, organise and share research that matters to you