Cryptology ePrint Archive: Report 2017/919

Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing

Oriol Farras and Tarik Kaced and Sebastia Martin and Carles Padro

Abstract: We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

Category / Keywords: cryptographic protocols / Secret sharing, Information inequalities, Rank inequalities, Common information, Linear Programming

Original Publication (with major differences): IACR-EUROCRYPT-2018

Date: received 20 Sep 2017, last revised 16 Dec 2019

Contact author: carles padro at upc edu

Available format(s): PDF | BibTeX Citation

Note: Extended version of the paper in EUROCRYPT 20018.

Version: 20191216:123009 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]