[crypto] [Serge.Fehr at cwi.nl: [risc-list] RISC at CWI (June 19): Padro']

[R. Hirschfeld]

------- Start of forwarded message -------
Date: Fri, 07 Jun 2013 17:22:40 +0200
From: Serge Fehr <Serge.Fehr at cwi.nl>
Subject: [risc-list] RISC at CWI (June 19): Padro'

Dear Colleague,

we cordially invite you to a joint RISC / Combinatorics & Optimization 
Seminar taking place on

                            *Wednesday June 19, 2013, at 1600h in Room 
L016 at CWI*

The program features a talk by

                          Prof. Carles Padro' (NTU Singapore, on leave 
from UPC Barcelona).

The talk is entitled

                      ``Secret Sharing, Rank Inequalities and 
Information Inequalities''


The abstract is quoted below. See also http://www.cwi.nl/crypto/risc.html

See you then and there!

best regards,


Ronald Cramer and Serge Fehr
(also on behalf of Monique Laurent).


------------------------------------------------
Carles Padro' (NTU, Singapore, on leave from UPC, Barcelona)

Secret Sharing, Rank Inequalities and Information Inequalities

Optimizing the length of the shares in secret sharing schemes is a 
difficult open problem. There is a huge gap between the best known lower 
and upper bounds. The only available technique to obtain lower bounds 
combines polymatroids, linear programming and information inequalities. 
Following the works by Csirmaz (1994) and Beimel and Orlov (2008), we 
analyze here the limitations of this technique.

Csirmaz proved that the best lower bounds that can be obtained by using 
only the basic Shannon inequalities are at most linear on the number of 
participants. Beimel and Orlov extended that result to all information 
inequalities on four or five variables, together with all information 
inequalities on more than five variables that are known to date. In this 
work, we prove that all (known or unknown) information inequalities on a 
bounded number of variables only can provide lower bounds that are 
polynomial on the number of participants. Our result is proved by 
finding solutions with small value for the involved linear programs. A 
simple family of uniform Boolean polymatroids is used in the search of 
such solutions.
---------------------------------------------

_______________________________________________
risc-list mailing list
risc-list at cwi.nl
https://lists.cwi.nl/mailman/listinfo/risc-list
------- End of forwarded message -------