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

09:17 [Pub][ePrint] On The Security of One-Witness Blind Signature Schemes, by Foteini Baldimtsi and Anna Lysyanskaya

  Blind signatures have proved an essential building block for applications that protect privacy while

ensuring unforgeability, i.e., electronic cash and electronic voting. One of the oldest, and most ecient blind

signature schemes is the one due to Schnorr that is based on his famous identication scheme. Although it

was proposed over twenty years ago, its unforgeability remains an open problem, even in the random-oracle

model. In this paper, we show that current techniques for proving security in the random oracle model do not

work for the Schnorr blind signature. Our results generalize to other important blind signatures, such as the

one due to Brands. Brands\' blind signature is at the heart of Microsoft\'s newly implemented UProve system,

which makes this work relevant to cryptographic practice as well.

09:17 [Pub][ePrint] Beyond the Limitation of Prime-Order Bilinear Groups, and Round Optimal Blind Signatures, by Jae Hong Seo and Jung Hee Cheon

  At Eurocrypt 2010, Freeman proposed a transformation from pairing-based schemes in composite-order bilinear groups to equivalent ones in prime-order bilinear groups. His transformation can be applied to pairing-based cryptosystems exploiting only one of two properties of composite-order bilinear groups: cancelling and projecting. At Asiacrypt 2010, Meiklejohn, Shacham, and Freeman showed that prime-order bilinear groups according to Freeman\'s construction cannot have two properties simultaneously except negligible probability and, as an instance of implausible conversion, proposed a (partially) blind signature scheme whose security proof exploits both the cancelling and projecting properties of composite-order bilinear groups.

In this paper, we invalidate their evidence by presenting a security proof of the prime-order version of their blind signature scheme. Our security proof follows a different strategy and exploits only the projecting property. Instead of the cancelling property, a new property, that we call {\\em translating}, on prime-order bilinear groups plays an important role in the security proof, whose existence was not known in composite-order bilinear groups. With this proof, we obtain a $2$-move (i.e., round optimal) (partially) blind signature scheme (without random oracle) based on the decisional linear assumption in the common reference string model, which is of independent interest.

As the second contribution of this paper, we construct prime-order bilinear groups that possess both the cancelling and projecting properties at the same time by considering more general base groups. That is, we take a rank $n$ $\\zp$-submodule of $\\zp^{n^2}$, instead of $\\zp^n$, to be a base group $G$, and consider the projections into its rank 1 submodules. We show that the subgroup decision assumption on this base group $G$ holds in the generic bilinear group model for $n=2$, and provide an efficient membership-checking algorithm to $G$, which was trivial in the previous setting.

Consequently, it is still open whether there exists a cryptosystem on composite-order bilinear groups that cannot be constructed on prime-order bilinear groups.

09:17 [Pub][ePrint] Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm, by Jean-Charles Faugère and Pierrick Gaudry and Louise Huot and Guénaël Renault

  In 2004, an algorithm is introduced to solve the DLP for elliptic

curves defined over a non prime finite field $\\F_{q^n}$. One of the

main steps of this algorithm requires decomposing points of the curve

$E(\\F_{q^n})$ with respect to a factor base, this problem is denoted PDP. In this paper, we will apply this algorithm to the case of Edwards curves, the well known family of elliptic curves that allow faster arithmetic as shown by Bernstein and Lange. More precisely, we show how to take advantage of some symmetries of twisted Edwards and

twisted Jacobi intersections curves to gain an exponential factor

$2^{3 (n-1)}$ to solve the corresponding PDP. Practical experiments

supporting the theoretical result are also given. For instance, the

complexity of solving the ECDLP for twisted Edwards curves defined

over $\\F_{q^5}$, with $q\\approx2^{64}$, is supposed to be $2^{160}$

operations in $E(\\F_{q^5})$ using generic algorithms compared to

$2^{127}$ operations (multiplication of two $32$ bits words) with

our method. For these parameters the PDP is untractable with the

original algorithm.

The main tool to achieve these results relies on the use of the

symmetries during the polynomial system solving step. Also, we use a

recent work on a new strategy for the change of ordering of Gröbner

basis which provides a better heuristic complexity of the total

solving process.

09:17 [Pub][ePrint] Aggregate Signcryption, by Alexander W. Dent

  Signcryption schemes provide an efficient messaging system for data that needs to be sent with data confidentiality, data integrity and data origin authentication. However, the bandwidth overhead for the use of signcryption in a network in which a large number of messages need to be sent may be high. Motivated by aggregate signature schemes, we propose the concept of an aggregate signcryption scheme. An aggregate signcryption scheme allows distinct signcryption ciphertexts intended for the same recipient to be merged into a single signcryption ciphertext of smaller size without losing any of their security guarantees. This has the potential to provide significant bandwidth savings. We propose security models for this scheme, analyse the trivial generic constructions, propose an efficient new scheme, and analyse the bandwidth requirements of these schemes for a practical distributed database application.

08:59 [Event][New] Provable Privacy Workshop

  Submission: 4 May 2012
Notification: 1 June 2012
From July 9 to July 10
Location: Vigo, Spain
More Information:

07:49 [News] CryptoDB updates

  CryptoDB has been updated with best paper awards, coauthor relationships, and DOIs.

21:17 [Pub][ePrint] Replay attacks that violate ballot secrecy in Helios, by Ben Smyth

  Helios 2.0 is a web-based end-to-end verifiable electronic voting system, suitable for use in low-coercion environments. In this paper we identify a vulnerability in Helios which allows an adversary to compromise the privacy of voters whom cast abstention votes. The vulnerability can be attributed to the absence of ballot independence and the use of homomorphic ElGamal encryption, in particular, these properties can be exploited by an adversary to construct a ballot related to an abstention vote cast by an honest voter and this ballot can be submitted by a corrupt voter to influence the election outcome, thereby introducing information that can be used to violate privacy. We demonstrate the attack by breaking privacy in a mock election using the current Helios implementation. It is unlikely that the vulnerability will be exploited in a real-world election and therefore our results are largely theoretical. Nonetheless, we cannot expect any computational proofs of ballot secrecy without fixing this vulnerability and, moreover, the attack methodology may be of interest -- in particular, it could represent a viable threat to existing protocols in the literature -- thus providing motivation to report these results.

21:17 [Pub][ePrint] Third-order nonlinearities of some biquadratic monomial Boolean functions, by Brajesh Kumar Singh

  In this paper, we estimate the lower bounds on third-order

nonlinearities of some biquadratic monomial Boolean functions of the

form $Tr_1^n(\\lambda x^d)$ for all $x \\in \\mathbb F_{2^n}$, where

$\\lambda \\in \\BBF_{2^n}^{*}$,


\\item [{(1)}]$d = 2^i + 2^j + 2^k + 1$, $i, j, k$

are integers such that $ i > j > k \\geq 1$ and $n > 2 i$.

\\item [{(2)}] $d = 2^{3\\ell} + 2^{2\\ell} + 2^{\\ell} + 1$, $\\ell$

is a positive integer such that $\\gcd (i, n) = 1$ and $n > 6$.


21:17 [Pub][ePrint] SmartTokens: Delegable Access Control with NFC-enabled Smartphones (Full Version), by Christian Wachsmann and Alexandra Dmitrienko and Ahmad-Reza Sadeghi and Sandeep Tamrakar

  Today\'s smartphones and tablets offer compelling computing and storage capabilities enabling a variety of mobile applications with rich functionality. The integration of new interfaces, in particular near field communication~(NFC) opens new opportunities for new applications and business models, as the most recent trend in industry for payment and ticketing shows. These applications require storing and processing security-critical data on smartphones, making them attractive targets for a variety of attacks. The state of the art to enhance platform security concerns outsourcing security-critical computations to hardware-isolated Trusted Execution Environments~(TrEE). However, since these TrEEs are used by software running in commodity operating systems, malware could impersonate the software and use the TrEE in an unintended way. Further, existing NFC-based access control solutions for smartphones are either not public or based on strong assumptions that are hard to achieve in practice.

We present the design and implementation of a generic access control system for NFC-enabled smartphones based on a multi-level security architecture for smartphones. Our solution allows users to delegate their access rights and addresses the bandwidth constraints of NFC.

Our prototype captures electronic access to facilities, such as entrances and offices, and binds NFC operations to a software-isolated TrEE established on the widely used Android smartphone operating system. We provide a formal security analysis of our protocols and evaluated the performance of our solution.

21:17 [Pub][ePrint] Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification, by Xin Li

  Dodis and Wichs introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable extractor $nmExt$ has the property that $nmExt(x,y)$ appears uniform even given $y$ as well as $nmExt(x,A(y))$, for an arbitrary function $A$ with $A(y) \\neq y$. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary.

Previously, there are only two known constructions of non-malleable extractors \\cite{DLWZ11, CRS11}. Both constructions only work for $(n, k)$-sources with $k>n/2$. Interestingly, both constructions are also two-source extractors.

In this paper, we present a strong connection between non-malleable extractors and two-source extractors. The first part of the connection shows that non-malleable extractors can be used to construct two-source extractors. If the non-malleable extractor works for small min-entropy and has a short seed length with respect to the error, then the resulted two-source extractor beats the best known construction of two-source extractors. This partially explains why previous constructions of non-malleable extractors only work for sources with entropy rate $>1/2$, and why explicit non-malleable extractors for small min-entropy may be hard to get.

The second part of the connection shows that certain two-source extractors can be used to construct non-malleable extractors. Using this connection, we obtain the first construction of non-malleable extractors for $k < n/2$. Specifically, we give an unconditional construction for min-entropy $k=(1/2-\\delta)n$ for some constant $\\delta>0$, and a conditional (semi-explicit) construction that can potentially achieve $k=\\alpha n$ for any constant $\\alpha>0$.

We also generalize non-malleable extractors to the case where there are more than one adversarial seeds, and show a similar connection between the generalized non-malleable extractors and two-source extractors.

Finally, despite the lack of explicit non-malleable extractors for arbitrarily linear entropy, we give the first 2-round privacy amplification protocol with asymptotically optimal entropy loss and communication complexity for $(n, k)$ sources with $k=\\alpha n$ for any constant $\\alpha>0$. This dramatically improves previous results and answers an open problem in \\cite{DLWZ11}.

21:17 [Pub][ePrint] Universally Composable Key-Management, by Steve Kremer and Robert Künnemann and Graham Steel

  We present the first key-management functionality in the Universal Composability (UC) framework. It allows the enforcement of a wide range of security policies and can be extended by diverse key usage operations with no need to repeat the security proof. We illustrate its use by proving an implementation of a Security API secure with respect to arbitrary key-usage operations and explore a proof technique that allows the storage of cryptographic keys externally, a novel development in the UC framework.