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

13:17 [Pub][ePrint] On formal and automatic security verification of WSN transport protocols, by Ta Vinh Thong and Amit Dvir

  In this paper, we address the problem of formal and automated security verification of WSN transport

protocols that may perform cryptographic operations. The verification of this class of protocols is difficult

because they typically consist of complex behavioral characteristics, such as real-time, probabilistic, and

cryptographic operations. To solve this problem, we propose a

probabilistic timed calculus for cryptographic protocols, and demonstrate how to use this formal language

for proving security or vulnerability of protocols. The main advantage of the proposed language is that it

supports an expressive syntax and semantics, including bisimilarities that supports real-time, probabilistic,

and cryptographic issues at the same time. Hence, it can be used to verify the systems that involve these three

property in a more convenient way. In addition, we propose an automatic verification method, based on the

well-known PAT process analysis toolkit, for this class of protocols.

For demonstration purposes, we apply the proposed manual and automatic proof methods for verifying the security of

DTSN and SDTP, which are two of the recently proposed WSN tranport protocols.

13:17 [Pub][ePrint] Complete and Unified Group Laws are not Enough for Elliptic Curve Cryptography, by Graham Enos

  We analyze four recently proposed normal forms for elliptic curves. Though these forms are mathematically appealing and exhibit some cryptographically desirable properties, they nonetheless fall short of cryptographic viability, especially when compared to various types of Edwards Curves. In this paper, we present these forms and demonstrate why they fail to measure up to the standards set by Edwards Curves.

13:17 [Pub][ePrint] Revocable Identity-Based Encryption Revisited: Security Model and Construction, by Jae Hong Seo and Keita Emura

  In ACM CCS 2008, Boldyreva et al. proposed an elegant way of achieving an Identity-based Encryption (IBE) with {\\em efficient} revocation, which we call revocable IBE (RIBE). One of the significant benefit of their construction is scalability, where the overhead of the trusted authority is logarithmically increased in the number of users, whereas that in the Boneh-Franklin naive revocation way is linearly increased. All subsequent RIBE schemes follow the Boldyreva et al. security model and syntax. In this paper, we first revisit the Boldyreva et al. security model,

and aim at capturing the exact notion for the security of the naive but non-scalable Boneh-Franklin RIBE scheme. To this end, we consider a realistic threat, which we call {\\em decryption key exposure}. We also show that all prior RIBE constructions except for the Boneh-Franklin one are vulnerable to decryption key exposure. As the second contribution, we revisit approaches to achieve (efficient and adaptively secure) scalable RIBE schemes, and propose a simple RIBE scheme, which is the first scalable RIBE scheme with decryption key exposure resistance, and is more efficient than previous (adaptively secure) scalable RIBE schemes.

In particular, our construction has the shortest ciphertext size and the fastest decryption algorithm even compared with all scalable RIBE schemes without decryption key exposure resistance.

13:17 [Pub][ePrint] Provable Security of S-BGP and other Path Vector Protocols: Model, Analysis and Extensions, by Alexandra Boldyreva and Robert Lychev

  This paper provides the provable-security treatment of path vector routing protocols. We first design a security definition for routing path vector protocols by studying, generalizing, and formalizing numerous known threats. Our model incorporates three major security goals. It is quite strong, yet simple to use. We prove by reduction that S-BGP satisfies two out of the security model\'s three goals, assuming the underlying signature scheme is secure. Under the same assumption, we next show how the protocol can be modified to meet all three security goals simultaneously. We also analyze SoBGP and show that it fails to meet two security goals. Finally, we study security of partial PKI deployment of path vector protocols when not all nodes have public keys. We investigate the possibilities of relaxing the PKI requirement and relying on non-cryptographic physical security of networks that use the protocol in order to achieve possibly weaker, but still well-defined, notions of security. We also present the necessary and sufficient conditions to achieve full security in the partial PKI deployment scenario. We believe our conclusions will prove useful for protocol developers, standards bodies and government agencies.

13:17 [Pub][ePrint] Efficient Delegation of Key Generation and Revocation Functionalities in Identity-Based Encryption, by Jae Hong Seo and Keita Emura

  In the public key cryptosystems, revocation functionality is required when a secret key is corrupted by hacking or the period of a contract expires. In the public key infrastructure setting, numerous solutions have been proposed, and in the Identity Based Encryption (IBE) setting, a recent series of papers proposed revocable IBE schemes. Delegation of key generation is also an important functionality in cryptography from a practical standpoint since it allows reduction of excessive workload for a single key generation authority. Although fficient solutions for either revocation or delegation of key generation in IBE systems have been proposed, an important open problem is efficiently delegating both the key generation and revocation functionalities in IBE systems. Libert and Vergnaud, for instance, left this as an open problem in their CT-RSA 2009 paper. In this paper, we propose the first solution for this problem. We prove the selective-ID security of our proposal under the Decisional Bilinear Diffie-Hellman assumption in the standard model.

13:17 [Pub][ePrint] On the Security of Plain and Randomized Cascades, by Peter Gazi

  The question of security of various efficient key-length

extending constructions for block ciphers in the ideal

cipher model has so far received considerable attention. The

security of triple encryption was investigated in

[Luc98,BR06], longer cascades were considered in [GM09] and

a construction with comparable security as triple encryption

requiring only 2 block cipher calls, denoted 2-XOR-cascade,

was proposed and analyzed in [GT12].

In this paper, we put the above results into perspective by

completing the picture of the investigated landscape in

various ways. We give the following attacks and security

lower bounds for constructions using a block cipher with key

length $k$ and block length $n$:

- For the plain cascade of odd (resp. even) length $l$ we

present a generic attack requiring roughly

$2^{k+\\frac{l-1}{l+1}n}$ (resp. $2^{k+\\frac{l-2}{l}n}$)

queries. This is a generalization of both the well-known

meet-in-the-middle attack on double encryption and the

attack on triple cascade given in [Luc98].

- For the general case of XOR-cascade of odd (resp. even)

length $l$ we prove security up to

$2^{k+\\frac{l-1}{l+1}n}$ (resp. $2^{k+\\frac{l-2}{l}n}$)

queries and also an improved bound $2^{k+\\frac{l-1}{l}n}$

for the special case $l\\in\\{3,4\\}$. This is achieved by

relating the problem to existing results in an independent

line of work on the security of key-alternating ciphers in

the random permutation model.

- Finally, for a natural class of sequential constructions

where block cipher encryptions are interleaved with

key-dependent permutations, we show a generic attack

requiring roughly $2^{k+\\frac{l-1}{l}n}$ queries. Since

XOR-cascades are sequential, this proves tightness of our

above result for XOR-cascades of length $l\\in\\{3,4\\}$ as

well as their optimal security within the class of

sequential constructions.

13:17 [Pub][ePrint] Aggregate and Verifiably Encrypted Signatures from Multilinear Maps Without Random Oracles, by Markus Rückert and Dominique Schroeder

  Aggregate signatures provide bandwidth-saving aggregation of ordinary signatures. We present the first unrestricted instantiation in the standard model, Moreover, our construction yields a multisignature scheme where a single message is signed by a number of signers. Our second result is an application to verifiably encrypted signatures. There, signers encrypt their signature under the public key of a trusted third party and output a proof that the signature is inside. Upon dispute between signer and verifier, the trusted third party is able to recover the signature. These schemes are provably secure in the standard model.

13:17 [Pub][ePrint] Rate-Limited Secure Function Evaluation: Definitions and Constructions, by Özgür Dagdelen and Payman Mohassel and Daniele Venturi

  We introduce the notion of rate-limited secure function evaluation (RL-SFE). Loosely speaking, in an RL-SFE protocol participants can monitor and limit the number of distinct inputs (i.e., rate) used by their counterparts in multiple executions of an SFE, in a private and verifiable manner. The need for RL-SFE naturally arises in a variety of scenarios: e.g., it enables service providers to ``meter\'\' their customers\' usage without compromising their privacy, or can be used to prevent oracle attacks against SFE constructions.

We consider three variants of RL-SFE providing different levels of security. As a stepping stone, we also formalize the notion of commit-first SFE (cf-SFE) wherein parties are committed to their inputs before each SFE execution. We provide compilers for transforming any cf-SFE protocol into each of the three RL-SFE variants. Our compilers are accompanied with simulation-based proofs of security in the standard model and show a clear tradeoff between the level of security offered and the overhead required. Moreover, motivated by the fact that in many client-server applications clients do not keep state, we also describe a general approach for transforming the resulting RL-SFE protocols into stateless ones.

As a case study, we take a closer look at the oblivious polynomial evaluation (OPE) protocol of Hazay and Lindell, show that it is commit-first and instantiate efficient rate-limited variants of it.

13:17 [Pub][ePrint] Nonlinear cryptanalysis of reduced-round Serpent and metaheuristic search for S-box approximations., by James McLaughlin and John A. Clark

  We utilise a simulated annealing algorithm to find several nonlinear approximations to various S-boxes which can be used to replace the linear approximations in the outer rounds of existing attacks. We propose three variants of a new nonlinear cryptanalytic algorithm which overcomes the main issues that prevented the use of nonlinear approximations in previous research, and we present the statistical frameworks for calculating the complexity of each version. We present new attacks on 11-round Serpent with better data complexity than any other known-plaintext or chosen-plaintext attack, and with the best overall time complexity for a 256-bit key.

13:17 [Pub][ePrint] A New Practical Identity-Based Encryption System, by Jong Hwan Park and Dong Hoon Lee

  We present a new practical Identity-Based Encryption (IBE) system that can be another candidate for standard IBE techniques. Our construction is based on a new framework for realizing an IBE trapdoor from pairing-based groups, which is motivated from the `two equation\' revocation technique suggested by Lewko, Sahai, and Waters. The new framework enables our IBE system to achieve a tight security reduction to the standard Decision Bilinear Diffie-Hellman assumption. Due to its the tightness, our system can take as input the shorter size of security parameters than the previous practical BF, SK, and BB$_{1}$ systems, which provides better efficiency to our system in terms of computational cost. With appropriate parametrization at the current 80-bit security level, our IBE system can obtain 11 times faster decryption than the previous ones and 77 times faster encryption than the BF system. We prove that our system is fully secure against chosen ciphertext attacks in the random oracle model. From computational variant of Naor\'s observation, we can also suggest a new signature scheme that features a tight security reduction to the Computational Diffie-Hellman assumption and provides strong unforgeability simultaneously.

10:17 [Pub][ePrint] Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security, by Kai-Min Chung and Rafael Pass and Karn Seth


The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS\'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques.

The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS\'12) instead requires the existence of an Oblivious Transfer protocol.

In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.