International Association
for Cryptologic Research

Proxy signatures allow an entity (the delegator) to delegate his signing capabilities to other entities (called proxies), who can then produce signatures on behalf of the delegator. Typically, a delegator may not want to give a proxy the power to sign any message on his behalf, but only messages from a well defined message space. Therefore, the so called delegation by warrant approach has been introduced. Here, a warrant is included into the delegator\'s signature (the so called certificate) to describe the message space from which a proxy is allowed to choose messages to produce valid signatures for. Interestingly, in all previously known constructions of proxy signatures following this approach, the warrant is made explicit and, thus, is an input to the verification algorithm of a proxy signature. This means, that a verifier learns the entire message space for which the proxy has been given the signing power. However, it may be desirable to hide the remaining messages in the allowed message space from a verifier. This scenario has never been investigated in context of proxy signatures, but seems to be interesting for practical applications. In this paper, we resolve this issue by introducing so called warrant-hiding proxy signatures. We provide a formal security definition of such schemes by augmenting the well established security model for proxy signatures by Boldyreva et al. Furthermore, we discuss strategies how to realize this warrant-hiding property and we also provide two concrete instantiations of such a scheme. They enjoy different advantages, but are both entirely practical. Moreover, we prove them secure with respect to the augmented security model.

In this paper, we revisit the private over-threshold data aggregation problem, and formally define the problem\'s security requirements as both data and user privacy goals. To achieve both goals, and to strike a balance between efficiency and functionality, we devise a novel cryptographic construction that comes in two schemes; a fully decentralized construction and its practical but semi-decentralized variant. Both schemes are provably secure in the semi-honest model.

We analyze the computational and communication complexities of our construction, and show that it is much more efficient than the existing protocols in the literature.

Finally, we show that our basic protocol is efficiently transformed into a stronger protocol secure in the presence of malicious adversaries, together with performance and security analysis.

We propose a new type of meet-in-the-middle attack that splits the

cryptographic primitive in parallel to the execution of the operations. The result of the division are two primitives that have smaller input sizes and thus require lower attack complexities.

However, the division is not completely independent and the sub-primitives depend (output of one is the input for the other) mutually on a certain number of bits. When the number of such bits is relatively small, we show a technique based on three classical meet-in-the-middle attacks that can recover the secret key of the cipher faster than an exhaustive search. We apply our findings to the lightweight block cipher KLEIN and show attacks on 10/11/13 rounds of KLEIN-64/-80/-96.

Our approach requires only one or two pairs of known plaintexts and always recovers the secret key.

We study provably secure anonymity, focusing on ultimate

anonymity - strongest-possible anonymity requirements and

adversaries. We begin with rigorous definition of anonymity

against wide range of computationally-bounded attackers,

including eavesdroppers, malicious peers, malicious destina-tions, and their combinations. Following the work of Hevia and Micciancio [15], our definition is generic, and captures dierent notions of anonymity (e.g., unobservability and sender anonymity).

We then study the feasibility of ultimate anonymity. We

show there is a protocol satisfying this requirement, but with

absurd (although polynomial) inefficiency and overhead. We

show that such inefficiency and overhead is unavoidable for

`ultimate anonymity\'. We then present a slightly-relaxed

requirement and present feasible protocols for it.

The hyperelliptic curve Ate pairing provides an efficient way to compute a

bilinear pairing on the Jacobian variety of a hyperelliptic curve.

We prove that, for supersingular elliptic curves with embedding degree

two, square of the Ate pairing is nothing but the Weil pairing.

Using the formula, we develop an X-coordinate only pairing inversion method.

However, the algorithm is still infeasible for cryptographic size problems.

Given a network of n = 2^k

gossipers, we want to schedule a cyclic calendar

of meetings between all of them, such that: (1) each gossiper communicates

(gossips) only once a day, with one other gossiper, (2) in every (n 1) consecutive

days, each gossiper meets all other gossipers, and (3) every gossip, initiated by

any gossiper, will reach all gossipers within k = log(n) days.

In this paper we study the above stated meet-all gossipers problem, by den-ing and constructing the Gossip Latin Square (GLS), a combinatorial structure

which solves the problem.

We present DURP, a decentralized protocol for

unobservable, anonymous reporting to an untrusted destination,

with low latency and overhead. DURP provably ensures strong

anonymity properties, as required for some applications (and not

provided by existing systems and practical designs, e.g., Tor),

specifically:

Provable unobservability against global eavesdropper and

malicious participants.

Provable source anonymity against a malicious destination.

Probable-innocence against a malicious destination which is

also a global eavesdropper.

DURP design is a modular combination of two modules: a

queuing module, ensuring fixed rates for certain events, together

with an anonymization module, which can use either Onion-Routing (DURP^OR) or Crowds (DURP^Crowds). We present anal-ysis, backed by simulation results, of the network properties and

performance of DURP, and show it has reasonable overhead. We

also use the analysis results to create an optimized version of

DURP.

Koblitz curves are a class of computationally efficient elliptic curves where scalar multiplications can be accelerated using $\\tau$NAF representations of scalars. However conversion from an integer scalar to a short $\\tau$NAF is costly and thus restricts speed. In this paper we present acceleration techniques for the recently proposed scalar conversion hardware based on division by $\\tau^2$. Acceleration is achieved in two steps. First we perform computational optimizations to reduce the number of long subtraction operations during the conversion of scalar. This helps in reducing the number of integer adder/subtracter circuits from the critical paths of the conversion architecture. In the second step, we perform pipelining in the conversion architecture in such a way that the pipeline stages are always utilized. Due to bubble free nature of the pipelining, clock cycle requirement of the conversion architecture remains same, while operating frequency increases drastically.

We present detailed experimental results to support our claims made in this paper.

In AsiaCCS 2011, Wang et al. proposed a two-level heuristic sieve algorithm for the shortest vector problem in lattices, which improves the Nguyen-Vidick sieve algorithm. Inspired by their idea, we present a three-level sieve algorithm in this paper, which is shown to have better time complexity. More precisely, the time complexity of our algorithm is $2^{0.3778n+o(n)}$ polynomial-time operations and the corresponding space complexity is $2^{0.2833n+o(n)}$ polynomially many bits.

We present the first decentralized secure funds transfer protocol with multiple participants. The protocol ensures that a participant can only lose money, if a peer it trusted is corrupted. Furthermore, the loss is

bounded by the credit allocated to this partner. The protocol supports expiration times for payment orders, and realistic network queuing delay.We achieve this using model and techniques from the Quality of Service area to guarantee delays and avoid payment order expiration. We present rigorous security proof.

The most widely used secure Internet communication standard TLS (Transport Layer Security) has an optional client certificate authentication feature that in theory has significant security advantages over HTML form-based password authentication. In this paper we discuss practical security and usability issues related to TLS client certificate authentication stemming from the server side and browser implementations. In particular we analyze Apache mod_ssl implementation on server side and the most popular browsers - Mozilla Firefox, Google Chrome and Microsoft Internet Explorer on client side. We complement our paper with a case study performed in Estonia where TLS client certificate authentication is widely used. We present our recommendations for TLS implementations on the client and server side to improve the security and usability of TLS client certificate authentication.

In August 2012, the Stribog hash function was selected as the new Russian hash standard (GOST R 34.11-2012). Stribog is an AES-based primitive and is considered as an asymmetric reply to the new SHA-3. In this paper we investigate the collision resistance of the Stribog compression function and its internal cipher. Specifically, we present a message differential path for the internal block cipher that allows us to efficiently obtain a 5-round free-start collision and a 7.75 free-start near collision for the internal cipher with complexities $2^8$ and $2^{40}$, respectively. Finally, the compression function is analyzed and a 7.75 round semi free-start collision, 8.75 and 9.75 round semi free-start near collisions are presented along with an example for 4.75 round 49 out of 64 bytes near colliding message pair.

In this article, we propose a new improvement of the rebound techniques, used for cryptanalyzing AES-like permutations during the past years. Our improvement, that allows to reduce the complexity of the attacks, increases the probability of the outbound part by considering a new type of differential paths. Moreover, we propose a new type of distinguisher, the multiple limited-birthday problem, based on the limited-birthday one, but where differences on the input and on the output might have randomized positions. We also discuss the generic complexity for solving this problem and provide a lower bound of it as well as we propose an efficient and generic algorithm for solving it. Our advances lead to improved distinguishing or collision results for many AES-based functions such as AES, ECHO, Grøstl, LED, PHOTON and Whirlpool.

We examine the security of the 64-bit lightweight block cipher PRESENT-80 against related-key differential attacks. With a computer search we are able to prove that no related-key differential characteristic exists with probability higher than $2^{-64}$ for the full-round PRESENT-80.

To overcome the exponential (in the state and key sizes) computational complexity we use truncated differences, however as the key schedule is not nibble oriented, we switch to actual differences and apply early abort techniques to prune the tree-based search.

With a new method called extended split approach we are able to make the whole search feasible and we implement and run it in real time.

Our approach targets the PRESENT-80 cipher however, with small modifications can be reused for other lightweight ciphers as well.

White-box cryptography has attracted a growing interest from researchers in the last decade. Several white-box implementations of standard block-ciphers (DES, AES) have been proposed but they have all been broken. On the other hand, neither evidence of existence nor proofs of impossibility have been provided for this particular setting. This might be in part because it is still quite unclear what

{white-box} cryptography really aims to achieve and which security properties are expected from white-box programs in applications. This paper builds a first step towards a practical answer to this question by translating folklore intuitions behind white-box cryptography into concrete security notions. Specifically, we introduce the notion of white-box compiler that turns a symmetric encryption scheme into randomized white-box programs, and we capture several desired security properties such as one-wayness, incompressibility and traceability for white-box programs. We also give concrete examples of white-box compilers that already achieve some of these notions. Overall, our results open new perspectives on the design of white-box programs that securely implement symmetric encryption.

A (k; n) threshold secret image sharing scheme, abbreviated as (k; n)-TSISS, splits a secret image into n shadow images in such a way

that any k shadow images can be used to reconstruct the secret image

exactly. In 2002, for (k; n)-TSISS, Thien and Lin reduced the size of each

shadow image to 1/k of the original secret image. Their main technique

is by adopting all coefficients of a (k-1)-degree polynomial to embed the secret pixels. This benet of small shadow size has drawn many researcher\'s attention and their technique has been extensively used in

the following studies. In this paper, we rst show that this technique

is neither information theoretic secure nor computational secure. Furthermore, we point out the security defect of previous (k; n)-TSISSs for

sharing textual images, and then fix up this security defect by adding an

AES encryption process. At last, we prove that this new (k; n)-TSISS is

computational secure.

It is a common wisdom that servers should better store the one-way hash of their clients\' passwords, rather than storing the password in the clear. This paper introduces Catena, a new one-way function for that purpose. Catena is sequentially memory-hard, which hinders massively parallel attacks on cheap memory-constrained hardware, such as recent \"graphical processing units\", GPUs. Furthermore, Catena has been designed to resist cache-timing attacks. This distinguishes Catena from scrypt, which is also sequentially memory-hard, but which we show to be vulnerable to cache-timing attacks. Additionally, Catena supports (1) client-independent updates (the server can increase the security parameters and update the password hash without user interaction or knowing the password), (2) a server relief protocol (saving the server\'s resources at the cost of the client), and (3) a variant Catena-KG for secure key derivation (to securely generate many cryptographic keys of arbitrary lengths such that compromising

some keys does not help to break others).

In June 2013 the U.S. National Security Agency proposed two families of ultra-lightweight block ciphers, called Simon and Speck. In this paper we present the first cryptanalysis of round-reduced versions of Simon. We mount differential distinguishers and key-recovery attacks on up to 14/32, 17/36, 21/44, 26/54, and 32/72 rounds, for the 32-, 48-, 64-, 96-, and 128-bit versions, respectively. Furthermore, we briefly consider impossible-differential and rotational attacks. While our attacks are mostly academic, they demonstrate the drawback of the aggressive optimizations in Simon which allow powerful differential cryptanalysis.

Helper data schemes are a security primitive used for privacy-preserving biometric databases and Physical Unclonable Functions.

One of the oldest known helper data schemes is the Code Offset Method (COM).

We propose an extension of the COM: the helper data is accompanied by many instances of fake helper data that is drawn from the same distribution as the real one.

While the adversary has no way to distinguish between them, the legitimate party has more information and *can* see the difference.

We use an LDPC code in order to improve the efficiency of the legitimate party\'s selection procedure.

Our construction provides a new kind of trade-off: more effective use of the source entropy, at the price of increased helper data storage.

We give a security analysis in terms of Shannon entropy and order-2 Renyi entropy.

We present the first anonymous hierarchical identity based encryption (HIBE) scheme using

Type-3 pairings with adaptive security based on standard assumptions. Previous constructions

of anonymous HIBE schemes did not simultaneously achieve all these features.

The new construction uses dual pairing vector spaces using an identity hash earlier used by Boneh, Boyen and Goh.

The proof of security follows dual system approach based on decisional subspace assumptions

which are implied by Symmetric eXternal Diffie-Hellman (SXDH) assumption in Type-3 pairing groups.