RISC Seminars (Research on Information Security and Cryptology)
Archives: [2024] [2023] [2022] [2021] [2020] [2019] [2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [List of Speakers](To receive information about upcoming seminars, register for the RISC mailing list.)
[print]
Joint RISC/Intercity Seminar on The Mathematics of Cryptology
Date: | January 21 |
Location: | Huygens Building, Room 201, Lorentz Center, Leiden |
Schedule: | |
11:00-12:00 | Carles Padró (UPC Barcelona): Secret Sharing Schemes, Error Correcting Codes and Matroids Abstract: Error correcting codes and matroids have been widely used in the study of secret sharing schemes. This talk deals mainly with the connections between codes, matroids and a special class of secret sharing schemes, namely multiplicative linear secret sharing schemes (MLSSS). Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries.
Two open problems related to the complexity of multiplicative linear secret sharing schemes will be considered. Hirt and Maurer proved that such a scheme can be costructed whenever the set of players is not the union of two unqualified subsets. Cramer, Damgard and Maurer proved that, in this case, a multiplicative linear secret sharing scheme can be efficiently constructed from any linear secret sharing scheme by increasing the complexity by a constant factor of 2. The first open problem we consider is to determine in which situations a multiplicative scheme can be obtained without increasing the complexity. We study this problem in an extremal case. Namely, to determine whether all self-dual vector space access structures admit an ideal MLSSS. By the aforementioned connection, this in fact constitutes an open problem about Matroid Theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids. The second open problem deals with strongly multiplicative linear secret sharing schemes. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. |
12:00-13:00 | Salil Vadhan (Harvard): Randomness Extractors and their Cryptographic Applications Abstract: Over the past two decades, a rich body of work has developed around the
problem of constructing randomness extractors --- algorithms that extract
high-quality randomness (i.e. nearly uniform and independent bits) from
low-quality randomness (i.e. sources of biased and correlated bits).
Although some of the early results on randomness extraction came from the
cryptography literature, most of the subsequent theory has been developed in
the setting of computational complexity, where extractors have unified the
study of a number of fundamental objects (such as pseudorandom generators,
expander graphs, and list-decodable error-correcting codes). In the past
few years, the relevance of extractors to cryptography has been
re-discovered, with increasing variety of applications being found.
In this talk, I will survey the basic theory of randomness extractors, give a sense of the current state-of-the-art, and describe some of their cryptographic applications. |
13:45-14:45 | Rafi Ostrovsky (UCLA): Survey on Private Information Retrieval Abstract: Consider a setting where a user wishes to retrieve an item from a database,
without letting the database administrator know which item is being
retrieved. Of course, a trivial (but expensive) solution is for the user to
request contents of the entire database, thus concealing from the database
administrator which item is of interest to the user. Can this be done with
less communication? Perhaps somewhat surprisingly, the answer is yes, under
various assumptions and settings. In this talk, I'll survey much progress
that has been achieved on this problem and point our some interesting
connections to other problems in coding theory and several hardness results
in cryptography.
|
15:00-16:00 | Phong Nguyen (ENS Paris): From Euclid to Lenstra-Lenstra-Lovasz: Revisiting Lattice Basis Reduction Abstract: Lattices are simple yet fascinating mathematical objects.
Roughly speaking, they are linear deformations of
the n-dimensional grid Z^n.
Lattices have many applications in mathematics and computer science.
Of particular importance is lattice basis reduction,
which is the problem of finding "nice" representations of lattices.
For instance, lattice basis reduction is the most popular tool
to attack public-key cryptosystems.
In this talk, we will revisit lattice basis reduction, from Euclid's gcd algorithm to the celebrated LLL algorithm. We will also briefly discuss recent results. Curiously, it is possible to obtain a Euclid-like complexity for lattice basis reduction: in some sense, one can compute a reduced basis (without fast integer arithmetic) in essentially the same time as the elementary method to multiply integers. |
16:15-17:15 | Steven Galbraith (Royal Holloway): The Eta Pairing Abstract: We introduce a new pairing on certain supersingular curves which
is very closely related to the Tate pairing, but which has some
implementation advantages. We interpret the results of Duursma
and Lee in terms of this pairing and we describe a fast pairing on
genus 2 curves in characteristic 2.
|
0.0111s c