Hardness of the LWE problem

One of the goals of the HEAT project is to better understand the hardness of the computational problems that underly SHE. One of those problems, the Learning with Errors problem, has been investigated repeatedly, but until now, there was no consistent way to specify security parameters. In order to resolve this and increase interest in LWE-based cryptosystems, we built an efficient online security estimation tool, available to anyone and straightforward to use.

The LWE problem has three parameters: a dimension n, a Gaussian width parameter s and a modulus q. In order to implement the complexity of attacks against LWE as a function of these parameters, we combined results from the literature of the last couple of years, with a main focus on the Bounded Distance Decoding attack and the Blum-Kalai-Wasserman (BKW) algorithm. 

Our webtool implements the following three attacks:

- The SIS-based attack is an attack against the LWE decision problem, as described by Micciancio and Regev. Given a pair (A,t), one searches a vector v orthogonal to the rows of A (mod q) and checks whether the inner product <v,t> is small. 

- The Bounded distance decoding (BDD) attack is a combination of lattice basis reduction and the nearest planes algorithm of Lindner and Peikert. It attempts to solve the LWE search problem by searching a lattice point close to t.

- The BKW (Blum-Kalai-Wasserman) algorithm approaches the LWE search problem as a noisy linear system and uses a blocked version of Gaussian elimination with back substitution. This method was recently optimised by Duc, Tramèr and Vaudenay. 

Designers of cryptosystems are no longer restricted to parameters proposed in papers, but can use this tool to query the security estimates of any set of LWE parameters. Finally, in order to further simplify the process of choosing LWE parameters, we also implemented the search for a suitable modulus q. A user can input parameters n and s and a security level sec to obtain the approximate value of log_2(q) that results in sec bits of security.

 

Lauren De Meyer

Satellite Case Study for Homomorphic Encryption

Satellite Case Study for Homomorphic Encryption

The satellite industry is strategically important for Europe, and generates significant revenue as well as employing many tens of thousands of people in Europe. A particular issue facing European satellite providers is shared use and reconfigurability of infrastructure. Flexibility and configurability, and particularly shared use of satellites and their infrastructure, is essential to enable affordable use of satellites. The costs of launching and managing a single use satellite are prohibitive for many organisations. The ability to share this cost over multiple customers would expand the commercial reach of European satellite providers.

Shared infrastructure would ideally cover the satellites themselves, communication links to the ground, and the ground infrastructure which collates, processes and otherwise manages data received from the satellites. However, it brings with it security concerns due to the differing commercial and national sensitivities of the applications and data. In the HEAT project, we are looking at how Homomorphic Encryption could allow encryption to be used to provide the required security separation on such shared infrastructure, while still allowing essential and value-add processing of data to take place. It could also allow more cost-effective outsourcing of data processing and storage to Cloud Computing providers.

Potential applications areas are:

•  Commercial domain: the ground segment for the European Space Agency (ESA) Copernicus programme. Access to the Sentinel satellites’ Earth-observation data and generated products is restricted for commercial reasons. These missions will require increased processing capacity and would benefit from Cloud solutions.
• Scientific domain: the future Euclid ground segment. Scientific data for missions such as Euclid are confidential as access needs to be restricted to institutes, universities, etc. contributing to the mission, in order to ensure that they will publish the first papers and have the benefit of any discoveries. The confidentiality of scientific data is not uniquely defined. Therefore, solutions that allow flexibility in the security separation required (i.e. are not tied to the infrastructure) and allow outsourcing of the processing and storage would be of significant benefit.
• Dual domain (civilian & military): ESA’s Space Surveillance Awareness programme, and in particular the Space Surveillance and Tracking centre. Examples of sensitive data include sensor data, operational information (e.g. precise orbit information or existence of a satellite) and tactical information (e.g. object detached from a satellite).

For more than 40 years now, Thales Alenia Space has designed, integrated, tested, operated and delivered innovative space systems. Thales Alenia Space’s satellites and payloads are recognized worldwide as benchmarks in delivering communications and navigation services, monitoring our environment and the oceans, better understanding climate change and supporting scientific research. Thales Alenia Space is a leader in Earth observation, based on its high or very-high resolution optical and radar payloads. The appropriate handling of such sensitive data, using techniques such as homomorphic encryption, is a challenge, which the results of the HEAT project will help to address.