IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
20 May 2019
María Naya-Plasencia, André Schrottenloher
In this paper, we study quantum algorithms for several variants of the k-xor problem. When quantum oracle access is allowed, we improve over previous results of Grassi et al. for almost all values of k. We define a set of "merging trees" which represent strategies for quantum and classical merging in k-xor algorithms, and prove that our method is optimal among these. We provide, for the first time, quantum speedups when the lists can be queried only classically.
We also extend our study to lists of limited size, up to the case where a single solution exists. We give quantum dissection algorithms that outperform the best known for many k, and apply to the multiple-encryption problem. Our complexities are confirmed by a Mixed Integer Linear Program that computes the best strategy for a given k-xor problem. All our algorithms apply when considering modular additions instead of bitwise XORs.
Jean-Claude Bajard, Julien Eynard, Paulo Martins, Leonel Sousa, Vincent Zucca
Michael Naehrig, Joost Renes
Ward Beullens, Thorsten Kleinjung, Frederik Vercauteren
Jiafan Wang, Sherman S. M. Chow
In this paper, with our encrypted index which enables queries for a sequence of contiguous keywords, we propose a generic upgrade of any DSSE to support range query (a.k.a. range DSSE), and a concrete construction which provides a new trade-off of reducing the client storage to "reclaim" the benefits of outsourcing.
Our schemes achieve forward security, an important property which mitigates file injection attacks. We identify a variant of file injection attack against a recent solution (ESORICS'18). We also extend the definition of backward security to range DSSE and show our schemes are compatible with a generic transformation for achieving backward security (CCS'17).
We comprehensively analyze the computation and communication overheads including some parts which were ignored in previous schemes, e.g., index-related operations in the client side. Our experiments demonstrate the high efficiency of our schemes.
Christian Majenz, Christian Schaffner, Jeroen van Wier
Marc Joye
ROME, ITALY, 22 June - 25 June 2020
Submission deadline: 9 September 2019
Notification: 20 January 2020
Haodong Jiang, Zhenfeng Zhang, Zhi Ma
In this paper, for KEM variants of the FO transformation, we show that a typical measurement-based reduction in the QROM from breaking standard OW-CPA (or IND-CPA) security of the underlying PKE to breaking the IND-CCA security of the resulting KEM, will inevitably incur a quadratic loss of the security, where ``measurement-based" means the reduction measures a hash query from the adversary and uses the measurement outcome to break the underlying security of PKE. In particular, all currently known security reductions in (TCC 2017 and Crypto 2018) are of this type, and our results suggest an explanation for the lack of progress in improving the reduction tightness in terms of the degree of security loss. We emphasize that our results do not expose any post-quantum security weakness of KEM variants of FO transformation.
Anamaria Costache, Kim Laine, Rachel Player
Daniel J. Bernstein, Andreas Hülsing
Eloi de Cherisey, Sylvain Guilley, Olivier Rioul, Pablo Piantanida
Ward Beullens
-A solution to a system of quadratic polynomials
-A solution to an instance of the Permuted Kernel Problem
We then remove the helper from the protocol with a "cut-and-choose" protocol and we apply the Fiat-Shamir transform to obtain signature schemes with security proof in the QROM. We show that the resulting signature schemes, which we call the "MUltivarite quaDratic FIat-SHamir" scheme (MUDFISH) and the "ShUffled Solution to Homogeneous linear SYstem FIat-SHamir" scheme (SUSHSYFISH), are more efficient than existing signatures based on the MQ problem and the Permuted Kernel Problem. We also leverage the ZK-proof for PKP to improve the efficiency of Stern-like Zero Knowledge proofs for lattice statements.
Leon Botros, Matthias J. Kannwischer, Peter Schwabe
Alan Kaminsky
19 May 2019
Michel Abdalla, Fabrice Benhamouda, Romain Gay
Suhyeon Lee, Seungjoo Kim
16 May 2019
London, UK, 11 November 2019
Submission deadline: 28 June 2019
Notification: 14 August 2019
15 May 2019
Centre for Quantum Technologies, Singapore
The position comes with an internationally competitive salary and generous support for travel. Moreover, there are ample opportunities to collaborate with excellent scientists both based at CQT/NUS and research visitors.
Closing date for applications: 31 October 2019
Contact: Divesh Aggarwal
Assistant Professor, NUS, and Principal Investigator, CQT (joint appointment)
divesh.aggarwal (at) gmail.com
CEA Saclay
CEA background in these fields
==============================
CEA LIST has been a key leader in fully homomorphic encryption techniques https://github.com/CEA-LIST/Cingulata. In the context of FHE, machine learning applications appear as a killer application. Many key advances have yet to be considered to fully address machine learning applications using FHE technologies. Next technological barriers depend on the computational cost of the considered stage (training or inference) but the main approaches are: first to limit operators used in graph neural networks such that FHE associated computational cost is kept reasonable. Second FHE can be viewed as a building block, which could be activated in specific parts of the pipeline to ensure model or data privacy. CEA LIST is also very active in the field of randomization algorithms to ensure data privacy and robustness to adversarial attacks. Past works include PhD thesis of Anne Morvan and Rafael Pinot.
Closing date for applications: 15 June 2019
Contact: Cedric Gouy-Pailler (cedric.gouy-pailler (at) cea.fr) or Renaud Sirdey
More information: https://gouypailler.github.io/files/phdCryptoRobust.pdf