MAK Crypto Seminar: Oriol Farràs

By: Oriol Farràs (Univ. Rovira Virgili). Title: Local Bounds for the Optimal Information Ratio of Secret Sharing Schemes. Wednesday 21 March 2018, at 12'00. Campus Nord UPC, Building C3, Room 204a (2nd floor).

  • MAK Crypto Seminar: Oriol Farràs
  • 2018-03-21T12:00:00+01:00
  • 2018-03-21T13:00:00+01:00
  • By: Oriol Farràs (Univ. Rovira Virgili). Title: Local Bounds for the Optimal Information Ratio of Secret Sharing Schemes. Wednesday 21 March 2018, at 12'00. Campus Nord UPC, Building C3, Room 204a (2nd floor).
Quan?

21/03/2018 de 12:00 a 13:00 (Europe/Madrid / UTC100)

On?

Campus Nord UPC, Building C3, Room 204a (2nd floor)

Afegiu l'esdeveniment al calendari

iCal

The main objective of this work is to find properties of the access structures that admit efficient secret sharing schemes. The specific question we consider is to know whether access structures that are close admit secret sharing schemes with similar information ratios. Answers to this question will help understand the limitations of secret sharing and the behavior of the optimal information ratio, seen as a function from the set of all the access structures with a positive number of participants to the real numbers.

We show that for every two access structures $\Gamma$ and $\Gamma'$ the difference between their optimal information ratios is at most $|\Gamma\cup \Gamma'|-|\Gamma\cap\Gamma'|$. As a consequence of this result, we see that close access structures admit secret sharing schemes with similar information ratio. We show that this property is also true for particular classes of secret sharing schemes and models of computation, like the family of linear secret sharing schemes, span programs, Boolean formulas and circuits.

In order to understand this property, we also study the limitations of the techniques for finding lower bounds on the information ratio and other complexity measures. We analyze the behavior of these bounds when we add or delete subsets from an access structure.

It is a joint work with Jordi Ribes-González and Sara Ricci.

Keywords
MAT