International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2015-02-24
04:17 [Pub][ePrint] Inner Product Masking Revisited, by Josep Balasch and Sebastian Faust and Benedikt Gierlichs

  Masking is a popular countermeasure against side channel attacks. Many practical works use Boolean masking because of its simplicity, ease of implementation and comparably low performance overhead. Some recent works have explored masking schemes with higher algebraic complexity and have shown that they provide more security than Boolean masking at the cost of higher overheads. In particular, masking based on the inner product was shown to be practical, albeit not efficient, for a small security parameter, and at the same time provable secure in the domain of leakage resilient cryptography for a large security parameter. In this work we explore a security versus efficiency tradeoff and provide an improved and tweaked inner product masking. Our practical security evaluation shows that it is less secure than the original inner product masking but more secure than Boolean masking. Our performance evaluation shows that our scheme is only four times slower than Boolean masking and more than two times faster than the original inner product masking. Besides the practical security analysis we prove the security of our scheme and its masked operations in the threshold probing model.



04:17 [Pub][ePrint] Provably weak instances of Ring-LWE, by Yara Elias and Kristin E. Lauter and Ekin Ozman and Katherine E. Stange

  The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus.

Our attack is based on the attack on Poly-LWE which was presented in [EHL]. We extend the EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-2 cyclotomic fields, presented using the minimal polynomial of $\\zeta_{2^n} \\pm 1$.



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] Re-encryption Verifiability: How to Detect Malicious Activities of a Proxy in Proxy Re-encryption, by Satsuya Ohata and Yutaka Kawai and Takahiro Matsuda and Goichiro Hanaoka and Kanta Matsuura

  In this paper, we introduce a new functionality for proxy re-encryption (PRE) that we call re-encryption verifiability. In a PRE scheme with re-encryption verifiability (which we simply call verifiable PRE, or VPRE), a receiver of a re-encrypted ciphertext can verify whether the received ciphertext is correctly transformed from an original ciphertext by a proxy, and thus can detect illegal activities of the proxy. We formalize the security model for a VPRE scheme, and show that the single-hop uni-directional PRE scheme by Hanaoka et al. (CT-RSA 2012) can be extended to a secure VPRE scheme.



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] Weak Ideal Functionalities for Designing Random Oracles with Applications to Fugue, by Shai Halevi, William E. Hall, Charanjit S. Jutla, Arnab Roy

  We define ideal functionalities that are weaker than ideal functionalities traditionally used in realizing variable input length (VIL) random oracles (RO) in the indifferentiability or universal-Composability (UC) model. We also show realization of VIL-RO using these weaker ideal functionalities, with applications to proving Fugue and CubeHash hash functions to be VIL-RO. We argue that components of Fugue realize this weaker ideal functionality using techniques employed in proving resistance of Fugue to differential collision-attacks. This should be contrasted with other hash functions that are proven VIL-RO assuming the components are extremely ideal, e.g. random permutations.



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] Efficient Hardware Design for Computing Pairings Using Few FPGA In-built DSPs, by Riadh Brinci and Walid Khmiri and Mefteh Mbarek and Abdellatif Ben Rabâa and Ammar Bouallègue

  This paper is devoted to the design of a 258-bit multiplier for computing pairings over Barreto-Naehrig (BN) curves at 128-bit security level. The proposed design is optimized for Xilinx field programmable gate array (FPGA). Each 258-bit integer is represented as a polynomial with five, 65 bit signed integer, coefficients. Exploiting this splitting we designed a pipelined 65-bit multiplier based on new Karatsuba- Ofman variant using non-standard splitting to fit to the Xilinx embedded digital signal processor (DSP) blocks. We prototype the coprocessor in two architectures pipelined and serial on a Xilinx Virtex-6 FPGA using around 17000 slices and 11 DSPs in the pipelined design and 7 DSPs in the serial. The pipelined 128-bit pairing is computed in 1. 8 ms running at 225MHz and the serial is performed in 2.2 ms running at 185MHz. To the best of our knowledge, this implementation outperforms all reported hardware designs in term of DSP use.

Keywords-