International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2015-03-22
09:17 [Pub][ePrint] Research Perspectives and Challenges for Bitcoin and Cryptocurrencies, by Joseph Bonneau, Andrew Miler, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, Edward W. Felten

  Bitcoin has emerged as the most successful cryptographic currency in history. Within two years of its quiet launch in 2009, Bitcoin grew to comprise billions of dollars of economic value, even while the body of published research and security analysis justifying the system\'s design was negligible. In the ensuing years, a growing literature has identified hidden-but-important properties of the system, discovered attacks, proposed promising alternatives, and singled out difficult future challenges. This interest has been complemented by a large and vibrant community of open-source developers who steward the system, while proposing and deploying numerous modifications and extensions.

We provide the first systematic exposition of the second generation of cryptocurrencies, including Bitcoin and the many alternatives that have been implemented as alternate protocols or ``altcoins.\'\' Drawing from a scattered body of knowledge, we put forward three key components of Bitcoin\'s design that can be decoupled, enabling a more insightful analysis of Bitcoin\'s properties and its proposed modifications and extensions. We contextualize the literature into five central properties capturing blockchain stability. We map the design space for numerous proposed modification, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools. We focus on anonymity issues in Bitcoin and provide an evaluation framework for analyzing a variety of proposals for enhancing unlinkability. Finally we provide new insights on a what we term disintermediation protocols, which absolve the need for trusted intermediaries in an interesting set of applications. We identify three general disintermediation strategies and provide a detailed comparative cost analysis.



09:17 [Pub][ePrint] A look at the PGP ecosystem through the key server data, by Hanno Böck

  PGP-based encryption systems use a network of key servers to share public keys. These key server operate on an add only basis, thus the data gives us access to PGP public keys from over 20 years of PGP usage. Analyzing this data allows searching for cryptographic weaknesses in large scale.

I created a parser script that puts the raw cryptographic data of the PGP keys into a database. Doing this allows large scale searches for well-known vulnerabilities. DSA signatures with a duplicate $k$ value due to bad random numbers allow the calculation of the private key. Similarly analyzing RSA keys for shared prime factors allows factoring the modulus and thus also regenerating the private key.

A small number of breakable keys due to these weaknesses were found.



09:17 [Pub][ePrint] Eclipse Attacks on Bitcoin\'s Peer-to-Peer Network, by Ethan Heilman. Alison Kendler, Aviv Zohar, Sharon Goldberg

  We present eclipse attacks on bitcoin\'s peer-to-peer network. Our attack allows an adversary controlling a sufficient number of IP addresses to monopolize all connections to and from a victim bitcoin node. The attacker can then exploit the victim for attacks on bitcoin\'s mining and consensus system, including N-confirmation double spending, selfish mining, and adversarial forks in the blockchain. We take a detailed look at bitcoin\'s peer-to-peer network, and quantify the resources involved in our attack via probabilistic analysis, Monte Carlo simulations, measurements and experiments with live bitcoin nodes. Finally, we present countermeasures, inspired by botnet architectures, that are designed to raise the bar for eclipse attacks while preserving the openness and decentralization of bitcoin\'s current network architecture.





2015-03-20
20:19 [Job][New] Visiting assistant professor, Department of Mathematical Sciences, University of Cincinnati

  The Department of Mathematical Sciences at the University of Cincinnati is seeking applicants for several Visiting Assistant Professorships in mathematics or statistics. Appointments will begin on August 15th, 2015 and will initially be for one year, with the possibility of renewal for a second year. Teaching load will nominally be two (3-4 credit) undergraduate courses per semester. Candidates must have a PhD in mathematics or statistics by the start date. The Department of Mathematical Sciences is dedicated to excellence in both research and teaching. The department has a graduate program offering MS and PhD degrees in mathematics and statistics. The department is looking for candidates with high-quality teaching and research and a strong potential for collaboration in areas of expertise of current faculty including cryptography, in particular, post-quantum cryptography. If you are interested, please apply immediately and contact: dingji (at) ucmail.uc.edu.

20:18 [Job][New] Marie Sklodowska-Curie Research Fellows in Cryptography (Early Stage Researchers – 2 posts), University of Bristol

  ECRYPT-NET is a research network of 6 universities and 2 companies that intends to develop advanced cryptographic techniques for the Internet of Things and the Cloud and to create efficient and secure implementations of those techniques on a broad range of platforms. ECRYPT-NET is funded by a prestigious Marie Sk?odowska-Curie ITN (Integrated Training Network) grant. The network will educate a group of 15 PhD students with a set of interdisciplinary skills in the areas of mathematics, computer science and electrical engineering. The training will be provided in an international context,that includes Summer Schools, workshops, internships, and complementary skills. Participants are expected to spend at least 6 months abroad in a network partner or in one of the 7 associated companies. We are looking for highly motivated candidates with a strong academic track record, ideally with some background on cryptology and with proven research abilities.

We offer an exciting working environment in an international network with top scientists that is geared towards cutting-edge research. The financial conditions are very attractive. The project offers an opportunity to travel and interact with other PhD students and scientists all over Europe. Candidates may have resided in the host country for a most 1 year in the 3 years preceding the application. They can have at most 2 years of research experience at the doctoral level.

The Cryptography and Information Security Group at Bristol are offering two ESR positions:

1) Leakage Resilience From Lattices:

2) MPC using FHE and Oblivious Transfer:

Marie Curie ITN eligibility criteria apply to both of these positions.



09:17 [Pub][ePrint] Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices, by Vadim Lyubashevsky and Thomas Prest

  A procedure for sampling lattice vectors is at the heart of many lattice constructions, and the algorithm of Klein (SODA 2000) and Gentry, Peikert, Vaikuntanathan (STOC 2008) is currently the one that produces the shortest vectors. But due to the fact that its most time-efficient (quadratic-time) variant requires the storage of the Gram-Schmidt basis, the asymptotic space requirements of this algorithm are the same for general and ideal lattices. The main result of the current work is a series of algorithms that ultimately lead to a sampling procedure producing the same outputs as the Klein/GPV one, but requiring only linear-storage when working on lattices used in ideal-lattice cryptography. The reduced storage directly leads to a reduction in key-sizes by a factor of $\\Omega(d)$, and makes cryptographic constructions requiring lattice sampling much more suitable for practical applications.

At the core of our improvements is a new, faster algorithm for computing the Gram-Schmidt orthogonalization of a set of vectors that are related via a linear isometry. In particular, for a linear isometry r:R^d --> R^d which is computable in time $O(d)$ and a d-dimensional vector $b$, our algorithm for computing the orthogonalization of $(b,r(b),r^2(b),...,r^{d-1}(b))$ uses $O(d^2)$ floating point operations. This is in contrast to $O(d^3)$ such operations that are required by the standard Gram-Schmidt algorithm. This improvement is directly applicable to bases that appear in ideal-lattice cryptography because those bases exhibit such ``isometric structure\'\'. The above-mentioned algorithm improves on a previous one of Gama, Howgrave-Graham, Nguyen (EUROCRYPT 2006) which used different techniques to achieve only a constant-factor speed-up for similar lattice bases. Interestingly, our present ideas can be combined with those from Gama et al. to achieve an even an larger practical speed-up.

We next show how this new Gram-Schmidt algorithm can be applied towards lattice sampling in quadratic time using only linear space. The main idea is that rather than pre-computing and storing the Gram-Schmidt vectors, one can compute them ``on-the-fly\'\' while running the sampling algorithm. We also rigorously analyze the required arithmetic precision necessary for achieving negligible statistical distance between the outputs of our sampling algorithm and the desired Gaussian distribution. The results of our experiments involving NTRU lattices show that the practical performance improvements of our algorithms are as predicted in theory.



05:36 [Job][New] Ph.D. student, Rochester Institute of Technology

  We are looking for outstanding candidates for a Ph.D. position at Rochester Institute of Technology. The potential candidates need to have strong interest in cryptographic engineering, and one or more of the following sub-areas: ECC software/hardware implementations, side-channel attacks, and post-quantum cryptography.

Please send your application to Mehran Mozaffari Kermani (mmkeme (-at-) rit.edu) and Reza Azarderakhsh (rxaeec (-at-) rit.edu) via e-mail. Applications should contain a CV, a short letter of motivation, copies of transcripts and certificates, and (if possible) names of references.



2015-03-19
09:17 [Pub][ePrint] Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE, by Patrick Derbez and Léo Perrin

  NXP Semiconductors and its academic partners challenged the

cryptographic community with finding practical attacks on the block

cipher they designed, PRINCE. Instead of trying to attack as many

rounds as possible using attacks which are usually impractical

despite being faster than brute-force, the challenge invites

cryptographers to find practical attacks and encourages them to

actually implement them.

In this paper, we present new attacks on round-reduced PRINCE including the ones which won the challenge in the

6 and 8-round categories --- the highest for which winners were

identified. Our first attacks rely on a meet-in-the-middle approach and break up to 10 rounds of the cipher.

We also describe heuristic methods we used to find practical SAT-based and differential attacks.

Finally, we also present an analysis of the cycle structure of the

internal rounds of PRINCE leading both to a low complexity

distinguisher for 4-round PRINCE-core and an alternative

representation of the cipher valid in particular contexts and which

highlights, in this cases, a poor diffusion.



09:17 [Pub][ePrint] Differential Analysis and Meet-in-the-Middle Attack against Round-Reduced TWINE, by Alex Biryukov, Patrick Derbez and Léo Perrin

  TWINE is a recent lightweight block cipher based on a Feistel

structure. We first present two new attacks on TWINE-128

reduced to 25 rounds that have a slightly higher overall complexity than the 25-round attack presented by Wang and Wu at ACISP 2014, but a lower data complexity.

Then, we introduce alternative representations of both the round

function of this block cipher and of a sequence of 4 rounds. LBlock,

another lightweight block cipher, turns out to exhibit the same

behaviour. Then, we illustrate how this alternative representation

can shed new light on the security of TWINE by deriving high

probability iterated truncated differential trails covering 4 rounds

with probability $2^{-16}$.

The importance of these is shown by combining different

truncated differential trails to attack 23-rounds TWINE-128 and by

giving a tighter lower bound on the high probability of some

differentials by clustering differential characteristics following

one of these truncated trails. A comparison between these high

probability differentials and those recently found in a variant of

LBlock by Leurent highlights the importance of considering the whole

distribution of the coefficients in the difference distribution

table of a S-Box and not only their maximum value.



09:17 [Pub][ePrint] Espresso: A Stream Cipher for 5G Wireless Communication Systems, by Elena Dubrova and Martin Hell

  The demand for more efficient ciphers is a likely to sharpen with new generation of products and applications. Previous cipher designs typically focused on optimizing only one of the two parameters - hardware size or speed, for a given security level. In this paper, we present a methodology for designing a class of stream ciphers which takes into account both parameters simultaneously. We combine the advantage of the Galois configuration of NLFSRs, short propagation delay, with the advantage of the Fibonacci configuration of NLFSRs, which can be analyzed formally. According to our analysis, the presented stream cipher Espresso is the fastest among the ciphers below 1500 GE, including Grain-128 and Trivium.



09:17 [Pub][ePrint] Compactly Hiding Linear Spans: Tightly Secure Constant-Size Simulation-Sound QA-NIZK Proofs and Applications, by Benoit Libert and Thomas Peters and Marc Joye and Moti Yung

  Quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proofs is a powerful paradigm, suggested recently by Jutla and Roy (Asiacrypt\'13), which is motivated by the Groth-Sahai seminal techniques for efficient non-interactive zero-knowledge (NIZK) proofs. In this paradigm, the common reference string may depend on specific language parameters, a fact that allows much shorter proofs in important cases. It even makes certain standard model applications competitive with the Fiat-Shamir heuristic in the Random Oracle idealization (such QA-NIZK proofs were recently optimized to constant size by Jutla and Roy (Crypto\'14) and Libert et al. (Eurocrypt\'14) for the important case of proving that a vector of group elements belongs to a linear subspace). While, e.g., the QA-NIZK arguments of Libert et al. provide unbounded simulation-soundness and constant proof length, their simulation-soundness is only loosely related to the underlying assumption (with a gap proportional to the number of adversarial queries) and it is unknown how to alleviate this limitation without sacrificing efficiency. Here, we deal with the basic question of whether and to what extent we can simultaneously optimize the proof size and the tightness of security reductions, allowing for important applications with tight security (which are typically to date quite lengthy) to be of shorter size. In this paper, we resolve this question by describing a novel simulation-sound QA-NIZK argument showing that a vector $\\vec{v} \\in \\G^n$ belongs to a subspace of rank $t