IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
13 September 2016
Raluca Ada Popa, Emily Stark, Jonas Helfer, Steven Valdez, Nickolai Zeldovich, M. Frans Kaashoek, Hari Balakrishnan
ePrint ReportAdria Gascon, Phillipp Schoppmann, Borja Balle, Mariana Raykova, Jack Doerner, Samee Zahur, David Evans
ePrint ReportJie Chen
ePrint ReportArtur Mariano, Thijs Laarhoven, Christian Bischof
ePrint ReportAggelos Kiayias, Ioannis Konstantinou, Alexander Russell, Bernardo David, Roman Oliynykov
ePrint ReportThijs Laarhoven
ePrint ReportIn practice, the large memory footprint makes it problematic to run sieving directly on high-dimensional lattices, and perhaps the most promising application of such algorithms is as part of a hybrid with lattice enumeration. It is well-known that a faster algorithm for solving the closest vector problem with preprocessing (CVPP) in low dimensions could be used to speed up enumeration for SVP or CVP in high dimensions, but so far it is not even clear whether the fastest sieving methods can be used to solve CVP at all.
Our contributions are two-fold. First, we show that with sieving, we can solve CVP with similar costs as SVP, improving upon the results of Becker-Gama-Joux. Our second and main contribution is that with lattice sieving we can construct a truly efficient CVPP solver. Heuristically, we can for instance solve CVPP in $2^{d/4 + o(d)}$ time and space, while the time complexity can be reduced to as little as $2^{\varepsilon d + o(d)}$ for arbitrary $\varepsilon > 0$ at the cost of $(1/\varepsilon)^{O(d)}$ space. Preliminary experiments support these claims, and in dimension $50$ we roughly obtain a factor $2000$ speedup for CVPP compared to solving SVP with sieving. This may be a first step towards a practical hybrid between enumeration and sieving.
Anne Canteaut, Sébastien Duval, Léo Perrin
ePrint ReportDaniel Hutchinson
ePrint ReportSince then, another improved sponge-based PRNG has been put forward by Ga\v{z}i and Tessaro (Eurocrypt 2016) who point out the necessity for a public seed to prevent an adversarial sampler from gaining non-negligible advantage. The authors further update the security model of Dodis et al. (CCS 2013) to accommodate a public random permutation, modelled in the ideal cipher model, and how this affects the notions of security.
In this paper we introduce \reverie, an improved and practical, sponge-like pseudo-random number generator together with a formal security analysis in the PRNG with input security model of Dodis et al. with the modifications of the Ga\v{z}i and Tessaro paper.
We prove that \reverie is \emph{robust} when used with a public random permutation; robustness is the strongest notion of security in the chosen security model. Robustness is proved by establishing two weaker notions of security, preserving and recovering security, which together, can be shown to imply the robustness result. The proofs utilise the H-coefficient technique that has found recent popularity in this area; providing a very useful tool for proving the generator meets the necessary security notions.
Ronald Cramer, Léo Ducas, Benjamin Wesolowski
ePrint ReportIn this work, we generalize the previous result to general ideals. We show an efficient way of finding a close enough principal multiple of any ideal by exploiting the classical theorem that, in our setting, the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, we conclude that worst-case Ideal-SVP in this same set-up --- choice of ring, and approximation factor $\exp(\tilde O(\sqrt n))$ --- is also solvable in quantum polynomial time.
Although it is not yet clear whether the security of further cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured one.
Ben Lampert, Riad S. Wahby, Shane Leonard, Philip Levis
ePrint ReportNikolaj Volgushev, Malte Schwarzkopf, Andrei Lapets, Mayank Varia, Azer Bestavros
ePrint ReportJinsheng Zhang, Qiumao Ma, Wensheng Zhang, Daji Qiao
ePrint ReportAnindya Shankar Bhandari
ePrint ReportSilvio Biagioni, Daniel Masny, Daniele Venturi
ePrint ReportIn this paper we study the conditions under which the two ciphertexts in the Naor-Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie-Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50\%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks.
As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. The scheme supports key-dependent messages computed via any affine function of the secret key.
Benoît Libert, San Ling, Fabrice Mouhartem, Khoa Nguyen, Huaxiong Wang
ePrint ReportJian Guo, Meicheng Liu, Ling Song
ePrint ReportYuyu Wang, Zongyang Zhang, Takahiro Matsuda, Goichiro Hanaoka, Keisuke Tanaka
ePrint ReportLei Wang, Jian Guo, Guoyan Zhang, Jingyuan Zhao, Dawu Gu
ePrint ReportJoël Alwen, Jeremiah Blocki, Krzysztof Pietrzak
ePrint ReportTowards this goal memory-hard functions (MHF) have been suggested, leveraging the fact that -- unlike computation -- memory cost on custom hardware is not cheaper than on general architectures. MHFs come in two flavors, data-dependent and data independent MHFs, the former are potentially easier to construct, but they succumb to side-channel attacks.
Data independent MHFs can be specified by a directed acyclic graph (DAG) $G_n$ on $n$ nodes of constant indegree and a single sink, the function is then defined as the label of the sink, where a label of a node is computed as the hash of the labels of its parents and the function input. The quality of the memory-hard function is captured by two parameters on the pebbling complexity of the underlying graph:
- The parallel cumulative pebbling complexity $\Pi^{\parallel}_{cc}(G_n)$ must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory).
- The sequential space-time pebbling complexity $\Pi_{st}(G_n)$ should be as close as possible to $\Pi^{\parallel}_{cc}(G_n)$ (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage).
In this paper we construct a family of DAGs with best possible parameters, i.e., where $\Pi^{\parallel}_{cc}(G_n)=\Omega(n^2/\log(n))$ (which matches a known upper bound) and $\Pi_{st}(G_n)$ is within a constant factor of $\Pi^{\parallel}_{cc}(G_n)$.
Our analysis relies on a new connection between depth-robustness (DR) of DAGs -- a well studied combinatorial property -- and their pebbling complexities. We show that high DR is _sufficient_ for high $\Pi^{\parallel}_{cc}$. This contrasts the recent results of Alwen and Blocki (ePrint/2016/115) showing that high DR is _necessary_. Together these results fully characterizes DAGs with high $\Pi^{\parallel}_{cc}$ in terms of DR. Along the way we also give a new tool for reducing the indegree of a DAG without loosing too much in $\Pi^{\parallel}_{cc}$ which may be of interest beyond this work.
Previous to our work the graphs with best asymptotic complexity were due to Alwen and Serbinenko (STOC'15) achieve $\Pi^{\parallel}_{cc}(G_n)\in\Omega(n^2/\log^{10}(n))$. Most of the constructions used in practice have recently been broken in strong sense, the graph underlying Arogon2i, the winner of the recent password hashing competition, has $\Pi^{\parallel}_{cc}$ complexity $\tilde{O}(n^{1.75})$, for the recently proposed Balloon-Hashing the upper bound is $O(n^{1.67})$ and the same bound holds for Catena. We prove a $\tilde{\Omega}(n^{5/3})$ lower bound on $\Pi^{\parallel}_{cc}$ for Argon2i, and a $\tilde{\Omega}(n^{1.5})$ lower bound for Catena and Balloon hashing. The lower bound for Argon2i leverages our connection between $\Pi^{\parallel}_{cc}$ and depth-robustness. To prove the lower bounds for Catena and Balloon hashing we identify a graph property dubbed ``dispersity", and show how it also lower bounds $\Pi^{\parallel}_{cc}$. We also present an improved recursive version of the pebbling attack of Alwen and Blocki (ePrint/2016/115) and show that it implies upper bounds of $O\left(n^{1.71} \right)$ and $O(n^{1.62})$ for Argon2i and Catena respectively.
University of South Florida
Job PostingPotential research topics include:
1) Algorithms for ideal lattices.
2) Post quantum cryptography.
3) Fully homomorphic encryption.
The deadline for applications for a January 2017 start date is October 1rst (US citizens and green card holders only).
The deadline for an August 2017 start date is February 1rst 2017 (no residency restrictions).
General instructions for applying to the maths graduate program of the USF can be found here: http://math.usf.edu/grad/apply/.
The conditions are:
a) 3 years of funding.
b) Stipend of $16,000 per year.
c) Teaching duties 5h/week.
d) Tuition waiver.
Please contact me if you are interested.
Closing date for applications: 1 October 2016
Contact: Jean-François Biasse (usf.phd.crypto (at) gmail.com)