J. Martí-Farré, C. Padró
Ideal secret sharing schemes whose minimal qualified subsets have at most three participants
Designs, Codes and Cryptography 52 (2009) 1-14. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201-215. Maiori, Italy, 2006.
One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants.We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme.
Download rank3.pdf