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] Differentially Private Linear Algebra in the Streaming Model, by Jalaj Upadhyay

  The focus of this paper is on differential privacy of streaming data using sketch-based algorithms. Previous works, like Dwork {\\it et al.} (ICS 2010, STOC 2010), explored random sampling based streaming algorithms. We work in the well studied streaming model of computation, where the database is stored in the form of a matrix and a curator can access the database row-wise or column-wise.

Dwork {\\it et al.} (STOC 2010) gave impossibility result for any non-trivial query on a streamed data with respect to the user level privacy. Therefore, in this paper, we restrict our attention to the event level privacy. {We provide optimal, up to logarithmic factor, space differentially private mechanism in the streaming model for three basic linear algebraic tasks: matrix multiplication, linear regression, and low rank approximation, while incurring significantly less additive error}.

Our approach for matrix multiplication and linear regression has some similarities with Blocki {\\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013) on the superficial level, but there are some subtle differences. For example, they perform an affine transformation to convert the private matrix in to a set of $\\{\\sqrt{w/n},1\\}^n$ vectors for some appropriate $w$, while we perform an input perturbation that raises the singular value of the private matrix. %On a high level, the mechanism for linear regression and matrix multiplication can be seen as a private analogue of the known streaming algorithms. In order to get a streaming algorithm for low rank approximation, we have to reuse the random Gaussian matrix in a specific way. We prove that the resulting distribution also preserve differential privacy.

We do not make any assumptions, like singular value separation, as made in the earlier works of Hardt and Roth (STOC 2013) and Kapralov and Talwar (SODA 2013). Further, we do not assume normalized row as in the work of Dwork {\\it et al.} (STOC 2014). All our mechanisms, in the form presented, can also be computed in the distributed setting of Biemel, Nissim, and Omri (CRYPTO 2008).

00:17 [Pub][ePrint] Secure modular password authentication for the web using channel bindings, by Mark Manulis and Douglas Stebila and Nick Denham

  Secure protocols for password-based user authentication are well-studied in the cryptographic literature but have failed to see wide-spread adoption on the Internet; most proposals to date require extensive modifications to the Transport Layer Security (TLS) protocol, making deployment challenging. Recently, a few modular designs have been proposed in which a cryptographically secure password-based mutual authentication protocol is run inside a confidential (but not necessarily authenticated) channel such as TLS; the password protocol is bound to the established channel to prevent active attacks. Such protocols are useful in practice for a variety of reasons: security no longer relies on users\' ability to validate server certificates and can potentially be implemented with no modifications to the secure channel protocol library.

We provide a systematic study of such authentication protocols. Building on recent advances in modelling TLS, we give a formal definition of the intended security goal, which we call password-authenticated and confidential channel establishment (PACCE). We show generically that combining a secure channel protocol, such as TLS, with a password authentication protocol, where the two protocols are bound together using either the transcript of the secure channel\'s handshake or the server\'s certificate, results in a secure PACCE protocol. Our prototype based on TLS is available as a cross-platform client-side Firefox browser extension and a server-side web application which can easily be installed on deployed web browsers and servers.

00:17 [Pub][ePrint] Resizable Tree-Based Oblivious RAM, by Tarik Moataz and Travis Mayberry and Erik-Oliver Blass

  Although newly proposed, tree-based Oblivious RAM schemes are drastically more efficient than older techniques, they come with a significant drawback: an inherent dependence on a fixed-size database. This capability is vital for real-world use of Oblivious RAM since one of its most promising deployment scenarios is for cloud storage, where scalability and elasticity are crucial. We revisit the original construction by Shi et al. [16] and propose several ways to support both increasing and decreasing the ORAM\'s size with sublinear communication. We show that increasing capacity can be accomplished by adding leaf nodes to the tree, but that it must be done carefully in order to preserve the probabilistic integrity of the data structures. We also provide new, tighter bounds for the size of interior and leaf nodes in the scheme, saving bandwidth and storage over previous constructions. Finally, we define an oblivious pruning technique for removing leaf nodes and decreasing the size of the tree. We show that this pruning method is both secure and efficient.

00:17 [Pub][ePrint] Augmented Learning with Errors: The Untapped Potential of the Error Term, by Rachid El Bansarkhani and Özgür Dagdelen and Johannes Buchmann

  The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security.

To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem.

As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.

00:17 [Pub][ePrint] S-box pipelining using genetic algorithms for high-throughput AES implementations: How fast can we go?, by Lejla Batina and Domagoj Jakobovic and Nele Mentens and Stjepan Picek and Antonio de la Piedr

  In the last few years, several practitioners have proposed a

wide range of approaches for reducing the implementation area of the

AES in hardware. However, an area-throughput trade-off that undermines high-speed is not realistic for real-time cryptographic applications. In this manuscript, we explore how Genetic Algorithms (GAs) can be used for pipelining the AES substitution box based on composite field arithmetic. We implemented a framework that parses and analyzes a Verilog netlist, abstracts it as a graph of interconnected cells and generates circuit statistics on its elements and paths. With this information, the GA extracts the appropriate arrangement of Flip-Flops (FFs) that maximizes the throughput of the given netlist. In doing so, we show that it is possible to achieve a 50 % improvement in throughput with only an 18 % increase in area in the UMC 0.13 um low-leakage standard cell library.

00:17 [Pub][ePrint] Dealer-Leakage Resilient Verifiable Secret Sharing, by Ruxandra F. Olimid

  Verifiable Secret Sharing (VSS) guarantees that honest parties reconstruct a consistent secret even in the presence of a malicious dealer that distributes invalid shares. We empower the dishonest dealer and consider the case when he subliminally leaks information in valid shares, allowing an adversary to access the secret prior to the reconstruction phase. We define the concept of Dealer-Leakage Resilient Verifiable Secret Sharing (DLR-VSS) as a stronger notion of VSS that achieves security under this settings. We propose an efficient DLR-VSS and prove its properties in the semi-honest adversarial model.

00:17 [Pub][ePrint] Cube Attacks and Cube-attack-like Cryptanalysis on the Round-reduced Keccak Sponge Function, by Itai Dinur and Pawel Morawiecki and Josef Pieprzyk and Marian Srebrny and Michal Straus

  In this paper, we comprehensively study the resistance of keyed variants of SHA-3 (Keccak) against algebraic attacks. This analysis covers a wide range of key recovery, MAC forgery and other types of attacks, breaking up to 9 rounds (out of the full 24) of the Keccak internal permutation much faster than exhaustive search. Moreover, some of our attacks on the 6-round Keccak are completely practical and were verified on a desktop PC. Our methods combine cube attacks (an algebraic key recovery attack) and related algebraic techniques with structural analysis of the Keccak permutation. These techniques should be useful in future cryptanalysis of Keccak and similar designs.

Although our attacks break more rounds than previously published techniques, the security margin of Keccak remains large. For Keyak -- a Keccak-based authenticated encryption scheme -- the nominal number of rounds is 12 and therefore its security margin is smaller (although still sufficient).

21:17 [Pub][ePrint] Protecting Encrypted Cookies from Compression Side-Channel Attacks, by Janaka Alawatugoda and Douglas Stebila and Colin Boyd

  Compression is desirable for network applications as it saves bandwidth; however, when data is compressed before being encrypted, the amount of compression leaks information about the amount of redundancy in the plaintext. This side channel has led to successful real-world attacks (the CRIME and BREACH attacks) on web traffic protected by the Transport Layer Security (TLS) protocol. The general guidance in light of these attacks has been to disable compression, preserving confidentiality but sacrificing bandwidth. In this paper, we examine two techniques---heuristic separation of secrets and fixed-dictionary compression---for enabling compression while protecting high-value secrets, such as cookies, from attack. We model the security offered by these techniques and report on the amount of compressibility that they can achieve.

06:31 [Event][New] IoTPTS 2015: ASIACCS Workshop on IoT Privacy, Trust, and Security

  Submission: 7 January 2015
Notification: 31 January 2015
From April 14 to April 14
Location: Singapore, Singapore
More Information:

21:17 [Pub][ePrint] Crypto-analyses on \"secure and efficient privacy-preserving public auditing scheme for cloud storage\", by Yalin Chen and Jue-Sam Chou*

  Recently, Worku et al. pointed out that the work \"privacy-preserving public auditing for data storage security in cloud computing\" proposed by Wang et al. is insecure and their second work \"privacy- preserving public auditing for secure cloud the storage\" is inefficient. Thus, they offered a secure and efficient-privacy public auditing scheme for cloud storage. They claimed that their system is provably secure in the random oracle model and the operation is effective. However, after crypto-analysis, we found that the scheme cannot reach the security goal, it has the existential forgery attack. We, therefore, alter it to incorporate the desired privacy preserving requirement, which is very significant in a privacy-preserving public auditing protocol for cloud storage.

18:17 [Pub][ePrint] A comprehensive empirical comparison of parallel ListSieve and GaussSieve, by Artur Mariano and Ozgur Dagdelen and Christian Bischof

  The security of lattice-based cryptosystems is determined by

the performance of practical implementations of, among others, algo-

rithms for the Shortest Vector Problem (SVP).

In this paper, we conduct a comprehensive, empirical comparison of two

SVP-solvers: ListSieve and GaussSieve. We also propose a practical par-

allel implementation of ListSieve, which achieves super-linear speedups

on multi-core CPUs, with efficiency levels as high as 183%. By compar-

ing our implementation with a parallel implementation of GaussSieve, we

show that ListSieve can, in fact, outperform GaussSieve for a large num-

ber of threads, thus answering a question that was still open to this day.