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-05-27
12:17 [Pub][ePrint]

The Double-Base Number System (DBNS) uses two bases, $2$ and $3$, in order to represent any

integer $n$.

A Double-Base Chain (DBC) is a special case of a DBNS expansion. DBCs have been introduced to speed up

the scalar multiplication $[n]P$ on certain families of elliptic curves used in cryptography.

In this context, our contributions are twofold.

First, given integers $n$, $a$, and $b$, we outline a recursive algorithm

to compute the number of different DBCs with a \\lt{} dividing $2^a3^b$ and representing $n$. A

simple

modification of the algorithm allows to

determine the number of DBCs with a specified length as well as the actual expansions. In turn, this

gives rise to a method to compute an optimal DBC representing $n$, i.e. an expansion with minimal

length.

Our implementation is able to return an optimal expansion for most integers up to $2^{60}$ bits

in a few minutes.

Second, we introduce an original and potentially more efficient approach to compute a random

scalar multiplication $[n]P$, called controlled DBC. Instead of generating a random integer $n$

and then trying to find an

optimal, or at least a short DBC to represent it, we propose to directly generate $n$ as a

random DBC with a chosen length $\\ell$ and \\lt{} $2^a3^b$.

To inform the selection of those parameters, in particular $\\ell$, which drives the

efficiency and the security of the

underlying cryptosystem, we

enumerate the total number of DBCs having a certain length $\\ell$ and a given

\\lt{} $2^a3^b$.

The comparison between this total number of DBCs and the total number of

integers that we wish to represent a priori provides some guidance regarding the selection of

suitable parameters. Our experiments indicate that the controlled DBC provides a speedup of at

least $6.98\\%$ and up to $8\\%$ for sizes from $192$ to $512$ bits. Experiments involve elliptic

curves defined over $\\F_p$, using the Inverted Edwards coordinate system and state of the art

scalar multiplication techniques.

12:17 [Pub][ePrint]

A constrained pseudorandom function (CPRF) PRF allows to derive constrained evaluation keys that only allow to evaluate PRF on a subset of inputs. CPRFs have only recently been introduced independently by three groups of researchers. However, somewhat curiously, all of them could only achieve a comparatively weak, selective-challenge form of security (except for small input spaces, very limited forms of constrained keys, or with superpolynomial security reductions).

In this paper, we construct the first fully secure CPRF without any of the above restrictions. Concretely, we support bit-fixing\'\' constrained keys that hardwire an arbitrary subset of the input bits to fixed values, we support exponentially large input spaces, and our security reduction is polynomial. We require very heavyweight tools: we assume multilinear maps, indistinguishability obfuscation, and our proof is in the random oracle model. Still, our analysis is far from tautological, and even with these strong building blocks, we need to develop additional techniques and tools.

As a simple application, we obtain the first adaptively secure non-interactive key exchange protocols for large user groups.

12:17 [Pub][ePrint]

The Sponge function is known to achieve 2^{c/2} security, where c is its capacity. This bound was carried over to keyed variants of the function, such as SpongeWrap, to achieve a min{2^{c/2},2^kappa} security bound, with kappa the key length. Similarly, many CAESAR competition submissions are designed to comply with the classical 2^{c/2} security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of min{2^{b/2},2^c,2^kappa}, with b>c the permutation size, by proving that the CAESAR submission NORX achieves this bound. Furthermore, we show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. For instance, NORX64 can increase its rate and decrease its capacity with 128 bits and Ascon-128 can encrypt three times as fast, both without affecting the provable security level.

12:17 [Pub][ePrint]

While expensive cryptographically verifiable computation aims at defeating malicious agents, many civil purposes of outsourced computation tolerate a weaker notion of security, i.e., lazy-but-honest\'\' contractors. Targeting this type of agents, we develop optimal contracts for outsourcing of computational tasks via appropriate use of rewards, punishments, auditing rate, and redundancy\'\'. Our contracts provably minimize the expense of the outsourcer (principal) while guaranteeing correct computation. Furthermore, we incorporate practical restrictions of the maximum enforceable fine, limited and/or costly auditing, and bounded budget of the outsourcer. By examining the optimal contracts, we provide insights on how resources should be utilized when auditing capacity and enforceability are limited. Finally, we present a light-weight cryptographic implementation of the contracts and discuss a comparison across different implementations of auditing in outsourced computation.

11:42 [News]

The IACR Fellows 2014 have been announced:
• Ran Canetti
• Antoine Joux
• Eyal Kushilevitz
• Moti Yung

06:59 [Event][New]

Submission: 15 June 2014
From July 20 to July 27
Location: Oriahovitza, Bulgaria

06:59 [Event][New]

Submission: 1 July 2014
From July 28 to August 1
Location: Bochum, Germany

2014-05-25
12:17 [Pub][ePrint]

Two open problems on using Matsui\'s Algorithm 2 with multiple linear approximations posed earlier by Biryukov, De Canni$\\grave{\\hbox{e}}$re and M. Quisquater at Crypto\'04 are solved in the present paper. That improves the linear cryptanalysis of 16-round DES reported by Matsui at Crypto\'94.

12:17 [Pub][ePrint]

Most existing symmetric searchable encryption schemes aim at allowing a user to outsource her encrypted data to a cloud server and delegate the latter to search on her behalf. These schemes do not qualify as a secure and scalable solution for the multi-party setting, where users outsource their encrypted data to a cloud server and selectively authorize each other to search. Due to the possibility that the cloud server may collude with some malicious users, it is a challenge to have a secure and scalable multi-party searchable encryption (MPSE) scheme. This is shown by our analysis on the Popa-Zeldovich scheme, which says that an honest user may leak all her search patterns even if she shares only one of her documents with another malicious user. Based on our analysis, we present a new security model for MPSE by considering the worst-case and average-case scenarios, which capture different server-user collusion possibilities. We then propose a MPSE scheme by employing the bilinear property of Type-3 pairings, and prove its security based on the Bilinear Diffie-Hellman Variant (BDHV) and Symmetric eXternal Diffie-Hellman (SXDH) assumptions in the random oracle model.

12:17 [Pub][ePrint]

In FSE 2014, an authenticated encryption mode COBRA [4], based on pseudorandom permutation (PRP) blockcipher, and POET [3], based on Almost XOR-Universal (AXU) hash and strong pseudorandom permutation (SPRP), were proposed. Few weeks later, COBRA mode and a simple

variant of the original proposal of POET (due to a forging attack [13] on the original proposal) with AES as an underlying blockcipher, were submitted in CAESAR, a competition [1] of authenticated encryption

(AE). In this paper we show a forging attack on the mode COBRA based on any n-bit blockcipher. Our attack on COBRA requires about O(n) queries with success probability about 1/2. This disproves the

claim proved in FSE 2014 paper. We also show both privacy and forging attack on the parallel version of POET, denoted POET-m. We can also recover some derived key of the construction. In case of the

modes POET or POE (the underlying modes for encryption), we show one query distinguishing attack when we instantiate the underlying AXU-hash function with some other AXU hash function, namely

uniform random involution. Thus, our result violates the designer\'s main claim (Theorem 8.1 in [1]). However, the attacks can not be extended directly for the specific choices of existing submitted versions to the CAESAR competition.

12:17 [Pub][ePrint]

The problem of secure data erasure has been extensively studied in the past with a rich body of literature available. All existing software-based solutions can be summarized as following the same one-bit-return protocol: the deletion program performs data erasure and returns either success or failure. However, such a one-bit-return protocol turns the data deletion system into a black box -- the user has to trust the outcome but cannot easily verify it. This is especially problematic when the deletion program is encapsulated within a Trusted Platform Module (TPM), and the user has no access to the code inside.

In this paper, we initiate a study on how to delete secret data with public verifiability. This is a subject that has not been investigated before, partly because it seems intuitively impossible. In this paper, we show a solution is possible by applying appropriate cryptographic primitives. Based on combining DHIES, Chaum-Pedersen Zero Knowledge Proof and ECDSA, we present a Secure Storage and Erasure (SSE) protocol. The key idea in our solution is based on a trust-but-verify\'\' paradigm, which is generally applicable to many security problems but has been largely neglected in the field of secure data deletion. Finally, we present a concrete implementation of the SSE system to demonstrate its practical feasibility.