RISC Seminar on Theory of Cryptography

Multiplicative linear secret sharing schemes are a very useful primitive in secure multiparty computation. In this talk, I will recall this notion and introduce a definition of multiplicative secret sharing where the space of secrets is a non-commutative algebra. I am mainly interested in the case of algebras of square matrices over a finite field (with the usual matrix multiplication) and direct products of those. I will present constructions of multiplicative schemes in these cases and discuss some applications to secure multiparty computation where these constructions may be especially interesting.

20 years ago, R. Cramer, I. Damgård and B. Schoenmakers used the notion of dual access structure in the design of partial knowledge proof systems. Later in 2000, R. Cramer, I. Damgård and U. Maurer used this same notion for designing general secure multiparty computation protocols. In this talk, we will see how the notion of dual access structures has been recently used in the design of an attribute-based signature scheme based on RSA (maybe the first one which does not use pairings).

We consider multi-prover bit-commitment schemes whose security is based on the assumption that the provers cannot communicate with each other. As Crépeau et al. pointed out, previous security proofs of such schemes make the implicit assumption that the provers are classical, i.e., they do not share an entangled quantum state. They showed that there are schemes that are secure against classical adversaries, but insecure in the quantum setting. Also, they showed that there are schemes which are secure against entangled adversaries.

We examine in how far it is possible to base the security of bit-commitment schemes only on the assumption that the provers cannot communicate with each other, making no further computational or physical assumptions. Adversaries that are only bound by this constraint are called non-signaling. In this talk, we give an introduction to the non-signaling setting, summarize the positive and negative results we achieved so far and give a proof of our impossibility result for a simple yet natural class of two-prover bit-commitment schemes.

Joint work with Serge Fehr

Secret sharing is a fundamental cryptographic primitive; in its basic form, it allows a secret s to be shared among n players in such a way that any set of t+1 player can reconstruct s, but any set consisting of at most t players cannot get any information on it, where n and t are some integer parameters.

Robust secret sharing has an additional requirement: to prevent incorrect reconstruction, it is asked that if all the n players pool together their shares, but up to t of them are incorrect, then the secret can nevertheless be reconstructed (except maybe with small probability, say 2^-k). If t < n/2 this is possible, but in the range n/3 < t < n/2 this comes at the price of some extra information that needs to be distributed along with the secret; our goal is to design a protocol that minimizes this overhead.

Previous work on this topic has obtained efficient schemes with an overhead of O(k+n) bits; our aim is to remove, or at least weaken, the dependency on n (whereas the linear dependency on k is unavoidable).

We consider a new approach, based on the combiation of AMD codes with list decoding schemes, which yields robust secret sharing schemes in the range t/n < 1/2 - e, for some (hopefully) small e. Using the “simplest” list-decoding scheme, we obtain an efficient protocol in the range t/n < 0.38 with an overhead of O(k+log n) bits.

Improving this restriction on t/n by means of more sophisticated list decoding schemes is work in progress; during the talk we shall discuss some possible techniques and tweaks to reach this goal.

Joint work with Serge Fehr and Ronald Cramer

A secret sharing scheme is a method to protect a secret. Given a secret, the scheme generates pieces of information, that are called shares, in such a way that the secret can be recovered from the shares. Considering that each share is held by a participant, the access structure of the scheme is defined as the family of subsets of participants that can recover the secret. A scheme is perfect if the subsets of participants that are not in the access structure do not have any information about the secret.

Every access structure admits many different secret sharing schemes. However, for the sake of efficiency, we are interested on schemes with small shares. We define the information ratio of a scheme as the size of the biggest share divided by the size of the secret. We know that for perfect schemes this ratio is always greater or equal than one, but for most access structures there are not any schemes attaining this bound. Indeed, for most access structures we only know schemes whose information ratio is exponential on the number of participants. In order to study this problem, we define the optimal information ratio of an access structure as the infimum of the information ratio of the schemes realizing it.

The aim of this talk is to present new results on the behavior of the optimal information ratio.

A secret sharing scheme is non-perfect if some subsets of participants that cannot recover the secret value have partial information about it. The information ratio of a secret sharing scheme is the ratio between the maximum length of the shares and the length of the secret. This talk is dedicated to the search of bounds on the information ratio of non-perfect secret sharing schemes. To this end, we extend the known connections between matroids polymatroids and perfect secret sharing schemes to the non-perfect case.

In order to study non-perfect secret sharing schemes in all generality, we describe their structure through their access function, a real function that measures the amount of information that every subset of participants obtains about the secret value. We prove that there exists a secret sharing scheme for every access function.

Uniform access functions, that is, the ones whose values depend only on the number of participants, generalize the threshold access structures. We determine the optimal information ratio of the uniform access functions.

Finally, we propose a new definition of ideal non-perfect secret sharing scheme and we explore the connection of ideal schemes with matroids. (Joint work with Oriol Farras, Torben Hansen and Tarik Kaced)

Counter-cryptanalysis attempts to exploit unavoidable anomalies introduced by cryptanalytic attacks to detect and block cryptanalytic attacks. Thus, in principle, it enables the continued secure use of weak cryptographic primitives. The first example is the efficient detection whether any given single message has been constructed -- together with an unknown sibling message – using a cryptanalytic collision attack on MD5 or SHA-1. An immediate application is in digital signature verification software to ensure that an (older) MD5 or SHA-1 based digital signature is not a forgery using a collision attack.

Only due to counter-cryptanalysis were we able to discover that Flame, a highly advanced malware for cyberwarfare uncovered in May 2012, employed an as of yet unknown variant of our chosen-prefix collision attack on MD5 to craft a signature forgery.

Given a linear error-correcting code, its square is defined to be the span of the componentwise products of all pairs of codewords. We explain how a code gives rise to a linear secret-sharing scheme and how the multiplicativity properties of that secret-sharing scheme are related to the square of the code. This connection motivates our interest in squares of codes. In particular we study whether the square of a random code of a certain dimension fills the whole space with high probability. We show that this is indeed the case as soon as the dimension is larger than the square root of the length. Combinatorial arguments about quadratic forms over finite fields play an important role.

This is a joint work with I. Cascudo, R. Cramer and G. Zémor.

We present explicit optimal binary pebbling algorithms for reversing one-way hash chains. For a hash chain of length 2^k, the number of hashes performed per output round is at most ⌈k/2⌉, whereas the number of hash values stored throughout is at most k. This is optimal for binary pebbling algorithms characterized by the property that the midpoint of the hash chain is computed just once and stored until it is output, and that this property applies recursively to both halves of the hash chain.

We develop a framework for easy comparison of explicit binary pebbling algorithms, including simple speed-1 binary pebbles, Jakobsson's binary speed-2 pebbles, and our optimal binary pebbles. Explicit schedules describe for each pebble exactly how many hashes need to be performed in each round. The optimal schedule exhibits a nice recursive structure, which allows fully optimized implementations that can readily be deployed. In particular, we develop in-place implementations with minimal storage overhead (essentially, storing only hash values), and fast implementations with minimal computational overhead.

We introduce a new proof technique where hybrid arguments are applied in a recursive (rather than linear) way. As applications we give proofs for the adaptive security of constrained PRFs and for the selective decryption problem which loses only quasipolynomial factors. Previously only proofs for selective security of these objects were known. This then translated to adaptive security via complexity leveraging losing an exponential factor.

In this talk, we describe the first signature and public-key encryption schemes that achieve the following properties simultaneously:

• They are (almost) tightly secure under a standard assumption. Specifically, their (EUF-CMA, resp. IND-CCA) security in the multi-user, multi-challenge setting can be reduced to the DDH assumption in a pairing-friendly group with a multiplicative loss of O(k), where k is the security parameter.
• They are compact, in the sense that public parameters, keys, and signatures (resp. ciphertexts) require only a constant number of group elements. Concretely, parameters, verification keys, and signatures of our signature scheme contain 18, 6, and 25 group elements, respectively.

Our results rely on a new technique we call “hidden partitioning.” During a security proof, hidden partitioning allows to make modifications to many challenge signatures (or ciphertexts) in a particularly economic way.