### Program and Abstracts

Click on the title of a talk to view the abstract. A printer-friendly version is available here.

#### Thursday, September 18

10:00-10:45 | Registration and Welcome with Coffee |

10:45-11:30 | Ignacio Cascudo (Aarhus University, Denmark) Multiplicative linear secret sharing for non-commutative algebras and applications |

11:30-11:45 | Coffee/Cookies |

11:45-12:10 | Javier Herranz (UPC Barcelona, Spain) Using dual access structures in some cryptographic protocols |

12:10-14:00 | Lunch in town (not organized) |

14:00-14:25 | Max Fillinger (CWI, The Netherlands) Bit-commitment schemes with non-signaling adversaries |

14:25-14:50 | Gabriele Spini (CWI and Universiteit Leiden, The Netherlands) Robust Secret Sharing through List Decoding |

14:50-15:00 | Short break |

15:00-15:25 | Oriol Farràs (Universitat Rovira i Virgili, Spain) On the optimization of secret sharing schemes for general access structures |

15:25-16:00 | Coffee/Cookies |

16:00-16:45 | Carles Padró (UPC Barcelona, Spain) On non-perfect secret sharing schemes |

16:45- | Cocktail Reception (location and exact time to be announced) |

#### Friday, September 19

10:00-10:45 | Registration and Welcome with Coffee |

10:45-11:30 | Marc Stevens (CWI, The Netherlands) Counter-cryptanalysis: secure use of weak standards |

11:30-11:45 | Coffee/Cookies |

11:45-12:10 | Diego Mirandola (CWI and Universiteit Leiden, The Netherlands) On squares of codes |

12:10-13:45 | Joint lunch at KNAW |

13:45-14:30 | Berry Schoenmakers (TUE, The Netherlands) Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal |

14:30-14.45 | Coffee |

14:45-15:30 | Krzysztof Pietrzak (IST, Austria) Nested hybrid arguments with applications to selective decryption and constrained PRFs |

15:30-16:00 | Coffee/Cookies |

16:00-16:45 | Dennis Hofheinz (KIT, Germany) Compact and tightly secure cryptography in the standard model |

16:45- | Closing remarks |

### Abstracts

Ignacio Cascudo (Aarhus University, Denmark)

Multiplicative linear secret sharing for non-commutative algebras and applications

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.

Javier Herranz (UPC Barcelona, Spain)

Using dual access structures in some cryptographic protocols

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).

Max Fillinger (CWI, The Netherlands)

Bit-commitment schemes with non-signaling adversaries

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

Gabriele Spini (CWI and Universiteit Leiden, The Netherlands)

Robust Secret Sharing through List Decoding

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

Oriol Farràs (Universitat Rovira i Virgili, Spain)

On the optimization of secret sharing schemes for general access structures

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.

Carles Padró (UPC Barcelona, Spain)

On non-perfect secret sharing schemes

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)

Marc Stevens (CWI, The Netherlands)

Counter-cryptanalysis: secure use of weak standards

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.

Diego Mirandola (CWI and Universiteit Leiden, The Netherlands)

On squares of codes

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.

Berry Schoenmakers (TUE, The Netherlands)

Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal

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.

Krzysztof Pietrzak (IST, Austria)

Nested hybrid arguments with applications to selective decryption and constrained PRFs

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.

Dennis Hofheinz (KIT, Germany)

Compact and tightly secure cryptography in the standard model

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.