International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) 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).

04:17 [Pub][ePrint] Statistical weakness in Spritz against VMPC-R: in search for the RC4 replacement, by Bartosz Zoltak

  We found a statistical weakness in the Spritz algorithm designed by Ronald L. Rivest and Jacob C. N. Schuldt. For N=8: Prob(output(x)=output(x+2)) = 1/N + 0.000498. The bias becomes statistically significant (for N=8) after observing about 2^21.9 outputs. Analogous bias occurs for N=16. We propose an algorithm (VMPC-R) which for N=8 produced 2^46.8 (31 million times more) outputs which remained undistinguishable from random in the same battery of tests. Supported by a series of additional statistical tests and security analyses we present VMPC-R as an algorithm we hope can be considered a worthwhile replacement for RC4.

04:17 [Pub][ePrint] Related-Key Differential Attack on Round Reduced RECTANGLE-80, by Jinyong Shan and Lei Hu and Ling Song and Siwei Sun and Xiaoshuang Ma

  RECTANGLE is a newly proposed lightweight block cipher which allows fast implementations for multiple platforms by using bit-slice techniques. It is an iterative 25-round SPN block cipher with a 64-bit block size and a 80-bit or 128-bit key size. Until now, the results on analyzing the cipher are not too much, which includes an attack on the 18-round reduced version proposed by the designers themselves. In this paper, we find all 15-round differential characteristics with 26--30 active S-boxes for given input, output and round subkey differences, which have a total probability $2^{-60.5}$. Based on these differential characteristics, we extend the corresponding distinguisher to 2 rounds backward and forward respectively, and propose an attack on the 19-round reduced RECTANGLE-80 with data complexity of $2^{62}$ plaintexts, time complexity of about $2^{67.42}$ encryptions and memory complexity of $2^{72}$. TThese data and time complexities are much lower than that of the designers for the 18-round reduced RECTANGLE-80.

02:29 [PhD][New] Hassan Jameel Asghar: Design and Analysis of Human Identification Protocols

  Name: Hassan Jameel Asghar
Topic: Design and Analysis of Human Identification Protocols
Category: cryptographic protocols

Description: Human identification protocols are authentication protocols that enable a human using an insecure terminal to authenticate to a remote server. The goal of such protocols is to ensure secure authentication in the presence of an adversary who can not only view the user’s inputs, and the internal computations and display of the terminal, but also eavesdrop on the communication link between the terminal and the server. An active\r\nadversary can in addition actively interfere with this communication link. However, protocols secure against active adversaries fall well short of usability. As a result, the focus of recent research has been on security against passive adversaries. Traditional authentication methods such as password-based authentication are not secure under this model, since the adversary can impersonate the user by learning the user’s password after observing a single authentication session.\r\n\r\nSince the introduction of the problem by Matsumoto and Imai in 1991, there have been sporadic attempts at constructing secure human identification protocols. However, to date there is no accepted solution, mainly because such protocols require mental computations from humans, and therefore the tradeoff between security and usability is huge. State-of-the-art protocols take between one to three minutes for authentication, but guarantee stronger security than traditional authentication methods. While this authentication time is not acceptable for most practical purposes, many interesting new mathematical problems and ideas have resulted in search for usable protocols.\r\n\r\nThis thesis aims to further the research in human identification protocols by focusing on the mathematical and analytical aspects of such protocols. We generalize some aspects of these protocols by analyzing their general structure. We give detailed security analysis of two protocols from literature, showing that without a thorough security analysis, these protocols are vulnerable to simple[...]

02:29 [PhD][New] Karine Heydemann

  Name: Karine Heydemann

02:29 [PhD][Update] Nicolas Moro: Security of assembly programs against fault attacks on embedded processors

  Name: Nicolas Moro
Topic: Security of assembly programs against fault attacks on embedded processors

Description: This thesis focuses on the security of embedded programs against fault injection attacks. Due to the spreadings of embedded systems in our common life, development of countermeasures is important. First, a fault model based on practical experiments with a pulsed electromagnetic fault injection technique has been built. The experimental results show that the injected faults were due to the corruption of the bus transfers between the Flash memory and the processor’s pipeline. Such faults enable to perform instruction replacements, instruction skips or to corrupt some data transfers from the Flash memory. Although replacing an instruction with another very specific one is very difficult to control, skipping an instruction seems much easier to perform in practice and has been observed very frequently. Furthermore many simple attacks can carried out with an instruction skip. A countermeasure that prevents such instruction skip attacks has been designed and formally verified with model-checking tool. The countermeasure replaces each instruction by a sequence of instructions. However, this countermeasure does not protect the data loads from the Flash memory. To do this, it can be combined with another assembly-level countermeasure that performs a fault detection. A first experimental test of these two countermeasures has been achieved, both on isolated instructions and complex codes from a FreeRTOS implementation. The proposed countermeasure appears to be a good complement for this detection countermeasure and allows to correct some of its flaws.[...]

16:17 [Pub][ePrint] Improved Differential Analysis of Block Cipher PRIDE, by Qianqian Yang and Lei Hu and Siwei Sun and Kexin Qiao and Ling Song and Jinyong Shan and Xiaoshuang Ma

  In CRYPTO 2014 Albrecht \\emph{et al.} brought in a 20-round iterative lightweight block

cipher PRIDE which is based on a good linear layer for achieving a

tradeoff between security and efficiency. A recent

analysis is presented by Zhao \\emph{et al.}. Inspired by their work, we use an

automatic search method to find out 56 iterative differential characteristics of PRIDE, containing 24

1-round iterative characteristics, based on three of them we construct a 15-round differential and perform a differential attack on the 19-round PRIDE, with data,

time and memory

complexity of $2^{62}$, $2^{63}$ and $2^{71}$ respectively.

16:17 [Pub][ePrint] The Chaining Lemma and its application, by Ivan Damgaard and Sebastian Faust and Pratyay Mukherjee and Daniele Venturi

  We present a new information theoretic result which we call the Chaining Lemma. It considers a so-called \"chain\" of random variables, defined by a source distribution X0 with high min-entropy and a number (say, t in total) of arbitrary functions (T1,....Tt) which are applied in succession to that source to generate the chain X0-->X1-->.....-->Xt such that Xi=Ti(X[i-1]). Intuitively, the Chaining Lemma guarantees that, if the chain is not too long, then either (i) the entire chain is \"highly random\", in that every variable has high min-entropy; or (ii) it is possible to find a point j ( 1

16:17 [Pub][ePrint] A Fast Phase-Based Enumeration Algorithm for SVP Challenge through y-Sparse Representations of Short Lattice Vectors, by Dan Ding, Guizhen Zhu, Yang Yu, Zhongxiang Zheng

  In this paper, we propose a new phase-based enumeration algorithm based on two interesting and useful observations for y-sparse representations of short lattice vectors in lattices from SVP challenge benchmarks. Experimental results show that the phase-based algorithm greatly outperforms other famous enumeration algorithms in running time and achieves higher dimensions, like the Kannan-Helfrich enumeration algorithm. Therefore, the phase-based algorithm is a practically excellent solver for the shortest vector problem (SVP).

16:17 [Pub][ePrint] Publicly Verifiable Non-Interactive Arguments for Delegating Computation, by Omer Paneth and Guy N. Rothblum

  We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier\'s running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings. All prior publicly verifiable non-interactive argument systems were based on non-falsifiable knowledge assumptions. Our new result builds on the beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who constructed privately verifiable 2-message arguments. While building on their techniques, our protocols avoid no-signaling PCPs, and we obtain a simplified and modular analysis.

As a second contribution, we also construct a publicly verifiable non-interactive argument for (logspace-uniform) computations of bounded depth. The verifier\'s complexity grows with the depth of the circuit. This second protocol is adaptively sound, and its security is based on a falsifiable assumption about the hardness of a search problem on graded encodings (a milder cryptographic assumption). This result builds on the interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using graded encodings to construct a non-interactive version of their protocol.

16:17 [Pub][ePrint] Outlier Privacy, by Edward Lui and Rafael Pass

  We introduce a generalization of differential privacy called \\emph{tailored differential privacy}, where an individual\'s privacy parameter is ``tailored\'\' for the individual based on the individual\'s data and the data set. In this paper, we focus on a natural instance of tailored differential privacy, which we call \\emph{outlier privacy}: an individual\'s privacy parameter is determined by how much of an ``\\emph{outlier}\'\' the individual is. We provide a new definition of an outlier and use it to introduce our notion of outlier privacy. Roughly speaking, \\emph{$\\eps(\\cdot)$-outlier privacy} requires that each individual in the data set is guaranteed ``$\\eps(k)$-differential privacy protection\'\', where $k$ is a number quantifying the ``outlierness\'\' of the individual. We demonstrate how to release accurate histograms that satisfy $\\eps(\\cdot)$-outlier privacy for various natural choices of $\\eps(\\cdot)$. Additionally, we show that $\\eps(\\cdot)$-outlier privacy with our weakest choice of $\\eps(\\cdot)$---which offers no explicit privacy protection for ``non-outliers\'\'---already implies a ``distributional\'\' notion of differential privacy w.r.t.~a large and natural class of distributions.

16:17 [Pub][ePrint] Public Verification of Private Effort, by Giulia Alberini and Tal Moran and Alon Rosen

  We introduce a new framework for polling responses from a large population. Our framework allows gathering information without violating the responders\' anonymity and at the same time enables public verification of the poll\'s result. In contrast to prior approaches to the problem, we do not require trusting the pollster for faithfully announcing the poll\'s results, nor do we rely on strong identity verification.

We propose an ``effort based\'\' polling protocol whose results can be publicly verified by constructing a ``responder certification graph\'\' whose nodes are labeled by responders\' replies to the poll, and whose edges cross-certify that adjacent nodes correspond to honest participants. Cross-certification is achieved using a newly introduced (privately verifiable) ``Private Proof of Effort\'\' (PPE). In effect, our protocol gives a general method for converting privately-verifiable proofs into a publicly-verifiable protocol. The soundness of the transformation relies on expansion properties of the certification graph.

Our results are applicable to a variety of settings in which crowd-sourced information gathering is required. This includes crypto-currencies, political polling, elections, recommendation systems, viewer voting in TV shows, and prediction markets.