*19:17* [Pub][ePrint]
Blank Digital Signatures, by Christian Hanser and Daniel Slamanig
In this paper we present a novel type of digital signatures, which we call blank digital signatures. The basic idea behind this scheme is that an originator can define and sign a message template, describing fixed parts of a message as well as multiple choices for exchangeable

parts of a message. One may think of a form with blank fields, where for such fields the originator specifies all the allowed strings to choose from. Then, a proxy is given

the power to sign an instantiation of the template signed by the originator by using some secret information. By an instantiation, the proxy

commits to one allowed choice per blank field in the template.

The resulting message signature can be publicly verified under the originator\'s and the proxy\'s signature verification keys.

Thereby, no verifying party except the originator and the proxy learn anything about the ``unused\'\' choices from the message template given a message signature. Consequently, the template is hidden from verifiers.

We discuss several applications, provide a formal definition of blank digital signature schemes and introduce a security model. Furthermore, we provide an efficient construction of such a blank digital signature scheme from any secure digital signature scheme, pairing-friendly elliptic curves and polynomial commitments, which we prove secure in our model. We also provide a detailed efficiency analysis of our proposed construction supporting its practicality. Finally, we outline several open issues and extensions for future work.

*19:17* [Pub][ePrint]
Two is the fastest prime, by Thomaz Oliveira and Juilo López and Diego F. Aranha and Francisco Rodríguez-Henríquez
In this work we present the $\\lambda$-coordinates, a new system forrepresenting points in binary elliptic curves. We also provide efficient elliptic curve operations based on the new representation and timing results of our software implementation over the field $F_{2^{254}}$. As a result, we improved the known speed records for protected/unprotected single/multi-core software implementations of the random-point elliptic curve scalar multiplication at the 128-bit security level. When implemented on a Sandy Bridge 3.4GHz Intel Xeon processor, our software is able to compute a single/multi-core unprotected scalar multiplication in 72,300 and 47,900 clock cycles, respectively; and a protected single-core scalar multiplication in 114,800 cycles. These numbers improve by 2% on the newer Ivy Bridge platform.

*19:17* [Pub][ePrint]
Yet Another Attack On the Chinese Remainder Theorem Based Hierarchical Access Control Scheme, by Niu Liu and Shaohua Tang and Lingling Xu
The hierarchical access control scheme based on Chinese ReminderTheorem [49] (CRTHACS) was supposed to be capable of hiding

hierarchical structure, but Geiselmann et al. [18] showed practical attacks on CRTHACS to reveal the hierarchies it hides. Then, Zou et al. modified it, and gave a new CRTHACS [50] to resist those attacks. Nevertheless, we find that the modified version is still defective if it permits changes of structure, i.e. the scheme works in a dynamic scenario. In this paper, we describe our attack on the modified version of CRTHACS. We extend the description of the CRTHACS in a more proper form making it easier for us to look into the problem it has. We find the key character of the vulnerability which we name as double-invariance. We generalize our attack in an algebraic form and apply it to a series of hierarchical cryptographic

access control schemes that share the same vulnerability with CRTHACS. We also give the countermeasure to fix this vulnerability.

*19:17* [Pub][ePrint]
New Lattice Based Signature Using The Jordan Normal Form, by Hemlata Nagesh and Birendra Kumar Sharma
In this paper it is shown that the use of Jordan normal form instead ofHermite normal form would improve substantially the efficiency and the security

of the lattice based signature scheme. In this scheme we also use a new

hash function in such a way that the efficiency improved is obtain without

decreasing the security of the function.

*19:17* [Pub][ePrint]
Hardcore Predicates for a Diffie-Hellman Problem over Finite Fields, by Nelly Fazio and Rosario Gennaro and Irippuge Milinda Perera and William E. Wkeith III
A long-standing open problem in cryptography is proving the existence of (deterministic) hard-core predicates for the Diffie-Hellman problem defined over finite fields. In this paper we make progress on this problem by defining a very natural variation of the Diffie-Hellman problem over $\\mathbb{F}_{p^2}$ and proving the unpredictability of every single bit of one of the coordinates of the secret DH value.To achieve our result we modify an idea presented at CRYPTO\'01 by Boneh and Shparlinski [4] originally developed to prove that the LSB of the Elliptic Curve Diffie-Hellman problem is hard. We extend this idea in two novel ways:

1. We generalize it to the case of finite fields $\\mathbb{F}{p^2}$;

2. We prove that any bit, not just the LSB, is hard using the list decoding techniques of

Akavia et al. [1] (FOCS\'03) as generalized at CRYPTO\'12 by Duc and Jetchev [6].

In the process we prove several other interesting results:

- Our result hold also for a larger class of predicates, called segment predicates in [1];

- We extend the result of Boneh and Shparlinski to prove that every bit (and every segment predicate) of the Elliptic Curve Diffie-Hellman problem is hard-core;

- We define the notion of partial one-way function over finite fields $\\mathbb{F}{p^2}$ and prove that every bit (and every segment predicate) of one of the input coordinate for these functions is hard-core.

*16:17* [Pub][ePrint]
Attribute-Based Encryption for Circuits from Multilinear Maps, by Sanjam Garg and Craig Gentry and Shai Halevi and Amit Sahai and Brent Waters
In this work, we provide the first construction of Attribute-BasedEncryption (ABE) for general circuits. Our construction is based on

the existence of multilinear maps. We prove selective security of

our scheme in the standard model under the natural multilinear

generalization of the BDDH assumption. Our scheme achieves both

Key-Policy and Ciphertext-Policy variants of ABE.

Our scheme and its proof of security directly translate to the recent multilinear map

framework of Garg, Gentry, and Halevi.

This paper is the result of a merge of the works of Garg, Genry, and Halevi and of Sahai and Waters,

and subsumes both these works.

*16:17* [Pub][ePrint]
An Ideal-Security Protocol for Order-Preserving Encoding, by Raluca Ada Popa and Frank H. Li and Nickolai Zeldovich
Order-preserving encryption - an encryption scheme where the sort order of ciphertexts matches the sort order of the corresponding plaintexts - allows databases and other applications to process queries involving order over encrypted data efficiently. The ideal security guarantee for order-preserving encryption put forth in the literature is for the ciphertexts to reveal no information about the plaintexts besides order. Even though more than a dozen schemes were proposed, all these schemes leak more information than order.This paper presents the first order-preserving scheme that achieves ideal security. Our main technique is mutable cipher- texts, meaning that over time, the ciphertexts for a small number of plaintext values change, and we prove that mutable ciphertexts are needed for ideal security. Our resulting protocol is interactive, with a small number of interactions.

We implemented our scheme and evaluated it on microbenchmarks and in the context of an encrypted MySQL database application. We show that in addition to providing ideal security, our scheme achieves 1-2 orders of magnitude higher performance than the state-of-the-art order-preserving encryption scheme, which is less secure than our scheme.