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:

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

2014-10-03
10:28 [Job][New] Lecturer/Senior Lecturer (Chancellor\'s Fellowship), University of Strathclyde, UK

  The University of Strathclyde recently announced another round of the Chancellor\'s Fellowship Scheme. This round aims to appoint up to 20 new early career academic staff members in areas of strategic priority (including computer security). The appointment will be made at lecturer or senior lecturer level. Candidates from all areas of computer security are welcome.

The benefits of the Chancellor\'s Fellowship include:

* Access to start up research funding, as appropriate for the discipline.

* A reduced teaching and administration load for the first stages of the Fellowship to allow you to concentrate on building your research portfolio.

* The Strathclyde Fellow will benefit from the normal academic probationary process, including completion of the Postgraduate Certificate in Advanced Academic Studies (Academic Practice).

* Bespoke learning and development events tailored for the Fellowship.

* Where appropriate, there will be the opportunity to gain experience working with external partner organisations through secondments and joint projects.

* Where appropriate, there will be an opportunity to participate in funded visits to international partners to further collaborative initiatives.





2014-10-01
06:17 [Pub][ePrint] Fully Secure and Succinct Attribute Based Encryption for Circuits from Multi-linear Maps, by Nuttapong Attrapadung

  We propose new fully secure attribute based encryption (ABE) systems for polynomial-size circuits in both key-policy and ciphertext-policy flavors. All the previous ABE systems for circuits were proved only selectively secure. Our schemes are based on asymmetric graded encoding systems in composite-order settings. The assumptions consist of the Subgroup Decision assumptions and two assumptions which are similar to Multi-linear Decisional Diffie-Hellman assumption (but more complex) and are proved to hold in the generic graded encoding model. Both of our systems enjoy succinctness: key and ciphertext sizes are proportional to their corresponding circuit and input string sizes. Our ciphertext-policy ABE for circuits is the first to achieve succinctness, and the first that can deal with unbounded-size circuits (even among selectively secure systems). We develop new techniques for proving co-selective security of key-policy ABE for circuits, which is the main ingredient for the dual-system encryption framework that uses computational arguments for enforcing full security.



06:17 [Pub][ePrint] Obfuscating Low-Rank Matrix Branching Programs, by Amit Sahai and Mark Zhandry

  In this work, we seek to extend the capabilities of the \"core obfuscator\" from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, and applies to matrix branching programs. All previous works, however, limited the applicability of such core obfuscators to matrix branching programs where each matrix was of full rank. As we illustrate by example, this limitation is quite problematic, and intuitively limits the core obfuscator to obfuscating matrix branching programs that cannot \"forget.\" At a technical level, this limitation arises in previous work because all previous work relies on Kilian\'s statistical simulation theorem, which is false when applied to matrices not of full rank.

In our work, we build the first core obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian\'s statistical simulation theorem. Furthermore, our obfuscator achieves two other notable advances over previous work:

- Our construction allows for non-square matrices of arbitrary dimensions. We also show that this flexibility yields concrete efficiency gains.

- Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit of output.

Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains even in applications not directly using obfuscation.



06:17 [Pub][ePrint] Automated Analysis and Synthesis of Block-Cipher Modes of Operation, by Alex J. Malozemoff and Jonathan Katz and Matthew D. Green

  Block ciphers such as AES are deterministic, keyed functions that operate on small, fixed-size blocks. Block-cipher \\emph{modes of operation} define a mechanism for probabilistic encryption of arbitrary length messages using any underlying block cipher. A mode of operation can be proven secure (say, against chosen-plaintext attacks) based on the assumption that the underlying block cipher is a pseudorandom function. Such proofs are complex and error-prone, however, and must be done from scratch whenever a new mode of operation is developed.

We propose an \\emph{automated} approach for the security analysis of block-cipher modes of operation based on a ``local\'\' analysis of the steps carried out by the mode when handling a \\emph{single} message block. We model these steps as a directed, acyclic graph, with nodes corresponding to instructions and edges corresponding to intermediate values. We then introduce a set of \\emph{labels} and \\emph{constraints} on the edges, and prove a meta-theorem showing that any mode for which there exists a labeling of the edges satisfying these constraints is secure (against chosen-plaintext attacks). This allows us to reduce security of a given mode to a constraint-satisfaction problem, which in turn can be handled using an SMT solver. We couple our security-analysis tool with a routine that automatically generates viable modes; together, these allow us to synthesize hundreds of secure modes.



06:17 [Pub][ePrint] Lock-free GaussSieve for Linear Speedups in Parallel High Performance SVP Calculation, by Artur Mariano, Shahar Timnat and Christian Bischof

  Lattice-based cryptography became a hot-topic in the past years because it seems to be quantum immune, i.e., resistant to attacks operated with quantum computers. The security of lattice-based cryptosystems is determined by the hardness of certain lattice problems, such as the Shortest Vector Problem (SVP). Thus, it is of prime importance to study how efficiently SVP-solvers can be implemented.

This paper presents a parallel shared-memory implementation of the GaussSieve algorithm, a well known SVP-solver. Our implementation achieves almost linear and linear speedups with up to 64 cores, depending on the tested scenario, and delivers better sequential performance than any other disclosed GaussSieve implementation. In this paper, we show that it is possible to implement a highly scalable version of GaussSieve on multi-core CPU-chips. The key features of our implementation are a lock-free singly linked list, and hand-tuned, vectorized code. Additionally, we propose an algorithmic optimization that leads to faster convergence.



06:17 [Pub][ePrint] How to Obfuscate Programs Directly, by Joe Zimmerman

  We propose a new way to obfuscate programs, using composite-order multilinear maps. Our construction operates directly on straight-line programs (arithmetic circuits), rather than converting them to matrix branching programs as in other known approaches. This yields considerable efficiency improvements. For an NC1 circuit of size $s$ and depth $d$, with $\\n$ inputs, we require only $O(d^2s^2 + \\n^2)$ multilinear map operations to evaluate the obfuscated circuit---as compared with other known approaches, for which the number of operations is exponential in $d$. We prove virtual black-box (VBB) security for our construction in a generic model of multilinear maps of hidden composite order, extending previous models for the prime-order setting.

Our scheme works either with \"noisy\" multilinear maps, which can only evaluate expressions of degree $\\lambda^c$ for pre-specified constant $c$; or with \"clean\" multilinear maps, which can evaluate arbitrary expressions. The \"noisy\" variant can be instantiated at present with the Coron-Lepoint-Tibouchi scheme, while the existence of \"clean\" maps is still unknown. With known \"noisy\" maps, our new obfuscator applies only to NC1 circuits, requiring the additional assumption of FHE in order to bootstrap to P/poly (as in other obfuscation constructions).

From \"clean\" multilinear maps, on the other hand (whose existence is still open), we present the first approach that would achieve obfuscation for P/poly directly, without FHE. We also introduce the concept of succinct obfuscation, in which the obfuscation overhead size depends only on the length of the input and of the secret part of the circuit. Using our new techniques, along with the assumption that factoring is hard on average, we show that \"clean\" multilinear maps imply succinct obfuscation for P/poly. For the first time, the only remaining obstacle to implementable obfuscation in practice is the noise growth in known, \"noisy\" multilinear maps. Our results demonstrate that the question of \"clean\" multilinear maps is not a technicality, but a central open problem.



01:22 [Event][New] PASSWORDS '14: The 7th International Conference on Passwords, Norway

  Submission: 27 October 2014
Notification: 10 November 2014
From December 8 to December 10
Location: Trondheim, Norway
More Information: https://passwordscon.org/norway-2014-cfp/




2014-09-30
15:17 [Pub][ePrint] Cryptanalysis of Reduced-round SIMON32 and SIMON48, by Qingju Wang and Zhiqiang Liu and Kerem Varici and Yu Sasaki and Vincent Rijmen and Yosuke Todo

  SIMON family is one of the recent lightweight block cipher designs introduced by NSA. So far there have been several cryptanalytic results on this cipher by means of differential, linear and impossible differential cryptanalysis.

In this paper, we study the security of SIMON32, SIMON48/72 and SIMON48/96 by using integral, zero-correlation linear and impossible differential cryptanalysis.

Firstly, we present a novel experimental approach to construct the best known integral distinguishers of SIMON32. The small block size, 32 bits, of SIMON32 enables us to experimentally find a 15-round integral distinguisher, based on which we present a key recovery attack on 21-round SIMON32, while previous best results published in FSE 2014 only achieved 19 rounds. Actually, our approach provides a very efficient way to elaborate good integral distinguishers of block ciphers with small block size.

Moreover, by applying the divide-and-conquer technique delicately, we attack 20-round SIMON32, 20-round SIMON48/72 and 21-round SIMON48/96 based on 11 and 12-round zero-correlation linear hulls of SIMON32 and SIMON48 respectively. The results for SIMON32 and SIMON48/96 are better than the known results published in FSE 2014.

Finally, we propose impossible differential attacks on 18-round SIMON32, 18-round SIMON48/72 and 19-round SIMON48/96,

which significantly improve the previous impossible differential attacks. Our analysis together with the previous results show that SIMON maintains enough security margin even if

various approaches of cryptanalysis are considered.



15:17 [Pub][ePrint] Access Control in Publicly Verifiable Outsourced Computation, by James Alderman and Carlos Cid and Jason Crampton and Christian Janson

  Publicly Verifiable Outsourced Computation (PVC) allows devices with restricted resources

to delegate expensive computations to more powerful external servers, and to verify

the correctness of results. Whilst this is highly beneficial in many situations, it also increases

the visibility and availability of potentially sensitive data, and thus we may wish to limit the

set of entities with access to input data and results. Additionally, within an organization it

is extremely unlikely that every user would have uncontrolled access to all functionality. It

is also not always reasonable to publish the results of a sensitive computation. Thus there

is a need to apply access control mechanisms in PVC environments.

In this work, we define a new framework for Publicly Verifiable Outsourced Computation

with Access Control (PVC-AC) that applies cryptographic enforcement mechanisms to address

these concerns, and we provide a provably secure instantiation using Key Assignment

Schemes. We also discuss example policies of interest in this setting.



15:17 [Pub][ePrint] On the Privacy Provisions of Bloom Filters in Lightweight Bitcoin clients, by Arthur Gervais and Ghassan O. Karame and Damian Gruber and Srdjan Capkun

  Lightweight Bitcoin clients are gaining increasing adoption among Bitcoin users, owing to their reduced resource and bandwidth consumption. These clients support a simplified payment verification (SPV) mode as they are only required to download and verify a part of the block chain -- thus supporting the usage of Bitcoin on constrained devices, such as smartphones. SPV clients rely on Bloom filters to receive transactions that are relevant to their local wallet. These filters embed all the Bitcoin addresses used by the SPV clients, and are outsourced to more powerful Bitcoin nodes which then only forward to those clients transactions relevant to their outsourced Bloom filters.

In this paper, we explore the privacy of existing SPV clients. We show analytically and empirically that the reliance on Bloom filters within existing SPV clients leaks considerable information about the addresses of Bitcoin users. Our results show that an SPV client who uses a modest number of Bitcoin addresses (e.g., < 20) risks revealing almost all of his addresses. We also show that this information leakage is further exacerbated when users restart their SPV clients and/or when the adversary has access to more than one Bloom filter pertaining to the same SPV client. Motivated by these findings, we propose an efficient countermeasure to enhance the privacy of users which rely on SPV clients; our proposal can be directly integrated within existing SPV client implementations.



15:17 [Pub][ePrint] One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin, by Jens Groth and Markulf Kohlweiss

  We construct a 3-move public coin special honest verifier zero-knowledge proof, a so-called Sigma-protocol, for a list of commitments having at least one commitment that opens to 0. It is not required for the prover to know openings of the other commitments. The proof system is efficient, in particular in terms of communication requiring only the transmission of a logarithmic number of commitments.

We use our proof system to instantiate both ring signatures and zerocoin, a novel mechanism for bitcoin privacy.

We use our Sigma-protocol as a (linkable) ad-hoc group identification scheme where the users have public keys that are commitments and demonstrate knowledge of an opening for one of the commitments to unlinkably identify themselves (once) as belonging to the group. Applying the Fiat-Shamir transform on the group identification scheme gives rise to ring signatures, applying it to the linkable group identification scheme gives rise to zerocoin.

Our ring signatures are very small compared to other ring signature schemes and we only assume the users\' secret keys to be the discrete logarithms of single group elements so the setup is quite realistic. Similarly, compared with the original zerocoin protocol we rely on a weak cryptographic assumption and do not require a trusted setup.

A third application of our Sigma protocol is an efficient proof of membership of a secret committed value belonging to a public list.