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

Identity Based Encryption (IBE) has been constructed from bilinear pairings, lattices and quadratic residuosity. The latter is an attractive basis for an IBE owing to the fact that it is a well-understood hard problem from number theory. Cocks constructed the first such scheme, and subsequent improvements have been made to achieve anonymity and improve space efficiency. However, the anonymous variants of Cocks\' scheme thus far are all less efficient than the original. In this paper, we present a new universally-anonymous IBE scheme based on the quadratic residuosity problem. Our scheme has better performance than the universally anonymous scheme from Ateniese and Gasti (CT-RSA 2009) at the expense of more ciphertext expansion. Another contribution of this paper is a modification to a variant of the space-efficient scheme by Boneh, Gentry and Hamburg (FOCS 07) that results in an IND-ID-CPA secure IBE scheme with comparable efficiency to Cocks, but with reduced ciphertext expansion.

06:17 [Pub][ePrint]

Program obfuscation is the process of making a program \"unintelligible\" without changing the program\'s underlying input/output behavior. Although there is a long line of work on heuristic techniques for obfuscation, such approaches do not provide any cryptographic guarantee on their effectiveness. A recent result by Garg et al. (FOCS 2013), however, shows that cryptographic program obfuscation is indeed possible based on a new primitive called a \\emph{graded encoding scheme}.

In this work, we present the first implementation of such an obfuscator. We describe several challenges and optimizations we made along the way, present a detailed evaluation of our implementation, and discuss research problems that need to be addressed before such obfuscators can be used in practice.

06:17 [Pub][ePrint]

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O\'Neill (CRYPTO 2007), is an important database encryption technique which allows quick, logarithmic-time, search over encrypted data items. The technique is most effective in scenarios where frequent search queries are performed over a huge database of highly sensitive, yet unpredictable, data items such as credit card or social security numbers. Such databases, however, are also the ideal target for hackers since even partial data leaks may reveal significantly damaging information to the attacker.

Motivated by the goal of limiting the damage in such scenarios, we apply the ideas from leakage resilient cryptography to deterministic public-key encryption (D-PKE). We formulate appropriate security notions for D-PKE in the presence of leakage, and present constructions that achieve them in the standard model. We work in the *continual* leakage model, where the secret-key is updated at regular intervals and an attacker can learn arbitrary but bounded leakage during each time interval. We, however, do not consider leakage during the updates. Our main construction is based on the (standard) linear assumption in bilinear groups, tolerating up to $0.5-o(1)$ fraction of arbitrary leakage. The leakage rate can be improved to $1-o(1)$ by relying on the SXDH assumption.

At a technical level, we propose and construct a continual leakage resilient\'\' version of the *all-but-one* lossy trapdoor functions, introduced by Peikert and Waters (STOC 2008). Our formulation and construction of leakage-resilient lossy-TDFs is of independent general interest for leakage-resilient cryptography.

06:17 [Pub][ePrint]

The topic of this paper is collusion resistant watermarking, a.k.a. traitor tracing, in particular bias-based traitor tracing codes as introduced by G.Tardos in 2003. The past years have seen an ongoing effort to construct efficient high-performance decoders for these codes.

In this paper we construct a score system from the Neyman-Pearson hypothesis test (which is known to be the most powerful test possible)

into which we feed all the evidence available to the tracer, in particular the codewords of *all* users. As far as we know, until now similar efforts have taken into consideration only the codeword of a single user, namely the user under scrutiny.

The Neyman-Pearson score needs as input the attack strategy of the colluders, which typically is not known to the tracer.

We insert the Interleaving attack, which plays a very special role in the theory of bias-based traitor tracing by virtue of being part of the asymptotic (i.e. large coalition size) saddlepoint solution.

The score system obtained in this way is universal: effective not only against the Interleaving attack, but against all other attack

strategies as well. Our score function for one user depends on the other users\' codewords in a very simple way: through the symbol tallies, which are easily computed.

We present bounds on the False Positive and False Negative error probability, yielding a.o. a prescription for setting the accusation threshold. We investigate the probability distribution of the score.

Finally we apply our construction to the area of (medical) Group Testing, which is related to traitor tracing.

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.