International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

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

2014-12-10
04:17 [Pub][ePrint]

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]

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]

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

02:29 [PhD][New]

Name: Karine Heydemann

02:29 [PhD][Update]

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

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.[...]

2014-12-07
16:17 [Pub][ePrint]

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]

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]

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]

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]

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]

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.