International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) 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).

09:17 [Pub][ePrint] Differential Properties of the HFE Cryptosystem, by Taylor Daniels and Daniel Smith-Tone

  Multivariate Public Key Cryptography (MPKC) has been put forth as a possible post-quantum family of cryptographic schemes. These schemes lack provable security in the reduction theoretic sense, and so their security against yet undiscovered attacks remains uncertain. The effectiveness of differential attacks on various field-based systems has prompted the investigation of differential properties of multivariate schemes to determine the extent to which they are secure from differential adversaries. Due to its role as a basis for both encryption and signature schemes we contribute to this investigation focusing on the HFE cryptosystem. We derive the differential symmetric and invariant structure of the HFE central map and provide a collection of parameter sets which make HFE provably secure against a differential adversary.

09:17 [Pub][ePrint] An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme, by Dustin Moody and Ray Perlner and Daniel Smith-Tone

  Historically, multivariate public key cryptography has been less than successful at offering encryption schemes which are both secure and efficient. At PQCRYPTO \'13 in Limoges, Tao, Diene, Tang, and Ding introduced a promising new multivariate encryption algorithm based on a fundamentally new idea: hiding the structure of a large matrix algebra over a finite field. We present an attack based on subspace differential invariants inherent to this methodology. The attack is is a structural key recovery attack which is asymptotically optimal among all known attacks (including algebraic attacks) on the original scheme and its generalizations.

09:17 [Pub][ePrint] Composable Oblivious Extended Permutations, by Peeter Laud and Jan Willemson

  An extended permutation is a function f : {1,...,m} -> {1,...,n}, used to map an n-element vector a to an m-element vector b by b_i = a_{f(i)}. An oblivious extended permutation allows this mapping to be done while preserving the privacy of a, b and f in a secure multiparty computation protocol. Oblivious extended permutations have

several uses, with private function evaluation (PFE) being the theoretically most prominent one.

In this paper, we propose a new technique for oblivious evaluation of

extended permutations. Our construction is at least as efficient as the existing techniques, conceptually simpler, and has wider applicability. Our technique allows the party providing the description of f to be absent during the computation phase of the protocol. Moreover, that party does not even have to exist - we show how to compute the private representation of f from private data that may itself be computed from the inputs of parties. In other words, our oblivious extended permutations can be freely composed with other privacy-preserving operations in a multiparty computation.

09:17 [Pub][ePrint] Software implementation of an Attribute-Based Encryption scheme, by Eric Zavattoni and Luis J. Dominguez Perez and Shigeo Mitsunari and Ana H. Sánchez-Ramírez and Tadanori Teruya and Francisco Rodr

  A ciphertext-policy attribute-based encryption protocol uses bilinear pairings to provide

control access mechanisms, where the set of user\'s attributes is specified by means of a linear secret sharing scheme. In this paper we present the design of a software cryptographic library that achieves record timings for the computation of a 126-bit security level attribute-based encryption scheme. We developed all the required auxiliary building blocks and compared the computational weight that each of them adds to the overall performance of this protocol.

In particular, our single pairing and multi-pairing implementations achieve state-of-the-art

time performance at the 126-bit security level.

09:17 [Pub][ePrint] On the Existence of Extractable One-Way Functions, by Nir Bitansky and Ran Canetti and Omer Paneth and Alon Rosen

  A function f is extractable if it is possible to algorithmically ``extract,\'\' from any adversarial program that outputs a value y in the image of f, a preimage of y.

When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard *knowledge assumption* on certain functions.

We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then

there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length.

On the positive side, for adversarial programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.

09:17 [Pub][ePrint] Generic Universal Forgery Attack on Iterative Hash-based MACs, by Thomas Peyrin and Lei Wang

  In this article, we study the security of iterative hash-based MACs, such as HMAC or NMAC, with regards to universal forgery attacks. Leveraging recent advances in the analysis of functional graphs built from the iteration of HMAC or NMAC, we exhibit the very first generic universal forgery attack against hash-based MACs. In particular, our work implies that the universal forgery resistance of an n-bit output HMAC construction is not 2^n queries as long believed by the community. The techniques we introduce extend the previous functional graphs-based attacks that only took in account the cycle structure or the collision probability: we show that one can extract much more meaningful secret information by also analyzing the distance of a node from the cycle of its component in the functional graph.

09:17 [Pub][ePrint] Large-Scale Secure Computation, by Elette Boyle and Kai-Min Chung and Rafael Pass

  We are interested in secure computation protocols in settings where the number of parties is huge and their data even larger. Assuming the existence of a single-use broadcast channel (per player), we demonstrate statistically secure computation protocols for computing (multiple) arbitrary dynamic RAM programs over parties\' inputs, handling (1/3-eps) fraction static corruptions, while preserving up to polylogarithmic factors the computation and memory complexities of the RAM program. Additionally, our protocol is load balanced and has polylogarithmic communication locality.

09:17 [Pub][ePrint] Indistinguishability Obfuscation versus Point Obfuscation with Auxiliary Input, by Christina Brzuska and Arno Mittelbach

  In a recent celebrated breakthrough, Garg et al. (FOCS 2013) gave the first candidate for so-called indistinguishability obfuscation (iO) thereby reviving the interest in obfuscation for a general purpose. Since then, iO has been used to advance numerous sub-areas of cryptography. While indistinguishability obfuscation is a general purpose obfuscation scheme, several obfuscators for specific functionalities have been considered. In particular, special attention has been given to the obfuscation of so-called \\emph{point functions} that return zero everywhere, except for a single point $\\alpha$. A strong variant is point obfuscation with auxiliary input (AIPO), which allows an adversary to learn some non-trivial auxiliary information about the obfuscated point $\\alpha$ (Goldwasser, Tauman-Kalai; FOCS, 2005).

Multi-bit point functions are a strengthening of point functions, where on $\\alpha$, the point function returns a string $\\beta$ instead of $1$. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed by Canetti and Bitansky (Crypto 2010) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by and Bitansky and Paneth (TCC 2012) to construct three-round weak zero-knowledge protocols for NP.

In this paper we present both positive and negative results. We show that if indistinguishability obfuscation exists, then MB-AIPO does not. Towards this goal, we build on techniques by Brzuska, Farshim and Mittelbach (Crypto 2014) who use indistinguishability obfuscation as a means of attacking a large class of assumptions from the Universal Computational Extractor framework (Bellare et al; Crypto 2013). On the positive side we introduce a weak version of MB-AIPO which we deem to be outside the reach of our impossibility result. We prove that this weak version of MB-AIPO suffices to construct a public-key encryption scheme that is secure even if the adversary can learn an arbitrary leakage function of the secret key, as long as the secret key remains computationally hidden. Thereby, we strengthen a result by Canetti et al. (TCC 2010) that showed a similar connection in the symmetric-key setting.

09:17 [Pub][ePrint] New Generic Attacks Against Hash-based MACs, by Gaëtan Leurent and Thomas Peyrin and Lei Wang

  In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an $n$-bit MAC is built from a hash function with a $l$-bit state ($l \\ge n$), there is a well-known existential forgery attack with complexity $2^{l/2}$. However, the remaining security after $2^{l/2}$ computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should still require $2^{n}$ computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should still require $2^{l}$ (or $2^k$ if $k < l$) computations.

In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only $\\tilde O(2^{l/2})$. In addition, we show a key-recovery attack with complexity $\\tilde O(2^{3l/4})$ against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instantiated with concrete hash functions.

We use techniques similar to the cycle-detection technique proposed by Peyrin et al. at Asiacrypt 2012 to attack HMAC in the related-key model. However, our attacks works in the single-key model for both HMAC and NMAC, and without restriction on the key size.

09:17 [Pub][ePrint] Towards Symmetric Functional Encryption for Regular Languages with Predicate Privacy, by Fu-Kuo Tseng and Rong-Jaye Chen and Bao-Shuh Paul Lin

  We present a symmetric-key predicate-only functional encryption system, SP-FE, which supports functionality for regular languages describe by deterministic finite automata. In SP-FE, a data owner can encrypt a string of symbols as encrypted symbols for matching. Later, the data owner can generate predicate tokens of the transitions in a deterministic finite automaton. The server with these tokens can decrypt a sequence of encrypted symbols correctly and transfer from one state to another accordingly. If the final state belongs to the set of accept states, the server takes assigned operations or returns the corresponding encrypted data. We have proven SP-FE preserves both plaintext privacy and predicate privacy through security analysis and security games. To achieve predicate privacy, we put bounds on the length of a string and the number of states of a DFA. Due to these restrictions, SP-FE can capture only finite languages. Finally, we present the performance analysis of SP-FE and mention possible future work.

06:17 [Forum] [2014 Reports] 2014/377 by Orr

  This looks like a paper of "how to tranform secret key algorithm into public key one using obfuscation". Take AES-X, and obfuscate. From: 2014-02-06 05:46:14 (UTC)