Edition du vendredi 29 mars 2019 en salle Henri Lebesgue au rez de chaussée de l’IRMAR de Rennes, bâtiments 22-23, campus de beaulieu.
- 10h15 – Illaria Chilloti, KU Leuven : Improved Bootstrapping for Approximate Homomorphic Encryption
Résumé : Since Cheon et al. introduced a homomorphic encryption scheme for approximate arithmetic (Asiacrypt ’17), it has been recognized as suitable for important real-life usecases of homomorphic encryption, including training of machine learning models over encrypted data. A follow up work by Cheon et al. (Eurocrypt ’18) described an approximate bootstrapping procedure for the scheme.
In this work, we improve upon the previous bootstrapping result. We improve the amortized bootstrapping time per plaintext slot by two orders of magnitude, from ∼ 1 second to ∼ 0.01 second. To achieve this result, we adopt a
smart level-collapsing technique for evaluating DFT-like linear transforms on a ciphertext. Also, we replace the Taylor approximation of the sine function with a more accurate and numerically stable Chebyshev approximation, and design a modified version of the Paterson-Stockmeyer algorithm for fast evaluation of Chebyshev polynomials over encrypted data.
(joint work with Hao Chen and Yongsoo Song)
- 11h30 : Ayoub Otmani, LITIS, Université de Rouen : Permutation Code Equivalence is Not Harder Than Graph Isomorphism When Hulls are Trivial
Résumé : This talk deals with the problem of deciding if two finite-dimensional linear subspaces over an arbitrary field are identical up to a permutation of the coordinates. This problem is referred to as the permutation code equivalence.
I will explain that given access to a subroutine that decides if two weighted undirected graphs are isomorphic, one may deterministically decide the permutation code equivalence provided that the underlying vector spaces intersect trivially with their orthogonal complement with respect to an arbitrary inner product. Such class of vector spaces are usually called linear codes with trivial hulls. The reduction is efficient because it essentially boils down to computing the inverse of a square matrix of order the length of the involved codes. Experimental results obtained with randomly drawn binary codes with trivial hulls show that permutation code equivalence can be decided in a few minutes for lengths up to 50,000.
- 13h30 :Ida Tucker, ENS Lyon : Practical fully secure unrestricted inner product functional encryption modulo prime p.
Résumé :Functional encryption (FE) is an advanced cryptographic primitive which allows, for a single encrypted message, to finely control how much information on the encrypted data each receiver can recover. To this end many functional secret keys are derived from a master secret key. Each functional secret key allows, for a ciphertext encrypted under the associated public key, to recover a specific function of the underlying plaintext.
However constructions for general FE are far from practical, or rely on non-standard and ill-understood cryptographic assumptions.
In this talk I will focus on the construction of efficient FE schemes for linear functions (i.e. the inner product functionality), and the framework in which our constructions hold. Such schemes yield many practical applications, and our constructions are the first FE schemes for inner products modulo a prime that are both efficient and recover the result whatever its size I will also describe an instantiation of the framework using class groups of imaginary quadratic fields.
- 14h45 Brice Minaud, INRIA : Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks
Résumé : Searchable encryption enables a client to encrypt data, and outsource its storage to an untrusted server, while retaining the ability to issue search queries over the outsourced data. For efficiency reasons, all practical constructions in this area allow for the host server to learn a limited amount of information on the encrypted data as it processes queries, expressed in the security model by a leakage function. In this talk, I will give a short introduction to searchable encryption, and focus on the implications of very general (and seemingly innocuous) leakage functions. We will see that the problem of reconstructing the contents of the database from leakage information is closely related to statistical learning theory. Using this new viewpoint, I will present attacks that approximately reconstruct the contents of an entire database using only the access pattern leakage of range queries, a minimal type of leakage present in all practical constructions today.
Joint work with Paul Grubbs, Marie-Sarah Lacharité, and Kenny Paterson, to appear at S&P 2019.
