International Association
for Cryptologic Research

Revoking corrupted users is a desirable functionality for cryptosystems. Since Boldyreva, Goyal, and Kumar (ACM CCS 2008) proposed a notable result for scalable revocation method in identity-based encryption (IBE), several works have improved either the security or the efficiency of revocable IBE (RIBE). Currently, all existing scalable RIBE schemes that achieve adaptively security against decryption key exposure resistance (DKER) can be categorized into two groups; either with long public parameters or over composite-order bilinear groups. From both practical and theoretical points of views, it would be interesting to construct adaptively secure RIBE scheme with DKER and short public parameters in prime-order bilinear groups.

In this paper, we address this goal by using Seo and Emura's technique (PKC 2013), which transforms the Waters IBE to the corresponding RIBE. First, we identify necessary requirements for the input IBE of their transforming technique. Next, we propose a new IBE scheme having several desirable properties; satisfying all the requirements for the Seo-Emura technique, constant-size public parameters, and using prime-order bilinear groups. Finally, by applying the Seo-Emura technique, we obtain the first adaptively secure RIBE scheme with DKER and constant-size public parameters in prime-order bilinear groups.

Energy consumption of block ciphers is critical in resource constrained devices. Unrolling has been explored in literature as a technique to increase efficiency by eliminating energy spent in loop control elements such as registers and multiplexers. However these savings are minimal and are offset by the increase in glitching power that comes with unrolling. We propose an efficient latch-based glitch filter for unrolled designs that reduces energy per encryption by an order of magnitude over a straightforward implementation, and by 28-32% over the best existing glitch filtering schemes. We explore the optimal number of glitch filters that should be used in order to minimize total energy, and provide estimates of the area cost. Partially unrolled designs also benefit from using our scheme with energies competitive to fully serialized implementations. We demonstrate our approach on the SIMON-128 and AES-256 block ciphers.

We provide a new family of elliptic curves that results in a one to two percent performance improvement of the elliptic curve integer factorization method. The speedup is confirmed by extensive tests for factors ranging from 15 to 63 bits.

True random number generators (TRNGs) are essential for cryptographic systems, and they are usually evaluated by the concept of entropy. In general, the entropy of a TRNG is estimated from its stochastic model, and reflected in the statistical results of the generated raw bits. Oscillator-based TRNGs are widely used in practical cryptographic systems due to its elegant structure, and its stochastic model has been studied in different aspects. In this paper, we investigate the applicability of the different entropy estimation methods for oscillator-based TRNGs, including the bit-rate entropy, the lower bound and the approx imate entropy. Particularly, we firstly analyze the two existing stochastic models (one of which is phase-based and the other is time-based), and deduce consistent bit-rate entropy results from these two models. Then, we design an approximate entropy calculation method on the output raw bits of a simulated oscillator-based TRNG, and this statistical calculation result well matches the bit-rate entropy from stochastic models. In addition, we discuss the extreme case of tiny randomness where some methods are inapplicable, and provide the recommendations for these entropy evaluation methods. Finally, we design a hardware verification method in a real oscillator-based TRNG, and validate these estimation methods in the hardware platform.

Online ciphers, in spite of being insecure against an sprp adversary, can be desirable at places because of their ease of implementation and speed. Here we propose a single-keyed inverse-free construction that achieves online sprp security with an optimal number of blockcipher calls. We also include a partial block construction, without requiring any extra key.

Attribute-Based Encryption (ABE) allows to target the recipients of a message according to a policy expressed as a predicate among some attributes. Ciphertext-policy ABE schemes can choose the policy at the encryption time.

In this paper, we define a new property for ABE: homomorphic-policy. A combiner is able to (publicly) combine ciphertexts under different policies into a ciphertext under a combined policy (AND or OR). More precisely, using linear secret sharing schemes, we design Attribute-Based Key Encapsulation Mechanisms (ABKEM) with the Homomorphic-Policy property: given several encapsulations of the same keys under various policies, anyone can derive an encapsulation of the same key under any combination of the policies.

As an application, in Pay-TV, this allows to separate the content providers that can generate the encapsulations of a session key under every attributes, this key being used to encrypt the payload, and the service providers that build the decryption policies according to the subscriptions. The advantage is that the aggregation of the encapsulations by the service providers does not contain any secret information.

We device a general secret sharing scheme for evolving access structures (following [KNY16]). Our scheme has (sub)exponentially smaller share complexity (share of $i$'th party) for certain access structures compared to the general scheme in ~\cite{KNY16}. We stress that unlike ~\cite{KNY16}'s scheme, our scheme requires that the entire evolving access structure is known in advance. Revising, ~\cite{KNY16}'s scheme (in its most optimized form) is based on a representation of the access structure by an ordered (possibly infinite) oblivious, read once decision tree. Each node is associated with an output of the function (0 or 1). The tree is augmented to cut paths that reach a node where $f$ evaluates to 1 at that node (works for evolving access structures, in which the descendants of all 1-nodes must be 1). Each party $P_i$ receives a (single-bit) share for each edge exiting a node labeled by $x_i$.

Generally, the scheme of ~\cite{KNY16} has share complexity $O(w_T(i))$, where $w_T(i)$ is the width of layer $i$ relevant decision tree. In general, this width can reach $\Omega(2^i)$. To get non trivial share complexity, $e^{n^{o(1)}}$, a \emph{tree} of width $e^{n^{o(1)}}$ is required.

Our scheme is based on a generalized (infinite) tree representation of the access structure. The main difference is that vertices are labeled with sequences of variables, rather than a single variable. As a result, we often get smaller trees, and the edges $e$ are labeled by more complex (non-evloving) monotone functions $g_e$ of the variables in the sequence. The share associated with the edge is shared (among the parties in the relevant sequence). As a result, the tree is smaller, while the shares received for every edge in it are bigger. Still, the tradeoff is often on our side. Namely, for access structures with ordered read-once \emph{branching programs} with relatively small width, $e^{O(i^c)}$ for $c<0.25$, share complexity of $e^{n^{o(1)}}$ is achieved. More specifically, the resulting share complexity is $(iw_{BP}(i^2))^{O(\log{i} + \log{w_{BP}(i^2)})}$. In particular, for $w=\Omega(i)$, we get share complexity of $w_{BP}(i^2)^{O(\log{w_{BP}(i^2)})}$.

Finally, a further improved variant of our scheme for a special class of ``counting'' access structures yields polynomial share complexity. In particular, we obtain an evolving secret sharing scheme for \emph{evolving majority} with share complexity $\tilde{O}(n^6)$, answering an open question of~\cite{KNY16}.

Event date: 2 April 2017
Submission deadline: 10 January 2017
Notification: 15 February 2017

At FSE 2006, Iwata introduced the CENC encryption mode and proved its security up to 2^{2n/3} plaintext blocks processed in total. He conjectured optimal security up to a constant. In this brief note, we confirm this conjecture. Rather than proving it ourselves, we point out that the conjecture's proof follows as a corollary of Patarin's ``Theorem P_i xor P_j for any xi_max'' from 2010. This connection appears to have remained unnoticed, and the sole purpose of this brief note is to make the connection explicit.

In broadcast encryption schemes, a distribution center broadcasts an encrypted message to a subset $ S $ chosen from a universe of receivers and only the intended users are able to decrypt the message. Most broadcast encryption schemes do not provide anonymity and the identities of target receivers are sent in plaintext. However, in several applications, the authorized users' identities has the same sensitivity as the message itself. YRL, is an anonymous attribute-based broadcast encryption scheme with linear computation, communication and storage overheads in the number of attributes. In this paper, we first propose an attack on the YRL scheme and show that unfortunately the unauthorized receivers can also decrypt the broadcasted message. Next, we propose the Improved-YRL scheme and prove that it achieves anonymity and semantic security under adaptive corruptions in the chosen ciphertext setting. The proof is provided using the dual system encryption technique and is based on three complexity assumptions in composite order bilinear maps. The Improved-YRL scheme is a step forward in solving the long-standing problem of secure and low overhead anonymous broadcast encryption.

We propose practically efficient signature schemes which feature several attractive properties: (a) they only rely on the security of symmetric-key primitives (block ciphers, hash functions), and are therefore a viable candidate for post-quantum security, (b) they have extremely small signing keys, essentially the smallest possible, and, (c) they are highly parameterizable.

For this result we take advantage of advances in two very distinct areas of cryptography. The first is the area of primitives in symmetric cryptography, where recent developments led to designs which exhibit an especially low number of multiplications. The second is the area of zero-knowledge proof systems, where significant progress for efficiently proving statements over general circuits was recently made.

We follow two different directions, one of them yielding the first practical instantiation of a design paradigm due to Bellare and Goldwasser, which allows us to obtain tightly secure signatures. For both our schemes we explore the whole design spectrum to obtain optimal parameter choices for different settings, thereby also taking reduction tightness into account. Within limits, in all cases our schemes allow to trade-off computational effort with signature sizes. We also demonstrate that our schemes are parallelizable to the extent that they can practically take advantage of several cores on a CPU.

An Oblivious Parallel RAM (OPRAM) provides a general method to simulate any Parallel RAM (PRAM) program, such that the resulting memory access patterns leak nothing about secret inputs. OPRAM was originally proposed by Boyle et al. as the natural parallel counterpart of Oblivious RAM (ORAM), which was shown to have broad applications, e.g., in cloud outsourcing, secure processor design, and secure multi-party computation. Since parallelism is common in modern computing architectures such as multi-core processors or cluster computing, OPRAM is naturally a powerful and desirable building block as much as its sequential counterpart ORAM is. Although prior work (in particular, Circuit ORAM) has shown how to construct ORAM schemes that are asymptotically tight under certain parameter ranges, the performance of known OPRAM schemes still do not match their sequential counterparts, leaving open two main questions: (i) whether one can construct an OPRAM scheme whose performance is competitive relative to known sequential counterparts; and (ii) whether one can construct OPRAM schemes that are asymptotically optimal.

Our paper answers the first question positively and gives partial answers to the second question. Specifically, we construct Circuit OPRAM, a new OPRAM scheme that makes the following contributions:

1. We achieve asymptotical improvement in terms of both total work and parallel runtime in comparison with known OPRAM schemes. More specifically, we improve the total work by a logarithmic factor and parallel runtime by poly-logarithmic factors.

2. We show that under sufficiently large block sizes, we can construct an OPRAM scheme that is asymptotically optimal both in total work and parallel runtime when the number of CPUs is not too small.

3. Our construction features a combination of novel techniques that enable us to (i) have asymptotically tight stochastic processes that do not suffer from worst-case and average-case discrepancies; and (ii) temporally reallocate work over offline and online stages of the algorithm such that we can achieve small parallel runtime overall. These techniques can be of independent interest in the design of of parallel oblivious algorithms in general.

In this paper we study public key encryption schemes of indistinguishability security against receiver selective opening (IND-RSO) attacks, where the attacker can corrupt some receivers and get the corresponding secret keys in the multi-party setting. Concretely:

-We present a general construction of RSO security against chosen ciphertext attacks (RSO-CCA) by combining any RSO secure scheme against chosen plaintext attacks (RSO-CPA) with any regular CCA secure scheme, along with an appropriate non-interactive zero-knowledge proof. -We show that the leakage-resistant construction given by Hazay \emph{et al.} in Eurocrypt 2013 from weak hash proof system (wHPS) is RSO-CPA secure.

-We further show that the CCA secure construction given by Cramer and Shoup in Eurocrypt 2002 based on the universal HPS is RSO-CCA secure, hence obtain a more efficient paradigm for RSO-CCA security.

In side channel attack (SCA) studies, it is widely believed that unprotected implementations leak information about the intermediate states of the internal cryptographic process. However, directly recovering the intermediate states is not common practice in today's SCA study. Instead, most SCAs exploit the leakages in a "guess-and-determine" way, where they take a partial key guess, compute the corresponding intermediate states, then try to identify which one fits the observed leakages better. In this paper, we ask whether it is possible to take the other way around---directly learning the intermediate states from the side channel leakages. Under certain circumstances, we find that the intermediate states can be efficiently recovered with the well-studied Independent Component Analysis (ICA). Specifically, we propose several methods to convert the side channel leakages into effective ICA observations. For more robust recovery, we also present a specialized ICA algorithm which exploits the specific features of circuit signals. Experiments confirm the validity of our analysis in various circumstances, where most intermediate states can be correctly recovered with only a few hundred traces. To our knowledge, this is the first attempt to directly recover the intermediate states in a completely non-profiled setting. Our approach brings new possibilities to the current SCA study, including building an alternative SCA distinguisher, directly attacking the middle encryption rounds and reverse engineering with fewer restrictions. Considering its potential in more advanced applications, we believe our ICA-based SCA deserves more research attention in the future study.

In this paper, we describe several attacks to the protocol by Nguyen et al. presented at ESORICS 2016, an authenticated key agreement protocol mediated by a proxy entity, restricted to only symmetric encryption primitives and intended for IoT environments. This protocol uses long-term weak secrets as intermediate values during encryption and decryption procedures, which implies that these can be used to encrypt and decrypt messages without knowing the corresponding secret keys. In our work, we show how access to weak secrets can break forward security and lead to key compromise impersonation attacks. Moreover, we demonstrate that this problem cannot be solved even if the affected user revokes his previous secret key and updates it to a new one. In addition, we explain how the choice of a keyed hash as part of the protocol makes it potentially vulnerable to length-extension attacks, depending on the choice of hash function. We illustrate this latter problem experimentally. Finally, we show how a combination of these exploits can be used to set up elaborate attack scenarios.

Masking schemes achieve provable security against side-channel analysis by using secret sharing to decorrelate key-dependent intermediate values of the cryptographic algorithm and side-channel information. Masking schemes make assumptions on how the underlying leakage mechanisms of hardware or software behave to account for various physical effects. In this paper, we investigate the effect of the physical placement on the security using leakage assessment on power measurements collected from an FPGA. In order to differentiate other masking failures, we use threshold implementations as masking scheme in conjunction with a high-entropy pseudorandom number generator. We show that we can observe differences in---possibly---exploitable leakage by placing functions corresponding to different shares of a cryptographic implementation in close proximity.

As recently been emphasized by NSA and NIST, there is an increasing need for cryptographic schemes being secure against quantum computer attacks. Especially in the area of digital signature schemes, multivariate cryptography is one of the main candidates for this. At Inscrypt 2015, Nie et al. proposed a new multivariate signature scheme called CUOV, whose public key consists both of quadratic and cubic polynomials. However, the scheme was broken by an attack of Hashimoto. In this paper we take a closer look on the CUOV scheme and its attack and propose two new multivariate signature schemes called CSSv and SVSv, which are secure against Hashimoto's attack and all other known attacks on multivariate schemes. Especially our second construction SVSv is very efficient and outperforms current multivariate signature schemes such as UOV and Rainbow in terms of key and signature size.

In this paper we consider the maximum absolute value $\Delta_f$ in the autocorrelation spectra (not considering the zero point) of a function $f$. In even number of variables $n$, bent functions possess the highest nonlinearity and $\Delta_f = 0$. The long standing (for two decades) open question in this area is to obtain a theoretical construction of balanced functions with $\Delta_f < 2^{\frac n2}$. So far there are only a few examples of such functions for $n = 10, 14$, but there is no general technique known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on $n$ variables having absolute indicator strictly lesser than $2^{\frac{n}{2}}-2^{\frac{n+6}{4}}$, nonlinearity strictly greater than $2^{n-1}-7\cdot 2^{\frac n2-3}-5\cdot2^{\frac{n-2}{4}}$ and algebraic degree $n-1$, where $n\equiv 2 \pmod 4$ and $n\geq 46$. While the bound $n \geq 46$ is required for proving the generic result, our construction starts from $n = 18$ and we could obtain a balanced function with $\Delta_f = 480 < 2^{\frac{18}{2}}$ and nonlinearity $130664 > 2^{17} - 2^9 = 130560$ and algebraic degree $17$.

Since the development of tree-based Oblivious RAM by Shi et al. (Asiacrypt '11) it has become apparent that privacy preserving outsourced storage can be practical. Although most current constructions follow a client-server model, in many applications it is desirable to share data between different clients, in a way that hides the access patterns, not only from the server, but also between the clients. In this work, we introduce Blurry-ORAM, an extension of Path-ORAM that allows for oblivious sharing of data in the multi-client setting, so that accesses can be hidden from the server and other clients. Our construction follows the design of Path-ORAM as closely as possible in order to benefit from its performance as well as security. We prove our construction secure in a setting where the clients are semi-honest, do not trust each other but try to learn the access patterns of each other.

We show how to construct pseudorandom permutations (PRPs) that remain secure even if the adversary can query the permutation on a quantum superposition of inputs. Such PRPs are called \emph{quantum-secure}. Our construction combines a quantum-secure pseudorandom \emph{function} together with constructions of \emph{classical} format preserving encryption. By combining known results, we obtain the first quantum-secure PRP in this model whose security relies only on the existence of one-way functions. Previously, to the best of the author's knowledge, quantum security of PRPs had to be assumed, and there were no prior security reductions to simpler primitives, let alone one-way functions.