(k, n)-Consecutive access structures

Abstract We consider access structures over a set of n participants, defined by a parameter k with $$1 \le k \le n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>k</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> in the following way: a subset is authorized if it contains at least k consecutive participants. Depending on whether we consider the participants placed in a line (that is, participant 1 is not next to participant n ) or in a circle, we obtain two different families, that we call ( k , n )-line-consecutive and ( k , n )-circle-consecutive access structures, respectively. Such access structures can appear in real-life situations involving distributed cryptography, which makes it more interesting to look for the best secret sharing schemes that can realize them. For both families, we characterize which are the configurations ( k , n ) that admit ideal secret sharing schemes. For the non-ideal ( k , n )-consecutive access structures, we give both upper and lower bounds on the information ratio of the best secret sharing schemes that can realize them. Some of these bounds are obtained after proving relations between the information ratios of access structures in the two considered families.