International Association
for Cryptologic Research

We present a new transformation of chosen-plaintext secure predicate encryption schemes with public index into chosen-ciphertext secure schemes. Our construction requires only a universal one-way hash function and is selectively secure in the standard model. The transformation is not generic but can be applied to various existing schemes constructed from bilinear groups. Using common structural properties of these schemes we provide an efficient and simple transformation without overhead in form of one-time signatures or message authentication codes as required in the known generic transformations.

Secure multi-party computation platforms are becoming more and more practical. This has paved the way for privacy-preserving statistical analysis using secure multi-party computation. Simple statistical analysis functions have been emerging here and there in literature, but no comprehensive system has been compiled. We describe and implement the most used statistical analysis functions in the privacy-preserving setting including simple statistics, t-test, $\\chi^{2}$ test, Wilcoxon tests and linear regression. We give descriptions of the privacy-preserving algorithms and benchmark results that show the feasibility of our solution.

Submission: 20 August 2014
Notification: 4 September 2014
From September 22 to September 24
Location: Lodz, Poland
More Information: http://sdiwc.net/conferences/2014/icieis2014/

We introduce the notion of \\emph{universal parameters} as a method for generating the

trusted parameters for many schemes from just a single trusted setup. In such a scheme

a trusted setup process will produce universal parameters $U$. These parameters can

then be combined with the description, $d(\\cdot)$ of any particular cryptographic setup

algorithm to produce parameters $p_d$ that can be used by the cryptographic system associated

with $d$. We give a solution in the random oracle model based on indistinguishability obfuscation.

From February 9 to February 11
Location: Angers, Loire Valley, France
More Information: http://www.icissp.org

WhirlBob is a new Authenticated Encryption with Associated Data (AEAD)

algorithm derived from the first round CAESAR candidate StriBob

and the Whirlpool hash algorithm. The main advantage of WhirlBob over

StriBob is its greatly reduced implementation footprint on

resource-constrained platforms. Remarkably, the entire C reference

implementation of WhirlBob $\\pi$ fits onto a single page of the Appendix.

On most low-end microcontrollers the total software footprint of

$\\pi$+BLNK = WhirlBob AEAD is less than half a kilobyte. The greatly

reduced hardware gate count is also reflected as efficient bitsliced

straight-line implementations, especially on 64-bit platforms. Bitslicing

works as an efficient countermeasure against AES-style cache timing

side-channel attacks. The new design utilizes only the LPS or $\\rho$

keying line of Whirlpool in a flexible domain-separated Sponge mode BLNK

and adds the number of rounds in $\\pi$ permutation from 10 to 12 as a

countermeasure against Rebound Distinguishing attacks of ASIACRYPT \'09.

As with StriBob, the reduced-size Sponge design has a strong provable

security link with the original hash algorithm. We finally present some

discussion and analysis on differences between Whirlpool, the Russian

GOST Streebog hash, and the recently proposed draft Russian

Encryption Standard Kuznyechik.

Over the past few years, online service providers have started gathering increasing amounts of personal information to build user profiles and monetize them with advertisers and data brokers. Users have little control of what information is processed and are often left with an all-or-nothing decision between receiving free services or refusing to be profiled. This paper explores an alternative approach where users only disclose an aggregate model -- the ``gist\'\' -- of their data. We aim to preserve data utility and simultaneously provide user privacy. We show that this approach can be efficiently supported by letting users contribute encrypted and differentially-private data to an aggregator. The aggregator combines encrypted contributions and can only extract an aggregate model of the underlying data. We evaluate our framework on a dataset of 100,000 U.S. users obtained from the U.S. Census Bureau and show that (i) it provides accurate aggregates with as little as 100 users, (ii) it generates revenue for both users and data brokers, and (iii) its overhead is appreciably low.

A Hidden Vector Encryption (HVE) scheme is a special type of anonymous identity-based encryption (IBE) scheme where the attribute string associated with the ciphertext or the user secret key can contain wildcards. In this paper, we introduce two constant-size ciphertext-policy hidden vector encryption (CP-HVE) schemes. Our first scheme is constructed on composite order bilinear groups, while the second one is built on prime order bilinear groups. Both schemes are proven secure in a selective security model which captures plaintext (or payload) and attribute hiding. To the best of our knowledge, our schemes are the first HVE constructions that can achieve constant-size ciphertext among all the existing HVE schemes.

We provide the first provable-security analysis of the Intel Secure Key hardware RNG (ISK-RNG), versions of which have appeared in Intel processors since late 2011. To model the ISK-RNG, we generalize the PRNG-with-inputs primitive, introduced Dodis et al. introduced at CCS\'13 for their /dev/[u]random analysis. The concrete security bounds we uncover tell a mixed story. We find that ISK-RNG lacks backward-security altogether, and that the forward-security bound for the ``truly random\'\' bits fetched by the RDSEED instruction is potentially worrisome. On the other hand, we are able to prove stronger forward-security bounds for the pseudorandom bits fetched by the RDRAND instruction. En route to these results, our main technical efforts focus on the way in which ISK-RNG employs CBCMAC as an entropy extractor.

A Kummer variety is the quotient of an abelian variety by

the automorphism $(-1)$ acting on it.

Kummer varieties can be seen as a higher dimensional generalisation of

the $x$-coordinate representation of a point of an elliptic curve

given by its Weierstrass model. Although there is no group law on the

set of points of a Kummer variety, there remains enough arithmetic

to enable the computation of exponentiations via a

Montgomery ladder based on differential additions.

In this paper, we explain that the arithmetic of a Kummer variety

is much richer than

usually thought. We describe a set of composition laws

which exhaust this arithmetic and show that these

laws may turn out to be useful in order to improve certain

algorithms. We explain how to compute efficiently these laws in the model of

Kummer varieties provided by level $2$ theta functions. We also

explain how to recover the full group law of the abelian variety

with a representation almost as compact and in many cases as efficient as

the level $2$ theta functions model of Kummer varieties.

We introduce the k-LWE problem, a Learning With Errors variant of the

k-SIS problem. The Boneh-Freeman reduction from SIS to k-SIS suffers from an exponential loss in k. We improve and extend it to an LWE to k-LWE reduction with a polynomial loss in k, by relying on a new technique involving trapdoors for random integer kernel lattices. Based on this hardness result, we present the first algebraic construction of a traitor tracing scheme whose security relies on the worst-case hardness of standard lattice problems. The proposed LWE traitor tracing is almost as efficient as the LWE encryption. Further, it achieves public traceability, i.e., allows the authority to delegate the tracing capability to untrusted parties. To this aim, we introduce the notion of projective sampling family in which each sampling function is keyed and, with a projection of the key on a well chosen space, one can simulate the sampling function in a computationally indistinguishable way. The construction of a projective sampling family from k-LWE allows us to achieve public traceability, by publishing the projected keys of the users. We believe that the new lattice tools and the projective sampling

family are quite general that they may have applications in other areas.

We present a signature scheme provably secure in the standard model (no random oracles) based on the

worst-case complexity of approximating the Shortest Vector Problem in ideal lattices within polynomial

factors. The distinguishing feature of our scheme is that it achieves short signatures (consisting of a

single lattice vector), and relatively short public keys (consisting of O(log n) vectors.) Previous lattice

schemes in the standard model with similarly short signatures, due to Boyen (PKC 2010) and Micciancio

and Peikert (Eurocrypt 2012), had substantially longer public keys consisting of Ω(n) vectors (even when

implemented with ideal lattices). We also present a variant of our scheme that further reduces the public

key size to just O(log log n) vectors and allows for a tighther security proof by making the signer stateful.

In Financial Cryptography 2013, Bringer, Chabanne

and Patey proposed two biometric authentication schemes between

a prover and a verifier where the verifier has biometric

data of the users in plain form. The protocols are based on secure

computation of Hamming distance in the two-party setting. Their

first scheme uses Oblivious Transfer (OT) and provides security

in the semi-honest model. The other scheme uses Committed

Oblivious Transfer (COT) and is claimed to provide full security

in the malicious case.

In this paper, we show that their protocol against malicious

adversaries is not actually secure. We propose a generic attack

where the Hamming distance can be minimized without knowledge

of the real input of the user. Namely, any attacker can

impersonate any legitimate user without prior knowledge. We

propose an enhanced version of their protocol where this attack

is eliminated. We provide a simulation based proof of the security

of our modified protocol. In addition, for efficiency concerns, the

modified version also utilizes Verifiable Oblivious Transfer (VOT)

instead of COT. The use of VOT does not reduce the security of

the protocol but improves the efficiency significantly.

Name: J. C. Migliore

We consider the notion of a non-interactive key exchange (NIKE). A NIKE scheme allows a party \\(A\\) to compute a common shared key with another party \\(B\\) from \\(B\\)\'s public key and \\(A\\)\'s secret key alone. This computation requires no interaction between \\(A\\) and \\(B\\), a feature which distinguishes NIKE from regular (i.e., interactive) key exchange not only quantitatively, but also qualitatively.

Our first contribution is a formalization of NIKE protocols as ideal

functionalities in the Universal Composability (UC) framework.

As we will argue, existing NIKE definitions (all of which are game-based) do not support a modular analysis either of NIKE schemes themselves, or of the use of NIKE schemes. We provide a simple and natural UC-based NIKE definition that allows for a modular analysis both of NIKE schemes and their use in larger protocols.

We proceed to investigate the properties of our new definition, and in

particular its relation to existing game-based NIKE definitions. We find that

(a) game-based NIKE security is equivalent to UC-based NIKE security

against \\emph{static} corruptions, and

(b) UC-NIKE security against adaptive corruptions cannot be achieved

without additional assumptions (but \\emph{can} be achieved in the random oracle model).

Our results suggest that our UC-based NIKE definition is a useful and simple abstraction of non-interactive key exchange.

Applications of elliptic curve cryptography to anonymity, privacy and

censorship circumvention call for methods to represent uniformly random

points on elliptic curves as uniformly random bit strings, so that, for

example, ECC network traffic can masquerade as random traffic.

At ACM CCS 2013, Bernstein et al. proposed an efficient approach,

called ``Elligator,\'\' to solving this problem for arbitrary elliptic

curve-based cryptographic protocols, based on the use of efficiently

invertible maps to elliptic curves. Unfortunately, such invertible maps

are only known to exist for certain classes of curves, excluding in

particular curves of prime order and curves over binary fields. A variant

of this approach, ``Elligator Squared,\'\' was later proposed by Tibouchi

(FC 2014) supporting not necessarily injective encodings to elliptic

curves (and hence a much larger class of curves), but, although some

rough efficiency estimates were provided, it was not clear how an actual

implementation of that approach would perform in practice.

In this paper, we show that Elligator Squared can indeed be implemented

very efficiently with a suitable choice of curve encodings. More

precisely, we consider the binary curve setting (which was not discussed

in Tibouchi\'s paper), and implement the Elligator Squared bit string

representation algorithm based on a suitably optimized version of the

Shallue--van de Woestijne characteristic 2 encoding, which we show can

be computed using only multiplications, trace and half-trace

computations, and a few inversions.

On the fast binary curve of Oliveira et al. (CHES 2013), our

implementation runs in an average of only 22850 Haswell cycles, making

uniform bit string representations possible for a very reasonable

overhead---much smaller even than Elligator on Edwards curves.

As a side contribution, we also compare implementations of Elligator and

Elligator Squared on a curve supported by Elligator, namely

Curve25519. We find that generating a random point and its uniform

bitstring representation is around 35-40% faster with Elligator for

protocols using a fixed base point (such as static ECDH), but 30-35%

faster with Elligator Squared in the case of a variable base point

(such as ElGamal encryption). Both are significantly slower

than our binary curve implementation.

The GGH Graded Encoding Scheme, based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis in the original paper, the scheme requires very large parameters to provide security for its underlying encoding re-randomization process. Our main contributions are to formalize, simplify and improve the efficiency and the security analysis of the re-randomization process in the GGH construction. This results in a new construction that we call GGHLite. In particular, we first lower the size of a standard deviation parameter of the re-randomization process of the original scheme from exponential to polynomial in the security parameter. This first improvement is obtained via a finer security analysis of the

drowning step of re-randomization, in which we apply the

Rényi divergence instead of the conventional statistical distance as a measure of distance between distributions. Our second improvement is to reduce the number of randomizers needed from $\\Omega(n \\log n)$ to $2$, where $n$ is the dimension of the underlying ideal lattices. These two contributions allow us to decrease the bit size of the public parameters from $O(\\lambda^5 \\log \\lambda)$ for the

GGH scheme to $O(\\lambda \\log^2 \\lambda)$ in GGHLite, with respect to the security parameter $\\lambda$ (for a constant multilinearity parameter $\\kappa$).

Related-key attacks (RKAs) concern the security of cryptographic primitives in the situation where the key can be manipulated by the adversary. In the RKA setting, the adversary\'s power is expressed through the class of related-key deriving (RKD) functions which the adversary is restricted to using when modifying keys. Bellare and Kohno (Eurocrypt 2003) first formalised RKAs and pin-pointed the foundational problem of constructing RKA-secure pseudorandom functions (RKA-PRFs). To date there are few constructions for RKA-PRFs under standard assumptions, and it is a major open problem to construct RKA-PRFs for larger classes of RKD functions. We make significant progress on this problem. We first show how to repair the Bellare-Cash framework for constructing RKA-PRFs and extend it to handle the more challenging case of classes of RKD functions that contain claws. We apply this extension to show that a variant of the Naor-Reingold function already considered by Bellare and Cash is an RKA-PRF for a class of affine RKD functions under the DDH assumption, albeit with an exponential-time security reduction. We then develop a second extension of the Bellare-Cash framework, and use it to show that the same Naor-Reingold variant is actually an RKA-PRF for a class of degree $d$ polynomial RKD functions under the stronger decisional $d$-Diffie-Hellman inversion assumption. As a significant technical contribution, our proof of this result avoids the exponential-time security reduction that was inherent in the work of Bellare and Cash and in our first result.

In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse integer representations of short vectors in lattices as chromesomes, which, we prove, can guarantee finding the shortest lattice vector under a Markov chain analysis. Moreover, we also suggest some improvements by introducing heuristic techniques: local search and heuristic pruning. The experimental results show that the genetic algorithm outperforms most enumeration algorithms in running time, and achieves the shortest vectors in larger dimensions under SVP challenge benchmarks

It has been an open problem for a number of years to construct an identity-based fully homomorphic encryption (IBFHE) scheme (first mentioned by Naccache at CHES/CRYPTO 2010). At CRYPTO 2013, Gentry, Sahai and Waters largely settled the problem by presenting leveled IBFHE constructions based on the Learning With Errors problem. However their constructions are not bootstrappable, and as a result, are not ``pure\'\' IBFHE schemes. The major challenge with bootstrapping in the identity-based setting is that it must be possible to non-interactively derive from the public parameters an ``encryption\'\' of the secret key for an arbitrary identity. All presently-known leveled IBFHE schemes only allow bootstrapping if such an ``encryption\'\' of the secret key is supplied out-of-band. In this work, we present a ``pure\'\' IBFHE scheme from indistinguishability obfuscation, and extend the result to the attribute-based setting. Our attribute-based scheme is the first to support homomorphic evaluation on ciphertexts with different attributes. Finally, we characterize presently-known leveled IBFHE schemes with a view to developing a ``compiler\'\' from a leveled IBFHE scheme to a bootstrappable IBFHE scheme, and sufficient conditions are identified.