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

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

2012-10-25
15:17 [Pub][ePrint] Extending Brickell-Davenport Theorem to Non-Perfect Secret Sharing Schemes, by Oriol Farras and Carles Padro

  One important result in secret sharing is Brickell-Davenport Theorem: every ideal perfect secret sharing scheme defines a matroid that is uniquely determined by the access structure. Even though a few attempts have been made, there is no satisfactory definition of ideal secret sharing scheme for the general case, in which non-perfect schemes are considered as well. Without providing another unsatisfactory definition of ideal non-perfect secret sharing scheme, we present a generalization

of Brickell-Davenport Theorem to the general case. After analyzing that result under a new point of view and identifying its combinatorial nature, we present a characterization of the (not necessarily perfect)

secret sharing schemes that are associated to matroids. Some optimality properties of such schemes are discussed.



15:17 [Pub][ePrint] Evaluating User Privacy in Bitcoin, by Elli Androulaki and Ghassan Karame and Marc Roeschlin and Tobias Scherer and Srdjan Capkun

  Bitcoin is quickly emerging as a popular digital payment system. However, in spite of its reliance on pseudonyms, Bitcoin raises a number of privacy concerns due to the fact that all of the transactions that take place are publicly announced in the system.

In this paper, we investigate the privacy guarantees of Bitcoin in the setting where Bitcoin is used as a primary currency for the daily transactions of individuals. More specifically, we evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that mimics Bitcoin client\'s behavior in the context where Bitcoin is used for all transactions within a university. In this setting, our results show that the profiles of almost 40% of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin. As a by-product, we have designed and implemented the first simulator of Bitcoin; our simulator can be used to model the interaction between Bitcoin users in generic settings.



15:17 [Pub][ePrint] A Novel Permutation-based Hash Mode of Operation FP and the Hash Function SAMOSA, by Souradyuti Paul and Ekawat Homsirikamol and Kris Gaj

  The contribution of the paper is two-fold. First, we design a novel permutation-based hash mode of operation FP, and analyze its security. The FP mode is derived by replacing the hard-to-invert primitive of the FWP mode -- designed by Nandi and Paul, Indocrypt 2010 -- with an easy-to-invert permutation; since easy-to-invert permutations with good cryptographic properties are normally easier to design, and are more efficient than the hard-to-invert functions, the FP mode is more suitable in practical applications than the FWP mode.

We show that any n-bit hash function that uses the FP mode is indifferentiable from a random oracle up to 2^n/2 queries (up to a constant factor), if the underlying 2n-bit permutation is free from any structural weaknesses. Based on our further analysis and experiments, we conjecture that the FP mode is resistant to all non-trivial generic attacks with work less than the brute force, mainly due to its large internal state. We compare the FP mode with other permutation-based hash modes, and observe that it displays the so-far best security/rate trade-off.

To put this into perspective, our second contribution is a proposal for a concrete hash function SAMOSA using the new mode and the $P$-permutations of the SHA-3 finalist Groestl. Based on our analysis we claim that the SAMOSA family cannot be attacked with work significantly less than the brute force. We also provide hardware implementation (FPGA) results for SAMOSA to compare it with the SHA-3 finalists. In our implementations, SAMOSA family consistently beats Groestl, Blake and Skein in the throughput to area ratio. With more efficient underlying permutation, it seems possible to design a hash function based on the FP mode that can achieve even higher performances.



15:17 [Pub][ePrint] Taking proof-based verified computation a few steps closer to practicality (extended version), by Srinath Setty and Victor Vu and Benjamin Braun and Andrew J. Blumberg and Michael Walfish

  We describe Ginger, a built system for unconditional, general-purpose,

and nearly practical verification of outsourced computation. Ginger is

based on Pepper, which uses the PCP theorem and cryptographic techniques

to implement an \\emph{efficient argument} system (a kind of interactive

protocol). Ginger slashes the query size and costs via theoretical

refinements that are of independent interest; broadens the computational

model to include (primitive) floating-point fractions, inequality

comparisons, logical operations, and conditional control flow; and

includes a parallel GPU-based implementation that dramatically reduces

latency.



15:17 [Pub][ePrint] Some observations to speed the polynomial selection in the number field sieve, by Min Yang, Qingshu Meng, Zhangyi Wang, Huanguo Zhang

  If the yield of a polynomial pair is closely correlated with the coefficients of the polynomial pair, we can select polynomials by checking the coefficients first. This can speed the selection of good polynomials. In this paper, we aim to study the correlation between the polynomial coefficients and the yield of the polynomials. By heuristic analysis and some experiments, we find that the yield of polynomial with the ending coefficient containing many small primes is usually better than the one whose ending coefficient does not contain. The ending coefficient has closer correlation with the yield than the leading coefficient has. The number of real roots can be determined only by partial coefficients of the polynomial if it is skewed. All these observations can be used to speed the search of good polynomials for the number filed sieve.



15:17 [Pub][ePrint] The LED Block Cipher, by Jian Guo, Thomas Peyrin, Axel Poschmann and Matt Robshaw

  We present a new block cipher LED. While dedicated to compact hardware implementation, and offering the smallest silicon footprint among comparable block ciphers, the cipher has been designed to simultaneously tackle three additional goals.

First, we explore the role of an ultra-light (in fact non-existent) key schedule. Second, we consider the resistance of ciphers, and LED in particular, to related-key attacks: we are able to derive simple yet interesting AES-like security proofs for LED regarding related- or single-key attacks. And third, while we provide a block cipher that is very compact in hardware, we aim to maintain a reasonable performance profile for software implementation.



15:17 [Pub][ePrint] How to Garble RAM Programs, by Steve Lu and Rafail Ostrovsky

 

Yao\'s Garbled Circuits is one of the central and one of the most widely used tools in cryptography, both in theory and in practice. It has numerous applications and multiple implementations, as well as over 1800 scientific citations (according to Google Scholar). It\'s applicability comes from multiple desirable features: it can be based on any one-way function (which yields efficient implementations based on block-ciphers such as AES), has minimal interaction, and garbled inputs can be generated given only the knowledge of the cryptographic keys used for garbling inputs and thus input garbling is independent of the garbled circuit structure. However, one of the major drawbacks of Yao\'s Garbled Circuit method is the need to \"compile\" Random Access Machine (RAM) programs into circuits, which often leads to exponential increases both in the garbled program size and in the garbled program running time, compared to the RAM program. Consider, for example, binary search: while the RAM program for binary search can be executed in logarithmic time in its input size, a circuit computation requires a linear-sized representation and work. Nevertheless, the non-interactive nature of Yao\'s Garbled Circuits can sometimes far outweigh the need to compile programs into circuits.

The question that we consider in this paper is this: is it possible to retain all of the desirable features of Yao\'s Garbled Circuits mentioned above, including its non-interactive feature without taking a potentially exponential hit in unrolling RAM programs into circuits? We affirmatively answer this question. In particular, we show how to garble any RAM program (where once garbled, the Garbled RAM program can be executed non-interactively on a single garbled input, just like Yao) so that its garbled program running time increases by a fixed polynomial in the security parameter (just like Yao) times poly-logarithmic quantity both in the input size and the original program running time. The garbled program sizeis proportional to the original program running time times a fixed polynomial in the security parameter times poly-log of the input size. The garbled input (compared to the original input) grows by poly-log in its size times the security parameter.

Just like Garbled Circuits, the input encoding is independent from the specific RAM program that is garbled, and only depends on the input encoding keys, and the recipient of the garbled program can select (parts of) the garbled input via Oblivious Transfer.

As an illustrative example, consider binary search: our result shows that Bob can give data consisting of $n$ sorted private-key encrypted numbers using $O(n * polylog(n))$ encryptions to Alice (assuming each encrypted number fits into a word). Later, Bob can garble any binary search into non-interactive garbled program of size $k^{O(1)} * polylog(n)$, where $k^{O(1)}$ is a fixed polynomial in the security parameter. The binary search query can be chosen and garbled by Bob after he uploaded his data to Alice and without having to remember the data. Alice can execute garbled binary search non-interactively in $k^{O(1)} * polylog(n)$ steps. We stress that the size of our garbled RAM program as well as its running time is only poly-logarithmic in the input size. In contrast, all previous secure protocols for binary search required either programs that were at least linear in the input size or, if sub-linear, required at least logarithmic number of rounds of interaction.

Our result is very general: an arbitrary garbled RAM program can be executed non-interactively with only poly-logarithmic increase in the running time (compared to insecure execution) and the garbled program will retain its compact size even if the program has multiple loops, multiple nested execution branches, recursion, etc.

Our techniques generalize and unify several previous results, including Oblivious RAMs and Yao\'s Garbled Circuits. As a stepping stone towards our general result, under the assumptions that one-way functions exist, we show how to make a one-round Oblivious RAM with poly-log overhead per read/write. Previous poly-log overhead, constant-round RAMs were either not secure or based on pairing-based hardness assumptions. In contrast, our result is based on the necessary assumption of any one way function. In fact, we need only PRFs or any symmetric-key encryption in our construction.



15:17 [Pub][ePrint] A note on invariant linear transformations in multivariate public key cryptography, by Andreas Wiemers

  Imai and Matsumoto introduced a public key cryptosystem based on

multivariate quadratic polynomials. In a simplified way, the essence of their cryptosystem can be described in the following way: Start with a central monomial F. The secret key comprises

two invertible linear transformations T and L such that TFL is the public key. In order to study equivalent public keys it is natural to ask for the \"invariant\" secret keys (T,L), i.e. TFL=F. Lin, Faugere, Perret and Wang give a partial answer to this question by considering such L which fulfill FL=F. In this paper we will determine all invariant invertible linear transformations (T,L).



15:17 [Pub][ePrint] Collecting Data while Preserving Individuals\' Privacy: A Case Study, by Alexis Bonnecaze and Robert Rolland

  Several companies exploit medical data to better understand medication consumption patterns.

Their analyses are useful to various health actors in order to enhance health care management.

In this article, we focus on a configuration which allows a network of pharmacies to forward medical data to

a private company in order to construct a database. Pharmacies must operate in full compliance with legal requirements in terms of confidentiality and privacy. We show that our solution fulfills all the requirements. Our work leads us to introduce the concept of generalized discrete logarithm problem which is proven to be as hard as the discrete logarithm problem.



15:17 [Pub][ePrint] Leakage-Resilient Cryptography from Minimal Assumptions, by Carmit Hazay and Adriana Lopez-Alt and Hoeteck Wee and Daniel Wichs

  We present new constructions of leakage-resilient cryptosystems, which remain provably secure even if the attacker learns some arbitrary partial information about their internal secret key. For any polynomial $\\ell$, we can instantiate these schemes so as to tolerate up to $\\ell$ bits of leakage. While there has been much prior work constructing such leakage-resilient cryptosystems under concrete number-theoretic and algebraic assumptions, we present the first schemes under general and minimal assumptions. In particular, we construct:

- Leakage-resilient public-key encryption from any standard public-key encryption.

- Leakage-resilient weak pseudorandom functions, symmetric-key encryption}, and message-authentication codes from any one-way function.

These are the first constructions of leakage-resilient symmetric-key primitives that do not rely on public-key assumptions. We also get the first constructions of leakage-resilient public-key encryption from ``search assumptions\'\', such as the hardness of factoring or CDH. Although our schemes can tolerate arbitrarily large amounts of leakage, the tolerated rate of leakage (defined as the ratio of leakage-amount to key-size) is rather poor in comparison to prior results under specific assumptions.

As a building block of independent interest, we study a notion of weak hash-proof systems in the public-key and symmetric-key settings. While these inherit some of the interesting security properties of standard hash-proof systems, we can instantiate them under general assumptions.





2012-10-23
12:35 [Event][New] ICT-EurAsia 2013: Information Communication Technology-Eurasia Conference 2013

  Submission: 20 November 2012
Notification: 15 December 2012
From March 25 to March 29
Location: Yogyakarta, Indonesia
More Information: http://www.ifs.tuwien.ac.at/ict-eurasia/