{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:03:20Z","timestamp":1777806200710,"version":"3.51.4"},"reference-count":34,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T00:00:00Z","timestamp":1640044800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2022,10,5]]},"abstract":"<jats:p>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\u2019s 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\u2019s 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.<\/jats:p>","DOI":"10.3233\/jcs-210065","type":"journal-article","created":{"date-parts":[[2021,12,21]],"date-time":"2021-12-21T12:59:55Z","timestamp":1640091595000},"page":"655-688","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal threshold padlock systems"],"prefix":"10.1177","volume":"30","author":[{"given":"Jannik","family":"Dreier","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France. E-mail:\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Guillaume","family":"Dumas","sequence":"additional","affiliation":[{"name":"University Grenoble Alpes, Laboratoire Jean Kuntzmann, CNRS UMR 5224, 38058 Grenoble, France. E-mail:\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Lafourcade","sequence":"additional","affiliation":[{"name":"University Clermont Auvergne, LIMOS, CNRS UMR 6158, 63178 Aubi\u00e8re, France. E-mails:\u00a0,\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e9o","family":"Robert","sequence":"additional","affiliation":[{"name":"University Clermont Auvergne, LIMOS, CNRS UMR 6158, 63178 Aubi\u00e8re, France. E-mails:\u00a0,\u00a0"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2021,12,21]]},"reference":[{"key":"ref001","unstructured":"T.D.\u00a0Ahle, K out of N encryption, 2012, https:\/\/crypto.stackexchange.com\/questions\/2783\/k-out-of-n-encryption, accessed 08\/01\/2021."},{"key":"ref002","unstructured":"A.V.\u00a0Aho and J.E.\u00a0Hopcroft, The Design and Analysis of Computer Algorithms, 1st edn, Addison-Wesley Longman Publishing Co., Inc., USA, 1974. ISBN 0201000296."},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"A.\u00a0Beimel, T.\u00a0Tassa and E.\u00a0Weinreb, Characterizing ideal weighted threshold secret sharing, in: Proceedings of the Second International Conference on Theory of Cryptography, TCC\u201905, Springer-Verlag, Berlin, Heidelberg, 2005, pp.\u00a0600\u2013619. ISBN 3540245731.","DOI":"10.1007\/978-3-540-30576-7_32"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"J.\u00a0Benaloh and J.\u00a0Leichter, Generalized secret sharing and monotone functions, in: CRYPTO\u201988, S.\u00a0Goldwasser, ed. Lecture Notes in Computer Science, New York, NY, 1990, pp.\u00a027\u201335. ISBN 978-0-387-34799-8.","DOI":"10.1007\/0-387-34799-2_3"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00108-3"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-1809.1939.tb02219.x"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.04.005"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"B.\u00a0Chor, S.\u00a0Goldwasser, S.\u00a0Micali and B.\u00a0Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults, in: Proceedings of the 26th Annual Symposium on Foundations of Computer Science, SFCS\u201985, USA, 1985, pp.\u00a0383\u2013395. ISBN 0818608444.","DOI":"10.1109\/SFCS.1985.64"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"C.J.\u00a0Colbourn, A.\u00a0Rosa et al., Triple Systems, Oxford University Press, 1999.","DOI":"10.1093\/oso\/9780198535768.001.0001"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-5906-5_330"},{"key":"ref011","unstructured":"Everlock, System SLX2, 2019, https:\/\/vimeo.com\/180052349."},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2182034"},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"P.\u00a0Feldman, A practical scheme for non-interactive verifiable secret sharing, in: Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS\u201987, IEEE Computer Society, USA, 1987, pp.\u00a0427\u2013438. ISBN 0818608072.","DOI":"10.1109\/SFCS.1987.4"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-005-6342-0"},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(02)00258-3"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1007\/BF02620229"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1962.1057714"},{"key":"ref018","unstructured":"D.E.\u00a0Knuth, The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical Algorithms, Addison-Wesley Longman Publishing Co., Inc., USA, 1997. ISBN 0201896842."},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.08.031"},{"key":"ref020","unstructured":"C.L.\u00a0Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New York, 1968, p.\u00a0393. ISBN 0070381240."},{"key":"ref021","unstructured":"R.\u00a0McNeil, Multiple Padlock Latch, 2003."},{"key":"ref022","unstructured":"R.\u00a0McNeil, Multiple padlock lock system, 2008."},{"key":"ref023","unstructured":"R.\u00a0McNeil, Multiple padlock locking device, 2014."},{"key":"ref024","unstructured":"R.\u00a0McNeil, Multiple padlock locking system, 2015."},{"key":"ref025","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor and A.\u00a0Shamir, Visual cryptography, in: EUROCRYPT\u201994, Workshop on the Theory and Application of Cryptographic Techniques, 1994, pp.\u00a01\u201312.","DOI":"10.1007\/BFb0053419"},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor and A.\u00a0Shamir, Visual cryptography II: Improving the contrast via the cover base, in: Security Protocols, International Workshop, Cambridge, United Kingdom, April 10\u201312, 1996, pp.\u00a0197\u2013202.","DOI":"10.1007\/3-540-62494-5_18"},{"key":"ref027","unstructured":"OEIS, The On-Line Encyclopedia of Integer Sequences, 2020, https:\/\/oeis.org\/A182079."},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"B.\u00a0Schoenmakers, A simple publicly verifiable secret sharing scheme and its application to electronic voting, in: CRYPTO\u201999, Springer-Verlag, 1999, pp.\u00a0148\u2013164.","DOI":"10.1007\/3-540-48405-1_10"},{"key":"ref029","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"ref031","doi-asserted-by":"publisher","DOI":"10.1007\/BF01171114"},{"key":"ref032","unstructured":"Tayhope, Multi-Locking Systems, 2020, http:\/\/sancy.univ-bpclermont.fr\/~lafourcade\/VIDEOS\/secu\/tayhope_voiceover.mp4."},{"key":"ref033","unstructured":"N.I.S.T.\u00a0Threshold, Schemes for Cryptographic Primitives: Challenges and Opportunities in Standardization and Validation of Threshold Cryptography,\n                      Federal Register\n                      69\n                      (8214) (2019), https:\/\/csrc.nist.gov\/Projects\/threshold-cryptography."},{"key":"ref034","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008280705142"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-210065","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-210065","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-210065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:39Z","timestamp":1777495539000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-210065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,21]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,5]]}},"alternative-id":["10.3233\/JCS-210065"],"URL":"https:\/\/doi.org\/10.3233\/jcs-210065","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,21]]}}}