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]
Special two-day RISC Seminar on the Theory of Cryptography
The second day (Friday) is jointly with the Intercity Number Theory Seminar. See here for more details (speakers, program, registration, etc).
Date: | September 18-19 |
Location: | Tinbergenzaal, KNAW Trippenhuis, Amsterdam |
Schedule: | |
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 Abstract: 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.
|
11:30-11:45 | Coffee/Cookies |
11:45-12:10 | Javier Herranz (UPC Barcelona, Spain): Using dual access structures in some cryptographic protocols Abstract: 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 some
privacy-preserving cryptographic protocols: one for restricted adaptive
oblivious transfer and one for attribute-based signatures (based on
RSA).
|
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 Abstract: 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 |
14:25-14:50 | Gabriele Spini (CWI and Universiteit Leiden, The Netherlands): Robust Secret Sharing through List Decoding Abstract: 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 |
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 Abstract: 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. |
15:25-16:00 | Coffee/Cookies |
16:00-16:45 | Carles Padró (UPC Barcelona, Spain): On non-perfect secret sharing schemes Abstract: 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) |
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 Abstract: 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. |
11:30-11:45 | Coffee/Cookies |
11:45-12:10 | Diego Mirandola (CWI and Universiteit Leiden, The Netherlands): On squares of codes Abstract: 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. Zemor. |
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 Abstract: We present explicit optimal binary pebbling algorithms for
reversing one-way hash chains. For a hash chain of length 2k, 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. |
14:30-14.45 | Coffee |
14:45-15:30 | Krzysztof Pietrzak (IST, Austria): Nested hybrid arguments with applications to selective decryption and constrained PRFs Abstract: 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.
|
15:30-16:00 | Coffee/Cookies |
16:00-16:45 | Dennis Hofheinz (KIT, Germany): Compact and tightly secure cryptography in the standard model Abstract: In this talk, we describe the first signature and public-key encryption
schemes that achieve the following properties simultaneously:
|
16:45- | Closing remarks |
0.02808s c