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

00:17 [Pub][ePrint] Enhanced certificate transparency (how Johnny could encrypt), by Mark D. Ryan

  The ``certificate authority\'\' model for authenticating public keys of websites has been attacked in recent years, and several proposals have been made to reinforce it. We develop and extend ``certificate transparency\'\', a proposal in this direction, so that it efficiently handles certificate revocation. We show how this extension can be used to build a secure end-to-end email or messaging system using PKI with no requirement to trust certificate authorities, or to rely on complex peer-to-peer key-signing arrangements such as PGP. We believe this finally makes end-to-end encrypted email as usable as encrypted web browsing is today, addressing the concerns of a classic paper explaining the difficulties users face in encrypting emails (``Why Johnny can\'t encrypt\'\', 1999). Underlying these ideas is a new attacker model appropriate for cloud computing, which we call ``malicious-but-cautious\'\'.

00:17 [Pub][ePrint] Solving the Elliptic Curve Discrete Logarithm Problem Using Semaev Polynomials, Weil Descent and Gröbner Basis Methods -- an Experimental Study, by Michael Shantz and Edlyn Teske

  At ASIACRYPT 2012, Petit and Quisquater suggested that there may be a subexponential-time index-calculus type algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP) in characteristic two fields. This algorithm uses Semaev polynomials and Weil Descent to create a system of polynomial equations that subsequently is to be solved with Gröbner basis methods. Its analysis is based on heuristic assumptions on the performance of Gröbner basis methods in this particular setting. While the subexponential behaviour would manifest itself only far beyond the cryptographically interesting range, this result, if correct, would still be extremely remarkable. We examined some aspects of the work by Petit and Quisquater experimentally.

13:27 [Event][New] DigitalSec: The International Conference on Digital Security and Forensics

  Submission: 24 May 2014
Notification: 3 June 2014
From June 24 to June 26
Location: Ostrava, Czech Republic
More Information:

09:17 [Pub][ePrint] SPHF-Friendly Non-Interactive Commitments, by Michel Abdalla and Fabrice Benhamouda and Olivier Blazy and Céline Chevalier and David Pointcheval

  In 2009, Abdalla et al. proposed a reasonably practical password-authenticated key exchange (PAKE) secure against adaptive adversaries in the universal composability (UC) framework. It exploited the Canetti-Fischlin methodology for commitments and the Cramer-Shoup smooth projective hash functions (SPHFs), following the Gennaro-Lindell approach for PAKE. In this paper, we revisit the notion of non-interactive commitments, with a new formalism that implies UC security. In addition, we provide a quite efficient instantiation. We then extend our formalism to SPHF-friendly commitments. We thereafter show that it allows a blackbox application to one-round PAKE and oblivious transfer (OT), still secure in the UC framework against adaptive adversaries, assuming reliable erasures and a single global common reference string, even for multiple sessions. Our instantiations are more efficient than the Abdalla et al. PAKE in Crypto 2009 and the recent OT protocol proposed by Choi~et al. in PKC 2013. Furthermore, the new PAKE instantiation is the first one-round scheme achieving UC security against adaptive adversaries.

03:17 [Pub][ePrint] Random Projections, Graph Sparsification, and Differential Privacy, by Jalaj Upadhyay

  This paper initiates the study of preserving {\\em differential privacy} ({\\sf DP}) when the data-set is sparse. We study the problem of constructing efficient sanitizer that preserves {\\sf DP} and guarantees high utility for answering cut-queries on graphs. The main motivation for studying sparse graphs arises from the empirical evidences that social networking sites are sparse graphs. We also motivate and advocate the necessity to include the efficiency of sanitizers, in addition to the utility guarantee, if one wishes to have a practical deployment of privacy preserving sanitizers.

We show that the technique of Blocki et al. (FOCS2012) ({\\sf BBDS}) can be adapted to preserve {\\sf DP} for answering cut-queries on sparse graphs, with an asymptotically efficient sanitizer than~{\\sf BBDS}. We use this as the base technique to construct an efficient sanitizer for arbitrary graphs. In particular, we use a preconditioning step that preserves the spectral properties (and therefore, size of any cut is preserved), and then apply our basic sanitizer. We first prove that our sanitizer preserves {\\sf DP} for graphs with high conductance. We then carefully compose our basic technique with the modified sanitizer to prove the result for arbitrary graphs. In certain sense, our approach is complementary to the Randomized sanitization for answering cut queries (Gupta, Roth, and Ullman, TCC 2012): we use graph sparsification, while Randomized sanitization uses graph densification.

Our sanitizers almost achieves the best of both the worlds with the same privacy guarantee, i.e., it is almost as efficient as the most efficient sanitizer and it has utility guarantee almost as strong as the utility guarantee of the best sanitization algorithm.

We also make some progress in answering few open problems by {\\sf BBDS}. We make a combinatorial observation that allows us to argue that the sanitized graph can also answer $(S,T)$-cut queries with same asymptotic efficiency, utility, and {\\sf DP} guarantee as our sanitization algorithm for $S, \\bar{S}$-cuts. Moreover, we achieve a better utility guarantee than Gupta, Roth, and Ullman (TCC 2012). We give further optimization by showing that fast Johnson-Lindenstrauss transform of Ailon and Chazelle~\\cite{AC09} also preserves {\\sf DP}.

03:17 [Pub][ePrint] PriWhisper: Enabling Keyless Secure Acoustic Communication for Smartphones, by Bingsheng Zhang, Qin Zhan, Junfei Wang, Kui Ren, Cong Wang, Di Ma

  Short-range wireless communication technologies have been used in many security-sensitive smartphone applications and services such as contactless micro payment and device pairing. Typically, the data confidentiality of the existing short-range communication systems relies on so-called \"key-exchange then encryption\" mechanism. Namely, both parties need to spend extra communication to establish a common key before transmitting their actual messages, which is inefficient, especially for short communication sessions. In this work, we present PriWhisper -- a keyless secure acoustic short-range communication system for smartphones. It is designed to provide a purely software-based solution to secure smartphone short-range communication without the key agreement phase. PriWhisper adopts the emerging friendly jamming technique from radio communication for data confidentiality. The system prototype is implemented and evaluated on several Android smartphone platforms for efficiency and usability. We theoretically and experimentally analyze the security of our proposed acoustic communication system against various passive and active adversaries. In particular, we also study the (in)separability of the data signal and jamming signal against Blind Signal Segmentation (BSS) attacks such as Independent Component Analysis (ICA). The result shows that PriWhisper provides sufficient security guarantees for commercial smartphone applications and yet strong compatibilities with most legacy smartphone platforms.

03:17 [Pub][ePrint] The Special Number Field Sieve in $\\F _{p^{n}}$, Application to Pairing-Friendly Constructions, by Antoine Joux and Cécile Pierrot

  In this paper, we study the

discrete logarithm problem in finite fields related to pairing-based

curves. We start with a precise analysis of the

state-of-the-art algorithms for computing discrete logarithms that

are suitable for finite fields related to pairing-friendly

constructions. To improve upon these algorithms, we extend the

Special Number Field Sieve to compute discrete logarithms in

$\\F_{p^{n}}$, where $p$ has an adequate sparse representation. Our

improved algorithm works for the whole range of applicability of the

Number Field Sieve.

03:17 [Pub][ePrint] polynomial selection for the number field sieve in geometric view, by Min yang, Qingshu Meng, Zhangyi Wang, Lina Wang, Huanguo Zhang

  Polynomial selection is the first important step in number field sieve. A good polynomial not only can produce more relations in the sieving step, but also can reduce the matrix size. In this paper, we propose to use geometric view in the polynomial selection. In geometric view, the coefficients\' interaction on size and the number of real roots are simultaneously considered in polynomial selection. We get two simple criteria. The first is that the leading coefficient should not be too large or some good polynomials will be omitted. The second is that the coefficient of degree $d-2$ should be negative and it is better if the coefficients of degree $d-1$ and $d-3$ have opposite sign. Using these new criteria, the computation can be reduced while we can get good polynomials. Many experiments on large integers show the effectiveness of our conclusion.

03:17 [Pub][ePrint] Cryptanalysis of GOST R Hash Function, by Zongyue Wang, Hongbo Yu, Xiaoyun Wang

  GOST R is the hash function standard of Russia. This paper presents some cryptanalytic results on GOST R. Using the rebound attack technique, we achieve collision attacks on the reduced round compression function. Result on up to 9.5 rounds is proposed, the time complexity is 2^{176} and the memory requirement is 2^{128} bytes. Based on the 9.5-round collision result, a limited birthday distinguisher is presented. More

over, a method to construct k collisions on 512-bit version of GOST R is given which show the weakness of the structure used in GOST R. To the best of our knowledge, these are the first results on GOST R.

03:17 [Pub][ePrint] On Algebraic Immunity of $\\Tr(x^{-1})$ over $\\mathbb{F}_{2^n}, by Xiutao Feng

  The trace inverse function $\\Tr(x^{-1})$ over the finite field $\\mathbb{F}_{2^n}$ is a class of very important Boolean functions in stream ciphers, which possesses many good properties,

including high algebraic degree, high nonlinearity, ideal autocorrelation, etc. In this work we discuss properties of $\\Tr(x^{-1})$ in resistance to (fast) algebraic attacks.

As a result, we prove that the algebraic immunity of $\\Tr(x^{-1})$ arrives the upper bound

given by Y. Nawaz et al when $n\\ge4$, that is, $\\AI(\\Tr(x^{-1}))=\\ceil{2\\sqrt{n}}-2$, which shows that D.K. Dalai\' conjecture on the algebraic immunity

of $\\Tr(x^{-1})$ is correct for almost all positive integers $n$. What is more, we further demonstrate some weak properties of $\\Tr(x^{-1})$ in resistance to fast algebraic attacks.

03:17 [Pub][ePrint] Generic related-key and induced chosen IV attacks using the method of key differentiation, by Enes Pasalic and Yongzhuang Wei

  Related-key and chosen IV attacks are well known cryptanalytic tools in cryptanalysis of stream ciphers. Though the related-key model is considered to be much more unrealistic scenario than the chosen IV model we show that under certain circumstances the attack assumptions may become equivalent. We show that the key differentiation method induces a generic attack in a related-key model whose time complexity in the on-line phase is less than the exhaustive key search. The case of formal equivalency between the two scenarios arises when so-called {\\em differentiable polynomials} with respect to some subset of key variables are a part of the state bit expressions (from which the output keystream bits are built). Then the differentiation over a key cube has the same effect as the differentiation over the corresponding IV cube, so that a generic nature of a related-key model is transferred into a more practical chosen IV model. The existence of such polynomials is confirmed for the reduced round stream cipher TRIVIUM up to some 710 rounds and an algorithm for their detection is proposed.

The key differentiation method induces a time/related-key trade-off (TRKTO) attack which (assuming the existence of differentiable polynomials) can be run in a chosen IV model. The resulting trade-off curve of our TMDTO attack is given by $T^2M^2D^2=(KV)^2$ ($V$ denoting the IV space), which is a significant improvement over the currently best known trade-off $TM^2D^2=(KV)^2$ \\cite{IVDunkel08}.