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

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-12-01
19:17 [Pub][ePrint]

The Internet of Things (IoT) will be formed by smart objects and services interacting autonomously and in real-time. Recently, Alcaide et al. proposed a fully decentralized anonymous authentication protocol for privacy-preserving IoT target-driven applications. Their system is set up by an ad-hoc community of decentralized founding nodes. Nodes can interact, being participants of cyberphysical systems, preserving full anonymity. In this study, we point out that their protocol is insecure. The adversary can cheat the data collectors by impersonating a legitimate user.

19:17 [Pub][ePrint]

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto\'92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.

In this work, we put forward an alternative concept for PoWs -- so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model, using graphs with high \"pebbling complexity\" and Merkle hash-trees.

19:17 [Pub][ePrint]

We initiate the investigation of {\\em gate}-tampering attacks against

cryptographic circuits. Our model is motivated by the plausibility of

tampering directly with circuit gates and by the increasing use of {\\em tamper

resilient gates} among the known constructions that are shown to be resilient

against {\\em wire-tampering} adversaries. We prove that gate-tampering is {\\em

strictly} stronger than wire-tampering. On the one hand, we show that there is

a gate-tampering strategy that perfectly simulates any given wire-tampering

strategy. On the other, we construct families of circuits over which it is

impossible for any wire-tampering attacker to simulate a certain gate-tampering

attack (that we explicitly construct). We also provide a tamper resilience

impossibility result that applies to both gate and wire tampering adversaries

and relates the amount of tampering to the depth of the circuit. Finally, we

show that defending against gate-tampering attacks is feasible by appropriately

abstracting and analyzing the circuit compiler of Ishai et al.

\\cite{Ishai:2006a} in a manner which may be of independent interest.

Specifically, we first introduce a class of compilers that, assuming certain

well defined tamper resilience characteristics against a specific class of

attackers, can be shown to produce tamper resilient circuits against that

same class of attackers. Then, we describe a compiler in this class for which

we prove that it possesses the necessary tamper-resilience characteristics

against gate-tampering attackers.

19:17 [Pub][ePrint]

We present a new generic construction of public key encryption (PKE) scheme that is secure against a-posteriori chosen-ciphertext λ-key-leakage attacks (LR-CCA-2 secure) from any universal hash proof system (HPS). Our construction relies only on the existence of universal hash proof systems, which makes our scheme simple, clean and efficient. Furthermore, our construction is a potential way to construct LR-CCA-2 secure PKE scheme from minimal assumption.

19:17 [Pub][ePrint]

This paper investigates the mathematical structure of the Isomorphism of Polynomial with One Secret\'\' problem (IP1S). Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable (as first observed by Bouillaguet et al.).

We show that the structure of the problem is directly linked to the

structure of quadratic forms in odd and even characteristic. We describe a completely new method allowing to efficiently solve most instances. Unlike previous solving techniques, this is not based upon Gröbner basis computations.

19:17 [Pub][ePrint]

Cube attacks can be used to analyse and break cryptographic primitives that have an easy algebraic description. One example for such a primitive is the stream cipher /Trivium.

In this article we give a new framework for cubes that are useful in the cryptanalytic context. In addition, we show how algebraic modelling of a cipher can greatly be improved when taking both cubes and linear equivalences between variables into account. When taking many instances of Trivium, we empirically show a saturation effect, i.e., the number of variables to model an attack will become constant for a given number of rounds. Moreover, we show how to systematically find cubes both for general primitives and also specifically for Trivium. For the latter, we have found all cubes up to round 446 and draw some conclusions on their evolution between rounds. All techniques in this article are general and can be applied to any cipher.

19:17 [Pub][ePrint]

At Crypto 2013 Libert, Peters, Joye and Yung introduced the notion of Linearly Homomorphic Structure Preserving Signatures (LHSPS) as a tool to perform verifiable computation on encrypted data and to create constant-size non malleable commitments to group elements. In this paper we improve our understanding of LHSPS by putting forward new methodologies and applications. First, we present a generic transform that converts LHSPS which are secure against weak random message attack (RMA) into ones that achieve full security guarantees. Next we give evidence that RMA secure linearly homomorphic structure preserving signatures are interesting in their own right by showing applications in the context of on-line/off-line homomorphic and network coding signatures. This notably provides what seems to be the first instantiations of homomorphic signatures achieving on-line/off-line efficiency trade-offs.

19:17 [Pub][ePrint]

Yoneyama et al. introduced Leaky Random Oracle Model (LROM for short) at ProvSec2008 in order to discuss security (or insecurity) of cryptographic schemes which use hash functions as building blocks when leakages from pairs of input and output of hash functions occur in the experiment of security definition. This kind of leakages occurs due to various attacks caused by sloppy usages or implementations. Their results showed that this kind of leakages may threaten the security of some cryptographic scheme. However, an important fact is that such attacks would leak not only pairs of input and output of hash functions, but also the secret key. Therefore, LROM is very limited in the sense that it considers leakages from pairs of input and output of hash functions alone, instead of taking into consideration other possible leakages from the secret key simultaneously. On the other hand, many recent leakage models mainly concentrate on leakages from the secret key and ignore leakages from hash functions for a cryptographic scheme exploiting hash functions. This is a weakness of these leakage models and there exist some schemes in these leakage models but is not secure any more when leakages from hash functions occur.

In this paper, we present an augmented model of both LROM and some leakage models. In our new model, both the secret key and pairs of input and output of hash functions can be leaked. Furthermore, the secret key can be leaked continually during the whole lifecycle of a cryptographic scheme. Hence, our new model is more universal and stronger than LROM and some leakage models (e.g. only computation leaks model and bounded memory leakage model). As an application example, we also present a public key encryption scheme which is provably IND-CCA secure in our new model.

19:17 [Pub][ePrint]

We present the first fully secure Identity-Based Encryption scheme

(IBE) from the standard assumptions where the security loss depends

only on the security parameter and is independent of the number of

secret key queries. This partially answers an open problem posed by

Waters (Eurocrypt 2005). Our construction combines Waters\' dual

system encryption methodology (Crypto 2009) with the Naor-Reingold

pseudo-random function (J. ACM, 2004) in a novel way. The security

of our scheme relies on the DLIN assumption in prime-order groups.

19:17 [Pub][ePrint]

This paper adapts a new group signature (GS) scheme to

the specific needs of certain application e.g., a vehicular adhoc network (VANET). Groth GS is the first efficient GS scheme in the BSZ-model with security proofs in the standard model. We modify the Groth GS in order to meet a restricted, but arguably sufficient set of privacy proper-ties. Although there are some authentication schemes using GS none of them satisfy all the desirable security and privacy properties. Either they follow GSs that rely on Random Oracle Model, or unable to satisfy potential application requirements. In particular, link management which allows any designated entities to link messages, whether they are coming from the same member or a certain group of members without revealing their identities; opening soundness that prevents malicious accusations by the opener against some honest member of the group; revocation system that privileges from fraudulent member like the traditional Public Key infrastructure (PKI). In order to achieve the aforementioned security properties together, we propose a new GS model where linkability, sound

opening and revocability properties are assembled in a single scheme. The novelty of our proposal stems from extending the Groth GS by relaxing strong privacy properties to a scheme with a lightly lesser privacy in order to fit an existing VANET application requirements. In addition, we partially minimize the Groth GS scheme to expedite efficiency.

2013-11-30
07:17 [Pub][ePrint]

The most influential broadcast encryption (BE) scheme till date was introduced in 2001 by Naor, Naor and Lotspiech (NNL) and is based on binary trees. This paper generalizes the ideas of NNL to obtain BE schemes based on $k$-ary trees for any $k\\geq 2$. The treatment is uniform across all $k$ and essentially provides a single scheme which is parameterized by the arity of the underlying tree. We perform an extensive analysis of the header length and user storage of the scheme. It is shown that for a $k$-ary tree with $n$ users out of which $r$ are revoked, the maximum header length is $\\min(2r-1,n-r,\\lceil n/k\\rceil)$. An expression for the expected header length is obtained and it is shown that the expression can be evaluated in $O(r\\log n)$ time. Experimental results indicate that for values of $r$ one would expect in applications such as pay TV systems, the average header length decreases as $k$ increases. The number of keys to be stored by any user is shown to be at most $(\\chi_k-2)\\ell_0(\\ell_0+1)/2$, where $\\ell_0=\\lceil\\log_k n\\rceil$ and $\\chi_k$ is the number of cyclotomic cosets modulo $2^k-1$. In particular, when the number of users is more than $1024$, we prove that the user storage required for $k=3$ is less than that of $k=2$. For higher values of $k$, the user storage is greater than that for binary trees. The option of choosing the value of $k$ provides a designer of a BE system with a wider range of trade-offs between average header length and user storage.