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

15:17 [Pub][ePrint] Oblivious Transfer from weakly Random Self-Reducible Public-Key Cryptosystem, by Claude Crepeau and Raza Ali Kazmi

  In this work, we define a new notion of weakly Random-Self-Reducibile cryptosystems and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems (based on Learning with errors and Approximate Integer GCD) can be considered as weakly Random-Self-Reducible.

15:17 [Pub][ePrint] Optimally Secure Tweakable Blockciphers, by Bart Mennink

  We consider the generic design of a tweakable blockcipher from one or more evaluations of a classical blockcipher, in such a way that all input and output wires are of size n bits. As a first contribution, we show that any tweakable blockcipher with one primitive call and arbitrary linear pre- and postprocessing functions can be distinguished from an ideal one with an attack complexity of about 2^{n/2}. Next, we introduce the tweakable blockcipher tilde{F}[1]. It consists of one multiplication and one blockcipher call with tweak-dependent key, and achieves 2^{2n/3} security. Finally, we introduce tilde{F}[2], which makes two blockcipher calls, one of which with tweak-dependent key, and achieves optimal 2^n security. Both schemes are more efficient than all existing beyond birthday bound tweakable blockciphers known to date, as long as one blockcipher key renewal is cheaper than one blockcipher evaluation plus one universal hash evaluation.

15:17 [Pub][ePrint] Privacy-preserving Context-aware Recommender Systems: Analysis and New Solutions, by Qiang Tang and Jun Wang

  Nowadays, recommender systems have become an indispensable part of our daily life and provide personalized services for almost everything. However, nothing is for free -- such systems have also upset the society with severe privacy concerns because they accumulate a lot of personal information in order to provide recommendations. In this work, we construct privacy-preserving recommendation protocols by incorporating cryptographic techniques and the inherent data characteristics in recommender systems. We first revisit the protocols by Jeckmans et al. at ESORICS 2013 and show a number of security and usability issues. Then, we propose two privacy-preserving protocols, which compute predicted ratings for a user based on inputs from both the user\'s friends and a set of randomly chosen strangers. A user has the flexibility to retrieve either a predicted rating for an unrated item or the Top-N unrated items. The proposed protocols prevent information leakage from both protocol executions and the protocol outputs: a somewhat homomorphic encryption scheme is used to make all computations run in encrypted form, and inputs from the randomly-chosen strangers guarantee that the inputs of a user\'s friends will not be compromised even if this user\'s outputs are leaked. Finally, we use the well-known MovieLens 100k dataset to evaluate the performances for different parameter sizes.

15:17 [Pub][ePrint] On the (im)possibility of receiving security beyond 2^l using an l-bit PRNG: the case of Wang et. al. protocol, by Masoumeh Safkhani and Nasour Bagheri and Mehdi Hosseinzadeh and Mojtaba Eslamnezhad N

  Recently,Wang et al. analyzed the security of two EPC C1-G2 compliant RFID authentication protocols, called RAPLT and SRP^+, and proved that these protocols are vulnerable against de-synchronization and secret disclosure attacks. The time complexity of their attacks were O(2^{16}). In addition, they proposed an improved version of SRP^+ entitled SRP^{++}, for which they claim the security would be O(2^{32}). However, in this letter, we analyze the security of SRP^{++} and show that the complexity of retrieving all secret parameters of a given tag is $O(2^{16})$, similar to its predecessor protocol.

15:17 [Pub][ePrint] A random zoo: sloth, unicorn, and trx, by Arjen K. Lenstra and Benjamin Wesolowski

  Many applications require trustworthy generation of public random numbers. It is shown how this can be achieved using a hash function

that is timed to be as slow as desired (sloth), while the correctness

of the resulting hash can be verified quickly. It is shown how sloth

can be used for uncontestable random number generation (unicorn),

and how unicorn can be used for a new trustworthy random elliptic

curves service (trx) and random-sample voting.

15:17 [Pub][ePrint] Improved Higher-Order Differential Attacks on MISTY1, by Achiya Bar-On

  MISTY1 is a block cipher designed by Matsui in 1997. It is widely

deployed in Japan, and is recognized internationally as an European

NESSIE-recommended cipher and an ISO standard. Since its introduction,

MISTY1 was subjected to extensive cryptanalytic

efforts, yet no attack significantly faster than exhaustive key search is

known on its full version. The best currently

known attack is a higher-order differential attack presented by Tsunoo

et al. in 2012 which breaks a reduced variant of MISTY1 that contains

7 of the 8 rounds and 4 of the 5 $FL$ layers in $2^{49.7}$ data and $2^{116.4}$


In this paper, we present improved higher-order differential attacks on

reduced-round MISTY1. Our attack on the variant considered by Tsunoo et al.

requires roughly the same amount of data and only $2^{100.4}$ time

(i.e., is $2^{16}$ times faster). Furthermore, we present the first attack

on a MISTY1 variant with 7 rounds and all 5 $FL$ layers, requiring

$2^{51.4}$ data and $2^{121}$ time. To achieve our results, we use a new

higher-order differential characteristic for 4-round MISTY1, as well as

enhanced key recovery algorithms based on the {\\it partial sums} technique.

15:17 [Pub][ePrint] Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library, by Evgeny Sidorov

  This paper describes a bug in the implementation of the Rabin-Williams digital signature in the \\texttt{Crypto++} framework. The bug is in the misuse of blinding technique that is aimed at preventing timing attacks on the digital signature system implementation, but eventually results in an opportunity to find the private key having only two different signatures of the same message. The CVE identifier of the issue is \\texttt{CVE-2015-2141}.

15:17 [Pub][ePrint] On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation, by Nir Bitansky and Omer Paneth

  The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak\'s technique has given rise to various powerful applications and it is a key component in all known protocols with non-black-box simulation.

We present the first non-black-box simulation technique that does not rely on Barak\'s technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity.

A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals as: simultaneously-resettable zero-knowledge, proofs of knowledge, and resettable-security from one-way functions. While previous works required tailored modifications to Barak\'s technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions.

The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality; thus, settling a question left open by Barak et al..

In the converse direction, we show a generic transformation from any resettably-sound zero-knowledge protocol to a family of functions that cannot be obfuscated.

15:17 [Pub][ePrint] Financial Cryptography: Discriminatory Pricing Mechanism , by Sumit Chakraborty

  This work presents an adaptive profitable discriminatory pricing mechanism for cloud computing based on secure function decomposition, cryptographic commitments and zero knowledge proof. Cloud computing is an emerging trend of enterprise resource planning where a selling agent or service provider (S) wants to allocate a set of computational resources and related IT services optimally and fairly among many buying agents or service consumers (B) within its capacity constraint. Each service consumer discloses its demand plan for an IT portfolio within its budget constraint and rank of preference. An IT portfolio may include SaaS, PaaS, IaaS, CaaS, DaaS and dSaaS. The basic objective of the service provider is to optimize its expected revenue within target profit margin. It is basically a problem of secure function evaluation where the concept of decomposition of a function is considered. It is a constrained non-linear optimization problem; the search is governed by a set of intelligent moves. The communication complexity of the pricing mechanism depends on the time constraint of the negotiating agents, their information state and the number of negotiation issues; it also depends on number of negotiation rounds and the complexity of IT portfolio. The computational cost depends on the complexity of function decomposition. The security and privacy of strategic data of the trading agents provides business intelligence to the pricing mechanism. The ultimate objective of the mechanism is to predict a profitable discriminatory pricing plan for each consumer.

15:17 [Pub][ePrint] Constant-Round MPC with Fairness and Guarantee of Output Delivery, by S. Dov Gordon and Feng-Hao Liu and Elaine Shi

  We study the round complexity of multiparty computation with fairness

and guaranteed output delivery, assuming existence of an honest majority. We demonstrate a new lower bound and a matching

upper bound. Our lower bound rules out any two-round

fair protocols in the standalone model, even when the parties are given access to a common reference string (CRS). The lower bound follows by a reduction to the impossibility result of virtual black box obfuscation of arbitrary circuits.

Then we demonstrate a three-round protocol with guarantee of output delivery, which in general is harder than achieving fairness (since the latter allows the adversary to force a fair abort). We develop a new construction of a threshold fully homomorphic encryption scheme, with a new property that we call ``flexible\'\' ciphertexts. Roughly, our threshold encryption scheme allows parties to adapt flexible ciphertexts to the public keys of the non-aborting parties, which provides a way of handling aborts without adding any communication.

06:17 [Pub][ePrint] Semantic Security and Indistinguishability in the Quantum World, by Tommaso Gagliardoni and Andreas H\\\"ulsing and Christian Schaffner

  At CRYPTO 2013, Boneh and Zhandry initiated the study of quantum-secure encryption. They proposed first indistinguishability definitions for the quantum world where the actual indistinguishability only holds for classical messages, and they provide arguments why it might be hard to achieve a stronger notion. In this work, we show that stronger notions are achievable, where the indistinguishability holds for quantum superpositions of messages. We investigate exhaustively the possibilities and subtle differences in defining such a quantum indistinguishability notion. We justify our stronger definition by showing their equivalence to novel quantum semantic-security notions that we introduce. Furthermore, we give a generic transformation to turn a big class of encryption schemes into quantum indistinguishable and hence quantum semantically secure ones.