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

15:34 [PhD][New] Jie Wang: Polynomial Time Creativity and its Applications (P-Creativity)

  Name: Jie Wang
Topic: Polynomial Time Creativity and its Applications (P-Creativity)
Category: (no category)

13:17 [Pub][ePrint] Efficient Non-Interactive Zero Knowledge Arguments for Set Operations, by Prastudy Fauzi and Helger Lipmaa and Bingsheng Zhang

  We propose a non-interactive zero knowledge \\emph{pairwise multiset sum equality test (PMSET)} argument in the common reference string (CRS) model that allows a prover to show that the given committed multisets $\\AAA_j$ for $j \\in \\set{1, 2, 3, 4}$ satisfy $\\AAA_1 \\uplus \\AAA_2 = \\AAA_3 \\uplus \\AAA_4$, i.e., every element is contained in $\\AAA_1$ and $\\AAA_2$ exactly as many times as in $\\AAA_3$ and $\\AAA_4$.

As a corollary to the $\\PUTME$ argument, we present arguments that enable to efficiently verify the correctness of various (multi)set operations, for example, that one committed set is the intersection or union of two other committed sets.

The new arguments have constant communication and verification complexity (in group elements and group operations, respectively), whereas the CRS length and the prover\'s computational complexity are both proportional to the cardinality of the (multi)sets.

We show that one can shorten the CRS length at the cost of a small increase of the communication and the verifier\'s computation.

13:17 [Pub][ePrint] One Weird Trick to Stop Selfish Miners: Fresh Bitcoins, A Solution for the Honest Miner., by Ethan Heilman

  Abstract--A recent result in Bitcoin is the selfish mining strategy in which a selfish cartel withholds blocks they mine to gain an advantage. This strategy is both incentive-compatible and harmful to Bitcoin. In this paper we introduce a new defense against selfish mining that improves on the previous best result, we raise the threshold of mining power necessary to profitably selfishly mine from 25% to 32% under all propagation advantages. While the security of our system uses unforgeable timestamps, it is robust to their compromise. Additionally, we discuss the difficulty a mining conspiracy would face attempting to keep the compromise of our scheme secret and we analyze incentives for getting miners to adopt these changes.

13:17 [Pub][ePrint] A Theoretical Study of Kolmogorov-Smirnov Distinguishers: Side-Channel Analysis vs. Differential Cryptanalysis, by Annelie Heuser and Sylvain Guilley and Olivier Rioul

  In this paper, we carry out a detailed mathematical study of two theoretical distinguishers based on the Kolmogorov-Smirnov (KS) distance. This includes a proof of soundness and the derivation of closed- form expressions, which can be split into two factors: one depending only on the noise and the other on the confusion coefficient of Fei, Luo and Ding. This allows one to have a deeper understanding of the relative influences of the signal-to-noise ratio and the confusion coefficient on the distinguisher\'s performance. Moreover, one is able to directly compare distinguishers based on their closed-form expressions instead of using evaluation metric that might obscure the actual performance and favor one distinguisher over the other. Furthermore, we formalize the link between the confusion coefficient and differential cryptanalysis, which shows that the stronger an S-box is resistant to differential attacks the weaker it is against side-channel attacks, and vice versa.

13:17 [Pub][ePrint] Characterization of EME with Linear Mixing, by Mridul Nandi and Nilanjan Datta

  Encrypt-Mix-Encrypt is a type of SPRP based construction, where a masked plaintext is encrypted in ECB mode of, then a non-linear mixing is performed and then again an encryption is performed in ECB mode which is masked to produce the ciphertext. Using the property of the binary field, the authors proved that the construction is not SPRP secure if the mixing used is linear. In this paper, we observe that relaxing the mixing operation to some specific efficient linear mixing provides the PRP property of the construction. Moreover choosing a linear mixing that gives the online property is not a difficult task. We can use this fact to construct an efficient Online PRP using Encrypt-Mix-Encrypt type of construction with the mix operation being a linear online mixing, making the construction efficient and online. We also show that the construction with linear mixing doesn\'t provide SPRP security even if we perform all the operations in a prime field instead of binary field. Thus, we fully characterize EME with linear mixing.

13:17 [Pub][ePrint] A Certificate-Based Proxy Signature with Message Recovery without Bilinear Pairing, by Ali Mahmoodi, Javad Mohajeri, Mahmoud Salmasizadeh

  In this paper, we propose the first provable secure certificate-based proxy signature with message recovery without bilinear pairing. The notion of certificate-based cryptography was initially introduced by Gentry in 2003, in order to simplify certificate management in traditional public key cryptography(PKC)and to solve the key escrow problem in identity-based cryptosystems. To date, a number of certificate-based proxy signature(CBPS)schemes from bilinear pairing have been proposed. Nonetheless, the total computation cost of a pairing is higher than that of scalar multiplication(e.g., over elliptic curve group). Consequently, schemes without pairings would be

more appealing in terms of efficiency. According to the available research in this regard, our scheme is the first provable secure CBPS scheme with message recovery which is based on the elliptic curve discrete logarithm problem. We prove the security of the presented scheme against existential forgery under adaptive chosen message and ID attacks in the random oracle model. Moreover, the paper will also show how it would be possible to convert this scheme to the CBPS scheme without message recovery. This scheme has more applications in situations with limited bandwidth and power-constrained devices.

17:27 [PhD][Update] Yossef Oren: Secure Hardware - Physical Attacks and Countermeasures

  Name: Yossef Oren
Topic: Secure Hardware - Physical Attacks and Countermeasures

Description: Any cryptographic functionality, such as encryption or authentication, must be implemented in the real world before it can be put to practical use. This implementation typically takes the form of either a software implementation for a general-purpose device such as a personal computer, or as a dedicated secure hardware device, whose main purpose is to embody the cryptographic functionality. Examples of such secure hardware devices include smart cards, car alarm key fobs and computerized ballots. To evaluate the security of a cryptographic system, researchers look for flaws which allow an attacker to break the security assumptions of the system (for example, allowing an unauthorized party to view or modify a message intended for someone else). Physical attacks (also called implementation attacks) compromise the system by taking advantage of the physical aspects of the algorithm's implementation. Some physical attacks (such as, for example, power analysis) recover the secret key used by the secure device by analyzing physical effects produced during its use; Others (such as, for example, relay attacks) disable or otherwise limit its secure behaviour by exploiting design or implementation flaws or by changing the underlying assumptions made by the designers of the system.
This research focuses on physical attacks on secure hardware devices and on countermeasures which protect against these attacks. My goals were to investigate vulnerabilities in current secure hardware implementations and to evaluate the effectiveness of current and proposed countermeasures against these vulnerabilities. The two main tracks of my research are side-channel analysis (and explicitly power analysis) and secure RFID.
In the side-channel analysis track, I investigated ways of reducing the data requirements of power analysis attacks. We showed how to mount key recovery attacks on a secure device using an extremely low amount of measurement data. The main novelty of our attack w[...]

13:17 [Pub][ePrint] The analysis of the Keccak with the new method called parity, by Ghanei yakhdan.mostafa, Noruzi, zynolabedin

  The Keccak hash function is a chosen of the SHA-3 competition. This function has the appropriate structural and so far it has been resistant against collision attacks. In the last few years after efforts cryptonalysis, first, the collision in the second round and near collision in the third rounds, was found. and after adi Shamir and Et al succeeded find collision in fourth round and near collision in 5 round for keccak 224,256. In this paper we propose a method that it can used, for any desired text and finds, near collision, in the second round, regardless of any probability. Our attack technique using the find the text that have the same parity such original text in theta function. It is practical for all keccak varies and it finds near collision for second round in few minute. We have named this method \" Parity Analyse\".

10:17 [Pub][ePrint] MaxMinMax problem and sparse equations over finite fields, by Igor Semaev

  Asymptotical complexity of sparse equation systems over finite field $F_q$ is studied.

Let the variable sets belong to a fixed family $\\mathcal{X}=\\{X_1,\\ldots,X_m\\}$ while

the polynomials $f_i(X_i)$ are taken independently and uniformly at random from the set of all polynomials

of degree $\\leq q-1$ in each of the

variables in $X_i$. In particular, for $|X_i|\\le3$, $m=n$, we prove

the average complexity of finding all solutions to $f_i(X_i)=0, i=1,\\ldots,m$ by Gluing algorithm ( Semaev, Des. Codes Cryptogr., vol. 49 (2008), pp.47--60) is at most $

q^{\\frac{n}{5.7883}+O(\\log n)}$ for arbitrary $\\mathcal{X}$ and $q$. The proof results from a detailed analysis of 3-MaxMinMax problem, a novel problem for hyper-graphs.

10:17 [Pub][ePrint] Pseudorandom Generator Based on Hard Lattice Problem, by Kuan Cheng

  This paper studies how to construct a pseudorandom generator using hard lattice problems.

We use a variation of the classical hard problem \\emph{Inhomogeneous Small Integer Solution} ISIS of lattice, say \\emph{Inhomogeneous Subset Sum Solution} ISSS. ISSS itself is a hash function. Proving the preimage sizes ISSS hash function images are almost the same, we construct a pseudorandom generator using the method in \\cite{GKL93}. Also, we construct a pseudoentropy generator using the method in \\cite{HILL99}. Most theoretical PRG constructions are not feasible in fact as they require rather long random bits as seeds. Our PRG construction only requires seed length to be $O(n^{2}\\log_{2} n)$ which is feasible practically.

10:17 [Pub][ePrint] $GF(2^n)$ Bit-Parallel Squarer Using Generalized Polynomial Basis For a New Class of Irreducible Pentanomials, by Xi Xiong and Haining Fan

  We present explicit formulae and complexities of bit-parallel $GF(2^{n})$ squarers for a new class of irreducible pentanomials

$x^{n}+x^{n-1}+x^{k}+x+1$, where $n$ is odd and $1