Notes on matroid theory related to secret sharing

2022 May 29

Matroid theory is related to ideal secret sharing schemes for special access structures, e.g., hierarchical and compartmented ones. "Ideal" here means that the size of each share is the same as the size of the secret. This means that the information ratio is 1. Shamir’s secret sharing scheme is ideal. The known upper bound for information ratio is O(2^{cn}) for some c<1 [1, 2] and the known lower bound is O(n/log n) [3]. 

An access structure is ideal if it admits an ideal scheme over some finite domain of secrets. 

An important theorem shown by Brickell and Davenport is that ideal access structures are determined by matroids:

(Brickell and Davenport [1]) Every ideal access structure is a matroid port.

There are several ways to define a matroid. If we take the rank function definition, a matroid on a set P is a pair (P, r) where r(.) is a rank function on subsets of P satisfying the following properties: (1) non-negative, (2) no greater than the cardinality of the input subset, (3) monotone (adding an element to the input subset never decreases the rank), (4) sub-modular (the sum of the rank of two subsets are no smaller than the sum of the rank on their union plus their intersection). Sub-modularity would imply sub-additivity because the latter requires only the sum of the rank of two subsets are no smaller than the rank on their union.

If a nonempty subset A of P satisfies the following: the rank of A is greater than the rank of A’ where A’ is A with any element removed, then A is called independent. Otherwise it’s dependent. In other words, an independent set decreases its rank by removing any of its elements and a dependent set has “redundant” elements. The maximal independent subsets are called basis, which become dependent by adding a single element. The minimal dependent subsets are called circuits, whose proper subsets are all independent. A matroid is said to be connected if for any two elements, we can find a circuit containing them. 

The previous theorem does not mean that if an access structure is a matroid port, then it is ideal. The other half of the story is:

(Brickell and Davenport [1]) If an access structure is a matroid port of a representable matroid, then the access structure is ideal.

A matroid port is an access structure whose minimal elements/subsets (i.e., authorized groups for the secret sharing scheme) are in correspondence with the circuits of a matroid containing a fixed point. 

Some known results:

Information ratio of secret sharing schemes realizing access structures that are not matroid ports is at least 1.5 [4]

Matroids that admit linear or multi-linear representations [7] are representable by partitions [30] and there exist algebraic matroids that are not representable by partitions [8]

Matroids whose ports admit ideal secret sharing schemes are multiples of entropic polymatroids and admit representations by partitions [5, 6]

Little is known about matroids not representable by partitions: 

There exist ports of matroids that are not representable by partitions that admit schemes with information ration arbitrarily close to 1 [9]

There exists a port of the Vámos matroid where the information ratio is at least 561/491 [10]

Matroids of rank 2 are linearly representable so ports of them admit ideal schemes. 

For rank k>2, there exist matroids of rank k that do not admit ideal schemes.[6]

[11] constructs a linear secret sharing scheme for ports of matroids of rank 3 that has information ratio at most n. Applying this recursively on ports of matroids of rank k >2, the scheme has information ratio at most n^{k-2}. This is meaningful upper bound for k << ln n / ln ln n 


Asymptotically almost every matroid has a minor that is the Vámos matroid, so almost every matroid port needs schemes with information ratio > 1

[1] Brickell, Ernest F., and Daniel M. Davenport. "On the classification of ideal secret sharing schemes." Journal of Cryptology 4.2 (1991): 123-134.

[2] Liu, Tianren, and Vinod Vaikuntanathan. "Breaking the circuit-size barrier in secret sharing." Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018.

[3] Csirmaz, László. "The size of a share must be large." Journal of cryptology 10.4 (1997): 223-231.

[4] Martí-Farré, Jaume, and Carles Padró. "On secret sharing schemes, matroids and polymatroids." Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2007.

[5] Matus, Frantisek. "Probabilistic Conditional Independence Structures And Matroid Theory: Background." (1994).

[6] Matus, F. "Matroid representations by partitions." Discrete Mathematics 203.1-3 (1999): 169-194.

[7] Simonis, Juriaan, and Alexei Ashikhmin. "Almost affine codes." Designs, Codes and Cryptography 14.2 (1998): 179-197.

[8] Ben-Efraim, Aner. "Secret-sharing matroids need not be algebraic." Discrete Mathematics 339.8 (2016): 2136-2145.

[9] Beimel, Amos, and Noam Livne. "On matroids and nonideal secret sharing." IEEE Transactions on Information Theory 54.6 (2008): 2626-2643.

[10] Gürpınar, Emirhan, and Andrei Romashchenko. "How to use undiscovered information inequalities: Direct applications of the copy lemma." 2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 2019.