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

13:17 [Pub][ePrint] Aggregate and Verifiably Encrypted Signatures from Multilinear Maps Without Random Oracles, by Markus Rückert and Dominique Schroeder

  Aggregate signatures provide bandwidth-saving aggregation of ordinary signatures. We present the first unrestricted instantiation in the standard model, Moreover, our construction yields a multisignature scheme where a single message is signed by a number of signers. Our second result is an application to verifiably encrypted signatures. There, signers encrypt their signature under the public key of a trusted third party and output a proof that the signature is inside. Upon dispute between signer and verifier, the trusted third party is able to recover the signature. These schemes are provably secure in the standard model.

13:17 [Pub][ePrint] Rate-Limited Secure Function Evaluation: Definitions and Constructions, by Özgür Dagdelen and Payman Mohassel and Daniele Venturi

  We introduce the notion of rate-limited secure function evaluation (RL-SFE). Loosely speaking, in an RL-SFE protocol participants can monitor and limit the number of distinct inputs (i.e., rate) used by their counterparts in multiple executions of an SFE, in a private and verifiable manner. The need for RL-SFE naturally arises in a variety of scenarios: e.g., it enables service providers to ``meter\'\' their customers\' usage without compromising their privacy, or can be used to prevent oracle attacks against SFE constructions.

We consider three variants of RL-SFE providing different levels of security. As a stepping stone, we also formalize the notion of commit-first SFE (cf-SFE) wherein parties are committed to their inputs before each SFE execution. We provide compilers for transforming any cf-SFE protocol into each of the three RL-SFE variants. Our compilers are accompanied with simulation-based proofs of security in the standard model and show a clear tradeoff between the level of security offered and the overhead required. Moreover, motivated by the fact that in many client-server applications clients do not keep state, we also describe a general approach for transforming the resulting RL-SFE protocols into stateless ones.

As a case study, we take a closer look at the oblivious polynomial evaluation (OPE) protocol of Hazay and Lindell, show that it is commit-first and instantiate efficient rate-limited variants of it.

13:17 [Pub][ePrint] Nonlinear cryptanalysis of reduced-round Serpent and metaheuristic search for S-box approximations., by James McLaughlin and John A. Clark

  We utilise a simulated annealing algorithm to find several nonlinear approximations to various S-boxes which can be used to replace the linear approximations in the outer rounds of existing attacks. We propose three variants of a new nonlinear cryptanalytic algorithm which overcomes the main issues that prevented the use of nonlinear approximations in previous research, and we present the statistical frameworks for calculating the complexity of each version. We present new attacks on 11-round Serpent with better data complexity than any other known-plaintext or chosen-plaintext attack, and with the best overall time complexity for a 256-bit key.

13:17 [Pub][ePrint] A New Practical Identity-Based Encryption System, by Jong Hwan Park and Dong Hoon Lee

  We present a new practical Identity-Based Encryption (IBE) system that can be another candidate for standard IBE techniques. Our construction is based on a new framework for realizing an IBE trapdoor from pairing-based groups, which is motivated from the `two equation\' revocation technique suggested by Lewko, Sahai, and Waters. The new framework enables our IBE system to achieve a tight security reduction to the standard Decision Bilinear Diffie-Hellman assumption. Due to its the tightness, our system can take as input the shorter size of security parameters than the previous practical BF, SK, and BB$_{1}$ systems, which provides better efficiency to our system in terms of computational cost. With appropriate parametrization at the current 80-bit security level, our IBE system can obtain 11 times faster decryption than the previous ones and 77 times faster encryption than the BF system. We prove that our system is fully secure against chosen ciphertext attacks in the random oracle model. From computational variant of Naor\'s observation, we can also suggest a new signature scheme that features a tight security reduction to the Computational Diffie-Hellman assumption and provides strong unforgeability simultaneously.

10:17 [Pub][ePrint] Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security, by Kai-Min Chung and Rafael Pass and Karn Seth


The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS\'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques.

The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS\'12) instead requires the existence of an Oblivious Transfer protocol.

In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

10:17 [Pub][ePrint] Achieving Anonymity Against Major Face Recognition Algorithms, by Benedikt Driessen and Markus Dürmuth

  An ever-increasing number of personal photos is stored online. This trend can be problematic, because face recognition software can undermine user privacy in unexpected ways. Face de-identification aims to prevent automatic recognition of faces thus improving user privacy, but previous work alters the image in a way that makes them indistinguishable for both computers and humans, which prevents a wide-spread use.

We propose a method for de-identification of images that effectively prevents face recognition software (using the most popular and effective algorithms) from identifying people, but still allows human recognition. We evaluate our method experimentally by adapting the CSU framework and using the FERET database. We show that we are able to achieve strong de-identification while maintaining reasonable image quality.

10:17 [Pub][ePrint] Simultaneous Resettable WI from One-way Functions, by Kai-Min Chung and Rafael Pass


In this short note, we demonstrate that the existence of one-way functions implies the existence of an $\\omega(1)$-round simultaneously resettable witness indistinguishable argument.

10:17 [Pub][ePrint] Evolving balanced Boolean functions with optimal resistance to algebraic and fast algebraic attacks, maximal algebraic degree, and very high nonlinearity., by James McLaughlin and John A. Clark

  Using simulated annealing, we derive several equivalence classes of balanced Boolean functions with optimum algebraic immunity, fast algebraic resistance, and maximum possible algebraic degree. For numbers n of input bits less than 16, these functions also possess superior nonlinearity to all Boolean functions so far obtained with said properties.

10:17 [Pub][ePrint] Tropical cryptography, by Dima Grigoriev and Vladimir Shpilrain

  We employ tropical algebras as platforms for several cryptographic

schemes that would be vulnerable to linear algebra attacks were they

based on ``usual\" algebras as platforms.

10:17 [Pub][ePrint] Efficiently Outsourcing Multiparty Computation under Multiple Keys, by Andreas Peter and Erik Tews and Stefan Katzenbeisser

  Secure Multiparty Computation (SMC) enables a set of users to evaluate certain functionalities on their respective inputs while keeping these inputs encrypted throughout the computation. In many scenarios, however, outsourcing these computations to an untrusted server is desirable, so that the server can perform the computation on behalf of the users. Unfortunately, existing solutions are either inefficient, rely heavily on user interaction, or require the inputs to be encrypted under the same key - drawbacks making the employment in practice very limited.

We propose the first general-purpose construction that avoids all these drawbacks: it is efficient, it requires no user interaction whatsoever (except for data up- and download), and it allows evaluating any dynamically chosen function on inputs encrypted under different independent public keys. Our solution assumes the existence of two non-colluding but untrusted servers that jointly perform the computation by means of a cryptographic protocol. This protocol is provably secure in the semi-honest model. We demonstrate the applicability of our result in two real-world scenarios from different domains: Privacy-Preserving Face Recognition and Private Smart Metering. Finally, we give a performance analysis of our general-purpose construction to highlight its practicability.

22:17 [Pub][ePrint] Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices, by Damien Stehlé and Ron Steinfeld

  NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security and that of its digital signature counterpart. In the present work, we show how to modify NTRUEncrypt and NTRUSign to make them provably secure in the standard (resp. random oracle) model, under the assumed quantum (resp. classical) hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields.

Our main contribution is to show that if the secret key polynomials of the encryption scheme are selected from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its range. We also show how to rigorously extend the encryption secret key into a signature secret key. The security then follows from the already proven hardness of the R-SIS and R-LWE problems.