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-07
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.

2014-12-05
15:21 [Job][New]

The Cryptography Group at ETH Zurich, led by Prof. Ueli Maurer, has an open position for a PhD student in the general field of Cryptography. Candidates with an excellent Master\'s degree in Mathematics, Computer Science, or a related field, and with good English skills (written and spoken), are invited to apply.

2014-12-02
15:24 [Job][New]

The Department of Electronic Systems at the School of Information and Communication Technology, Royal Institute of Technology (KTH), seeks qualified applicants for a postdoctoral position in secure and trustworthy hardware. The research will be focused on developing efficient cryptographic solutions for hardware applications as well as on providing assurance of the new security solutions.

The candidate must hold a PhD Degree in computer science or computer engineering and have top grades.

Send following documents to the contact person (in pdf) :

- Curriculum Vitae

- List of publications

- Poof of English proficiency

- PhD degree and transcripts (translation if the original is not in English)

- Research proposal (1 page) describing the research you would like to do

- Names and contact details of 2 referees

KTH offers highly competitive salaries and is an equal opportunity employer.

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

SIMON is a family of lightweight block ciphers designed by the U.S. National Security Agency (NSA) that has attracted much attention since its publication in 2013.

In this paper, we thoroughly investigate the properties of linear approximations of the bitwise AND operation with dependent input bits. By using a Mixed-integer Linear Programming based technique presented in Aasicrypt 2014 for automatic search for characteristics, we obtain improved linear characteristics for several versions of the SIMON family. Moreover, by employing a recently published method for automatic enumeration of differential and linear characteristics by Sun et. al., we present an improved linear hull analysis of some versions of the SIMON family, which are the best results for linear cryptanalysis of SIMON published so far.

Specifically, for SIMON$128$, where the number denotes the block length, a 34-round linear characteristic with correlation $2^{-61}$ is found, which is the longest linear characteristic that can be used in a key-recovery attack for SIMON$128$ published so far. Besides, several linear hulls superior to the best ones known previously are presented as follows: linear hulls for the 13-round SIMON$32$ with potential $2^{-30.19}$ versus previous $2^{-31.69}$, for the 15-round SIMON$48$ with potential $2^{-42.28}$ versus previous $2^{-44.11}$ and linear hulls for the 21-round SIMON$64$ with potential $2^{-61.10}$ versus previous $2^{-62.53}$.

10:17 [Pub][ePrint]

In this paper we consider permutations on n symbols as bijections

on Z/nZ. Treating permutations this way facilitates us with additional

structures such as group, ring defined in the set Z/nZ. We explore

some of the properties of permutations arising out of this treatment.

We propose two properties viz. affine equivalence and non-linearity for permutations on the lines similar to there description given in the case of functions. We also establish some results which are quite similar to those given for Boolean functions. We also define Mode Transform of a permutation and investigate its relationship with non-linearity.

We propose an efficient algorithm using Mode transform for computing non-linearity of a permutation and show that it is O(n^2), as

compared to O(n^3) of the direct approach. At the end we discuss

these properties in the context of cryptography.

10:17 [Pub][ePrint]

Shortly following Cheon, Han, Lee, Ryu and Stehle attack against the multilinear map of Coron, Lepoint and Tibouchi (CLT), two independent approaches to thwart this attack have been proposed on the cryptology ePrint archive, due to Garg, Gentry, Halevi and Zhandry on the one hand, and Boneh, Wu and Zimmerman on the other. In this short note, we show that both countermeasures can be defeated in polynomial time using extensions of the Cheon et al. attack.

10:17 [Pub][ePrint]

Cloud computing sparked interest in Verifiable Computation protocols, which allow a weak client to securely outsource computations to remote parties. Recent work has dramatically reduced the client\'s cost to verify the correctness of results, but the overhead to produce proofs largely remains impractical.

Geppetto introduces complementary techniques for reducing prover overhead and increasing prover flexibility. With Multi-QAPs, Geppetto reduces the cost of sharing state between computations (e.g., for MapReduce) or within a single computation by up to two orders of magnitude. Via a careful instantiation of cryptographic primitives, Geppetto also brings down the cost of verifying outsourced cryptographic computations (e.g., verifiably computing on signed data); together with Geppetto\'s notion of bounded proof bootstrapping, Geppetto improves on prior bootstrapped systems by five orders of magnitude, albeit at some cost in universality. Geppetto also supports qualitatively new properties like verifying the correct execution of proprietary (i.e., secret) algorithms. Finally, Geppetto\'s use of energy-saving circuits brings the prover\'s costs more in line with the program\'s actual (rather than worst-case) execution time.

Geppetto is implemented in a full-fledged, scalable compiler that consumes LLVM code generated from a variety of apps, as well as a large cryptographic library.