Carlos Cid

We analyse the complexity of algebraic algorithms for solving systems of linear equations with \emph{noise}. Such systems arise naturally in the theory of error-correcting codes as well as in computational learning theory. More recently, linear systems with noise have found application in cryptography. The \emph{Learning with Errors} (LWE) problem has proven to be a rich and versatile source of innovative cryptosystems, such as fully homomorphic encryption schemes. Despite the popularity of the LWE problem, the complexity of algorithms for solving it is not very well understood, particularly when variants of the original problem are considered. Here, we focus on and generalise a particular method for solving these systems, due to Arora \& Ge, which reduces the problem to non-linear but noise-free system solving. Firstly, we provide a refined complexity analysis for the original Arora-Ge algorithm for LWE. Secondly, we study the complexity of applying algorithms for computing Gröbner basis, a fundamental tool in computational commutative algebra, to solving Arora-Ge-style systems of non-linear equations. We show positive and negative results. On the one hand, we show that the use of Gröbner bases yields an exponential speed-up over the basic Arora-Ge approach. On the other hand, we give a negative answer to the natural question whether the use of such techniques can yield a subexponential algorithm for the LWE problem. Under a mild algebraic assumption, we show that it is highly unlikely that such an improvement exists. We also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show under a natural algebraic assumption that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g.\ m=O(nloglog⁡n)m=O(n \log \log n). We also derive precise complexity bounds for BinaryError-\LWE with m=O(n)m=O(n), showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as m/n≥6.6m/n \geq 6.6. More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from m=n(1+Ω(1/log(n))m=n\left(1+\Omega\big(1/{\rm log}(n)\right) (a case for which BinaryError-\LWE{} is as hard as solving some lattice problem in the worst case) to m=O(n2)m=O(n^2) (a case for which it can be solved in polynomial-time). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-\LWE for many cryptographic applications. The results in this work depend crucially on the assumption the algebraic systems considered systems are not easier and not harder to solve than a random system of equations. We have verified experimentally such hypothesis. We also have been able to prove formally the assumptions is several restricted situations. We emphasize that these issues are highly non-trivial since proving our assumptions in full generality would allow to prove a famous conjecture in commutative algebra known as Fröberg's Conjecture.

The combination of software-as-a-service and the increasing use of mobile devices gives rise to a considerable difference in computational power between servers and clients. Thus, there is a desire for clients to outsource the evaluation of complex functions to a server and to be able to verify that the resulting value is correct. Previous work in this area of Publicly Verifiable Outsourced Computation (PVC) requires a costly pre-processing stage. However, in many practical situations multiple clients will be interested in the same set of core functions and will make use of the same servers. Thus, the pre-processing phase may be performed many more times than is necessary. In this paper we introduce a Key Distribution Center (KDC) that handles the generation and distribution of the keys that are required to support PVC, thereby eliminating this redundancy. We define a number of new security models and functionalities that arise with the introduction of the KDC, and present a construction of such a scheme built upon Key-Policy Attribute-based Encryption.

This paper is a guide for the pure mathematician who would like to know more about cryptography based on group theory. The paper gives a brief overview of the subject, and provides pointers to good textbooks, key research papers and recent survey papers in the area. Introduction In the last few years, many papers have proposed cryptosystems based on group theoretic concepts. Notes from a recent advanced course on the subject by Myasnikov, Shpilrain and Ushakov have recently been published as a monograph [63], and a textbook (with a rather different focus) by González Vasco, Magliveras and Steinwandt [31] is promised in 2010. Group-based cryptosystems have not yet led to practical schemes to rival RSA and Diffie–Hellman, but the ideas are interesting and the different perspective leads to some worthwhile group theory. The cryptographic literature is vast and diverse, and it is difficult for a newcomer to the area to find the right sources to learn from. (For example, there are many introductory textbooks aimed at the mathematical audience that introduce RSA. How many of these textbooks hint that the basic RSA scheme is insecure if refinements such as message padding are not used? For a discussion of these issues, see Smart [78, Chapters 17,18 and 20], for example.) Our paper will provide some pointers to some sources that, in our opinion, provide a good preparation for reading the literature on group-based cryptography; the paper will also provide a high level overview of the subject.