2012-2013: First results

During this first year, several tracks were followed in parallel, but not really independently, as they have to converge to a global vision of the security.

  1. The first track concerns the study and improvement of security mecanisms related to data or request privacy in the Cloud. In particular, we focused on the following ones:
    • Fully Homomorphic Encryption schemes.Since the introduction of the notion of \emph{privacy homomorphism} by Rivest et al. in the late seventies, the design of efficient and secure encryption schemes allowing to perform general computations in the encrypted domain has been one of the holy grails of the cryptographic community. Despite numerous partial answers, the  problem of designing such a powerful primitive has remained open until the theoretical breakthrough of the Fully Homomorphic Encryption (FHE)  scheme published by Gentry in the late noughties.  FHE refers to cryptosystems that are able to process both additions and multiplications in the encrypted domain. With such schemes, any polynomial function over encrypted data can be computed. It was really a breakthrough after 30 years of huge efforts, as it opens the way to many more powerful real applications than before. Nevertheless, due to its huge algorithmic complexity, large key size and ciphertext expansion, current FHE schemes remain today not efficient in practice. Since 2009, a lot of publications provided variants and improvements. In particular, several so-called somewhat FHE cryptosystems have been proposed, which allow any number of additions but a bounded number of
      multiplications. These schemes are really interesting as they are less complex than the fully homomorphic ones and are able to process a number of multiplications that is sufficient for most applications. Hence, they are considered today as the most promising schemes for practical applications.But despite these promising characteristics, their overhead remains today too high to make them directly usable in practice. There are mainly two ways to improve their efficiency. The first one is to propose new tricky variants that are less complex. The other one is to find some crafty way to implement them. Unfortunately, very few implementations have been published and publicly discussed yet, to measure how far we stand from their use in real  applications.We performed a number of steps towards bridging the gap between non trivial algorithms and their practical, relatively seamless, execution on (somewhat) FHE schemes. We have also provided some preliminary experimental results indicating that there is hope, in the near term, to be able to homomorphically execute simple algorithms on BGV-style cryptosystems in reasonable time.
    • Anonymous delivery protocol for multimedia content, which enables both privacy and traceability of malicious users.Active fingerprinting schemes were originally invented to deter malicious users from illegally releasing an item, such as a movie or a picture. To do so, each time an item is released, a different fingerprint is embedded in it. This fingerprint is generated with the help of an anti-collusion code. Thus, even if several malicious users collude to release a fake copy of the item, it should be possible to identify at least one of them by analyzing the fingerprint that can be extracted from this fake copy. The fingerprinting scheme is generally encapsulated inside an asymmetric distributed fingerprinting protocol, which objective is to prevent both parties (i.e., the merchant and the buyer) from cheating. Some of these protocols also address privacy concerns.We are currently working on the design of PIMENTO, the first privacy-preserving asymmetric fingerprinting protocol based on the famous Tardos anti-collusion codes.
  2. The second track focused on the design of a support tool allowing, for a given security policy, selection of the best mechanism or combination of mechanisms to enforce this security policy. To achieve this goal, we have used the following methodology:
    •  Using an Epistemic Linear Temporal Logic (Epistemic LTL), we defined an expressive language allowing to: (1) formally model a system composed of involved entities and the data on which the security policy should be enforced. (2) formally express the security policy defined by the security administrators.
    • We conducted a formal study of the security mechanisms allowing the achievement of a chosen goal. This formal study enables us to extract the security and utility properties that characterize each security mechanism. These properties are formally expressed using our language.
    • Based on the system formalization, the security policy formalization and the security mechanisms properties formalization,we formally identify the relevant combination of mechanisms to efficiently enforce the defined security policy.
  3. The third track concerns the adaptation of security solutions to the particular contexts of Cloud and peer-to-peer networks. It began later than the others. We are currently studying and deploying some usage scenarios based on cloud computing while considering the medical domain. We also have identified different security mechanisms we are going to adapt in such a framework. They treat aspects such as confidentiality, integrity and traitor tracing to cope with untrusted and roaming servers

2014: Anis Bkakria got a grant from EIT ICT Labs Doctoral Training Center to visit SAP AG in Karlsruhe (Germany).

Anis Bkakria, PhD student in POSEIDON, got a sponsorship from the EIT ICT Labs Doctoral Training Centre which includes the opportunity to make an internship in another Lab or industrial in Europe. In january 2014, he started an internship of three months in SAP AG Karlsruhe under the supervision of Andreas Schaad and Florian Kerschbaum. His main mission during my internship is the application of our approach of specification and deployment of Integrated Security Policies for Outsourced Data in one of the current security projects in SAP.

2014-2016: Dissemination of the results, and project’s dynamics


The tracks initated during the first year  have been pushed further, leading to several important results.

  • We provided the first generic experimental framework and platform dedicated to the implementation of fully homomorphic encryption. This platform includes tools to help programmers to use these particular encryption schemes in their applications.
  • We designed the first multimedia distribution protocol mixing optimal traitor tracing anti-collusion codes (Tardos codes) to trace dishonnest users, while preserving privacy issues for honnest users. A proper security analysis and an implementation have also been driven. This first protocol, PIMENTO, has been presented in an international conference in 2014 and an extended version PIMENTO+ is submitted for publication in a journal. A second protocol has been designed with the company NagraVisions and a common patent is to be applied for this second protocol before publication.
  • We designed and implemented a language to properly state and manage security properties of mechanisms that could be used to secure outsourced data and services. This provides guidelines to see which mechanisms can be mixed or not, and which ones are the most appropriate for a given use case.
  • We designed and implemented a POC of a platform dedicated to outsourced medical images sharing.

PhD defenses

Anis Bkakria defended his PhD in December 2015.
Julien Lolive will defend his PhD on May, 13rd 2016.

Final report

Our final report presenting all the results, dissemination and dynamics resulting from the project is now available: Final report poseidon

2017-2019: beyond POSEIDON – TYREX

POSEIDON’s goal was to improve security mechanisms and their management. Several types of mechanisms have been addressed within POSEIDON, and the purpose of TYREX is to push further some research direction concerning one of them, namely Fully Homomorphic Encryption.

To summarize the context, post-quantum security has been pointed out as a crucial issue by the NIST http://csrc.nist. gov/groups/ST/post-quantum-crypto/. Several tracks have been derived to address this issue, among which Euclidean lattices is particularly promising. Moreover, this mathematical structure provides efficient encryption schemes which enable to process data in a non trivial way while it is encrypted. These schemes are called Fully Homomorphic Encryption (FHE) schemes, and will greatly help to secure Cloud Computing services. With old-style homomorphic encryption schemes designed between 1978 and 2005, we were only able to run additions or multiplications on encrypted data, but not a mix of them. Since 2009, Euclidean lattices based schemes enable to run any polynomial on encrypted data, at least in theory. In practice, several issues have still to be addressed to propose practical solutions, but things evolve quickly. Among these issues, one can mention the huge size of the ciphertexts and a better understanding of the real underlying security. It is important to notice that estimating properly the security level is not trivial at all, and has important consequences on the parameters of the scheme, and then on the ciphertexts size and on the running time. Hence, anyone that would like to use this technology will be interested by new results on the security analysis of these schemes.

TYREX is based on a specific collaboration between IRIS team of Lab-STICC and EMSEC team of IRISA.

  • A first line of work was to focus mathematical structures underlying Fully Homomorphic Encryption schemes, in order to explore new solutions and better understand their security.
  • A second line of work was to focus on a stlightly different paradigm, called Functional Encryption. More precisely, our goal was to better understand the resulting security issues (private information leakage) for use cases where Functional Encryption is used to perform encrypted data classification.

More information about TYREX can be found here.

Comments are closed.