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

2012-08-05
15:17 [Pub][ePrint]

Group signatures are a central cryptographic primitive, simultaneously supporting accountability and anonymity. They allow

users to anonymously sign messages on behalf of a group they are

members of. The recent years saw the appearance of several

constructions with security proofs in the standard model ({\\it

i.e.}, without appealing to the random oracle heuristic). For a

digital signature scheme to be adopted, an efficient revocation

scheme (as in regular PKI) is absolutely necessary.

Despite over a decade of extensive research, membership revocation

remains a non-trivial problem in group signatures: all existing

solutions are not truly scalable due to either high overhead (e.g., large group public key size), or limiting operational requirement (the need for all users to follow the system\'s entire history). In the standard model, the situation is even worse as many existing solutions are not readily adaptable. To fill this gap and tackle this challenge, we describe a new revocation approach based, perhaps

somewhat unexpectedly, on the Naor-Naor-Lotspiech framework which was introduced for a different problem (namely, that of broadcast encryption). Our mechanism yields efficient and scalable revocable group signatures in the standard model. In particular, the size of signatures and the verification cost are independent of the number of

revocations and the maximal cardinality $N$ of the group while other

complexities are at most polylogarithmic in $N$. Moreover, the

schemes are history-independent: unrevoked group members do not have

to update their keys when a revocation occurs.

15:17 [Pub][ePrint]

The core of the 3rd Generation Partnership Project (3GPP) encryption standard 128-EEA3 is a stream cipher called ZUC. It was designed by the Chinese Academy of Sciences and proposed for inclusion in the cellular wireless standards called \"Long Term Evolution\" or \"4G\". The LFSR-based cipher uses a 128-bit key. In this paper, we first show timing attacks on ZUC that can recover, with about 71.43% success rate, (i) one bit of the secret key immediately, and (ii) information involving 6 other key bits. The time, memory and data requirements of the attacks are negligible. While we see potential improvements to the attacks, we

also suggest countermeasures.

15:17 [Pub][ePrint]

A commonly used metric for comparing the resilience of key predistribution schemes is $\\fail_s$, which measures the proportion of network connections which are broken\' by an adversary which has compromised $s$ nodes. In Random key predistribution schemes for sensor networks\', Chan, Perrig and Song present a formula for measuring the resilience in a class of random key predistribution schemes called $q$-composite schemes. We present a correction to this formula for schemes where more than one key may be used to secure a link between a pair of nodes. Our corrected formula features an additional parameter which makes it applicable to a wider variety of random key predistribution schemes, including the original Eschenauer Gligor scheme. We also present a simplification of the formula for calculating connectivity.

We refer to the recent paper by Yum and Lee which also claims to correct the original formula for the $q$-composite scheme. However the resulting formula is complicated, computationally demanding, and hard to understand. The formula which we propose and prove is easily computable and can be applied to a wider range of schemes.

15:17 [Pub][ePrint]

Genus 2 curves with simple but not absolutely simple jacobians can be used to construct pairing-based cryptosystems more efficient than for a generic genus 2 curve. We show that there is a full analogy between methods for constructing ordinary pairing-friendly elliptic curves and simple abelian varieties, which are iogenous over some extension to a product of elliptic curves. We extend the notion of complete, complete with variable discriminant, and sparse families introduced in by Freeman, Scott and Teske for elliptic curves, and we generalize the Cocks-Pinch method and the Brezing-Weng method to construct families of each type. To realize abelian surfaces as jacobians we use of genus 2 curves of the form $y^2=x^5+ax^3+bx$ or $y^2=x^6+ax^3+b$, and apply the method of Freeman and Satoh. As applications we find some families of abelian surfaces with recorded $\\rho$-value $\\rho=2$ for embedding degrees $k=3,4,6,12$, or $\\rho=2.1$ for $k=27,54$. We also give variable-discriminant families with best $\\rho$-values.

15:17 [Pub][ePrint]

We use ideas from game theory to improve two families of authentication protocols, namely password-based and manual authentication schemes. The protocols will be transformed so that even if an intruder attacks different protocol runs between honest nodes, its expected payoff will still be lower than when it does not attack. A rational intruder, who always tries to maximise its payoff, therefore has no incentive to attack any protocol run among trustworthy parties. To illustrate the use of our method, we present a case study relating to the password-based authentication stage of on-line banking, where passwords are chosen either randomly or biasedly by, e.g., humans. For the latter we use the publicly available 32 million passwords of the social gaming network website RockYou as the source of human-selected passwords.

15:17 [Pub][ePrint]

Epsilon-biased distribution has many applications in practice, including universal hashing computation. In this paper we will improve an existing epsilon-biased distribution construction due to Alon et al. that requires to uniformly and efficiently sample irreducible polynomials of a large degree, e.g. between 80 and 160. To remove the need for such a sampling which can be computationally expensive, we will replace the irreducible polynomials by random monic polynomials of higher degree, i.e. every degree r monic polynomial whether irreducible or reducible is selected with the same probability 2^{-r}. To analyse the security of the scheme, we need to

find the maximum number of degree r polynomials that divide a degree n polynomial where n > r.

15:17 [Pub][ePrint]

Secure electronic circuits must implement countermeasures against a wide range of attacks.

Often, the protection against side channel attacks requires to be tightly integrated within the functionality to be protected.

It is now part of the designer\'s job to implement them.

But this task is known to be error-prone, and with current development processes, countermeasures are evaluated often very late (at circuit fabrication).

In order to improve the confidence of the designer in the efficiency of the countermeasure,

we suggest in this article to resort to formal methods early in the design flow for two reasons.

First of all, we intend to check that the process of transformation of the design from the vulnerable description to the protected one does not alter the functionality.

Second, we wish to prove that the security properties (that can derive from a formal security functional specification) are indeed met after transformation.

Our first contribution is to show how such a framework can be setup (in COQ) for netlist-level protections.

The second contribution is to illustrate that this framework indeed allows to detect vulnerabilities in dual-rail logics.

15:17 [Pub][ePrint]

We identify a potential weakness in the standard security model for dynamic group signatures which appears to have been overlooked previously. More specifically, we highlight that even if a scheme provably meets the security requirements of the model, a malicious group member can potentially claim ownership of a group signature produced by an honest group member by forging a proof of ownership. This property leads to a number of vulnerabilities in scenarios in which dynamic group signatures are likely to be used. We furthermore show that the dynamic group signature scheme by Groth (ASIACRYPT 2007) does not provide protection against this type of malicious behavior.

To address this, we introduce the notion of \\emph{opening soundness} for group signatures which essentially requires that it is infeasible to produce a proof of ownership of a valid group signature for any user except the original signer. We then show a relatively simple modification of the scheme by Groth which allows us to prove opening soundness for the modified scheme without introducing any additional assumptions.

We believe that opening soundness is an important and natural security requirement for group signatures, and hope that future schemes will adopt this type of security.

15:17 [Pub][ePrint]

Tor is a widely used anonymity network providing low-latency communication capabilities. Around 400,000 users per day use Tor to route TCP traffic through a sequence of relays; three hops are selected from a pool of currently almost 3000 volunteer-operated Tor relays to comprise a route through the network for a limited time. In comparison to single-hop proxies, forwarding TCP streams through multiple relays increases the anonymity of the users significantly: each hop along the route only knows its successor and predecessor.

The anonymity provided by Tor heavily relies on the hardness of linking a user\'s entry and exit nodes. If an attacker gains access to the topological information about the Tor network instead of having to consider the network as a fully connected graph, this anonymity may be reduced. In fact, we have found ways to probe the connectivity of a Tor relay. We demonstrate how the resulting leakage of the Tor network topology can be used and present attacks to trace back a user from an exit relay to a small set of potential entry nodes.

15:17 [Pub][ePrint]

Consider a setting of two mutually distrustful parties Alice and Bob who want to securely

evaluate some function on pre­-specified inputs. The well studied notion of two­-party secure computation

allows them to do so in the stand­alone setting. Consider a deterministic function (e.g., 1­-out­-of­-2 bit

OT) that Alice and Bob can not evaluate trivially and which allows only Bob to receive the output. We

show that Alice and Bob can not securely compute any such function in the concurrent setting even

when their inputs are pre­-specified. Our impossibility result also extends to all deterministic functions in

which both Alice and Bob get the same output. Our results have implications in the bounded­-concurrent

setting as well.

15:17 [Pub][ePrint]

We present new protocols for {\\em publicly verifiable} secure outsourcing of polynomials and matrix multiplication, which can

be instantiated over RSA moduli, and proven secure under the DDH/RSA/Factoring Assumptions over such groups. Since all previous solutions are based on the use of bilinear maps, we demonstrate that publicly verifiable computation can be achieved even under different and standard assumptions.

Perhaps more interestingly, our solution can handle polynomials over finite fields of {\\em any} characteristic (starting from 2), and thus it can also support public verification of boolean formulas. This allows for a lot of flexibility, and it avoids the efficiency penalty of working bit by bit in fields larger than 2.

The core of our result is a new concept of Algebraic One-Way Functions which may be of independent interest.