Cryptology ePrint Archive: Report 2013/082
Secret Sharing, Rank Inequalities and Information Inequalities
Sebastia Martin and Carles Padro and An Yang
Abstract: Beimel and Orlov proved that all
information inequalities on four or five variables,
together with all information inequalities
on more than five variables
that are known to date,
provide lower bounds on the size of the shares in
secret sharing schemes that are at most
linear on the number of participants.
We present here another two negative results
about the power of information
inequalities in the search for
lower bounds in secret sharing.
First, we prove that all information inequalities
on a bounded number of variables can only provide
lower bounds that are polynomial on the number of participants.
And second, we prove that the rank inequalities that
are derived from the existence of two common informations
can provide only lower bounds that are at most
cubic in the number of participants.
Category / Keywords: cryptographic protocols / Secret sharing, Information inequalities, Rank inequalities, Polymatroid.
Original Publication (with major differences): IACR-CRYPTO-2013
Date: received 17 Feb 2013, last revised 25 Nov 2014
Contact author: cpadro at ma4 upc edu
Available format(s): PDF | BibTeX Citation
Version: 20141125:151308 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]