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

00:17 [Pub][ePrint] Machine-Generated Algorithms, Proofs and Software for the Batch Verification of Digital Signature Schemes, by Joseph A. Akinyele and Matthew Green and Susan Hohenberger and Matthew W. Pagano

  As devices everywhere increasingly communicate with each other, many security applications will require low-bandwidth signatures that can be processed quickly. Pairing-based signatures can be very short, but are often costly to verify. Fortunately, they also tend to have efficient batch verification algorithms. Finding these batching algorithms by hand, however, can be tedious and error prone.

We address this by presenting AutoBatch, an automated tool for generating batch verification code in either Python or C++ from a high level representation of a signature scheme. AutoBatch outputs both software and, for transparency, a LaTeX file describing the batching algorithm and arguing that it preserves the unforgeability of the original scheme.

We tested AutoBatch on over a dozen pairing-based schemes to demonstrate that a computer could find competitive batching solutions in a reasonable amount of time. Indeed, it proved highly competitive. In particular, it found an algorithm that is significantly faster than a batching algorithm from Eurocrypt 2010. Another novel contribution is that it handles cross-scheme batching, where it searches for a common algebraic structure between two distinct schemes and attempts to batch them together.

In this work, we expand upon an extended abstract on AutoBatch appearing in ACM CCS 2012 in a number of ways. We add a new loop-unrolling technique and show that it helps cut the batch verification cost of one scheme by roughly half. We describe our pruning and search algorithms in greater detail, including pseudocode and diagrams. All experiments were also re-run using the RELIC pairing library. We compare those results to our earlier results using the MIRACL library, and discuss why RELIC outperforms MIRACL in all but two cases. Automated proofs of several new batching algorithms are also included.

AutoBatch is a useful tool for cryptographic designers and implementors, and to our knowledge, it is the first attempt to outsource to machines the design, proof writing and implementation of signature batch verification schemes.

00:17 [Pub][ePrint] Distinguishing Attacks on RC4 and A New Improvement of the Cipher, by Jing Lv and Bin Zhang and Dongdai Lin

  RC4, designed by Rivest in 1987, is the most widely deployed stream cipher in practical applications. In this paper, two new class of statistical biases inherent in RC4 are depicted and it is shown that the RC4 keystream is distinguishable from random no matter how many initial bytes have been dumped.

RC4A, proposed by Paul and Preneel at FSE 2004 to strengthen the security of RC4, is also found to be vulnerable to similar attacks. Instead, a new pseudorandom bit generator RC4B is proposed, which is believed to provide better immunity against the known attacks.

00:17 [Pub][ePrint] A generic construction for voting correctness at minimum cost - Application to Helios, by Veronique Cortier and David Galindo and Stephane Glondu and Malika Izabachene

  Most voting schemes aim at providing verifiability: voters should be able to check that their ballots did contribute to the outcome (individual verifiability) and that the tallying authorities did their job properly (universal verifiability). Surprisingly, verifiability still does not answer a very simple and natural question: how can I be sure that the published result corresponds to the (sum of) intended votes of the voters? This property is called correctness by Juels, Catalano, and Jakobsson. Actually, even a prominent voting system like Helios does not achieve correctness in the case of a dishonest bulletin board, since it may add ballots.

We generalize the aforementioned definition of correctness to account for a malicious bulletin board (full correctness) and we provide a generic construction that transforms a correct voting scheme into a fully correct voting scheme. This construction simply requires to send credentials to the voters, with no additional infrastructure. We further provide a simple and natural criteria that implies voting correctness, which can then be turned into full correctness due to our construction. As an application, we build a variant of Helios that is both fully correct, verifiable and private.

Real-world elections often require threshold cryptosystems so that any t out of l trustees can proceed to tallying. We describe a fully distributed (with no dealer) threshold cryptosystem suitable for Helios (in particular, suitable to partial decryption). In doing so we happen to revisit the seminal multi-authority election system from Cramer, Gennaro and Schoenmakers. Altogether, we provide the first proof of privacy, verifiability and correctness for a fully distributed Helios voting scheme (and its enhanced version with credentials), together with its detailed description. This also implies, to our knowledge, the first formal proofs of privacy, verifiability and correctness for the scheme by Cramer et al. Last but not least, we provide an open source implementation of our variant of Helios.

18:17 [Pub][ePrint] Fast Collision Attack on MD5, by Tao Xie and Fanbao Liu and Dengguo Feng

  We presented the first single block collision attack on MD5 with complexity of $2^{47}$ MD5 compressions and posted the challenge for another completely new one in 2010. Last year, Stevens presented a single block collision attack to our challenge, with complexity of $2^{50}$ MD5 compressions. We really appreciate Stevens\'s hard work. However, it is a pity that he had not found even a better solution than our original one, let alone a completely new one and the very optimal solution that we preserved and have been hoping that someone can find it, whose collision complexity is about $2^{41}$ MD5 compressions. In this paper, we propose a method how to choose the optimal input difference for generating MD5 collision pairs. First, we divide the sufficient conditions into two classes: strong conditions and weak conditions, by the degree of difficulty for condition satisfaction. Second, we prove that there exist strong conditions in only 24 steps (one and a half rounds) under specific conditions, by utilizing the weaknesses of compression functions of MD5, which are difference inheriting and message expanding. Third, there should be no difference scaling after state word $q_{25}$ so that it can result in the least number of strong conditions in each differential path, in such a way we deduce the distribution of strong conditions for each input difference pattern. Finally, we choose the input difference with the least number of strong conditions and the most number of free message words. We implement the most efficient 2-block MD5 collision attack, which needs only about $2^{18}$ MD5 compressions to find a collision pair, and show a single-block collision attack with complexity $2^{41}$.

18:17 [Pub][ePrint] Confined Guessing: New Signatures From Standard Assumptions, by Florian Böhl and Dennis Hofheinz and Tibor Jager and Jessica Koch and Christoph Striecks

  We put forward a new technique to construct very efficient and compact signature schemes. Our technique combines several instances of an only mildly secure signature scheme to obtain a fully secure scheme. Since the mild security notion we require is much easier to achieve than full security, we can combine our strategy with existing techniques to obtain a number of interesting new (stateless and fully secure) signature schemes. Concretely, we get:

* A scheme based on the computational Diffie-Hellman (CDH) assumption in pairing-friendly groups. Signatures contain O(1) and verification keys O(log(k)) group elements, where k is the security parameter. Our scheme is the first CDH-based scheme with such compact verification keys.

* A scheme based on the (non-strong) RSA assumption in which both signatures and verification keys contain O(1) group elements. Our scheme is significantly more efficient than existing RSA-based schemes.

* A scheme based on the Short Integer Solutions (SIS) assumption. Signatures contain O(log(k) m) and verification keys O(n m) Z_p-elements, where p may be polynomial in k, and n, m denote the usual SIS matrix dimensions. Compared to state-of-the-art SIS-based schemes, this gives very small verification keys, at the price of slightly larger signatures.

In all cases, the involved constants are small, and the arising schemes provide significant improvements upon state-of-the-art schemes. The only price we pay is a rather large (polynomial) loss in the security reduction. However, this loss can be significantly reduced at the cost of an additive term in signature and verification key size.

18:17 [Pub][ePrint] On the Applicability of Time-Driven Cache Attacks on Mobile Devices (Extended Version), by Raphael Spreitzer and Thomas Plos

  Cache attacks are known to be sophisticated attacks against cryptographic implementations on desktop computers. Recently, also investigations of such attacks on testbeds with processors that are employed in mobile devices have been done. In this work we investigate the applicability of Bernstein\'s timing attack and the cache-collision attack by Bogdanov et al. in real environments on three state-of-the-art mobile devices. These devices are: an Acer Iconia A510, a Google Nexus S, and a Samsung Galaxy SIII. We show that T-table based implementations of the Advanced Encryption Standard (AES) leak enough timing information on these devices in order to recover parts of the used secret key using Bernstein\'s timing attack. We also show that systems with a cache-line size larger than 32 bytes exacerbate the cache-collision attack by Bogdanov et al.

06:17 [Pub][ePrint] Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries, by David Cash and Stanislaw Jarecki and Charanjit Jutla and Hugo Krawczyk and Marcel Rosu and Michael Steiner

  This work presents the design, analysis and implementation of the first sub-linear searchable symmetric encryption (SSE) protocol that supports conjunctive search and general Boolean queries on symmetrically-encrypted data and that scales to very large data sets and arbitrarily-structured data including free text search. To date, work in this area has focused mainly on single-keyword search. For the case of conjunctive search, prior SSE constructions required work linear in the total number of documents in the database and provided good privacy only for structured attribute-value data, rendering these solutions too slow and inflexible for large practical databases.

In contrast, our solution provides a realistic and practical trade-off between performance and privacy by efficiently supporting very large databases at the cost of moderate and well-defined leakage to the outsourced server (leakage is in the form of data access patterns, never as direct exposure of plaintext data or searched values). A key aspect of our protocols is that it allows the searcher to pivot its conjunctive search on the estimated least frequent keyword in the conjunction. We show that a Decisional Diffie-Hellman (DDH) based pseudo-random function can be used not just to implement search tokens but also to hide query access pattern of non-pivot, and hence possibly highly frequent, keywords in conjunctive queries. We present a formal cryptographic analysis of the privacy and security of our protocols and establish precise upper bounds on the allowed leakage.

To demonstrate the real-world practicality of our approach, we provide performance results of a prototype applied to several large representative data sets.

18:17 [Pub][ePrint] On secure embedded token design (Long Version) -- Quasi-looped Yao circuits and bounded leakage, by Simon Hoerder and Kimmo Järvinen and Dan Page

  Within a broader context of mobile and embedded computing, the design of practical, secure tokens that can store and/or process security-critical information remains an ongoing challenge. One aspect of this challenge is the threat of information leakage through side-channel attacks, which is exacerbated by any resource constraints. Although any countermeasure can be of value, it seems clear that approaches providing robust guarantees are most attractive. Along these lines, this paper extends previous work on use of Yao circuits via two contributions. First, we show how careful analysis can fix the maximum number of traces acquired during a DPA attack, effectively bounding leakage from a Yao-based token: for a low enough bound, the token can therefore be secured via conventional (potentially less robust) countermeasures. To achieve this we use modularised Yao circuits, which also support our second contribution: the first Yao-based mplementation of a secure authentication payload, namely HMAC based on SHA.

15:17 [Pub][ePrint] A New Security and Privacy Framework for RFID In Cloud Computing, by Süleyman Kardas, Serkan Çelik, Muhammed Ali Bingöl, Albert Levi

  RFID is a leading technology that has been

rapidly deployed in several daily life applications such as

payment, access control, ticketing, and e-passport, which

requires strong security and privacy mechanisms. However,

RFID systems commonly have limited computational capacity,

poor resources and inefficient data management. Hence there

is a demanding urge to address these issues in the light

of some mechanism which can make the technology excel.

Cloud computing is one of the fastest growing segments of

IT industry which can provide a cost effective technology

and information solution to handling and using data collected

with RFID. As more and more information on individuals and

companies is placed in the cloud, concerns are beginning to

grow about just how safe an environment it is. Therefore, while

integrating RFID into the cloud, the security and privacy of

the tag owner must be considered.

Motivated by this need, we first provide a security and

privacy model for RFID technology in the cloud computing. In

this model, we first define the capabilities of the adversary and

then give the definitions of the security and privacy. After that

we propose an example of an RFID authentication protocol

in the cloud computing. We prove that the proposal is narrow

strong private+ in our privacy model.

15:17 [Pub][ePrint] On generalized semi-bent (and partially bent) Boolean functions, by Brajesh Kumar Singh

  In this paper, we obtain a characterization of generalized Boolean functions based on spectral analysis. We investigate a relationship between the Walsh-Hadamard spectrum and $\\sigma_f$, the sum-of-squares-modulus indicator (SSMI) of the generalized Boolean function. It is demonstrated that $\\sigma_f = 2^{2n + s}$ for every $s$-plateaued generalized Boolean function in $n$ variables. Two classes of generalized semi-bent Boolean functions are constructed.% and it is demonstrated that their SSMI is over generalized $s$-plateaued Boolean functions is $2^{2n + s}$. We have constructed a class of generalized semi-bent functions in $(n+1)$ variables from generalized semi-bent functions in $n$ variables and identify a subclass of it for which $\\sigma_f$ and $\\triangle_{f}$ both have optimal value. Finally, some construction on generalized partially bent Boolean functions are given.

15:17 [Pub][ePrint] Single Password Authentication, by Tolga Acar and Mira Belenkiy and Alptekin Küpçü

  Users frequently reuse their passwords when authenticating to various online services. Combined with the use of weak passwords or honeypot/phishing attacks, this brings high risks to the security of the user\'s account information. In this paper, we propose several protocols that can allow a user to use a single password to authenticate to multiple services securely. All our constructions provably protect the user from dictionary attacks on the password, and cross-site impersonation or honeypot attacks by the online service providers.

Our solutions assume the user has access to either an untrusted online cloud storage service (as per Boyen [14]), or a mobile storage device that is trusted until stolen. In the cloud storage scenario, we consider schemes that optimize for either storage server or online service performance, as well as anonymity and unlinkability of the user\'s actions. In the mobile storage scenario, we minimize the assumptions we make about the capabilities of the mobile device: we do not assume synchronization, tamper resistance, special or expensive hardware, or extensive cryptographic capabilities. Most importantly, the user\'s password remains secure even after the mobile device is stolen. Our protocols provide another layer of security against malware and phishing. To the best of our knowledge, we are the first to propose such various and provably secure password-based authentication schemes. Lastly, we argue that our constructions are relatively easy to deploy, especially if a few single sign-on services (e.g., Microsoft, Google, Facebook) adopt our proposal.