International Association for Cryptologic Research

# IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

You can also access the full news archive.

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

2013-05-28
05:22 [Pub][ePrint]

To instill greater confidence in computations outsourced to the cloud, clients should be able to verify the correctness of the results returned. To this end, we introduce Pinocchio, a built system for efficiently verifying general computations while relying only on cryptographic assumptions. With Pinocchio, the client creates a public evaluation key to describe her computation; this setup is proportional to evaluating the computation once. The worker then evaluates the computation on a particular input and uses the evaluation key to produce a proof of correctness. The proof is only 288 bytes, regardless of the computation performed or the size of the inputs and outputs. Anyone can use a public verification key to check the proof. Pinocchio achieves strong asymptotic efficiency by refining the Quadratic Arithmetic Programs of Gennaro, Gentry, Parno, and Raykova (EuroCrypt 2013).

Crucially, our evaluation on seven applications demonstrates that Pinocchio is efficient in practice too. Pinocchio\'s verification time is typically 10ms: 5-7 orders of magnitude less than previous work; indeed Pinocchio is the first general-purpose system to demonstrate per-instance verification cheaper than native execution (for some apps). Pinocchio also reduces the worker\'s proof effort by an additional 19-60x. As an additional feature, Pinocchio generalizes to zero-knowledge proofs at a negligible cost over the base protocol. Finally, to aid development, Pinocchio provides an end-to-end toolchain that compiles a subset of C into programs that implement the verifiable computation protocol.

05:22 [Pub][ePrint]

We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme known to date. We formally prove that Path ORAM requires O(log^2 N / k) bandwidth overhead for block size B = k * log N. For block sizes bigger than O(log^2 N) bits, Path ORAM is asymptotically better than the best known ORAM scheme with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.

05:22 [Pub][ePrint]

Basing signature schemes on strong lattice problems has been a long standing open issue. Today, two families of lattice-based signature schemes are known: the ones based on the hash-and-sign construction of Gentry et al.; and Lyubashevsky\'s schemes, which are based on the Fiat-Shamir framework.

In this paper we show for the first time how to adapt the schemes of Lyubashevsky to the ring signature setting. In particular we transform the scheme of ASIACRYPT 2009 into a ring signature scheme that provides strong properties of security under the random oracle model. Anonymity is ensured in the sense that signatures of different users are within negligible statistical distance even under full key exposure. In fact, the scheme satisfies a notion which is stronger than the classical full key exposure setting as even if the keypair of the signing user is adversarially chosen, the statistical distance between signatures of different users remains negligible.

Considering unforgeability, the best lattice-based ring signature schemes provide either unforgeability against arbitrary chosen subring attacks or insider corruption in log-sized rings. In this paper we present two variants of our scheme. In the basic one, unforgeability is ensured in those two settings. Increasing signature and key sizes by a factor k (typically 80 − 100), we provide a variant in which unforgeability is ensured against insider corruption attacks for arbitrary rings. The technique used is pretty general and can be adapted to other existing schemes.

05:22 [Pub][ePrint]

With increasing usage of hardware accelerators in modern heterogeneous

System-on-Chips (SoCs), the distinction between hardware and software is no longer rigid. The domain of cryptography is no exception and efficient hardware design of so-called software ciphers are becoming increasingly popular. In this paper, for the first time we propose an efficient hardware accelerator design for SOSEMANUK, one of the finalists of the eSTREAM stream cipher competition in the software category. Since SOSEMANUK combines the design principles of the block cipher Serpent and the stream cipher SNOW 2.0, we make our design

flexible to accommodate the option for independent execution of Serpent and SNOW 2.0. In the process, we identify interesting design points and explore different levels of optimizations. We perform a detailed experimental evaluation of the performance figures of each design point and in each case our figures by far outperform the existing benchmarks. The best throughput achieved by the combined design is 67.84 Gbps for SOSEMANUK, 33.92 Gbps for SNOW 2.0 and 2.12 Gbps for Serpent. The throughput for SOSEMANUK by far outperforms all existing benchmarks on the eSTREAM candidates.

05:22 [Pub][ePrint]

We put forward a new notion, function privacy, in identity-based encryption and, more generally, in functional encryption. Intuitively, our notion asks that decryption keys reveal essentially no information on their corresponding identities, beyond the absolute minimum necessary. This is motivated by the need for providing predicate privacy in public-key searchable encryption. Formalizing such a notion, however, is not straightforward as given a decryption key it is always possible to learn some information on its corresponding identity by testing whether it correctly decrypts ciphertexts that are encrypted for specific identities.

In light of such an inherent difficulty, any meaningful notion of function privacy must be based on the minimal assumption that, from the adversary\'s point of view, identities that correspond to its given decryption keys are sampled from somewhat unpredictable distributions. We show that this assumption is in fact sufficient for obtaining a strong and realistic notion of function privacy. Loosely speaking, our framework requires that a decryption key corresponding to an identity sampled from any sufficiently unpredictable distribution is indistinguishable from a decryption key corresponding to an independently and uniformly sampled identity.

Within our framework we develop an approach for designing function-private identity-based encryption schemes, leading to constructions that are based on standard assumptions in bilinear groups (DBDH, DLIN) and lattices (LWE). In addition to function privacy, our schemes are also anonymous, and thus yield the first public-key searchable encryption schemes that are provably keyword private: A search key sk_w enables to identify encryptions of an underlying keyword w, while not revealing any additional information about w beyond the minimum necessary, as long as the keyword w is sufficiently unpredictable.

05:22 [Pub][ePrint]

Abstract: We present a paper-based voting method that attempts to achieve the privacy of voters and election universal verifiability and integrity with only paper ballots and without using any cryptography method. The voting procedure is easy and it needs only selecting the intention of voter over screen of an electronic device. The rest of the voting procedure will be carried out by the device. Voter gets a receipt that can be used to verify that his vote has been counted in final tally as he intended. However the receipt cannot help voter to reveal who he voted for. Also vote selling or coercion is not possible even with the voter\'s cooperation. The ballot in our voting method has two side, one positive and one negative. Ballots have been prepared for voting in prepackaged form (i.e. 5 ballots per package). Some bubbles of each ballot are prefilled in random way. Numbers of positive and negative filled bubbles are equal with each other and also for each candidate in a package. For example if every package has 30 filled bubbles and if there are three candidates, there would be 10 filled bubbles for each candidate in a package. As it is clear half of those are positive and the other half are negative. The procedure of OneBallot voting is as follows: Voter puts the ballot inside of an electronic device and then he chooses his candidate on the device screen. Then device print another ballot exact same as the original one by one difference; the device fills one positive bubble or unfills one negative bubbles for the selected candidate. First action can be done on the original ballot but the second one needs to print new ballot inevitably. Then device makes a copy from new ballot as voter\'s receipt and transfers original ballot to the ballot box. After election, there will be a copy from all of ballots in a public board (i.e. a website).

05:22 [Pub][ePrint]

In this paper we will prove a basic property of weil pairing which helps in evaluating its value. We will show that the weil pairing value as

computed from the definition is equivalent with the ratio formula based on the miller function. We prove a novel theorem (Theorem 2) and use it

to establish the equivalence. We further validate our claims with actual random examples.

05:22 [Pub][ePrint]

Ristenpart, Shacham and Shrimpton (Eurocrypt 2011) recently presented schemes which are provably secure in the random-oracle model (ROM),

but easily broken if the random oracle is replaced by typical indifferentiable hash constructions such as chop-MD or prefix-free-MD.

They found that the indifferentiability framework, due to Maurer, Renner and Holenstein (TCC 2004), does not

necessarily allow composition in multi-stage settings, that is, settings consisting of multiple disjoint adversarial stages. On the positive

side, they prove that the non-adaptive chosen distribution attack (CDA) game of Bellare et al.~(Asiacrypt 2009), a multi-stage game capturing the security of deterministic encryption schemes,

remains secure if the random oracle is implemented by an NMAC-like hash function.

In this paper we introduce a framework to work with the indifferentiability notion in multi-stage scenarios. For this we provide

a model for iterative hash functions which is general enough to cover not only NMAC-like functions, but also functions such as chop-MD

or even hash trees. We go on to define a property on multi-stage games called \\emph{unsplittability} which intuitively captures that

adversaries cannot split the computation of a single hash value over several stages. We present a composition theorem for

unsplittable multi-stage games which generalizes the single-stage composition theorem for indifferentiable hash functions. We then show that

the CDA game (adaptive or non-adaptive) is unsplittable for \\emph{any} iterative hash function (thereby extending the preliminary results

by Ristenpart et al.). Finally, we prove that the \\emph{proof-of-storage} game presented by Ristenpart et al.~as a counterexample to

the general applicability of the indifferentiability framework is unsplittable for any multi-round iterative hash function, such as

Liskov\'s Zipper Hash (SAC~2006).

05:22 [Pub][ePrint]

This paper describes new algorithm for breaking McEliece cryptosystem, built on Reed-Muller binary code $RM(r, m)$, which receives the private key from the public key. The algorithm has complexity $O(n^d+n^4log_2n)$ bit operations, where $n=2^m, d=\\text{GCD}(r,m-1).$ In the case of $\\text{GCD}(r,m-1)$ limitation, attack has polynomial complexity. Practical results of implementation show that McEliece cryptosystems, based on the code with length $n=65536$ bits, can be broken in less than 7 hours on a personal computer.

05:22 [Pub][ePrint]

In this paper, security analysis of block ciphers with key length greater than block length is proposed. For a well-designed block cipher with key length k and block length n s.t. k>n and for all P, C, there are 2^{k-n} keys which map P to C. For given block cipher, if there is an efficient algorithm that can classify such keys, we propose an algorithm will be able to recover the secret key with complexity O(max{2^n, 2^{k-n}}). We apply this method on 2-round block cipher KASUMI.

05:22 [Pub][ePrint]

We present novel security requirements for second price auctions and a

simple, efficient and practical protocol that provably maintains these

requirements. Novel requirements are needed because commonly used requirements,

such as the indistinguishability-based secrecy requirement of encryption schemes

presented by \\cite{goldwasser1982pep}, do not fit properly in the second price

auctions context. Additionally, the presented protocol uses a trustworthy

supervisor that checks if the auctioneer deviated from the protocol and fines

him accordingly. By making sure the expected utility of the auctioneer when

deviating from the protocol is lower than his expected utility when abiding by

the protocol we ascertain that a {\\em rational} auctioneer will abide by the

protocol. This allows the supervisor to optimize by performing

(computationally-intensive) inspections of the auctioneer with only low

probability.