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

03:17 [Pub][ePrint] Fault Analysis of Kuznyechik, by Riham AlTawy and Onur Duman and Amr M. Youssef

  Kuznyechik is an SPN block cipher that has been chosen recently to be standardized by the Russian federation as a new GOST cipher. In this paper, we present two fault analysis attacks on two different settings of the cipher. The first attack is a differential fault attack which employs the random byte fault model, where the attacker

is assumed to be able to fault a random byte in rounds seven and eight. Using this fault model enables the attacker to recover the master key using an average of four faults. The second attack considers the cipher with a secret sbox. By utilizing an ineffective fault analysis in the byte stuck-at-zero fault model, we present a four stage attack to recover both the master key and the secret sbox parameters. Our second attack is motivated by the fact that, similar to GOST 28147-89, Kuznyechik is expected to include the option of using secret sbox based on the user supplied key to increase its security margin. Both the presented attacks have practical complexities and aim to demonstrate the importance of protecting the hardware and software implementations of the new standard even if its sbox is kept secret.

03:17 [Pub][ePrint] A Hardware-based Countermeasure to Reduce Side-Channel Leakage - Design, Implementation, and Evaluation, by An­dre­as Gor­nik and Amir Mo­ra­di and Jür­gen Oehm and Chris­tof Paar

  Side-channel attacks are one of the major concerns for security-enabled applications as they make use of information leaked by the physical implementation of the underlying cryptographic algorithm. Hence, reducing the side-channel leakage of the circuits realizing the cryptographic primitives is amongst the main goals of circuit designers. In this work we present a novel circuit concept, which decouples the main power supply from an internal power supply that is used to drive a single logic gate. The decoupling is done with the help of buffering capacitances integrated into semiconductor. We also introduce - compared to the previously known schemes - an improved decoupling circuit which reduces the crosstalk from the internal to the external power supply. The result of practical side-channel evaluation on a prototype chip fabricated in a 150nm CMOS technology shows a high potential of our proposed technique to reduce the side-channel leakages.

03:17 [Pub][ePrint] Efficient Searchable Symmetric Encryption for Storing Multiple Source Data on Cloud, by Chang Liu and Liehuang Zhu and Jinjun Chen

  Cloud computing has greatly facilitated large-scale data outsourcing due to its cost efficiency, scalability and many other advantages. Subsequent privacy risks force data owners to encrypt sensitive data, hence making the outsourced data no longer searchable. Searchable Symmetric Encryption (SSE) is an advanced cryptographic primitive addressing the above issue, which maintains efficient keyword search over encrypted data without disclosing much information to the storage provider. Existing SSE schemes implicitly assume that original user data is centralized, so that a searchable index can be built at once. Nevertheless, especially in cloud computing applications, user-side data centralization is not reasonable, e.g. an enterprise distributes its data in several data centers. In this paper, we propose the notion of Multi-Data-Source SSE (MDS-SSE), which allows each data source to build a local index individually and enables the storage provider to merge all local indexes into a global index afterwards. We propose a novel MDS-SSE scheme, in which an adversary only learns the number of data sources, the number of entire data files, the access pattern and the search pattern, but not any other distribution information such as how data files or search results are distributed over data sources. We offer rigorous security proof of our scheme, and report experimental results to demonstrate the efficiency of our scheme.

03:17 [Pub][ePrint] Improving Local Collisions: New Attacks on Reduced SHA-256, by Florian Mendel and Tomislav Nad and Martin Schläffer

  In this paper, we focus on the construction of semi-free-start collisions for SHA-256, and show how to turn them into collisions. We present a collision attack on 28 steps of the hash function with practical complexity. Using a two-block approach we are able to turn a semi-free-start collision into a collision for 31 steps with a complexity of at most $2^{65.5}$. The main improvement of our work is to extend the size of the local collisions used in these attacks. To construct differential characteristics and confirming message pairs for longer local collisions, we had to improve the search strategy of our automated search tool. To test the limits of our techniques we present a semi-free-start collision for 38 steps.

03:17 [Pub][ePrint] Database Outsourcing with Hierarchical Authenticated Data Structures, by Mohammad Etemad and Alptekin Küpçü

  In an outsourced database scheme, the data owner delegates the data management tasks to a remote service provider. At a later time, the remote service is supposed to answer any query on the database. The essential requirements are ensuring the data integrity and authenticity with efficient mechanisms. Current approaches employ authenticated data structures to store security information, generated by the client and used by the server, to compute proofs that show the answers to the queries are authentic. The existing solutions have shortcomings with multi-clause queries and duplicate values in a column.

We propose a hierarchical authenticated data structure for storing security information, which alleviates the mentioned problems. Our solution handles many different types of queries, including multi-clause selection and join queries, in a dynamic database. We provide a unified formal definition of a secure outsourced database scheme, and prove that our proposed scheme is secure according to this definition, which captures previously separate properties such as correctness, completeness, and freshness. The performance evaluation based on our prototype implementation confirms the efficiency of our proposed scheme, showing about 3x to 5x enhancement in proof size and proof generation time in comparison to previous work, and about only 4% communication overhead compared to the actual query result in a real university database.

03:17 [Pub][ePrint] Broadcast from Minicast Secure Against General Adversaries, by Pavel Raykov

  Byzantine broadcast is a distributed primitive that allows a specific party to consistently distribute a message among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. The celebrated result of \\cite{PSL80} shows that broadcast is achievable from point-to-point channels if and only if $t < n/3$.

The following two generalizations have been proposed to the original broadcast problem. In~\\cite{FM98} the authors considered a \\emph{general adversary} characterized by the sets of parties that can be corrupted. It was shown that broadcast is achievable from point-to-point channels if and only if no three possible corrupted sets can cover the whole party set. In~\\cite{CFFLMM05} the notion of point-to-point channels has been extended to the $b$-minicast channels allowing to locally broadcast among any subset of $b$ parties. It has been shown that broadcast secure against adversaries corrupting up to $t$ parties is achievable from $b$-minicast if and only if $t < \\frac{b-1}{b+1}n$.

In this paper we combine both generalizations by considering the problem of achieving broadcast from $b$-minicast channels secure against general adversaries. Our main result is a condition on the possible corrupted sets such that broadcast is achievable from $b$-minicast if and only if this condition holds.