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).

2015-02-27
22:17 [Pub][ePrint]

Functional encryption (FE) enables fine-grained access control of encrypted data while promising simplified key management. In the past few years substantial progress has been made on functional encryption and a weaker variant called predicate encryption. Unfortunately, fundamental impossibility results have been demonstrated for constructing FE schemes for general functions satisfying a simulation-based definition of security.

We show how to use \\emph{hardware tokens} to overcome these impossibility results. In our envisioned scenario, an authority gives a hardware token and some cryptographic information to each authorized user; the user combines these to decrypt received ciphertexts. Our schemes rely on \\emph{stateless} tokens that are \\emph{identical} for all users. (Requiring a different token for each user trivializes the problem, and would be a barrier to practical deployment.) The tokens can implement relatively lightweight\'\' computation relative to the functions supported by the scheme.

Our token-based approach can be extended to support hierarchal functional encryption, function privacy, and more.

22:17 [Pub][ePrint]

We study the question of protecting arithmetic circuits against additive attacks, which can add an arbitrary fixed value to each wire in the circuit.

This extends the notion of algebraic manipulation detection (AMD) codes, which protect information against additive attacks, to that of AMD circuits which protect computation.

We present a construction of such AMD circuits: any arithmetic circuit $C$ over a finite field $F$ can be converted into a functionally-equivalent randomized arithmetic circuit $\\widehat{C}$ of size $O(|C|)$ that is fault-tolerant in the following sense. For any additive attack on the wires of $\\widehat{C}$, its effect on the output of $\\widehat{C}$ can be simulated, up to $O(|C|/|F|)$ statistical distance, by an additive attack on just the input and output.

Given a small tamper-proof encoder/decoder for AMD codes, the input and output can be protected as well.

We also give an alternative construction, applicable to small fields (for example, to protect Boolean circuits against wire-toggling attacks). It uses a small tamper-proof decoder to ensure that, except with negligible failure probability, either the output is correct or tampering is detected.

Our study of AMD circuits is motivated by simplifying and improving protocols for secure multiparty computation (MPC). Typically, securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries.

We observe that in simple MPC protocols that were designed to protect circuit evaluation only against passive adversaries, the effect of any active adversary corresponds precisely to an additive attack on the original circuit\'s wires. Thus, to securely evaluate a circuit $C$ in the presence of active adversaries, it suffices to apply the passive-secure protocol to $\\widehat{C}$. We use this methodology to simplify feasibility results and attain efficiency improvements in several standard MPC models.

22:17 [Pub][ePrint]

Several new services incentivize clients to compete in

solving large computation tasks in exchange for financial rewards.

This model of competitive distributed computation enables every

user connected to the Internet to participate in a game in which

he splits his computation power among a set of competing pools

-- the game is called a computation power splitting game. We

formally model this game and show its utility in analyzing the

security of pool protocols that dictate how financial rewards are

shared among the members of a pool.

As a case study, we analyze the Bitcoin cryptocurrency

which attracts computing power roughly equivalent to billions

of desktop machines, over 70% of which is organized into public

pools. We show that existing pool reward sharing protocols

are insecure in our game-theoretic analysis, when considering

a single attack strategy called the \"block withholding attack\".

This attack is a topic of debate, initially thought to be ill-

incentivized in today\'s pool protocols: i.e., causing a net loss

to the attacker, and later argued to be always profitable. Our

analysis shows that the attack is always well-incentivized in the

long-run, but may not be so for a short duration. This implies that

existing pool protocols are insecure, and if the attack is conducted

systematically, Bitcoin pools could lose millions of dollars worth

in months. The equilibrium state is a mixed strategy--that is--in

equilibrium all clients are incentivized to probabilistically attack

to maximize their payoffs rather than participate honestly. As

a result, the overall capacity of the Bitcoin network is under-

utilized.

22:17 [Pub][ePrint]

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we show how to derandomize lossy encryption (with long messages) to obtain lossy trapdoor functions, and hence injective one-way trapdoor functions.

Bellare, Halevi, Sahai and Vadhan (CRYPTO \'98) showed that if E is an IND-CPA secure cryptosystem, and $H$ is a random oracle, then $x \\mapsto E(x,H(x))$ is an injective trapdoor function. In this work, we show that if E is a lossy encryption with messages at least 1-bit longer than randomness, and $h$ is a pairwise independent hash function, then $x \\mapsto E(x,h(x))$ is a lossy trapdoor function,

and hence also an injective trapdoor function.

The works of Peikert, Vaikuntanathan and Waters and Hemenway, Libert, Ostrovsky and Vergnaud showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption.

In their construction, if the sender randomness is shorter than the message in the OT, it will also be shorter than the message in the lossy encryption.

This gives an alternate interpretation of our main result. In this language, we show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for strings

longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is in contrast to the black box separation of

injective trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption.

22:17 [Pub][ePrint]

We show a generic conversion that converts an attribute based encryption (ABE) scheme for arbitrary predicate into an ABE scheme for its dual predicate. In particular, it can convert key-policy ABE (KP-ABE) into ciphertext-policy ABE (CP-ABE), and vice versa, for dually related predicates. It is generic in the sense that it can be applied to arbitrary predicates. On the other hand, it works only within the generic ABE framework recently proposed by Attrapadung (Eurocrypt\'14), which provides a generic compiler that compiles a simple primitive called pair encodings into fully secure ABE. Inside this framework, Attrapadung proposed the first generic dual conversion that works only for subclass of encodings, namely, perfectly secure encodings. However, there are many predicates for which realizations of such encodings are not known, and hence the problems of constructing fully secure ABE for their dual predicates were left unsolved.

In this paper, we revisit the dual conversion of Attrapadung, and show that, somewhat surprisingly, the very same conversion indeed also works for broader classes of encodings, namely, computationally secure encodings. Consequently, we thus solve the above open problems as we obtain the first fully secure realizations of completely-unbounded CP-ABE and CP-ABE with short keys for Boolean formulae, via applying the conversion to previously proposed KP-ABE.

Moreover, we provide a generic conversion that converts ABE into its dual-policy variant. Dual-policy ABE (DP-ABE) conjunctively combines both KP-ABE and CP-ABE into one primitive, and hence can be useful in general-purpose applications. As for instantiations, we obtain the first realizations of fully secure DP-ABE for formulae, unbounded DP-ABE for formulae, and DP-ABE for regular languages. The latter two systems are the first to realize such functionalities, let alone are fully secure.

22:17 [Pub][ePrint]

We construct a general-purpose multi-input functional encryption scheme in the private-key setting. Namely, we construct a scheme where a functional key corresponding to a function $f$ enables a user holding encryptions of $x_1, \\ldots, x_t$ to compute $f(x_1, \\ldots, x_t)$ but nothing else. Our construction assumes any general-purpose private-key single-input scheme (without any additional assumptions), and is proven to be adaptively-secure for any constant number of inputs $t$. Moreover, it can be extended to a super-constant number of inputs assuming that the underlying single-input scheme is sub-exponentially secure.

Instantiating our construction with existing single-input schemes, we obtain multi-input schemes that are based on a variety of assumptions (such as indistinguishability obfuscation, multilinear maps, learning with errors, and even one-way functions), offering various trade-offs between security and efficiency.

Previous constructions of multi-input functional encryption schemes either relied on somewhat stronger assumptions and provided weaker security guarantees (Goldwasser et al., EUROCRYPT \'14), or relied on multilinear maps and could be proven secure only in an idealized generic model (Boneh et al., EUROCRYPT \'15).

22:17 [Pub][ePrint]

ALE is a new authenticated encryption algorithm published at FSE 2013. The authentication component of ALE is based on the strong Pelican MAC, and the authentication security of ALE is claimed to be 128-bit. In this paper, we propose the leaked-state-forgery attack (LSFA) against ALE by exploiting the state information leaked from the encryption of ALE. The LSFA is a new type of differential cryptanalysis in which part of the state information is known and exploited to improve the differential probability. Our attack shows that the authentication security of ALE is only 97-bit. And the results may be further improved to around 93-bit if the whitening key layer is removed. We implemented our attacks against a small version of ALE (using 64-bit block size instead of 128-bit block size). The experimental results match well with the theoretical results.

19:17 [Pub][ePrint]

In [19], Peikert presents an efficient and provably secure set of lower level primitives for practical post-quantum cryptography. These primitives also give the first lattice-based scheme to provide perfect forward secrecy, and thus represent a major advancement in providing the same sort of security guarantees that are now expected for modern internet traffc protection. However, the presentation in [19] might prove a bit daunting for the slightly less mathematical reader. Here we provide what we hope will be a clear and self-contained exposition of how the algorithm can be implemented, along with sample code and some initial analysis for potential parameter sizes.

We focus on the simpler case, as chosen by Bos et al in [1], of cyclotomic rings whose degree is a power of two. We describe the necessary arithmetic setup and choices regarding error sampling, and give a possibly cleaner mechanism for reconciliation of the shared secrets. Then we present Peikert\'s Diffe-Hellman-like key exchange algorithms along with security, correctness and implementation analysis.

19:17 [Pub][ePrint]

In this work we have analyzed some password hashing schemes for performance under various settings of time and memory complexities. We have attempted to benchmark the said algorithms at similar levels of memory consumption. Given the wide variations in security margins of the algorithms and incompatibility of memory and time cost settings, we have attempted to be as fair as possible in choosing the various parameters while executing the benchmarks.

19:17 [Pub][ePrint]

It has been roughly two decades since the random oracle model for security reductions was introduced and one decade since we first discussed the controversy that had arisen concerning its use. In this retrospective we argue that there is no evidence that the need for the random oracle assumption in a proof indicates the presence of a real-world security weakness in the corresponding protocol. We give several examples of attempts to avoid random oracles that have led to protocols that have security weaknesses that were not present in the original ones whose proofs required random oracles. We also argue that the willingness to use random oracles gives one the flexibility to modify certain protocols so as to reduce dependence on potentially vulnerable pseudorandom bit generators. Finally, we discuss a modified version of ECDSA, which we call ECDSA+, that may have better real-world security than standard ECDSA, and compare it with a modified Schnorr signature. If one is willing to use the random oracle model (and the analogous generic group model), then various security reductions are known for these two schemes. If one shuns these models, then no provable security result is known for them.

18:07 [Event][New]

Submission: 23 June 2015