International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2013-08-15
09:17 [Pub][ePrint]

In this paper, we present an efficient public-key broadcast encryption (PKBE) scheme with sub-linear size of public keys, private keys, and ciphertexts and prove its adaptive security under standard assumptions. Compared with the currently best scheme that provides adaptive security under standard assumptions and sub-linear size of various parameters, the ciphertext size of our scheme is $94\\%$ shorter and the encryption algorithm of our scheme is also $2.8$ times faster than those of the currently best scheme.

To achieve our scheme, we adapt the dual system encryption technique of Waters. However, there is a challenging problem to use this technique for the construction of PKBE with sub-linear size of ciphertexts such as a tag compression problem. To overcome this problem, we first devise a novel tag update technique for broadcast encryption. Using this technique, we build an efficient PKBE scheme in symmetric bilinear groups, and prove its adaptive security under standard assumptions. After that, we build another PKBE scheme in asymmetric bilinear groups and also prove its adaptive security under simple assumptions.

09:17 [Pub][ePrint]

The increasing demand for on-line collaborative applications has sparked the interest for multicast services, which in many cases have to guarantee properties such as authentication or confidentiality within groups of users.To do so, cryptographic protocols are generally used and the cryptographic keys, in which they rely, have to be managed (e.g. created, updated, distributed). The procedures to perform these operations are determined by the so-called Group Key Management Schemes. Many schemes have been proposed and some

of them have been proven to be vulnerable. This is the case of the Piao et al. scheme, whose scalability/efficiency is very good but it is vulnerable to many attacks because its security is based on a weak\'\' mathematical problem, so it can be broken in polynomial time.

Inspired by the concepts proposed in the Piao et al. scheme we have re-designed the protocol and we have founded it on a hard mathematical problem and tweaked some of the procedures. This way, we propose a new scheme that is efficient, collusion free, and provides backward and forward secrecy.

09:17 [Pub][ePrint]

In this paper we present new constraints to EPCglobal Class 1 Generation 2 (EPC-C1 G2) standard which if they have been considered in the design of EPC-C1 G2 complaint authentication protocols, lead to prevent predecessor\'s protocols\' weaknesses and also present the secure ones. Also in this paper as an example, we use Pang \\textit{et al.} EPC-C1 G2-friendly protocol which has been recently proposed, to show our proposed constraints in EPC-C1 G2 standard. Pang \\textit{et al.}\'s protocol security analysis show how its security claim based on untraceability and resistance against de-synchronization attacks is ruined. More precisely, we present very efficient de-synchronization attack and traceability attack against the protocol. Finally, take Pang \\textit{et al.} protocol\'s vulnerability points, we present new conditions to design EPC-C1 G2 complaint protocols and based on it we propose a secure (EPC-C1 G2) RFID authentication scheme which is a good sample to EPC-C1 G2 complaint protocols.

09:17 [Pub][ePrint]

We propose an optimization and generalization of OT extension of Ishai et al. of Crypto 2003. For computational security parameter k, our OT extension for short secrets offers O(log k) factor performance improvement in communication and computation, compared to prior work. In concrete terms, for today\'s security parameters, this means approx. factor 2-3 improvement.

This results in corresponding improvements in applications relying on

such OT. In particular, for two-party semi-honest SFE, this results in O(log k) factor improvement in communication over state of the art Yao Garbled Circuit, and has the same asymptotic complexity as the recent multi-round construction of Kolesnikov and Kumaresan of SCN 2012. For multi-party semi-honest SFE, where their construction is inapplicable, our construction implies O(log k) factor communication and computation improvement over best previous constructions. As with our OT extension, for today\'s security parameters, this means approximately factor 2 improvement in semi-honest multi-party SFE.

Our building block of independent interest is a novel IKNP-based framework for 1-out-of-n OT extension, which offers O(log n) factor performance improvement over previous work (for n

09:17 [Pub][ePrint]

Cryptographic access control promises to offer easily distributed trust and broader applicability, while reducing reliance on low-level online monitors. Traditional implementations of cryptographic access control rely on simple cryptographic primitives whereas recent endeavors employ primitives with richer functionality and security guarantees. Worryingly, few of the existing cryptographic access-control schemes come with precise guarantees, the gap between the policy specication and the implementation being analyzed only informally, if at all.

In this paper we begin addressing this shortcoming. Unlike prior work that targeted ad-hoc policy specification, we look at the well-established Role-Based Access Control (RBAC) model, as used in a

typical file system. In short, we provide a precise syntax for a computational version of RBAC, offer rigorous denitions for cryptographic policy enforcement of a large class of RBAC security policies, and demonstrate that an implementation based on attribute-based encryption meets our security notions.

We view our main contribution as being at the conceptual level. Although we work with RBAC for concreteness, our general methodology could guide future research for uses of cryptography in other

access-control models.

09:17 [Pub][ePrint]

In this paper, we present a new class of semi-bent quadratic Boolean functions of the form $f(x)=\\sum_{i=1}^{\\lfloor\\frac{m-1}{2}\\rfloor}Tr^n_1(c_ix^{1+4^{i}})$ $~(c_i\\in \\mathbb{F}_4$,$n=2m)$. We first characterize the semi-bentness of these quadratic Boolean functions. There exists semi-bent functions only when $m$ is odd. For the case: $m=p^r$, where $p$ is an odd prime with some conditions, we enumerate the semi-bent functions. Further, we give a simple characterization of semi-bentness for these functions with linear properties of $c_i$. In particular, for

a special case of $p$, any quadratic Boolean function $f(x)=\\sum_{i=1}^{\\frac{p-1}{2}}Tr^{2p}_1(c_ix^{1+4^{i}})$ over $\\mathbb{F}_{2^{2p}}$ is a semi-bent function.

09:17 [Pub][ePrint]

The series of published works, related to Differential Fault Attack

(DFA) against the Grain family, require (i) quite a large number (hundreds) of faults (around $n \\ln n$, where $n = 80$ for Grain v1 and $n = 128$ for Grain-128, Grain-128a) and also (ii) several assumptions on location and timing of the fault injected. In this paper we present a significantly improved scenario from the adversarial point of view for DFA against the Grain family of stream ciphers. Our model is the most realistic one so far as it considers that the cipher to be re-keyed a very few times and fault can be injected at any random location and at any random point of time, i.e., no precise control is needed over the location and timing

of fault injections. We construct equations based on the algebraic description of the cipher by introducing new variables so that the degrees of the equations do not increase. In line of algebraic cryptanalysis, we accumulate such equations based on the fault-free and faulty key-stream bits and solve them using the SAT Solver

Cryptominisat-2.9.5 installed with SAGE 5.7. In a few minutes we can recover the state of Grain v1, Grain-128 and Grain-128a with as little as 10, 4 and 10 faults respectively (and may be improved further with more computational efforts).

09:17 [Pub][ePrint]

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]

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]

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]

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