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

2014-03-04
09:19 [Event][New]

Submission: 27 May 2014
From December 7 to December 11
Location: Kaohsiung, Taiwan

09:18 [Event][New]

Submission: 27 May 2014
From December 7 to December 11
Location: Kaohsiung, Taiwan

01:17 [Pub][ePrint]

Verifiable computation (VC) enables thin clients to efficiently verify the computational results produced by a powerful server. Although VC was initially considered to be mainly of theoretical interest, over the last two years, impressive progress has been made on implementing VC. Specifically, we now have open-source implementations of VC systems that can handle all classes of computations expressed either as circuits or in the RAM model. However, despite this very encouraging progress, new enhancements in the design and implementation of VC protocols are required in order to achieve truly practical VC for real-world applications. In this work, we show that for functionalities that can be expressed efficiently in terms of set operations (e.g., a subset of SQL queries) VC can be enhanced to become drastically more practical: We present the design and prototype implementation of a novel VC scheme that achieves orders of magnitude speed-up in comparison with the state of the art. Specifically, we build and evaluate TRUESET, a system that can verifiably compute any polynomial-time function expressed as a circuit consisting of \"set gates\" such as union, intersection, difference and set cardinality. Moreover, TRUESET supports hybrid circuits consisting of both set gates and traditional arithmetic gates and, therefore, does not lose any of the expressiveness of the previous schemes (allowing, at the same time, the user to choose the most efficient way to represent different parts of a computation task). By expressing set computations as polynomial operations and introducing a novel Quadratic Polynomial Program technique, TRUESET achieves prover performance speed-up ranging from 30x to 150x and yields up to 97% evaluation key size reduction.

01:17 [Pub][ePrint]

We apply the Flush-Reload side-channel attack based on cache hits/misses to extract a small amount of data from OpenSSL ECDSA signature requests. We then apply a standard\'\' lattice technique to extract the private key, but unlike previous attacks we are able to make use of the side-channel information from almost all of the observed executions. This means we obtain private key recovery by observing a relatively small number of executions, and by expending a relatively small amount of post-processing via lattice reduction. We demonstrate our analysis via experiments using the curve secp256k1 used in the Bitcoin protocol. In particular we show that with as little as 200 signatures we are able to achieve a reasonable level of success in recovering the secret key for a 256-bit curve. This is significantly better than prior methods of applying lattice reduction techqniques to similar side channel information.

01:17 [Pub][ePrint]

Signcryption is a useful paradigm which simultaneously offers both the functions of encryption and signature in a single logic step. It would be interesting to make signcryption certificateless to ease the heavy burden of certificate management in traditional public key cryptography (PKC) and solve the key escrow problem in Identity-based public key cryptography (ID-PKC). Most certificateless signcryption (CL-SC) schemes are constructed in the random oracle model instead of the standard model. By exploiting Bellare and Shoup\'s one-time signature, Hwang et al.\'s certificateless encryption and Li et al.\'s identity-based signcryption, this paper proposes a new CL-SC scheme secure in the standard model. It is proven that our CL-SC scheme satisfies semantic security and unforgeability against the outside adversary and malicious-but-passive key generation center (KGC) assuming the hardness of bilinear decision Diffie-Hellman (BDDH) and computational Diffie-Hellman (CDH) problems. Our security proofs do not depend on random oracles.

01:17 [Pub][ePrint]

Amongst areas of cryptographic research, there has recently been a widening interest for code-based cryptosystems and their implementations. Besides the {\\it a priori} resistance to quantum computer attacks, they represent a real alternative to the currently used cryptographic schemes. In this paper we consider the implementation of the Stern authentication scheme and one recent variation of this scheme by Aguilar {\\it et al.}. These two schemes allow public authentication and public signature with public and private keys of only a few hundreds bits. The contributions of this paper are twofold: first, we describe how to implement a code-based signature in a constrained device through the Fiat-Shamir paradigm, in particular we show how to deal with long signatures. Second, we implement and explain new improvements for code-based zero-knowledge signature schemes. We describe implementations for these signature and authentication schemes, secured against side channel attacks, which drastically improve the previous implementation presented at Cardis 2008 by Cayrel {\\it et al.}. We obtain a factor 3 reduction of speed and a factor of about 2 for the length of the signature. We also provide an extensive comparison with RSA signatures.

01:17 [Pub][ePrint]

Nonlinearity and resiliency are well known as some of the most important

cryptographic parameters of Boolean functions, it is actual the problem of

the constructing of functions that have high nonlinearity and resiliency

simultaneously. In 2000 three groups of au\\-thors obtained independently the

upper bound $2^{n-1}-2^{m+1}$ for the nonlinearity of an $m$-resilient

function of $n$ variables. It was shown that if this bound is achieved then

$(n-3)/2\\le m\\le n-2$. Simultaneously in 2000 Tarannikov constructed

functions that achieve this bound for $(2n-7)/3\\le m\\le n-2$. In 2001

Tarannikov constructed such functions for $0.6n-1\\le m$ introducing for this

aim so called proper matrices; later in 2001 Fedorova and Tarannikov

constructed by means of proper matrices the functions that achieve the bound

$2^{n-1}-2^{m+1}$ for $m\\ge cn(1+o(1))$ where

$c=1/\\log_2(\\sqrt{5}+1)=0.5902...$ but proved simultaneously

that by means of proper matrices it is impossible to improve this

result. During the period since 2001 it was not any further progress

in the problem on the achievability of the bound $2^{n-1}-2^{m+1}$ in spite of

this problem was well known and actual except the constructing

in 2006--2007 by three groups of authors by means of a computer search

concrete functions for $n=9$, $m=3$. In this paper we find the new

approach that uses the generalization of the concept of proper

matrices. We formulate com\\-bi\\-na\\-to\\-ri\\-al problems solutions of which

allow to construct generalized proper matrices with parameters impossible

for old proper matrices. As a result we obtain the constructions of

$m$-resilient functions of $n$ variables with maximal nonlinearity for

$m\\ge cn(1+o(1))$ where $c=0.5789...$, and also we demonstrate how further

constant $c$.

01:17 [Pub][ePrint]

With the fast development of cryptography research and computer technology, the cryptosystems of RSA and Diffe-Hellman are getting more and more unsafe, and Elliptic Curve Cryptosystem is becoming the trend of public cryptography in the future. Scalar Point Multiplication Scalar multiplication is the time consuming operation in elliptic curve based cryptosystem. In this paper, Nicolas Meloni1,2 2012 springer algorithm for addition of points on elliptic curve is used along with multibase concept to improve the speed of the scalar multiplication. Comparative analysis of proposed approach and some previous approaches is also discussed in last.

01:17 [Pub][ePrint]

In the field of collusion-resistant traitor tracing, Oosterwijk et al. recently determined the optimal suspicion function for simple decoders. Earlier, Moulin also considered another type of decoder: the generic joint decoder that compares all possible coalitions, and showed that usually the generic joint decoder outperforms the simple decoder. Both Amiri and Tardos, and Meerwald and Furon described constructions that assign suspicion levels to $c$-tuples, where $c$ is the number of colluders. We investigate a novel idea: the tuple decoder, assigning a suspicion level to tuples of a fixed size. In contrast to earlier work, we use this in a novel accusation algorithm to decide for each distinct user whether or not to accuse him. We expect such a scheme to outperform simple decoders while not being as computationally intensive as the generic joint decoder. In this paper we generalize the optimal suspicion functions to tuples, and describe a family of accusation algorithms in this setting that accuses individual users using this tuple-based information.

01:17 [Pub][ePrint]

Random number generators (RNGs) play a crucial role in many cryptographic schemes and protocols, but their security proof usually assumes that their internal state is initialized with truly random seeds and remains secret at all times. However, in many practical situations these are unrealistic assumptions: The seed is often gathered after a reset/reboot from low entropy external events such as the timing of manual key presses, and the state can be compromised at unknown points in time via side channels or penetration attacks. The usual remedy (used by all the major operating systems, including Windows, Linux, FreeBSD, MacOS, iOS, etc.) is to periodically replenish the internal state through an auxiliary input with additional randomness harvested from the environment. However, recovering from such attacks in a provably correct and computationally optimal way had remained an unsolved challenge so far.

In this paper we formalize the problem of designing an efficient recovery mechanism from state compromise, by considering it as an online optimization problem. If we knew the timing of the last compromise and the amount of entropy gathered since then, we could stop producing any outputs until the state becomes truly random again. However, our challenge is to recover within a time proportional to this optimal solution even in the hardest (and most realistic) case in which (a) we know nothing about the timing of the last state compromise, and the amount of new entropy injected since then into the state, and (b) any premature production of outputs leads to the total loss of all the added entropy {\\em used by the RNG}, since the attacker can use brute force to enumerate all the possible low-entropy states. In other words, the challenge is to develop recovery mechanisms which are guaranteed to save the day as quickly as possible after a compromise we are not even aware of. The dilemma that we face is that any entropy used prematurely will be lost, and any entropy which is kept unused will delay the recovery.

After developing our formal definitional framework for RNGs with inputs, we show how to construct a nearly optimal RNG which is secure in our model. Our technique is inspired by the design of the Fortuna RNG (which is a heuristic RNG construction that is currently used by Windows and comes without any formal analysis), but we non-trivially adapt it to our much stronger adversarial setting. Along the way, our formal treatment of Fortuna enables us to improve its entropy efficiency by almost a factor of two, and to show that our improved construction is essentially tight, by proving a rigorous lower bound on the possible efficiency of any recovery mechanism in our very general model of the problem.

01:17 [Pub][ePrint]

Instant messaging services are quickly becoming the most dominant form of communication among consumers around the world. Apple iMessage, for example, handles over 2 billion message each day, while WhatsApp claims 16 billion messages from 400 million international users. To protect user privacy, these services typically implement end-to-end and transport layer encryption, which are meant to make eavesdropping infeasible even for the service providers themselves. In this paper, however, we show that it is possible for an eavesdropper to learn information about user actions, the language of messages, and even the length of those messages with greater than 96% accuracy despite the use of state-of-the-art encryption technologies simply by observing the sizes of encrypted packet. While our evaluation focuses on Apple iMessage, the attacks are completely generic and we show how they can be applied to many popular messaging services, including WhatsApp, Viber, and Telegram.