IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
09 November 2018
Hart Montgomery
ePrint ReportIn particular, we build several parallel (in $NC^{2}$) lattice-based PRFs with modulus independent of the number of PRF input bits based on both standard LWE and ring LWE. Our modulus for these PRFs is just $O \left(m^{ f \left(m \right)} \right)$ for lattice dimension $m$ and any function $f \left(m \right) \in \omega \left(1 \right)$. The only known parallel construction of a lattice-based PRF with such a small modulus is a construction from Banerjee's thesis, and some of our parallel PRFs with equivalently small modulus have smaller key sizes and are very slightly faster (when using FFT multiplication). These PRFs also asymptotically match the computational efficiency of the most efficient PRFs built from any LWE- or ring LWE-based assumptions known (potentially excluding some concurrent work), respectively, and concretely require less computation per output than any known parallel lattice-based PRFs (again when using FFT multiplication).
We additionally use our techniques to build other efficient PRFs with very low circuit complexity (but higher modulus) which improve known results on highly parallel lattice PRFs. For instance, for input length $\lambda$, we show that there exists a ring LWE-based PRF in $NC^{1}$ with modulus proportional to $m^{\lambda^{c}}$ for any $c \in \left(0, 1 \right)$. Constructions from lattices with this circuit depth were only previously known from larger moduli.
Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Pass, Elaine Shi
ePrint ReportInterestingly, the original proposal of (two-party) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum's notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions.
In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum's weak fairness notion in multi-party coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum's notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.
Jannis Bossert, Eik List, Stefan Lucks
ePrint ReportFelix Wegener, Amir Moradi
ePrint ReportJung Hee Cheon, Kyoohyung Han, Minki Hhan
ePrint ReportFirst, we proposed new method to evaluate the DFT homomorphically for a given packed ciphertext from the Cooley-Tukey fast Fourier transform algorithm. While the previous method requires $O(\sqrt n)$ rotations and $O(n)$ constant vector multiplications, our method only needs $O(\log n)$ rotations/multiplications by consuming $O(\log n)$ depth for the length of input vector $n$.
Second, we apply the same method to the linear transform of bootstrapping for $\textsf{HEAAN}$. To achieve this, we construct a recursive relation of matrices in those linear transformations. Accordingly, we can highly accelerate the linear transformation part of bootstrapping: the number of homomorphic operations becomes logarithmic to the number of slots, as in homomorphic DFT.
We also implement both algorithms. Our homomorphic DFT with length $2^{14}$ only takes about 8 seconds which is about 150 times faster result than previous one. The bootstrapping for $\textsf{HEAAN}$ with our linear transform algorithm takes about 2 minutes for $\mathbb{C}^{32768}$ plaintext space with 8 bit precision, which takes 26 hours using the previous method.
Mahdi Sajadieh, Mohsen Mousavi
ePrint ReportMurat Yasin Kubilay, Mehmet Sabir Kiraz, Haci Ali Mantar
ePrint ReportKwak Wi Song, Kim Chol Un
ePrint ReportEshan Chattopadhyay, Xin Li
ePrint ReportWe continue the line of investigation on explicit constructions of non-malleable codes in the information theoretic setting, and give explicit constructions for several new classes of tampering functions. These classes strictly generalize several previously studied classes of tampering functions, and in particular extend the well studied split-state model which is a "compartmentalized" model in the sense that the codeword is partitioned a prior into disjoint intervals for tampering. Specifically, we give explicit non-malleable codes for the following classes of tampering functions.
(1) Interleaved split-state tampering: Here the codeword is partitioned in an unknown way by an adversary, and then tampered with by a split-state tampering function.
(2) Linear function composed with split-state tampering: In this model, the codeword is first tampered with by a split-state adversary, and then the whole tampered codeword is further tampered with by a linear function. In fact our results are stronger, and we can handle linear function composed with interleaved split-state tampering.
(3) Bounded communication split-state tampering: In this model, the two split-state tampering adversaries are allowed to participate in a communication protocol with a bounded communication budget. Our results are the first explicit constructions of non-malleable codes in any of these tampering models. We derive all these results from explicit constructions of seedless non-malleable extractors, which we believe are of independent interest. Using our techniques, we also give an improved seedless extractor for an unknown interleaving of two independent sources.
Dana Dachman-Soled, Huijing Gong, Mukul Kulkarni, Aria Shahverdi
ePrint Report- Introduce the search and decision Leaky-RLWE assumptions (Leaky-SRLWE, Leaky-DRLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret and/or error.
- Present and implement an efficient key exposure attack that, given certain $1/4$-fraction of the coordinates of the NTT transform of the RLWE secret, along with RLWE instances, recovers the full RLWE secret for standard parameter settings.
- Present a search-to-decision reduction for Leaky-RLWE for certain types of key exposure.
- Analyze the security of NewHope key exchange under partial key exposure of $1/8$-fraction of the secrets and error.
We show that, assuming that Leaky-DRLWE is hard for these parameters, the shared key $v$ (which is then hashed using a random oracle) is computationally indistinguishable from a random variable with average min-entropy $238$, conditioned on transcript and leakage, whereas without leakage the min-entropy is $256$.
Xavier Bonnetain, María Naya-Plasencia, André Schrottenloher
ePrint ReportIn this paper we propose many other types of quantum slide attacks. First, we are able to quantize classical advanced slide attacks on Feistel networks. With modular additions inside branch or key-addition operations, these attacks reach up to two round self-similarity. With only XOR operations, they reach up to four rounds self-similarity, with a cost at most quadratic in the block size.
Moreover, some of these variants combined with whitening keys (FX construction) can be successfully attacked. We show how these results relate to general quantization principles of classical techniques including sliding with a twist, complementation slide and mirror slidex.
Furthermore, we show that some quantum slide attacks can be composed with other quantum attacks to perform efficient key-recoveries even when the round founction is a strong function classically.
Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, that were thought to enjoy an exponential speed up in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.
Akinori Hosoyamada, Takashi Yamakawa
ePrint ReportRussell W. F. Lai, Giulio Malavolta, Dominique Schröder
ePrint ReportNithyashankari Gummidipoondi Jayasankaran, Adriana Sanabria Borbon, Edgar Sanchez-Sinencio, Jiang Hu, Jeyavijayan Rajendran
ePrint ReportMashael AlSabah, Gabriele Oligeri, Ryan Riley
ePrint ReportIn this work, we analyze a meta-data rich data leak from a Middle Eastern bank with a demographically-diverse user base. We provide an analysis of passwords created by groups of people of different cultural backgrounds, some of which are under-represented in existing data leaks, e.g., Arab, Filipino, Indian, and Pakistani.
The contributions provided by this work are many-fold. First, our results contribute to the existing body of knowledge regarding how users include personal information in their passwords. Second, we illustrate the differences that exist in how users from different cultural/linguistic backgrounds create passwords. Finally, we study the (empirical and theoretical) guessability of the dataset based on two attacker models, and show that a state of the art password strength estimator inflates the strength of passwords created by users from non-English speaking backgrounds. We improve its estimations by training it with contextually relevant information.
Manuel Zander, Tom Waite, Dominik Harz
ePrint ReportBehnam Zahednejad, Majid Bayat, Ashok Kumar Das
ePrint Report07 November 2018
Darmstadt, Germany, 18 May 2019
Event CalendarSubmission deadline: 10 February 2019
Notification: 3 March 2019
06 November 2018
Alejandro Cabrera Aldaya, Billy Bob Brumley, Sohaib ul Hassan, Cesar Pereida Garc\'ia, Nicola Tuveri
ePrint ReportPromise Software Inc.
Job PostingWe are a high-energy, innovation-focused team of engineers and technologists passionate about leveraging advanced cryptographic primitives. Promise’s environment is highly collaborative, and the ideal candidate will have an eye for detail and be a team player who enjoys working with others to find cutting-edge solutions to tricky problems. Come join us!
What we are looking for in the Senior Cryptography Engineer?
This role is ideal for cryptography scientists who have deep research experience and familiarity with evolving and established post quantum cryptographic protocols and their implementation.
Preferred areas of research interest would be post-quantum cryptography. Candidates are required to have a Ph.D. in Computer Science, ECE or a related area, by the time of appointment and an outstanding research record. Solid background in cryptography, network security, distributed systems, protocols and algorithms, is highly desirable.
What you will be responsible doing?
1. Design and architect post quantum cryptography protocols in distributed p2p systems
2. Work with core internal team and external open source community
3. Collaborate with engineering and product teammates to produce protocol specification that help serve Promise customer objectives
4. Collaborate and support other teams in developing crypto economic consensus protocol
5. Identify and recommend technologies to solve technical challenges such as proof sizes
6. Interest in working in startup environments with a brisk pace and constantly changing challenges
Salary and Benefits:
Please get more information and apply here: https://aquila-1.workable.com/jobs/860808
Closing date for applications:
Contact: Head of Recruiting
jobs (at) promiseprotocols.com
More information: https://aquila-1.workable.com/jobs/860808