Optimal threshold padlock systems
Journal of Computer Security · 05.10.2022 · 30 (5) · 655-688
DOI: 10.3233/jcs-210065 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Computer Security, online erschienen am 21.12.2021. Verfasst von Jannik Dreier und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 34 Literaturangaben.
Abstract (Originalsprache)
In 1968, Liu described the problem of securing documents in a shared secret project. In an example, at least six out of eleven participating scientists need to be present to open the lock securing the secret documents. Shamir proposed a mathematical solution to this physical problem in 1979, by designing an efficient k-out-of- n secret sharing scheme based on Lagrange’s interpolation. Liu and Shamir also claimed that the minimal solution using physical locks is clearly impractical and exponential in the number of participants. In this paper we relax some implicit assumptions in their claim and propose an optimal physical solution to the problem of Liu that uses physical padlocks, but the number of padlocks is not greater than the number of participants. Then, we show that no device can do better for k-out-of- n threshold padlock systems as soon as [Formula: see text], which holds true in particular for Liu’s example. More generally, we derive bounds required to implement any threshold system and prove a lower bound of [Formula: see text] padlocks for any threshold larger than 2. For instance we propose an optimal scheme reaching that bound for 2-out-of- n threshold systems and requiring less than [Formula: see text] padlocks. We also discuss more complex access structures, a wrapping technique, and other sublinear realizations like an algorithm to generate 3-out-of- n systems with [Formula: see text] padlocks. Finally we give an algorithm building k-out-of- n threshold padlock systems with only [Formula: see text] padlocks. Apart from the physical world, our results also show that it is possible to implement secret sharing over small fields.
Zitieren
APA
Dreier, J., Dumas, J., Lafourcade, P., & Robert, L. (2022). Optimal threshold padlock systems. Journal of Computer Security, 30(5), 655-688. https://doi.org/10.3233/jcs-210065
Vancouver
Dreier J, Dumas J, Lafourcade P, Robert L. Optimal threshold padlock systems. Journal of Computer Security. 2022;30(5):655-688. doi:10.3233/jcs-210065
BibTeX
@article{Dreier2022,
author = {Dreier, Jannik and Dumas, Jean-Guillaume and Lafourcade, Pascal and Robert, Léo},
title = {Optimal threshold padlock systems},
journal = {Journal of Computer Security},
year = {2022},
volume = {30},
number = {5},
pages = {655--688},
doi = {10.3233/jcs-210065}
}
EUVIMED