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

2015-04-23
15:17 [Pub][ePrint]

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]

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]

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]

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}$

time.

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]

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]

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]

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]

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]

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]

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]

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.