*09:17* [Pub][ePrint]
Revocable IBE Systems with Almost Constant-size Key Update, by Le Su and Hoon Wei Lim and San Ling and Huaxiong Wang
Identity-based encryption (IBE) has been regarded as an attractive alternative to more conventional certificate-based public key systems.It has recently attracted not only considerable research from the academic community, but also interest from the industry and standardization bodies. However, while key revocation is a fundamental requirement to any public key systems, not much work has been done in the identity-based setting. In this paper, we continue the study of revocable IBE (RIBE) initiated by Boldyreva, Goyal, and Kumar. Their proposal of a selective secure RIBE scheme, and a subsequent construction by Libert and Vergnaud in a stronger adaptive security model are based on a binary tree approach, such that their key update size is logarithmic in the number of users. We ask the question of whether or not the key update size could be further reduced by using a cryptographic accumulator. We show that, indeed, the key update material can be made constant with some small amount of auxiliary information, through a novel combination of the Lewko and Waters IBE scheme and the Camenisch, Kohlweiss, and Soriente pairing-based dynamic accumulator.

*09:17* [Pub][ePrint]
Rational Protocol Design: Cryptography Against Incentive-driven Adversaries, by Juan Garay and Jonathan Katz and Ueli Maurer and Bjoern Tackmann and Vassilis Zikas
Existing work on \"rational cryptographic protocols\" treats each party (or coalition of parties) running the protocol as a selfish agent trying to maximize its utility. In this work we propose a fundamentally different approach that is better suited to modeling a protocol under attack from an external entity. Specifically, we consider a two-party game between an protocol designer and an external attacker. The goal of the attacker is to break security properties such as correctness or privacy, possibly by corrupting protocol participants; the goal of the protocol designer is to prevent the attacker from succeeding.We lay the theoretical groundwork for a study of cryptographic protocol design in this setting by providing a methodology for defining the problem within the traditional simulation paradigm. Our framework provides ways of reasoning about important cryptographic concepts (e.g., adaptive corruptions or attacks on communication resources) not handled by previous game-theoretic treatments of cryptography. We also prove composition theorems that--for the first time--provide a sound way to design rational protocols assuming \"ideal communication resources\" (such as broadcast or authenticated channels) and then instantiate these resources using standard cryptographic tools.

Finally, we investigate the problem of secure function evaluation in our framework, where the attacker has to pay for each party it corrupts. Our results demonstrate how knowledge of the attacker\'s incentives can be used to

*09:17* [Pub][ePrint]
Improvement of Camenisch-Neven-Shelat Oblivious Transfer Scheme, by Zhengjun Cao and Hanyue Cao
In 2007, Camenisch, Neven and Shelat proposed an adaptive oblivious transfer (OT) in which a sender has $N$ messages, of which a receiver can adaptively choose to receive $k$ one-after-the-other.In this paper, we show that the scheme has a drawback that the sender can only serve a single receiver only once. The drawback results from the deterministic encryption used. To fix it, we suggest to replace the deterministic encryption with a probabilistic encryption. The OT scheme adopts the paradigm of ``encryption and proof of knowledge\" in order to force the sender to keep the consistency of the transferred messages. We remark that the paradigm is unnecessary. In most reasonable applications of OT, the transferred messages must be recognizable for the receiver or the sender is willing to disclose some messages to the receiver. This property has been explicitly specified in the earlier works by Rabin, Even, Goldreich and Lempel.

*09:17* [Pub][ePrint]
Non-Malleable Codes from Two-Source Extractors, by Stefan Dziembowski and Tomasz Kazana and Maciej Obremski
We construct an efficient information-theoretically non-mall\\-eable code in the split-state model for one-bit messages. Non-malleable codes were introduced recently by Dziembowski, Pietrzak and Wichs (ICS 2010), as a general tool for storing messages securely on hardware that can be subject to tampering attacks. Informally, a code $(Enc : \\cal M \\rightarrow \\cal L \\times \\cal R, Dec : \\cal L \\times \\cal R \\rightarrow \\cal M)$ is {\\em non-malleable in the split-state model} if any adversary, by manipulating {\\em independently} $L$ and $R$ (where $(L,R)$ is an encoding of some message $M$), cannot obtain an encoding of a message $M\'$ that is not equal to $M$ but is ``related\'\' $M$ in some way. Until now it was unknown how to construct an information-theoretically secure code with such a property, even for $\\cal M = \\{0,1\\}$. Our construction solves this problem. Additionally, it is leakage-resilient, and the amount of leakage that we can tolerate can be an arbitrary fraction $\\xi < {1}/{4}$ of the length of the codeword. Our code is based on the inner-product two-source extractor, but in general it can be instantiated by any two-source extractor that has large output and has the property of being {\\em flexible}, which is a new notion that we define.

We also show that the non-malleable codes for one-bit messages have an equivalent, perhaps simpler characterization, namely such codes can be defined as follows: if $M$ is chosen uniformly from $\\{0,1\\}$ then the probability (in the experiment described above) that the output message $M\'$ is not equal to $M$ can be at most $1/2 + \\epsilon$.

*09:17* [Pub][ePrint]
Limits on the Power of Cryptographic Cheap Talk, by Pavel Hubacek and Jesper Buus Nielsen and Alon Rosen
We revisit the question of whether cryptographic protocols can replace correlated equilibria mediators in two-player strategic games. This problem was first addressed by Dodis, Halevi and Rabin (CRYPTO 2000), who suggested replacing the mediator with a secure protocol and proved that their solution is stable in the Nash equilibrium (NE) sense, provided that the players are computationally bounded.We show that there exist two-player games for which no cryptographic protocol can implement the mediator in a sequentially rational way; that is, without introducing empty threats. This explains why all solutions so far were either sequentially unstable, or were restricted to a limited class of correlated equilibria (specifically, those that do not dominate any NE, and hence playing them does not offer a clear advantage over playing any NE).

In the context of computational NE, we classify necessary and sufficient cryptographic assumptions for implementing a mediator that allows to achieve a given utility profile of a correlated equilibrium. The picture that emerges is somewhat different than the one arising in semi-honest secure two-party computation. Specifically, while in the latter case every functionality is either \"complete\" (i.e., implies Oblivious Transfer) or \"trivial\" (i.e., can be securely computed unconditionally), in the former there exist some \"intermediate\" utility profiles whose implementation is equivalent to the existence of one-way functions.

*09:17* [Pub][ePrint]
Obfuscating Branching Programs Using Black-Box Pseudo-Free Groups, by Ran Canetti and Vinod Vaikuntanathan
We show that the class of polynomial-size branching programs can be obfuscated according to a virtual black-box notion akin to that of Barak et al. [Crypto 01], in an idealized black-box group modelover pseudo-free groups. This class is known to lie between $NC^1$ and $P$ and includes most interesting cryptographic algorithms. The construction is rather simple and is based on Kilian\'s randomization

technique for Barrington\'s branching programs.

The black-box group model over pseudo-free groups is a strong idealization. In particular, in a pseudo-free group, the group operation can be efficiently performed, while finding surprising relations between group elements is intractable.

%inverses or linking between different representations of the same group element are infeasible. A black-box representation of the group provides an ideal interface which permits prescribed group operations, and nothing else. Still, the algebraic structure and security requirements appear natural and potentially realizable. They are also unrelated to the specific function to be obfuscated.

Our modeling should be compared with the recent breakthrough obfuscation scheme of Garg et al. [FOCS 2013]: While the high level structure is similar, some important details differ. It should be stressed however that, unlike Garg et al., we do not provide a candidate concrete instantiation of our abstract structure.

*09:17* [Pub][ePrint]
Proving TLS-attack related open biases of RC4, by Santanu Sarkar and Sourav Sen Gupta and Goutam Paul and Subhamoy Maitra
After a series of works on RC4 cryptanalysis in last few years (published in flagship cryptology conferences and journals), the most significant (and also very recent) attack on the cipher has been the discovery of vulnerabilities in the SSL/TLS protocol, by AlFardan, Bernstein, Paterson, Poettering and Schuldt. They ran extensive computations to identify significant short-term single-byte keystream biases of RC4, and utilized that knowledge in the attack. The biases identified by AlFardan et al. consist of earlier known biases of RC4, as well as some newly discovered ones. In this paper, we attempt at proving the new, unproved or partially proved biases amongst the above-mentioned ones. The theoretical proofs of these biases not only assert a scientific justification, but also discover intricate patterns and operations of the cipher associated with these biases. For example, while attempting the proof of a bias of the first output byte towards 129, we observe that this bias occurs prominently only for certain lengths of the secret key of RC4. In addition, our findings reveal that this bias may be related to the old and unsolved problem of ``anomalies\'\' in the distribution of the state array after the Key Scheduling Algorithm. In this connection, we prove the anomaly in $S_0[128] = 127$, a problem open for more than a decade.

Other than proving the new biases, we also complete the proof for the extended keylength dependent biases in RC4, a problem attempted and partially solved by Isobe, Ohigashi, Watanabe and Morii in FSE 2013. Our new proofs and observations in this paper, along with the connection to the older results, provide a comprehensive view on the state-of-the-art literature in RC4 cryptanalysis.

*15:17* [Pub][ePrint]
Golden Sequence for the PPSS Broadcast Encryption Scheme with an Asymmetric Pairing, by Renaud Dubois and Margaux Dugardin and Aurore Guillevic
Broadcast encryption is conventionally formalized as broadcast encapsulation in which, instead of a cipher-text, a session key is produced, which is required to be indistinguishable from random. Such a scheme can

provide public encryption functionality in combination with a symmetric encryption through the hybrid en-

cryption paradigm. The Boneh-Gentry-Waters scheme of 2005 proposed a broadcast scheme with constant-size

ciphertext. It is one of the most efficient broadcast encryption schemes regarding overhead size. In this work we

consider the improved scheme of Phan-Pointcheval-Shahandashi-Ste

er [PPSS12] which provides an adaptive

CCA broadcast encryption scheme. These two schemes may be tweaked to use bilinear pairings[DGS].

This document details our choices for the implementation of the PPSS scheme. We provide a complete golden sequence

of the protocol with efficient pairings (Tate, Ate and Optimal Ate). We target a 128-bit security

level, hence we use a BN-curve [BN06]. The aim of this work is to contribute to the use and the standardization of

PPSS scheme and pairings in concrete systems.

*15:17* [Pub][ePrint]
Enabling End-to-End Secure Communication with Anonymous and Mobile Receivers - an Attribute-Based Messaging Approach, by Stefan G. Weber
Mechanisms for secure mobile communication can be enablers for novel applications in the area of cooperative work. In this context, this article exemplarily investigates an emergency management setting. An efficient support of emergency communication is of high practical importance, but has specific challenges: unpredictable local crisis situations harden the establishment of communication structures, legal requirements dictate the use of end-to-end secure and documentable approaches, while end users demand user-friendliness and privacy protection. Dealing with these challenges, the contribution of this article is two-fold. Firstly, together with emergency practioners, we follow a participatory design approach. We define security requirements, patterns for efficient communication and derive a design proposal. Secondly, we devise a novel approach to multilaterally end-to-end secure, user-friendly attribute-based messaging for one-to-many communication. It builds on a hybrid encryption technique, which efficiently combines ciphertext-policy attribute-based encryption, location-based encryption and symmetric encryption. The hybrid encryption approach supports dynamic location attributes as user-friendly selectors for targeted messaging with dynamic groups of mobile and anonymous receivers. The achieved security of the approach and concrete application scenarios are discussed.