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

00:17 [Pub][ePrint] Accelerating Bliss: the geometry of ternary polynomials, by Léo Ducas

  The signature scheme Bliss proposed by Ducas, Durmus, Lepoint and Lyubashevsky at Crypto\'13, is currently the most compact and efficient lattice-based signature scheme that is provably secure under lattice assumptions. It does compare favourably with the standardized schemes RSA and ECDSA on both Software and Hardware.

In this work, we introduce a new technique that improves the above scheme, offering an acceleration factor up to 2.8, depending on the set of parameters.

Namely, we improve the unnatural geometric bound used in Bliss to a tighter and much more natural bound by using some extra degree of freedom: the ternary representations of binary challenges. Precisely, we efficiently choose a ternary representation that makes the result deterministically shorter than the expected length for a random challenges.

Our modified scheme Bliss-b is rather close to the original scheme, and both versions are compatible. The patch has been implemented on the Open-Source Software implementation of Bliss, and will be released under similar license.

21:17 [Pub][ePrint] Leakage-Resilient Circuits Revisited -- Optimal Number of Computing Components without Leak-free Hardware, by Dana Dachman-Soled and Feng-Hao Liu and Hong-Sheng Zhou

  Side channel attacks -- attacks that exploit implementation-dependent information of a cryptosystem -- have been shown to be highly detrimental, and the cryptographic community has recently

focused on developing techniques for securing implementations against such attacks. An important model called \\emph{Only Computation Leaks} (OCL) [Micali and Reyzin, TCC \'04] and its stronger variants were proposed to model a broad class of leakage attacks (a type of

side-channel attack). These models allow for unbounded, arbitrary leakage as long as (1) information in each leakage observation is bounded, and (2) different parts of the computation leak independently. Various results and techniques have been developed for these models and we continue this line of research in the current work.

We address the problem of compiling any circuit into a circuit secure against OCL attacks. In order to leverage the OCL assumption, the resulting circuit will be split into components, where at any point in time only a single component is active. Optimally, we would like to output a circuit that has only one component, and no part of the computation needs to be leak-free. However, this task is impossible due to the result of Barak et al. [JACM \'12].The current state-of-the-art constructions achieve either two components with additional leak-free hardware, or many components without leak-free hardware.

In this work, we show how to achieve the best of both worlds: We construct two-component OCL schemes without relying on leak-free components. Our approach is general and modular -- we develop generic techniques to remove the hardware component from hardware-based constructions, when the functionality provided by the hardware satisfies some properties. Our techniques use universal deniable encryption (recently constructed by Sahai and Water [STOC \'14] using indistinguishable obfuscation) and non-committing encryption in a novel way. Then, we observe that the functionalities of the hardware used in previous two-component constructions of Juma and Vahlis [Crypto \'10], and Dziembowski and Faust [TCC \'12] satisfy the required properties.

The techniques developed in this paper have deep connections with adaptively secure and leakage tolerant multi-party computation (MPC).

Our constructions immediately yield adaptively secure and leakage tolerant MPC protocols for any no-input randomized functionality in the semi-honest model. The result holds in the CRS model, without pre-processing. Our results also have implications to two-party leakage tolerant computation for arbitrary functionalities, which we obtain by combining our constructions with a recent result of Bitansky, Dachman-Soled, and Lin [Crypto \'14].

21:17 [Pub][ePrint] Pseudonymous Secure Computation from Time-Lock Puzzles, by Jonathan Katz and Andrew Miller and Elaine Shi

  In standard models of secure computation, point-to-point channels between parties are as-

sumed to be authenticated by some pre-existing means. In other cases, even stronger pre-existing

setup--e.g., a public-key infrastructure (PKI)--is assumed. These assumptions are too strong

for open, peer-to-peer networks, where parties do not necessarily have any prior relationships

and can come and go as they please. Nevertheless, these assumptions are made due to the

prevailing belief that nothing \"interesting\" can be achieved without them.

Taking inspiration from Bitcoin, we show that precise bounds on computational power can

be used in place of pre-existing setup to achieve weaker (but nontrivial) notions of security.

Specifically, under the assumptions that digital signatures exist and each party can solve cryp-

tographic \"time-lock\" puzzles only at a bounded rate, we show that without prior setup and

with no bound on the number of corruptions, a group of parties can agree on a PKI with which

they can then realize pseudonymous notions of authenticated communication, broadcast, and

secure computation. Roughly, \"pseudonymous\" here means that inputs/outputs are (effectively)

bound to pseudonyms rather than parties\' true identities.

21:17 [Pub][ePrint] Adaptively Secure, Universally Composable, Multi-Party Computation in Constant Rounds, by Dana Dachman-Soled and Jonathan Katz and Vanishree Rao

  Cryptographic protocols with adaptive security ensure that security holds against an adversary who can dynamically determine which parties to corrupt as the protocol progresses---or even after the protocol is finished. In the setting where all parties may potentially be corrupted, and secure erasure is not assumed, it has been a long-standing open question to design secure-computation protocols with adaptive security running in constant rounds.

Here, we show a constant-round, universally composable protocol for computing any functionality, tolerating a malicious, adaptive adversary corrupting any number of parties. Interestingly, our protocol can compute all functionalities, not just adaptively well-formed ones.

21:17 [Pub][ePrint] Provably secure pairing-free identity-based partially blind signature scheme and its application in online e-cash system, by SK Hafizul Islam, G. P. Biswas

  The blind signature scheme permits the user to acquire a signature

from the signer; however, the message and the final signature are

unknown to the signer. In a partially blind signature (PBS) scheme,

the signer can explicitly incorporate a common information in the

signature based on some agreement with the user and without

violating the blindness property. Many PBS schemes have been

proposed recently either by using certificate authority-based public

infrastructure (CA-PKI) or pairing along with map-to-point function.

The CA-PKI-based PBS scheme needs huge computation and storage to

keep public keys and certificates. On the other hand, pairing and

map-to-point function are costly operations. Thus, the ID-PBS scheme

without pairing is more appropriate for real environments, and an

efficient pairing-free ID-PBS scheme is proposed in this paper. In

the random oracle model, our scheme is analyzed to be provably

secure. The proposed scheme is used to design an online e-cash

system, in which a bank agrees on a common piece of information with

a customer and can blindly sign some messages. It may be noted that

our e-cash system has the properties of unforgeability,

unlinkability, and non-deniability and can prevent the

double-spending of e-cash.

21:17 [Pub][ePrint] Differential Factors: Improved Attacks on SERPENT, by Cihangir Tezcan and Ferruh Özbudak

  A differential attack tries to capture the round keys corresponding to the S-boxes activated by a differential. In this work, we show that for a fixed output difference of an S-box, it may not be possible to distinguish the guessed keys that have a specific difference. We introduce these differences as differential factors. Existence of differential factors can reduce the time complexity of differential attacks and as an example we show that the 10, 11, and 12-round differential-linear attacks of Dunkelman et al. on SERPENT can actually be performed with time complexities reduced by a factor of 4, 4, and 8, respectively.

21:17 [Pub][ePrint] Cats and Dogs An Integrity for Voting Systems Based on Paper Ballots, by İhsan Haluk Akın

  Abstract--Voting systems based on paper ballots has a long

history with various problems. Vote-selling and correct outcome

are two major problems among many. In this work, we propose

a new solution to these problems by using UltraViolet (UV)

fiber paper Physical Unclonable Function (PUF). When applied

this solution not only prevents vote-selling but also ensures the

correctness of the outcome. With these two problems eliminated,

the voting systems based on paper ballots will have complete


21:17 [Pub][ePrint] Low-Latency ECDSA Signature Verification - A Road Towards Safer Traffic -, by Miroslav Knezevic, Ventzislav Nikov, and Peter Rombouts

  Car-to-car and Car-to-Infrastructure messages exchanged in Intelligent Transportation Systems can reach reception rates up to and over 1000 messages per second. As these messages contain ECDSA signatures this puts a very heavy load onto the verification hardware. In fact the load is so high that currently it can only be achieved by implementations running on high end CPUs and FPGAs. These implementations are far from cost-effective nor energy efficient. In this paper we present an ASIC implementation of a dedicated ECDSA verification engine that can reach verification rates of up to 27.000 verifications per second using only 1.034 kGE.

21:17 [Pub][ePrint] A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation, by Matthew D. Green and Jonathan Katz and Alex J. Malozemoff and Hong-Sheng Zhou

  It is well known that the random oracle model is not sound in the sense that there exist cryptographic systems that are secure in the random oracle model but when instantiated by any family of hash functions become insecure. However, all known separation results require the attacker to send an appropriately crafted message to the challenger in order to break security. Thus, this leaves open the possibility that some cryptographic schemes, such as bit-encryption, are still sound in the random oracle model.

In this work we refute this possibility, assuming the existence of indistinguishability obfuscation. We do so in the following way. First, we present a random oracle separation for bit-encryption; namely, we show that there exists a bit-encryption protocol secure in the random oracle model but \\emph{completely insecure} when the random oracle is instantiated by any concrete function. Second, we show how to adapt this separation to work for most natural simulation-based and game-based definitions. Our techniques can easily be adapted to other idealized models, and thus we present a \\emph{unified approach} to showing separations for most protocols of interest in most idealized models.

21:17 [Pub][ePrint] How to Choose Interesting Points for Template Attack More Effectively?, by Guangjun Fan, Yongbin Zhou, Hailong Zhang, Dengguo Feng

  Template Attacks are widely accepted to be the most powerful side-channel attacks from an information theoretic point of view. For Template Attacks to be practical, one needs to choose some special samples as the interesting points in actual power traces. Up to now, many different approaches were introduced for choosing interesting points for Template Attacks. However, it is unknown that whether or not the pervious approaches of choosing interesting points will lead to the best classification performance of Template Attacks. In this work, we give a negative answer to this important question by introducing a practical new approach which has completely different basic principle compared with all the pervious approaches. Our new approach chooses the point whose distribution of samples approximates to a normal distribution as the interesting point. Evaluation results exhibit that Template Attacks based on the interesting points chosen by our new approach can achieve obvious better classification performance compared with Template Attacks based on the interesting points chosen by the pervious approaches. Therefore, our new approach of choosing interesting points should be used in practice to better understand the practical threats of Template Attacks.

21:17 [Pub][ePrint] Impossibility Results for Leakage-Resilient Zero Knowledge and Multi-Party Computation, by Rafail Ostrovsky and Giuseppe Persiano and Ivan Visconti

  In [AGP14] Ananth et al. showed that continual leakage-resilient non-transferable interactive proofs exist when a leak-free input-encoding phase is allowed and a common reference string is available. They left open the problem of removing the need of a common reference string.

In [BGJK12] Boyle et al. showed that for some interesting functionalities continual leakage-resilient secure computation is possible when leak-free interactive preprocessing and input-encoding phases are allowed. They left open the problem of removing the interactive preprocessing.

In this work we study the above questions. Our main contribution shows that leakage-resilient black-box zero-knowledge is impossible when relying on a leak free input-encoding phase only (i.e., without CRS/preprocessing). Additionally, we also show that leakage-resilient multi-party computation for all functionalities is impossible (regardless of the number of players assuming just one corrupted player) when relying only on a leak-free input-encoding phase (i.e., without CRS/preprocessing).

Our results are achieved by means of a new technique to prove lower bounds for leakage-resilient security. We use leakage queries to run an execution of a communication-efficient insecure (i.e., non-simulatable) protocol in the head of the adversary. Moreover our work shows an interesting connection between leakage resilience and security against reset attacks.