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

We describe a new technique for conducting partitioning arguments\'\'. Partitioning arguments are a popular way to prove the security of a cryptographic scheme. For instance, to prove the security of a signature scheme, a partitioning argument could divide the set of messages into signable\'\' messages for which a signature can be simulated during the proof, and unsignable\'\' ones for which any signature would allow to solve a computational problem. During the security proof, we would then hope that an adversary only requests signatures for signable messages, and later forges a signature for an unsignable one.

In this work, we develop a new class of partitioning arguments from simple assumptions. Unlike previous partitioning strategies, ours is based upon an algebraic property of the partitioned elements (e.g., the signed messages), and not on their bit structure. This allows to perform the partitioning efficiently in a hidden\'\' way, such that already a single slot\'\' for a partitioning operation in the scheme can be used to implement many different partitionings sequentially, one after the other. As a consequence, we can construct complex partitionings out of simple basic (but algebraic) partitionings in a very space-efficient way.

As a demonstration of our technique, we provide the first signature and public-key encryption schemes that achieve the following properties simultaneously: they are (almost) tightly secure under a simple assumption, and they are fully compact (in the sense that parameters, keys, and signatures, resp.~ciphertexts only comprise a constant number of group elements).

15:17 [Pub][ePrint]

Fault injection has become over the years one of the most dangerous threats for embedded devices such as smartcards. It is thus mandatory for any embedded system to implement efficient protections against this hazard. Among the various countermeasures suggested so far, the idea of infective computation seems fascinating, probably due to its aggressive strategy. Originally conceived to protect asymmetric cryptosystems, infective computation has been recently adapted to symmetric systems. This paper investigates the security of a new symmetric infective countermeasure suggested at CHES 2014. By noticing that the number of executed rounds is not protected, we develop four different attacks allowing one to efficiently recover the secret key of the underlying cryptosystem by using any of the three most popular fault models used in literature.

15:17 [Pub][ePrint]

We reconsider the concept of two-prover (and more generally: multi-prover) commitments, as introduced in the late eighties in the seminal work by Ben-Or et al. As was recently shown by Cr{\\\'e}peau et al., the security of known two-prover commitment schemes not only relies on the explicit assumption that the two provers cannot communicate, but also depends on what their information processing capabilities are. For instance, there exist schemes that are secure against classical provers but insecure if the provers have quantum information processing capabilities, and there are schemes that resist such quantum attacks but become insecure when considering general so-called non-signaling provers, which are restricted solely by the requirement that no communication takes place.

This poses the natural question whether there exists a two-prover commitment scheme that is secure under the sole assumption that no communication takes place, and that does not rely on any further restriction of the information processing capabilities of the dishonest provers; no such scheme is known.

In this work, we give strong evidence for a negative answer: we show that any single-round two-prover commitment scheme can be broken by a non-signaling attack. Our negative result is as bad as it can get: for any candidate scheme that is (almost) perfectly hiding, there exists a strategy that allows the dishonest provers to open a commitment to an arbitrary bit (almost) as successfully as the honest provers can open an honestly prepared commitment, i.e., with probability (almost) $1$ in case of a perfectly sound scheme. In the case of multi-round schemes, our impossibility result is restricted to perfectly hiding schemes.

On the positive side, we show that the impossibility result can be circumvented by considering {\\em three} provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.

15:17 [Pub][ePrint]

Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain-based transaction ledger, maintained through proofs-of-work that also generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of scalability and computational cost. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding double-spending attacks.

09:17 [Pub][ePrint]

Large-scale datasets of consumer behavior might revolutionize the way we gain competitive advantages and increase our knowledge in the respective domains. At the same time, valuable datasets pose potential privacy risks that are difficult to foresee. In this paper we study the impact that the prices from consumers\' purchase histories have on the consumers\' location privacy. We show that using a small set of low-priced product prices from the consumers\' purchase histories, an adversary can determine the country, city, and local retail store where the transaction occurred with high confidence. Our paper demonstrates that even when the product category, precise time of purchase, and currency are removed from the consumers\' purchase history (e.g., for privacy reasons), information about the consumers\' location is leaked. The results are based on three independent datasets containing thousands of low-priced and frequently-bought consumer products. In addition, we show how to identify the local currency, given only the total price of a consumer purchase in a global currency (e.g., in Bitcoin). The results show the existence of location privacy risks when releasing consumer purchase histories. As such, the results highlight the need for systems that hide transaction details in consumer purchase histories.

09:17 [Pub][ePrint]

We describe a zero-knowledge proof system in which a prover holds a large dataset $M$ and can repeatedly prove NP relations about that dataset. That is, for any (public) relation $R$ and $x$, the prover can prove that $\\exists w: R(M,x,w)=1$. After an initial setup phase (which depends only on $M$), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a {\\em random-access machine (RAM)} implementation of $R$, up to polylogarithmic factors. In particular, the cost per proof in many applications is sublinear in $|M|$. Additionally, the storage requirement between proofs for the verifier is constant.

02:01 [Event][New]

Submission: 10 June 2015
From July 19 to July 26
Location: Oriahovitza, Bulgaria

2015-05-25
15:17 [Pub][ePrint]

In 2012, Wen and Li proposed a secure and robust dynamic identity based remote user authentication scheme with key agreement using smart cards. They claimed that their scheme is efficient and secure. But in this paper, we demonstrate that their scheme is completely insecure and vulnerable to various known attacks like offline and online password guessing attack, impersonation attack, server masquerading attack, denial of service attack and an insider attack. Also we point out that there are loopholes in password change phase and online secret renew phase which leads to the desynchronization between user and the server and even the legitimate user is rejected by the server. In addition, an adversary can easily generate the common session key of further transmission between user and the server. Thus the entire system collapses and authors claims are proven to be wrong and their scheme will not be secure and efficient for practical purpose.

15:17 [Pub][ePrint]

In this work we define multiple relaxations to the definition of correctness in secure obfuscation. While still remaining meaningful, these relaxations provide ways to obfuscate many primitives in a more direct and efficient way. In particular, we first show how to construct a secure obfuscator for the re-encryption primitive from the Decisional Learning with Errors (DLWE) assumption, without going through fully homomorphic encryption. This can be viewed as a meaningful way to trade correctness for efficiency.

Next, we show how our tools can be used to construct secure obfuscators for the functional re-encryption and multi-hop unidirectional re-encryption primitives. In the former case, we improve upon the efficiency of the only previously known construction that satisfies the stronger notion of collusion-resistant obfuscation (due to Chandran et al. - TCC 2012) and obtain a construction with input ciphertexts of constant length. In the latter case, we provide the first known obfuscation-based definition and construction; additionally, our scheme is the first scheme where the size of the ciphertexts does not grow with every hop.

15:17 [Pub][ePrint]

In this paper, we evaluate the performances of state-of-the-art higher-order masking schemes for the AES. Doing so, we pay a particular attention to the comparison between specialized solutions introduced exclusively as countermeasures against side-channel analysis, and a recent proposal by Roche and Prouff exploiting MultiParty Computation (MPC) techniques. We show that the additional security features this latter scheme provides (e.g. its glitch-freeness) comes at the cost of large performance overheads. We then study how exploiting standard optimization techniques from the MPC literature can be used to reduce this gap. In particular, we show that packed secret sharing\" based on a modified multiplication algorithm can speed up MPC-based masking when the order of the masking scheme increases. Eventually, we discuss the randomness requirements of masked implementations. For this purpose, we first show with information theoretic

arguments that the security guarantees of masking are only preserved if this randomness is uniform, and analyze the consequences of a deviation from this requirement. We then conclude the paper by including the cost of randomness generation in our performance evaluations. These results should help actual designers to choose a masking scheme based on security and performance~constraints.

15:17 [Pub][ePrint]

Infective countermeasures have been a promising class of fault attack countermeasures. However, they have been subjected to several attacks owing to lack of formal proofs of security and improper implementations. In this paper, we first provide a formal information theoretic proof of security for one of the most recently proposed infective countermeasures against DFA, under the assumption that the adversary does not change the flow sequence or skip any instruction. Subsequently, we identify weaknesses in the infection

mechanism of the countermeasure that could be exploited by attacks which change the flow sequence. We propose suitable randomizations to reduce the success probabilities of such attacks. Furthermore, we develop a fault tolerant implementation of the countermeasure using the x86 instruction set to make such attacks which attempt to change the control flow of the algorithm practically infeasible. All the claims have been validated by supporting simulations and real life experiments on a SASEBO-W platform. We also compare the performance and security provided by the proposed countermeasure against that provided by the existing scheme.