International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service 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).

2012-05-10
00:17 [Pub][ePrint] The Linux Psedorandom Number Generator Revisited, by Patrick Lacharme and Andrea Röck and Vincent Strubel and Marion Videau

  The Linux pseudorandom number generator (PRNG) is a PRNG with entropy

inputs which is widely used in many security related applications and

protocols. This PRNG is written as an open source code which is

subject to regular changes. It was last analyzed in the work of

Gutterman et al. in 2006 [GPR06] but since then no new

analysis has been made available, while in the meantime several changes have been applied to the code,

among others, to counter the attacks presented

[GPR06]. Our work describes the Linux PRNG of kernel

versions 2.6.30.7 and upwards. We detail the PRNG architecture

in the Linux system and provide its first accurate mathematical

description and a precise analysis of the building blocks, including entropy estimation and extraction. Subsequently, we give a security analysis including the feasibility of cryptographic attacks and an empirical test of the entropy estimator..

Finally, we underline some important changes to the previous

versions and their consequences.



00:17 [Pub][ePrint] Fair Private Set Intersection with a Semi-trusted Arbiter, by Changyu Dong and Liqun Chen and Jan Camenisch and Giovanni Russello

  A private set intersection (PSI) protocol allows two parties to compute the intersection of their input sets privately. Most of the previous PSI protocols only output the result to one party and the other party gets nothing from running the protocols. However, a mutual PSI protocol in which both parties can get the output is highly desirable in many applications. A major obstacle in designing a mutual PSI protocol is how to ensure fairness. In this paper we present the first fair mutual PSI protocol which is efficient and secure. Fairness of the protocol is obtained in an optimistic fashion, i.e. by using an offline third party arbiter. In contrast to many optimistic protocols which require a fully trusted arbiter, in our protocol the arbiter is only required to be semi-trusted, in the sense that we consider it to be a potential threat to both parties\' privacy but believe it will follow the protocol and not collude with any of the two parties. The arbiter can resolve disputes blindly without knowing any private information belongs to the two parties. This feature is appealing for a PSI protocol in which privacy may be of ultimate importance.



00:17 [Pub][ePrint] Cryptanalysis of pairing-free certificateless authenticated key agreement protocol, by Zhian Zhu

  Recently, He et al. [D. He, J. Chen, J. Hu, A pairing-free certificateless authenticated key agreement protocol, International Journal of Communication Systems, 25(2), pp. 221-230, 2012] proposed a pairing-free certificateless authenticated key agreement protocol and demonstrated that their protocol is provable security in the random oracle model. However, in this paper, we show that t He et al. protocol is completely broken.



00:17 [Pub][ePrint] FastPRP: Fast Pseudo-Random Permutations for Small Domains, by Emil Stefanov and Elaine Shi

  We propose a novel small-domain pseudo-random permutation, also referred to as a small-domain cipher or small-domain (deterministic) encryption. We prove that our construction achieves \"strong security\", i.e., is indistinguishable from a random permutation even when an adversary has observed all possible input-output pairs. More importantly, our construction is 1,000 to 8,000 times faster in most realistic scenarios, in comparison with the best known construction (also achieving strong security). Our implementation leverages the extended instruction sets of modern processors, and we also introduce a smart caching strategy to freely tune the tradeoff between time and space.



00:17 [Pub][ePrint] How to Garble Arithmetic Circuits, by Benny Applebaum and Yuval Ishai and Eyal Kushilevitz

  Yao\'s garbled circuit construction transforms a boolean circuit $C:\\{0,1\\}^n\\to\\{0,1\\}^m$ into a ``garbled circuit\'\' $\\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications.

Motivated by these applications, we suggest an efficient arithmetic variant of Yao\'s original construction. Our construction transforms an arithmetic circuit $C : \\mathbb{Z}^n\\to\\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\\hat{C}$ along with $n$ affine functions $L_i : \\mathbb{Z}\\to \\mathbb{Z}^k$ such that $\\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors (LWE) problem.



00:17 [Pub][ePrint] The myth of generic DPA...and the magic of learning, by Carolyn Whitnall and Elisabeth Oswald and Fran\\c{c}ois-Xavier Standaert

  A prominent strand within the side-channel literature is the quest for generic strategies: methods by which data-dependent leakage measurements may be fruitfully analysed with minimal a priori insight into the processes occasioning that leakage. In this paper, we introduce a well-reasoned formal definition for `a generic strategy\', enabling us, for the first time, to clarify precise conditions (on the target function) under which (asymptotic) success is possible. The range of vulnerable targets is shown to be limited---noninjectivity and nonlinearity being minimal requirements---and so the `myth\' is somewhat dispelled. However, we then explore the particular opportunities presented by linear regression-based methods, which are able to operate generically, but can in fact be leveraged by non-specific intuition about the leakage through the application of a model building technique called stepwise regression. Thus a minor relaxation of the strict generic assumptions `magically\' produces asymptotically successful outcomes even against injective targets.



00:17 [Pub][ePrint] The Transformation from the Galois NLFSR to the Fibonacci Configuration, by Lin Zhiqiang

  The Galois configuration of Nonlinear Feedback Shift Registers

(NLFSRs) is attractive for stream ciphers for which high throughput

is very important. In this paper, we prove that any Galois NLFSR can be transformed into an equivalent NLFSR in the Fibonacci configuration, which is the conventional conguration of NLFSRs. The transformation is mentioned in the proof. The mapping between the initial states of the Galois NLFSR and its equivalent Fibonacci configuration is also derived. Moreover, some properties of Galois NLFSRs are presented.



00:17 [Pub][ePrint] Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols, by José Bacelar Almeida and Manuel Barbosa and Endre Bangerter and Gilles Barte and Stephan Krenn and Santiago Z

  Developers building cryptography into security-sensitive applications

face a daunting task. Not only must they understand the security

guarantees delivered by the constructions they choose,

they must also implement and combine them correctly and

efficiently.

Cryptographic compilers free developers from having to implement

cryptography on their own by turning high-level specifications

of security goals into efficient implementations. Yet, trusting such

tools is hard as they rely on complex mathematical

machinery and claim security properties that are subtle and difficult

to verify.

In this paper, we present ZKCrypt, an optimizing cryptographic compiler that achieves an unprecedented level of assurance without sacrificing

practicality for a comprehensive class of cryptographic protocols, known

as Zero Knowledge Proofs of Knowledge. The pipeline of ZKCrypt tightly

integrates purpose-built verified compilers and verifying compilers

producing formal proofs in the CertiCrypt framework. By combining the

guarantees delivered by each stage in the pipeline, ZKCrypt provides

assurance that the implementation it outputs securely

realizes the high-level proof goal given as input. We report on the

main characteristics of ZKCrypt, highlight new definitions and concepts

at its foundations, and illustrate its applicability through a

representative example of an anonymous credential system.



00:17 [Pub][ePrint] A Novel Strong Designated Verifier Signature Scheme without Random Oracles, by Maryam Rajabzadeh Asaar and Mahmoud Salmasizadeh

  In this study, a novel pairing based strong designated verifier signature

scheme based on non-interactive zero knowledge proofs is proposed. The security of

the proposal is presented by sequences of games without random oracles; furthermore,

this scheme has a security proof for the property of privacy of the signer\'s identity in

comparison with the scheme proposed by Zhang et al. in 2007. In addition, this proposal

compared to the scheme presented by Huang et al. in 2011 supports non-delegatability.

The non-delegatability of our proposal is achieved since we do not use the common secret

key shared between the signer and the designated verifier in our construction. Furthermore,

if a signer delegates her signing capability which is derived from her secret key on

a specific message to a third party, then, the third party cannot generate a valid designated

verifier signature due to the relaxed special soundness of the non-interactive zero

knowledge proof. To the best of our knowledge, this construction is the first attempt to

generate a designated verifier signature scheme with non-delegatability in the standard

model, while satisfying of non-delegatability property is loose.



00:17 [Pub][ePrint] Transposition of AES Key Schedule, by Jialin Huang, Xuejia Lai

  In this paper, we point out a new weakness of the AES key schedule by revisiting an old observation exploited by many known attacks. We also discover a major cause for this weakness is that the column-by-column word-wise property in the key schedule matches nicely with the MixColumns operation in the cipher\'s diffusion layer. Then we propose a new key schedule by minor modification to increase the security level for AES. First, it reduces the number of rounds that some attacks are effective, such as SQUARE attacks and meet-in-the-middle attacks; Second, it is interesting that our new key schedule also protects AES from the most devastating related-key differential type attacks, which work against AES-192 and AES-256 with the full number of rounds. Compared with the original key schedule, ours just does a transposition on the output matrix of the subkeys. Compared with other proposed modifications of AES key schedule, our modification adds no non-linear operations, no need to complicate the diffusion method, or complicate the iteration process of generating subkeys. Finally, our results suggest that the route of diffusion propagation should get more attention in the design of key schedules.



00:17 [Pub][ePrint] Dual Form Signatures: An Approach for Proving Security from Static Assumptions, by Michael Gerbush and Allison Lewko and Adam O\'Neill and Brent Waters

  In this paper, we introduce the abstraction of Dual Form Signatures as a useful framework for proving security (existential unforgeability) from static assumptions for schemes with special structure that are used as a basis of other cryptographic protocols and applications. We demonstrate the power of this framework by proving security under static assumptions for close variants of pre-existing schemes:

\\begin{itemize}

\\item the LRSW-based Camenisch-Lysyanskaya signature scheme

\\item the identity-based sequential aggregate signatures of Boldyreva, Gentry, O\'Neill, and Yum.

\\end{itemize}

The Camenisch-Lysyanskaya signature scheme was previously proven only under the interactive LRSW assumption, and our result can be viewed as a static replacement for the LRSW assumption. The scheme of Boldyreva, Gentry, O\'Neill, and Yum was also previously proven only under an interactive assumption that was shown to hold in the generic group model. The structure of the public key signature scheme underlying the BGOY aggregate signatures is quite distinctive, and our work presents the first security analysis of this kind of structure under static assumptions.

We view our work as enhancing our understanding of the security of these signatures, and also as an important step towards obtaining proofs under the weakest possible assumptions.

Finally, we believe our work also provides a new path for proving security of signatures with embedded structure. Examples of these include:

attribute-based signatures, quoteable signatures, and signing group elements.