International Association for Cryptologic Research

# IACR News Central

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-04
06:17 [Pub][ePrint]

In this paper, we construct a fully homomorphic encryption (FHE) scheme over integers with the message space $Z_Q$ for any prime $Q$. Even for the binary case $Q=2$, our decryption circuit has a smaller degree than that of the previous scheme; the multiplicative degree is reduced from $O(\\lambda (\\log \\lambda)^2)$ to $O(\\lambda)$, where $\\lambda$ is the security parameter. We also extend our FHE scheme to a batch FHE scheme.

2014-10-03
10:28 [Job][Update]

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.

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

10:28 [Job][New]

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.

* 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]

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]

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]

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]

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]

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]

Submission: 27 October 2014
From December 8 to December 10
Location: Trondheim, Norway

2014-09-30
15:17 [Pub][ePrint]

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]

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

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.