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]

Insynd is a cryptographic scheme for secure and privacy-preserving one-way messaging. Insynd is ideally suited for sending personalised breach notifications to end-users, enabling services to provide positive evidence to a third party that they have complied with their obligations (and conversely, for end-users to prove that the notification was not timely). Insynd provides i) secrecy of messages, ii) message integrity and authenticity, iii) protection against recipient profiling, and iv) publicly verifiable proofs of who sent what message to which recipient at what particular time. Our scheme is built on an authenticated data structure, named Balloon, enabling the safe outsourcing of storage of messages to an untrusted server (such as commodity cloud services). The author of messages is in the forward-security model. Insynd uses modern cryptographic primitives, making it also a suitable secure logging system or evidence store, despite the use of \"slow\" public-key cryptography. Our prototype implementation shows improved performance over related work and competitive performance for more data-intensive settings like secure logging.

22:17 [Pub][ePrint]

A 25-gigabyte \"point obfuscation\" challenge \"using security parameter 60\" was announced at the Crypto 2015 rump session; \"point obfuscation\" is another name for password hashing. This paper shows that the particular matrix-multiplication hash function used in the challenge is much less secure than previous password-hashing functions are believed to be. This paper\'s attack algorithm broke the challenge in just 19 minutes using a cluster of 21 PCs.

22:17 [Pub][ePrint]

The calculation of the Tate pairing on ordinary curves involves two major steps: the Miller Loop (ML) followed by the Final Exponentiation (FE). The first step for achieving a full pairing inversion would be to invert this FE, which in itself is a mathematically difficult problem. To our best knowledge, most fault attack schemes proposed against pairing algorithms have mainly focussed on the ML. They solved, if at all, the inversion of the FE in some special easy\' cases or even showed that the complexity of the FE is an intrinsic countermeasure against a successful full fault attack on the Tate pairing. In this paper, we present a fault attack on the FE whereby the inversion of the final exponentiation becomes feasible using $3$ independent faults.

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.