International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

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

2014-07-08
15:17 [Pub][ePrint]

This work presents the first differential power analysis of an implementation of the McEliece cryptosystem. Target of this side-channel attack is a state-of-the-art FPGA implementation of the efficient QC-MDPC McEliece decryption operation as presented at DATE 2014. The presented cryptanalysis succeeds to recover the complete secret key after a few observed decryptions. It consists of a combination of a differential leakage analysis during the syndrome computation followed by an algebraic step that exploits the relation between the public and private key.

09:17 [Pub][ePrint]

A presentation of a group with two generators having unsolvable word problem and an explicit countable presentation of Mihailova subgroup of F_2×F_2 with finite number of generators are given. Where Mihailova subgroup of F_2×F_2 enjoys the unsolvable subgroup membership problem.One then can use the presentation to create entities\' private key in a public key cryptsystem.

09:17 [Pub][ePrint]

We investigate new models and constructions which allow

leakage-resilient signatures secure against existential forgeries,

where the signature is much shorter than the leakage bound.

Current models of leakage-resilient signatures against existential

forgeries demand that the adversary cannot produce a new valid

message/signature pair $(m, \\sigma)$ even after receiving some

$\\lambda$ bits of leakage on the signing key. If $\\vert \\sigma \\vert \\le \\lambda$, then the adversary can just choose to leak a valid

signature $\\sigma$, and hence signatures must be larger than the

allowed leakage, which is impractical as the goal often is to have

large signing keys to allow a lot of leakage.

We propose a new notion of leakage-resilient signatures against

existential forgeries where we demand that the adversary cannot

produce $n = \\lfloor \\lambda / \\vert \\sigma \\vert \\rfloor + 1$

distinct valid message/signature pairs

$(m_1, \\sigma_1), \\ldots, (m_n, \\sigma_n)$ after receiving

$\\lambda$ bits of leakage. If $\\lambda = 0$, this is the usual notion of existential unforgeability. If $1 09:17 [Pub][ePrint] In this article, we propose a new comparison metric, the figure of adversarial merit (FOAM), which combines the inherent security provided by cryptographic structures and components with their implementation properties. To the best of our knowledge, this is the first such metric proposed to ensure a fairer comparison of cryptographic designs. We then apply this new metric to meaningful use cases by studying Substitution-Permutation Network permutations that are suited for hardware implementations, and we provide new results on hardware-friendly cryptographic building blocks. For practical reasons, we considered linear and differential attacks and we restricted ourselves to fully serial and round-based implementations. We explore several design strategies, from the geometry of the internal state to the size of the S-box, the field size of the diffusion layer or even the irreducible polynomial defining the finite field. We finally test all possible strategies to provide designers an exhaustive approach in building hardware-friendly cryptographic primitives (according to area or FOAM metrics), also introducing a model for predicting the hardware performance of round-based or serial-based implementations. In particular, we exhibit new diffusion matrices (circulant or serial) that are surprisingly more efficient than the current best known, such as the ones used in AES, LED and PHOTON. 09:17 [Pub][ePrint] The wide availability of inexpensive positioning systems made it possible to embed them into smartphones and other personal devices. This marked the beginning of location-aware applications, where users request personalized services based on their geographic position. The location of a user is, however, highly sensitive information: the user\'s privacy can be preserved if only the minimum amount of information needed to provide the service is disclosed at any time. While some applications, such as navigation systems, are based on the users\' movements and therefore require constant tracking, others only require knowledge of the user\'s position in relation to a set of points or areas of interest. In this paper we focus on the latter kind of services, where the location information is essentially used to determine membership in one or more geographic sets. We address this problem using Bloom Filters (BF), a compact data structure for representing sets. In particular, we present an extension of the original bloom filter idea: the Spatial Bloom Filter (SBF). SBF\'s are designed to manage spatial and geographical information in a space efficient way, and are well-suited for enabling privacy in location-aware applications. We show this by providing two multi-party protocols for privacy-preserving computation of location information, based on the known homomorphic properties of public key encryption schemes. The protocols keep the user\'s exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user. 09:17 [Pub][ePrint] Physical Unclonable Functions (PUFs) have emerged as a promising solution for securing resource-constrained embedded devices such as RFID-tokens. PUFs use the inherent physical differences of every chip to either securely authenticate the chip or generate cryptographic keys without the need of non-volatile memory. Securing non-volatile memory and cryptographic algorithms against hardware attacks is very costly and hence PUFs are believed to be a good alternative to traditional cryptographic algorithms and key generation on constrained embedded devices. However, PUFs have shown to be vulnerable to model building attacks if the attacker has access to challenge and response pairs. In these model building attacks, machine learning is used to determine the internal parameters of the PUF to build an accurate software model. Nevertheless, PUFs are still a promising building block and several protocols and designs have been proposed that are believed to be resistant against machine learning attacks. In this paper we take a closer look at a two such protocols, one based on reverse fuzzy extractors[15] and one based on pattern matching [15,17]. We show that it is possible to attack these protocols using machine learning despite the fact that an attacker does not have access to direct challenge and response pairs. The introduced attacks demonstrate that even highly obfuscated responses or helper data can be used to attack PUF protocols. Hence, our work shows that even protocols in which it would be computationally infeasible to compute enough challenge and response pairs for a direct machine learning attack can be attacked using machine learning. 2014-07-07 12:17 [Forum] Hi, I think that this is not exactly obfuscation: To my understanding, obfuscation is a reversible permutation, because its actually 1-1 mapping. The process of logic synthesis proposed in the publication is inherently not reversible, because it involves a loss of information. The only way to reverse it is to go through all possible inputs and record the associated outputs, which is similar to brute force attack From: 2014-07-07 09:25:43 (UTC) 09:17 [Pub][ePrint] We study the adaptive security of constrained PRFs in the standard model. We initiate our exploration with puncturable PRFs. A puncturable PRF family is a special class of constrained PRFs, where the constrained key is associated with an element$x\'$in the input domain. The key allows evaluation at all points$x\\neq x\'$. We show how to build puncturable PRFs with adaptive security proofs in the standard model that involve only polynomial loss to the underlying assumptions. Prior work had either super-polynomial loss or applied the random oracle heuristic. Our construction uses indistinguishability obfuscation and DDH-hard algebraic groups of composite order. 09:17 [Pub][ePrint] Constrained pseudorandom functions (introduced independently by Boneh and Waters (CCS 2013), Boyle, Goldwasser, and Ivan (PKC 2014), and Kiayias, Papadopoulos, Triandopoulos, and Zacharias (CCS 2013)), are pseudorandom functions (PRFs) that allow the owner of the secret key$k$to compute a constrained key$k_f$, such that anyone who possesses$k_f$can compute the output of the PRF on any input$x$such that$f(x) = 1$for some predicate$f$. The security requirement of constrained PRFs state that the PRF output must still look indistinguishable from random for any$x$such that$f(x) = 0$. Boneh and Waters show how to construct constrained PRFs for the class of bit-fixing as well as circuit predicates. They explicitly left open the question of constructing constrained PRFs that are delegatable - i.e., constrained PRFs where the owner of$k_f$can compute a constrained key$k_{f\'}$for a further restrictive predicate$f\'$. Boyle, Goldwasser, and Ivan left open the question of constructing constrained PRFs that are also verifiable. Verifiable random functions (VRFs), introduced by Micali, Rabin, and Vadhan (FOCS 1999), are PRFs that allow the owner of the secret key$k$to prove, for any input$x$, that$y$indeed is the output of the PRF on$x$; the security requirement of VRFs state that the PRF output must still look indistinguishable from random, for any$x$for which a proof is not given. In this work, we solve both the above open questions by constructing constrained pseudorandom functions that are simultaneously verifiable and delegatable. 09:17 [Pub][ePrint] In this work we explore new techniques for building short signatures from obfuscation. Our goals are twofold. First, we would like to achieve short signatures with adaptive security proofs. Second, we would like to build signatures with fast signing, ideally significantly faster than comparable signatures that are not based on obfuscation. The goal here is to create an \"imbalanced\" scheme where signing is fast at the expense of slower verification. We develop new methods for achieving short and fully secure obfuscation-derived signatures. Our base signature scheme is built from punctured programming and makes a novel use of the \"prefix technique\" to guess a signature. We find that our initial scheme has slower performance than comparable algorithms (e.g. EC-DSA). We find that the underlying reason is that the underlying PRG is called l^2 times for security parameter l. To address this issue we construct a more efficient scheme by adapting the Goldreich-Goldwasser-Micali [GGM86] construction to form the basis for a new puncturable PRF. This puncturable PRF accepts variable-length inputs and has the property that evaluations on all prefixes of a message can be efficiently pipelined. Calls to the puncturable PRF by the signing algorithm therefore make fewer invocations of the underlying PRG, resulting in reduced signing costs. We evaluate our puncturable PRF based signature schemes using a variety of cryptographic candidates for the underlying PRG. We show that the resulting performance on message signing is competitive with that of widely deployed signature schemes. 09:17 [Pub][ePrint] Hyper-bent functions as a subclass of bent functions attract much interest and it is elusive to completely characterize hyper-bent functions. Most of known hyper-bent functions are Boolean functions with Dillon exponents and they are often characterized by special values of Kloosterman sums. In this paper, we present a method for characterizing hyper-bent functions with Dillon exponents. A class of hyper-bent functions with Dillon exponents over$\\mathbb{F}_{2^{2m}}$can be characterized by a Boolean function over$\\mathbb{F}_{2^m}\$, whose Walsh spectrum takes the same value twice.

Further, we show several classes of

hyper-bent functions with Dillon exponents characterized by

Kloosterman sum identities and the Walsh

spectra of some common Boolean functions.