International Association for Cryptologic Research

IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

20 October 2017
Event Calendar Second Workshop on Targeted Attacks Nieuwpoort, Curaçao, 2 March 2018
Event date: 2 March 2018
Submission deadline: 12 December 2017
Notification: 22 January 2018
Imperial College London is providing three PhD studentship at Imperial College Computing Department in the area of ‘security and privacy, with a potential focus on blockchain security, privacy and scalability

  • To start: as soon as possible.

  • Studentship: Three untaxed stipend of £17K per annum and respectively 2 home/EU fees (at the UK/EU student rate only) provided by Imperial College London and 1 overseas fees provided by Nimiq.com.

With over 5 years of full-time blockchain expertise, a PhD degree and PostDoc from ETH Zurich, in the area of blockchain security, privacy and scalability, Dr. Arthur Gervais (www.arthurgervais.com) will be supervising the students directly. Arthur has authored 8+ influential peer-reviewed scientific articles on blockchain published at top-tier security conferences. Arthur has also shown how to convert scientific research into real-world products by providing the first automated formal verification tool for Ethereum based smart contracts (www.securify.ch).

The qualified candidate is encouraged to team up with other researchers at Imperial (e.g. researchers from Imperial business school) to collaborate on interdisciplinary research topics.

Applicants should have knowledge in one or more of:

  • Security and Privacy

  • Machine learning

  • Data analysis and modelling

  • Economics/finance (especially data economy)

  • Mathematical finance, etc.

      Closing date for applications: 1 April 2018

      Contact: Applicants should send by email to Dr. Arthur Gervais (a.gervais (at) imperial.ac.uk) their CV, details of academic qualifications and a short statement of your motivation and experience.

      More information: http://arthurgervais.com/BlockchainPhDAdvert.pdf

18 October 2017
We provide an alternative method for constructing lattice-based digital signatures which does not use the ``hash-and-sign'' methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the $\tilde{O}(n^{1.5})-SIVP$ problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also much simpler, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices.
17 October 2017
We explore a new security model for secure computation on large datasets. We assume that two servers have been employed to compute on private data that was collected from many users, and, in order to improve the efficiency of their computation, we establish a new tradeoff with privacy. Specifically, instead of claiming that the servers learn nothing about the input values, we claim that what they do learn from the computation preserves the differential privacy of the input. Leveraging this relaxation of the security model allows us to build a protocol that leaks some information in the form of access patterns to memory, while also providing a formal bound on what is learned from the leakage.

We then demonstrate that this leakage is useful in a broad class of computations. We show that computations such as histograms, PageRank and matrix factorization, which can be performed in common graph-parallel frameworks such as MapReduce or Pregel, benefit from our relaxation. We implement a protocol for securely executing graph-parallel computations, and evaluate the performance on the three examples just mentioned above. We demonstrate marked improvement over prior implementations for these computations.
ePrint Report A Faster Software Implementation of the Supersingular Isogeny Diffie-Hellman Key Exchange Protocol Armando Faz-Hern\'andez, Julio L\'opez, Eduardo Ochoa-Jim\'enez, Francisco Rodr\'iguez-Henr\'iquez
Since its introduction by Jao and De Feo in 2011, the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol has positioned itself as a promising candidate for post-quantum cryptography. One salient feature of the SIDH protocol is that it requires exceptionally short key sizes. However, the latency associated to SIDH is higher than the ones reported for other post-quantum cryptosystem proposals. Aiming to accelerate the SIDH runtime performance, we present in this work several algorithmic optimizations targeting both elliptic-curve and field arithmetic operations. We introduce in the context of the SIDH protocol a more efficient approach for calculating the elliptic curve operation P + [k]Q. Our strategy achieves a factor 1.4 speedup compared with the popular variable-three-point ladder algorithm regularly used in the SIDH shared secret phase. Moreover, profiting from pre-computation techniques our algorithm yields a factor 1.7 acceleration for the computation of this operation in the SIDH key generation phase. We also present an optimized evaluation of the point tripling formula, and discuss several algorithmic and implementation techniques that lead to faster field arithmetic computations. A software implementation of the above improvements on an Intel Skylake Core i7-6700 processor gives a factor 1.33 speedup against the state-of-the-art software implementation of the SIDH protocol reported by Costello-Longa-Naehrig in CRYPTO 2016.
ePrint Report Attacking Deterministic Signature Schemes using Fault Attacks Damian Poddebniak, Juraj Somorovsky, Sebastian Schinzel, Manfred Lochter, Paul Rösler
Many digital signature schemes rely on random numbers that are unique and non-predictable per signature. Failures of random number generators may have catastrophic effects such as compromising private signature keys. In recent years, many widely-used cryptographic technologies adopted deterministic signature schemes because they are presumed to be safer to implement.

In this paper, we analyze the security of deterministic ECDSA and EdDSA signature schemes and show that the elimination of random number generators in these schemes enables new kinds of fault attacks. We formalize these attacks and introduce practical attack scenarios against EdDSA using the Rowhammer fault attack. EdDSA is used in many widely used protocols such as TLS, SSH and IPSec, and we show that these protocols are not vulnerable to our attack. We formalize the necessary requirements of protocols using these deterministic signature schemes to be vulnerable, and discuss mitigation strategies and their effect on fault attacks against deterministic signature schemes.
ePrint Report Homomorphic SIMMD Operations: Single Instruction Much More Data Wouter Castryck, Ilia Iliashenko, Frederik Vercauteren
In 2014, Smart and Vercauteren introduced a packing technique for homomorphic encryption schemes by decomposing the plaintext space using the Chinese Remainder Theorem. This technique allows to encrypt multiple data values simultaneously into one ciphertext and execute Single Instruction Multiple Data operations homomorphically. In this paper we improve and generalize their results by introducing a flexible Laurent polynomial encoding technique and by using a more fine-grained CRT decomposition of the plaintext space. The Laurent polynomial encoding provides a convenient common framework for all conventional ways in which input data types can be represented, e.g.finite field elements, integers, rationals, floats and complex numbers. Our methods greatly increase the packing capacity of the plaintext space, as well as one's flexibility in optimizing the system parameters with respect to efficiency and/or security.
ePrint Report Conditional Cube Attack on Round-Reduced River Keyak Wenquan Bi, Zheng Li, Xiaoyang Dong, Lu Li, Xiaoyun Wang
This paper evaluates the security level of the River Keyak against the cube-like attack. River Keyak is the only lightweight scheme of the Keccak-permutation-based Authenticated Encryption Cipher Keyak, which is one of the 16 survivors of the 3rd round CAESAR competition. Dinur et al. gave the seven-round cube-like attack on Lake Keyak (1600-bit) using the divide-and-conquer method at EUROCRYPT 2015, then Huang et al. improved the result to 8-round using a new conditional cube attack at EUROCRYPT 2017. While for River Keyak, the 800-bit state is so small that the equivalent key (256-bit capacity) occupy double lanes, the attacks can not be applied to the River Keyak trivially.

In this paper, we comprehensively explore the conditional cube attack on the small state (800-bit) River Keyak. Firstly, we find a new conditional cube variable which has a much weaker diffusion than Huang et al.'s, this makes the conditional cube attack possible for small state (800-bit) River Keyak. Then we find enough cube variables for 6/7-round River Keyak and successfully launch the key recovery attacks on 6/7-round River Keyak with the time complexity $2^{33}$ and $2^{49}$ respectively. We also verify the 6 and 7-round attack on a laptop. Finally, by using linear structure technique with our new conditional cube variable, we greatly increase the freedom degree to find more cube variables for conditional cube attacks as it is complex for 800-bit state to find enough cube variables for 8-round attack. And then we use the new variables by this new method to launch 8-round conditional cube attack with the time complexity $2^{81}$. These are the first cryptanalysis results on round-reduced River Keyak. Our attacks do not threaten the full-round (12) River Keyak.
Event Calendar SICHERHEIT 2018: SICHERHEIT 2018 Konstanz, Germany, 25 April - 27 April 2018
Event date: 25 April to 27 April 2018
Submission deadline: 30 November 2017
Notification: 24 January 2018
Event date: 13 June to 15 June 2018
Submission deadline: 10 February 2018
Notification: 8 April 2018
16 October 2017
The 2017 Election for Directors of the IACR Board is now open.

You may vote as often as you wish now through November 16th using the Helios cryptographically-verifiable election system, but only your last vote will be counted.

Please see https://www.iacr.org/elections/eVoting/about-helios.html for a brief overview of how the Helios system works and https://www.iacr.org/elections/eVoting/ for information on the IACR decision to adopt Helios.

2017 members of the IACR (generally people who attended an IACR conference or workshop in 2016) should shortly receive voting credentials from system@heliosvoting.org sent to their email address of record with the IACR. Questions about this election may be sent to elections@iacr.org.

Information about the candidates can be found below and also at https://www.iacr.org/elections/2017/vote.html.

The IACR Election Committee
Tal Rabin (Chair)
Michel Abdalla (Returning Officer)
Bart Preneel

Candidates for Election in 2017

The candidates below are listed in alphabetical order.

Director (Select as many as desired. Top three vote recipients will be elected.)
  • Masayuki Abe
    I have been serving the Board of Directors for three years and am currently serving the School Committee and Asiacrypt Steering Committee. Many changes have been made over the years. I would like to support the trend and contribute to the community using my experience.
  • Josh Benaloh
    I have had the privilege of serving on the IACR Board for 17 years - as an officer, a conference chair, and a director. We have grown and addressed many challenges in those years, and we have many new challenges today. I seek the opportunity to continue working for the community.
  • Tancrède Lepoint
    As your IACR board member, I will (1) foster fruitful relations among our theoretical & practical researchers, industry, and standards, (2) improve the online services provided by the IACR (front- and back-end), and (3) further develop the open and international dissemination of our results and code.
  • Moti Yung
    I like to continue supporting IACR's growth and increased excellence, to assure the special needs of individuals and all sub-communities (e.g., CHES, TCC). We need diversity of opinions, geographies, genders, and scientific areas, to assure continued success. Serving last term was a pleasure mixed with modest progress!
    • Candidate home page: None given
    • Longer statement: None given
14 October 2017
Event date: 24 January 2018
Submission deadline: 17 November 2017
Notification: 18 December 2017
13 October 2017
Oblivious Transfer (OT) is a simple, yet fundamental primitive which suffices to achieve almost every cryptographic application. In a recent work (Latincrypt `15), Chou and Orlandi (CO) present the most efficient, fully UC-secure OT protocol to date and argue its security under the CDH assumption. Unfortunately, a subsequent work by Genc et al. (Eprint `17) exposes a flaw in their proof which renders the CO protocol insecure. In this work, we make the following contributions: We first point out two additional, previously undiscovered flaws in the CO protocol and then show how to patch the proof with respect to static and malicious corruptions in the UC model under the stronger Gap Diffie-Hellman (GDH) assumption. With the proof failing for adaptive corruptions even under the GDH assumption, we then present a novel OT protocol which builds on ideas from the CO protocol and can be proven fully UC-secure under the CDH assumption. Interestingly, our new protocol is actually significantly more efficient (roughly by a factor of two) than the CO protocol. This improvement is made possible by avoiding costly redundancy in the symmetric encryption scheme used in the CO protocol. Our ideas can also be applied to the original CO protocol, which yields a similar gain in efficiency.
Digital rights management is an important technique to protect digital contents from abuse. Usually it is confronted with severe challenges because of the untrusted environment its application executed in. This condition is formally described as white-box attack model. White-box cryptography aims at protecting software implementation of cryptographic algorithms from white-box attack, hence can be employed to provide security guarantee for digital rights management. Key extraction, code lifting, and illegal distribution are three major threats in digital rights management application, they extremely compromise the benefit of content producer. In this paper, we propose the first solution based on white-box cryptography against the three threats above simultaneously, by implementing traceability of a white-box scheme which has unbreakability and incompressibility. Specifically, We constructively confirm there exists secure white-box compiler which can generate traceable white-box programs, by hiding slight perturbations in the lookup-table based white-box implementation. Security and performance analyses show our solution can be effectively achieved in practice.
ePrint Report Architecture level Optimizations for Kummer based HECC on FPGAs Gabriel Gallin, Turku Ozlum Celik, Arnaud Tisserand
On the basis of a software implementation of Kummer based HECC over Fp presented in 2016, we propose new hardware architectures. Our main objectives are: definition of architecture parameters (type, size and number of units for arithmetic operations, memory and internal communications); architecture style optimization to exploit internal par-allelism. Several architectures have been designed and implemented on FPGAs for scalar multiplication acceleration in embedded systems. Our results show significant area reduction for similar computation time than best state of the art hardware implementations of curve based solutions.
ePrint Report Automatic Characterization of Exploitable Faults: A Machine Learning Approach Sayandeep Saha, Dirmanto Jap, Sikhar Patranabis, Debdeep Mukhopadhyay, Shivam Bhasin, Pallab Dasgupta
Characterization of the fault space of a cipher to filter out a set of faults potentially exploitable for fault attacks (FA), is a problem with immense practical value. A quantitative knowledge of the exploitable fault space is desirable in several applications, like security evaluation, cipher construction and implementation, design, and testing of countermeasures etc. In this work, we investigate this problem in the context of block ciphers. The formidable size of the fault space of a block cipher suggests for an automation to solve this problem, which should be able to characterize each individual fault instance quickly. On the other hand, the automation is expected to be applicable to most of the block cipher constructions. Existing techniques for automated fault attacks do not satisfy both of these goals simultaneously and hence are not directly applicable in the context of exploitable fault characterization. In this paper, we present a supervised machine learning (ML) assisted automated framework, which successfully addresses both of the criteria mentioned. The key idea is to extrapolate the knowledge of some existing FAs on a cipher to rapidly figure out new attack instances on the same. Experimental validation of the proposed framework on two state-of-the-art block ciphers – PRESENT and LED, establishes that our approach is able to provide fairly good accuracy in identifying exploitable fault instances at a reasonable cost. Finally, the effect of different S-Boxes on the fault space of a cipher is evaluated utilizing the framework.
Protecting malware using encryption prevents an analyst, defending some computer(s) in the network, from analyzing the malicious code and identifying the intentions of the malware author. We discuss malware encryption schemes that use environmental encryption keys, generated from some computer(s) the malware author intends to attack, and is able to rerandomize ciphertexts, to make each malware sample in the network indistinguishable. We are interested in hiding the intentions and identity of the malware author, not in hiding the existence of malware.
In this work, we study unconditionally-secure multi-party computation (MPC) tolerating $t < n/3$ corruptions, where $n$ is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with $t<n/3$ requires a communication of $O(n^5)$ field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires $O(n^2)$ communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.
We give a first tight security reduction for a conversion from a weakly secure public-key encryption scheme to an IND-CCA-secure key-encapsulation mechanism scheme in the quantum random oracle model. To the best of our knowledge, previous reductions are non-tight as the security levels of the obtained schemes are degraded to at most half or quater of the original security level (Boneh, Dagdelen, Fischlin, Lehmann, Schafner, and Zhandry (CRYPTO 2012), Targhi and Unruh (TCC 2016-B), and Hofheinz, Hövelmanns, and Kiltz (TCC 2017)).
In this paper, we initiate the study of \emph{garbled protocols} --- a generalization of Yao's garbled circuits construction to distributed protocols. More specifically, in a garbled protocol construction, each party can independently generate a garbled protocol component along with pairs of input labels. Additionally, it generates an encoding of its input. The evaluation procedure takes as input the set of all garbled protocol components and the labels corresponding to the input encodings of all parties and outputs the entire transcript of the distributed protocol.

We provide constructions for garbling arbitrary protocols based on standard computational assumptions on bilinear maps (in the common random/reference string model). Next, using garbled protocols we obtain a general compiler that compresses any arbitrary round multiparty secure computation protocol into a two-round UC secure protocol. Previously, two-round multiparty secure computation protocols were only known assuming witness encryption or learning-with errors. Benefiting from our generic approach we also obtain two-round protocols (i) for the setting of random access machines (RAM programs) while keeping the (amortized) communication and computational costs proportional to running times, (ii) making only a black-box use of the underlying group, eliminating the need for any expensive non-black-box group operations and (iii) satisfying semi-honest security in the plain model.

Our results are obtained by a simple but powerful extension of the non-interactive zero-knowledge proof system of Groth, Ostrovsky and Sahai [Journal of ACM, 2012].
ePrint Report Secure Multi-Party Computation in Large Networks Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, Mahdi Zamani
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a significant number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous environment, we allow the adversary to corrupt less than a $1/8$ fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of messages and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide statistical and universally-composable security.

To achieve our asynchronous MPC result, we define the threshold counting problem and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model.
In this paper, we propose new classes of trapdoor functions to solve the closest vector problem in lattices. Specifically, we construct lattices based on properties of polynomials for which the closest vector problem is hard to solve unless some trapdoor information is revealed. We thoroughly analyze the security of our proposed functions using state-of-the-art attacks and results on lattice reductions. Finally, we describe how our functions can be used to design quantum-safe encryption schemes with reasonable public key sizes. In particular, our scheme can offer around $106$ bits of security with a public key size of around $6.4$ KB. Our encryption schemes are efficient with respect to key generation, encryption and decryption.
An Order-Revealing Encryption (ORE) scheme gives a public procedure by which two ciphertext can be compared to reveal the order of their underlying plaintexts. The ideal security notion for ORE is that only the order is revealed --- anything else, such as the distance between plaintexts, is hidden. The only known constructions of ORE achieving such ideal security are based on cryptographic multilinear maps, and are currently too impractical for real-world applications. In this work, we give evidence that building ORE from weaker tools may be hard. Indeed, we show black-box separations between ORE and most symmetric-key primitives, as well as public key encryption and anything else implied by generic groups in a black-box way. Thus, any construction of ORE must either (1) achieve weaker notions of security, (2) be based on more complicated cryptographic tools, or (3) require non-black-box techniques. This suggests that any ORE achieving ideal security will likely be somewhat inefficient. Central to our proof is an proof of impossibility for something we call information theoretic ORE, which has connections to tournament graphs and a theorem by Erdos. This impossibility proof will be useful for proving other black box separations for ORE.
12 October 2017
Job Posting Research Scientist Temasek Laboratories, NTU, Singapore
The Physical Analysis and Cryptographic Engineering (PACE), Temasek Laboratories (TL) @ Nanyang Technological University, Singapore is seeking one motivated researcher, in the area of hardware security.

Candidates should ideally have already completed, or be close to completing a PhD degree in mathematics, computer science, electrical engineering, or related disciplines, with strong track record in R&D (publications in international journals and conferences). Master degree with relevant research experience can be considered.

You will be joining a dynamic group performing research on embedded security, specific to physical attacks. This position is available from December 2017. The initial contract will be one year. There are strong possibilities for extensions upon successful performance. TL offers competitive salary package plus other benefits.

Review of applications will start immediately until position is filled.

Interested candidates should send their detailed CVs, cover letter and references ,

Closing date for applications: 28 February 2018

Contact: Shivam Bhasin, Co-Principle Investigator: sbhasin (at) ntu.edu.sg

Job Posting Post Doc in Embedded System Security Laboratoire Hubert Curien, University of Lyon, Saint-Etienne, France
The main objective of the research in the Embedded System Security Group is to propose efficient and robust hardware architectures aimed at applied cryptography and telecom that are resistant to passive and active cryptographic attacks. Currently, the central theme of this research consists in designing architectures for secure embedded systems implemented in logic devices such as FPGAs and ASICs. More information on https://laboratoirehubertcurien.univ-st-etienne.fr/en/teams/secure-embedded-systems-hardware-architectures.html.

For a new project which addresses the problem of secure and privacy in MPSoC architectures, we proposes a Post Doc position to work on security evaluation of heterogeneous MPSoC with ARM core. We are looking for candidates with an outstanding Ph.D in hardware/software security and a strong publication record in this field. Knowledge of French is not mandatory.

The Post-Doc position will start at the beginning of 2018 (flexible starting date), it is funded for 14 months.

To apply please send your detailed CV (with publication list), motivation for applying (1 page) and names of at least two people who can provide reference letters (e-mail).

Closing date for applications: 18 December 2017

Contact: Prof. Lilian BOSSUET lilian.bossuet(at)univ-st-etienne.fr

11 October 2017
ePrint Report No right to remain silent: Isolating Malicious Mixes Hemi Leibowitz, Ania Piotrowska, George Danezis, Amir Herzberg
Mix networks are a key technology to provide network anonymity, used for messaging, voting and private lookups. However, simple mix networks are insecure against malicious mixes, which can drop or delay packets to facilitate traffic analysis attacks. Mix networks with provable robustness address this by using complex and expensive proofs of correct shuffling, which come with a cost and make assumptions that are unnatural to many settings in which mix networks are deployed. We present \sysname, a synchronous mix network mechanism, which is provably secure against malicious mixes -- yet retaining the simplicity, efficiency and practicality of mix network designs. \sysname\ uses first-hand experience of unreliability by mixes and clients, to derive a mix `reputation', and to ensure that each active attack -- including dropping of packets -- results in reduction in the connectivity of the malicious mixes, thus reducing their ability to attack. Besides the practical importance of \sysname itself, our results are applicable to other mix networks designs and anonymous communication, and even unrelated settings in which reputation could provide effective defense against malicious participants.
Asymptotically, the best known algorithms for solving the Shortest Vector Problem (SVP) in a lattice of dimension $n$ are sieve algorithms, which have heuristic complexity estimates ranging from $(4/3)^{n+o(n)}$ down to $(3/2)^{n/2 +o(n)}$ when Locality Sensitive Hashing techniques are used. Sieve algorithms are however outperformed by pruned enumeration algorithms in practice by several orders of magnitudes, despite the larger super-exponential asymptotical complexity $2^{\Theta(n \log n)}$ of the latter. In this work, we show a concrete improvement of sieve-type algorithms. Precisely, we show that a few calls to the sieve algorithm in lattices of dimension less than $n-d$ allows to solve SVP in dimension $n$, where $d = \Theta(n/\log n)$.

Although our improvement is only sub-exponential, its practical effect in relevant dimensions is quite significant. We implemented it over a simple sieve algorithm with $(4/3)^{n+o(n)}$ complexity, and it outperforms the best sieve algorithms from the literature by a factor 10 in dimensions 70-80. It performs less than an order of magnitude slower than pruned enumeration in the same range.

By design, this improvement can also be applied to most other variants of sieve algorithms, including LSH sieve algorithms and tuple-sieve algorithms. In this light, we may expect sieve-techniques to outperform pruned enumeration in practice in the near future.
Logic encryption is an important hardware protection technique that adds extra keys to lock a given circuit. With recent discovery of the effective SAT-based attack, new enhancement methods such as SARLock and Anti-SAT have been proposed to thwart the SAT-based and similar exact attacks. Since these new techniques all have very low error rate, approximate attacks such as Double DIP and AppSAT have been proposed to find an almost correct key with low error rate. However, measuring the performance of an approximate attack is extremely challenging, since exact computation of the error rate is very expensive, while estimation based on random sampling has low confidence. In this paper, we develop a suite of scientific encryption benchmarks where a wide range of error rates are possible and the error rate can be found out by simple eyeballing. Then, we conduct a thorough comparative study on different approximate attacks, including AppSAT and Double DIP. The results show that approximate attacks are far away from closing the gap and more investigations are needed in this area.
ePrint Report Hash Proof Systems over Lattices Revisited Fabrice Benhamouda, Olivier Blazy, Léo Ducas, Willy Quach
Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt'02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting.

Only one construction of an SPHF over lattices has been proposed in the standard model, by Katz and Vaikuntanathan at Asiacrypt'09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring $q$ many trapdoor inversion attempts, where $q$ is the modulus of the underlying Learning With Errors (LWE) problem.

Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-IND-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt'12). We then improve our construction and our analysis in the case where the tag is known in advance or fixed (in the latter case, the scheme is only IND-CPA) with a super-polynomial modulus, to get a stronger type of SPHF, which was never achieved before for any language over lattices.

Finally, we conclude with applications of these SPHFs: password-based authenticated key exchange, honest-verifier zero-knowledge proofs, and a relaxed version of witness encryption.
ePrint Report Large FHE gates from Tensored Homomorphic Accumulator Guillaume Bonnoron, Léo Ducas, Max Fillinger
The main bottleneck of all known Fully Homomorphic Encryption schemes lies in the bootstrapping procedure invented by Gentry (STOC'09). The cost of this procedure can be mitigated either using Homomorphic SIMD techniques, or by performing larger computation per bootstrapping procedure.

In this work, we propose new techniques allowing to perform more operations per bootstrapping in FHEW-type schemes (EUROCRYPT'13). While maintaining the quasi-quadratic $\tilde O(n^2)$ complexity of the whole cycle, our new scheme allows to evaluate gates with $\Omega(\log n)$ input bits, which constitutes a quasi-linear speed-up. Our scheme is also very well adapted to large threshold gates, natively admitting up to $\Omega(n)$ inputs. This could be helpful for homomorphic evaluation of neural networks.

Our theoretical contribution is backed by a preliminary prototype implementation, which can perform $6$-to-$6$ bit gates in less than $10$ seconds on a single core, as well as threshold gates over $63$ input bits even faster.

  older items