*04:17* [Pub][ePrint]
Dynamic Searchable Symmetric Encryption with Minimal Leakage and Efficient Updates on Commodity Hardware, by Attila A. Yavuz and Jorge Guajardo
Dynamic Searchable Symmetric Encryption (DSSE) enables a client to perform keyword queries and update operations on the encrypted file collections. DSSE has several important applications such as privacy-preserving data outsourcing for computing clouds. In this paper, we developed a new parallelizable DSSE scheme that achieves the highest privacy among all compared alternatives with low information leakage, non-interactive and efficient updates, compact client storage, low server storage for large file-keyword pairs with an easy design and implementation. Our scheme achieves these desirable properties with a very simple data structure (i.e., a bit matrix supported with two static hash tables) that enables efficient yet secure search/update operations on it. We formally prove that our scheme is secure (in random oracle model) and demonstrated that it is fully practical with large number of file-keyword pairs even with an implementation on simple hardware configurations.

*04:17* [Pub][ePrint]
TRACING ATTACKS ON U-PROVE WITH REVOCATION MECHANISM, by Lucjan Hanzlik and Przemys{\\l}aw Kubiak and Miros{\\l}aw Kuty{\\l}owski
Anonymous credential systems have to provide strong privacy protection. A user presenting anonymous credentials may prove his (chosen) attributes without leaking informations about his identity. In this paper we consider U-Prove -- one of the major commercial anonymous credential systems. We show that the efficient revocation mechanism designed for U-Prove enables a system provider to efficiently trace the users\' activities. Namely, the Revocation Authority run the system provider may execute the U-Prove protocol in a malicious way so that:

(a) the deviations from the protocol remain undetected,

(b) the Revocation Authority becomes aware of each single authentication of a user in the whole system and can link them (regardless which attributes are disclosed by the user against the verifiers),

(c) can link presentation tokens with the corresponding token issuing procedure (under some conditions).

Thereby, the system described in the technical drafts of U-Prove does not protect privacy of a user unless one can unconditionally trust the system provider. In fact, a malicious system provider may convert the Revocation Authority into a ``Big Brother\'\' installation.

*04:17* [Pub][ePrint]
sHMQV: An Efficient Key Exchange Protocol for Power-limited Devices, by Shijun Zhao and Qianying Zhang
In this paper we focus on designing authenticated key exchange protocols for practical scenarios where the party consists of a powerful but untrusted host (e.g., PC, mobile phone, etc) and a power-limited but trusted device (e.g., Trusted Platform Module, Mobile Trusted Module, Smart Card, etc). HMQV and (s,r)OAKE protocols are the state-of-the-art in the integrity of security and efficiency. However, we find that they are not suitable for the above scenarios as all (or part) of the online exponentiation computations must be performed in the power-limited trusted devices, which makes them inefficient for the deployment in practice.To overcome the above inefficiency, we propose a variant of HMQV protocol, denoted sHMQV, under some new design rationales which bring the following advantages: 1) eliminating the validation of the ephemeral public keys, which costs one exponentiation; 2) the power-limited trusted device only performs one exponentiation, which can be pre-computed offline; 3) all the online exponentiation computations can be performed in the powerful host. The above advantages make sHMQV enjoy better performance than HMQV and (s,r)OAKE, especially when deployed in the scenarios considered in this paper. We finally formally prove the security of sHMQV in the CK model.

*04:17* [Pub][ePrint]
The Multivariate Hidden Number Problem, by Steven D. Galbraith and Barak Shani
This work extends the line of research on the hidden number problem. Motivated by studying bit security in finite fields, we define the multivariate hidden number problem. Here, the secret and the multiplier are vectors, and partial information about their dot product is given. Using tools from discrete Fourier analysis introduced by Akavia, Goldwasser and Safra, we show that if one can find the significant Fourier coefficients of some function, then one can solve the multivariate hidden number problem for that function. This allows us to generalise the work of Akavia on the hidden number problem with (non-adaptive) chosen multipliers to all finite fields.We give two further applications of our results, both of which generalise previous works to all (finite) extension fields. The first considers the general (random samples) hidden number problem in F_{p^m} and assumes an advice is given to the algorithm. The second considers a model that allows changing representations, where we show hardness of individual bits for elliptic curve and pairing based functions for elliptic curves over extension fields, as well as hardness of any bit of any component of the Diffie-Hellman secret in F_{p^m} (m>1).

*04:17* [Pub][ePrint]
How to Compress Homomorphic Ciphertexts, by Anne Canteaut and Sergiu Carpov and Caroline Fontaine and Tancrède Lepoint and María Naya-Plasencia and Pascal Paillier and Renaud Sirdey
In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob\'s public key pk and to send the ciphertext c = HE_pk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting c as efficiently as possible from Alice to Charlie. As previously noted, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random key k and sends a much smaller ciphertext c′ = (HE_pk(k), E_k(m)) that Charlie decompresses homomorphically into the original c using a decryption circuit.In this paper, we revisit that paradigm in light of its concrete implementation constraints; in particular E is chosen to be an additive IV-based stream cipher. We propose 2 new designs such that the decryption circuit has very small multiplicative depth, typically between 8 and 12 for 128-bit security. Our first construction of depth 12 is inspired by Trivium and reportedly the current fastest option. Our second construction, based on exponentiation in binary fields, is impractical but sets the lowest depth record to 8 for 128-bit security.

*04:17* [Pub][ePrint]
Comprehensive Efficient Implementations of ECC on C54xx Family of Low-cost Digital Signal Processors, by Muhammad Yasir Malik
Resource constraints in smart devices demand an efficient cryptosystem that allows for low power and memory consumption. This has led to popularity of comparatively efficient Elliptic curve cryptog-raphy (ECC). Prior to this paper, much of ECC is implemented on re-configurable hardware i.e. FPGAs, which are costly and unfavorable as low-cost solutions.We present comprehensive yet efficient implementations of ECC on fixed-point TMS54xx series of digital signal processors (DSP). 160-bit prime field GF(p) ECC is implemented over a wide range of coordinate choices. This paper also implements windowed recoding technique to provide better execution times. Stalls in the programming are mini-mized by utilization of loop unrolling and by avoiding data dependence. Complete scalar multiplication is achieved within 50 msec in coordinate implementations, which is further reduced till 25 msec for windowed-recoding method. These are the best known results for fixed-point low power digital signal processor to date.

*04:17* [Pub][ePrint]
Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy, by Maciej Skorski
Hardcore lemmas are results in complexity theory which state that average-case hardness must have a very hard ``kernel\'\', that is a subset of instances where the given problem is extremely hard. They find important applications in hardness amplification. In this paper we revisit the following two fundamental results:\\begin{enumerate}[(a)]

\\item The hardcore lemma for unpredictability, due to Impagliazzo (FOCS \'95). It states that if a boolean function $f$ is ``moderately\'\' hard to predict on average, then there must be a set of noticeable size on which $f$ is ``extremely\'\' hard to predict.

\\item The hardcore lemma for indistinguishability, proved by Maurer and Tessaro (TCC\'10), states that for two random variables $X$ and $Y$ which are $\\epsilon$-computationally close, there are events $A$ and $B$ of probability $1-\\epsilon$ such that the distributions of $X|A$ and $Y|B$ are ``computationally\'\' identical.

\\end{enumerate}

Using only the standard min-max theorem and some basic facts about convex approximations in $L_p$ spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform setting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strengthening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to extract pseudorandomness from a sequence of metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.

*04:17* [Pub][ePrint]
Constructing and Understanding Chosen Ciphertext Security via Puncturable Key Encapsulation Mechanisms, by Takahiro Matsuda and Goichiro Hanaoka
In this paper, we introduce and study a new cryptographic primitive that we call \"puncturable key encapsulation mechanism\" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC\'91), and \"break down\" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security.To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT\'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: \"sender non-committing encryption\" (SNCE) and non-interactive witness indistinguishable proofs.

Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: \"SNCE\" and \"symmetric key encryption secure for key-dependent messages\" (KDM secure SKE). Our construction realizes the \"decrypt-then-re-encrypt\"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.