research-article

On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate

Authors:

Benny Applebaum,

Barak ArkisAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 12, Issue 4

Article No.: 24, Pages 1 - 21

https://doi.org/10.1145/3417756

Published: 30 September 2020 Publication History

Abstract

Consider the following secret-sharing problem: A file s should be distributed between n servers such that (d-1)-subsets cannot recover the file, (d+1)-subsets can recover the file, and d-subsets should be able to recover s if and only if they appear in some pre-defined list L. The goal is to minimize the information ratio—that is, the number of bits stored on a server per each bit of the secret.

We show that for any constant d and any pre-defined list L, if the file is sufficiently long (exponential in n^d), the problem can be solved with a constant asymptotic information ratio of c_d that does not grow with the number of servers n. This result is based on a new construction of d-party conditional disclosure of secrets for arbitrary predicates over an n-size domain in which each party communicates at most four bits per secret bit.

In both settings, previous results achieved a non-constant information ratio that grows asymptotically with n, even for the simpler special case of d = 2. Moreover, our constructions yield the first example of an access structure whose amortized information ratio is constant, whereas its best-known non-amortized information ratio is sub-exponential, thus providing a unique evidence for the potential power of amortization in the context of secret sharing.

Our main result applies to exponentially long secrets, and so it should be mainly viewed as a barrier against amortizable lower-bound techniques. We also show that in some natural simple cases (e.g., low-degree predicates), amortization kicks in even for quasi-polynomially long secrets. Finally, we prove some limited lower bounds and point out some limitations of existing lower-bound techniques.

References

[1]

William Aiello, Yuval Ishai, and Omer Reingold. 2001. Priced oblivious transfer: How to sell digital goods. In Advances in Cryptology—EUROCRYPT 2001. Lecture Notes in Computer Science, Vol. 20145. Springer, 119--135.

[2]

Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan. 2017. Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations. In Advances in Cryptology—CRYPTO 2017. Lecture Notes in Computer Science, Vol. 10401. Springer, 727--757.

[3]

Benny Applebaum, Amos Beimel, Oriol Farràs, Oded Nir, and Naty Peter. 2019. Secret-sharing schemes for general and uniform access structures. In Advances in Cryptology—EUROCRYPT 2019. Lecture Notes in Computer Science, Vol. 11478. Springer, 441--471.

Digital Library

[4]

Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. 2020. The communication complexity of private simultaneous messages, revisited. Journal of Cryptology 33, 3 (2020), 917--953.

[5]

Amos Beimel. 2011. Secret-sharing schemes: A survey. In Coding and Cryptology. Lecture Notes in Computer Science, Vol. 6639. Springer, 11--46.

[6]

Amos Beimel, Oriol Farràs, and Yuval Mintz. 2016. Secret-sharing schemes for very dense graphs. Journal of Cryptology 29, 2 (2016), 336--362.

Digital Library

[7]

Amos Beimel, Oriol Farràs, Yuval Mintz, and Naty Peter. 2017. Linear secret-sharing schemes for forbidden graph access structures. In Theory of Cryptography. Lecture Notes in Computer Science, Vol. 10678. Springer, 394--423.

[8]

Amos Beimel and Yuval Ishai. 2001. On the power of nonlinear secrect-sharing. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity. IEEE, Los Alamitos, CA, 188--202.

Digital Library

[9]

Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. 2014. On the cryptographic complexity of the worst functions. In Theory of Cryptography. Lecture Notes in Computer Science, Vol. 8349. Springer, 317--342.

[10]

Amos Beimel, Eyal Kushilevitz, and Pnina Nissim. 2018. The complexity of multiparty PSM protocols and related models. In Advances in Cryptology—EUROCRYPT 2018. Lecture Notes in Computer Science, Vol. 10821. Springer, 287--318.

[11]

Amos Beimel and Ilan Orlov. 2011. Secret sharing and non-Shannon information inequalities. IEEE Transactions on Information Theory 57, 9 (2011), 5634--5649.

Digital Library

[12]

Josh Cohen Benaloh and Jerry Leichter. 1988. Generalized secret sharing and monotone functions. In Advances in Cryptology—CRYPTO 1988. Lecture Notes in Computer Science, Vol. 403. Springer, 27--35.

[13]

G. R. Blakley. 1979. Safeguarding cryptographic keys. In Proceedings of the AFIPS 1979 National Computer Conference. 313--317.

[14]

Andrej Bogdanov, Siyao Guo, and Ilan Komargodski. 2016. Threshold secret sharing requires a linear size alphabet. In Theory of Cryptography. Lecture Notes in Computer Science, Vol. 9986. Springer, 471--484.

[15]

Renato M. Capocelli, Alfredo De Santis, Luisa Gargano, and Ugo Vaccaro. 1993. On the size of shares for secret sharing schemes. Journal of Cryptology 6, 3 (1993), 157--167.

Digital Library

[16]

Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. 1998. Private information retrieval. Journal of the ACM 45, 6 (1998), 965--981.

Digital Library

[17]

László Csirmaz. 1997. The size of a share must be large. Journal of Cryptology 10, 4 (1997), 223--231.

Digital Library

[18]

Romain Gay, Iordanis Kerenidis, and Hoeteck Wee. 2015. Communication complexity of conditional disclosure of secrets and attribute-based encryption. In Advances in Cryptology—CRYPTO 2015. Lecture Notes in Computer Science, Vol. 9216. Springer, 485--502.

[19]

Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. 2000. Protecting data privacy in private information retrieval schemes. Journal of Computer and System Sciences 60, 3 (2000), 592--629.

Digital Library

[20]

Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. 2006. Attribute-based encryption for fine-grained access control of encrypted data. In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS’06). ACM, New York, NY, 89--98.

Digital Library

[21]

M. Ito, A. Saito, and T. Nishizeki. 1987. Secret sharing scheme realizing general access structure. In Proceedings of the 1987 IEEE GLOBECOM Conference. IEEE, Los Alamitos, CA, 99--102.

[22]

Mauricio Karchmer and Avi Wigderson. 1993. On span programs. In Proceedings of the 8th Annual Structure in Complexity Theory Conference. IEEE, Los Alamitos, CA, 102--111.

[23]

Ehud D. Karnin, J. W. Greene, and Martin E. Hellman. 1983. On secret sharing systems. IEEE Transactions on Information Theory 29, 1 (1983), 35--41.

Digital Library

[24]

Jonathan Katz and Hovav Shacham (Eds.). 2017. Advances in Cryptology—CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20--24, 2017, Proceedings, Part I. Lecture Notes in Computer Science, Vol. 10401. Springer.

[25]

Tianren Liu and Vinod Vaikuntanathan. 2018. Breaking the circuit-size barrier in secret sharing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18). https://eprint.iacr.org/2018/333.

Digital Library

[26]

Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. 2017. Conditional disclosure of secrets via non-linear reconstruction. In Advances in Cryptology—CRYPTO 2017. Lecture Notes in Computer Science, Vol. 10401. Springer, 758--790.

[27]

Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. 2018. Towards breaking the exponential barrier for general secret sharing. In Advances in Cryptology—EUROCRYPT 2018. Lecture Notes in Computer Science, Vol. 10820. Springer, 567--596.

[28]

Yuval Mintz. 2012. Information Ratios of Graph Secret-Sharing Schemes. Master’s Thesis. Department of Computer Science, Ben Gurion University.

[29]

Sebastià Martín Molleví, Carles Padró, and An Yang. 2016. Secret sharing, rank inequalities, and information inequalities. IEEE Transactions on Information Theory 62, 1 (2016), 599--609.

Digital Library

[30]

Amit Sahai and Brent Waters. 2005. Fuzzy identity-based encryption. In Advances in Cryptology—EUROCRYPT 2005. Lecture Notes in Computer Science, Vol. 3494. Springer, 457--473.

Digital Library

[31]

Adi Shamir. 1979. How to share a secret. Communications of the ACM 22, 11 (1979), 612--613.

Digital Library

[32]

Douglas R. Stinson. 1994. Decomposition constructions for secret-sharing schemes. IEEE Transactions on Information Theory 40, 1 (1994), 118--125.

Digital Library

[33]

Hung-Min Sun and Shiuh-Pyng Shieh. 1997. Secret sharing in graph-based prohibited structures. In Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’97). IEEE, Los Alamitos, CA, 718--724. http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4979.

[34]

Vinod Vaikuntanathan and Prashant Nalini Vasudevan. 2015. Secret sharing and statistical zero knowledge. In Advances in Cryptology—ASIACRYPT 2015. Lecture Notes in Computer Science, Vol. 9452. Springer, 656--680.

Digital Library

Cited By

Allerstorfer RBuhrman HMay ASpeelman FVerduyn Lunel P(2024)Relating non-local quantum computation to information theoretic cryptographyQuantum10.22331/q-2024-06-27-13878(1387)Online publication date: 27-Jun-2024
https://doi.org/10.22331/q-2024-06-27-1387
Hajiabadi MKhazaei SVahdani B(2024)Randomness Recoverable Secret Sharing SchemesJournal of Cryptology10.1007/s00145-024-09515-437:4Online publication date: 20-Aug-2024
https://dl.acm.org/doi/10.1007/s00145-024-09515-4
Beimel AOthman HPeter N(2023)Quadratic Secret Sharing and Conditional Disclosure of SecretsIEEE Transactions on Information Theory10.1109/TIT.2023.329658869:11(7295-7316)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3296588
Show More Cited By

Index Terms

On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate
1. Security and privacy
  1. Cryptography
    1. Information-theoretic techniques
2. Theory of computation
  1. Computational complexity and cryptography
    1. Communication complexity

Recommendations

Fair secret reconstruction in (t, n) secret sharing

In Shamir's (t, n) threshold secret sharing scheme, one secret s is divided into n shares by a dealer and all shares are shared among n shareholders, such that knowing t or more than t shares can reconstruct this secret; but knowing fewer than t shares ...
Strong (n,t,n) verifiable secret sharing scheme

A (t,n) secret sharing divides a secret into n shares in such a way that any t or more than t shares can reconstruct the secret; but fewer than t shares cannot reconstruct the secret. In this paper, we extend the idea of a (t,n) secret sharing scheme ...
Secret sharing with secure secret reconstruction
Abstract
Threshold secret sharing is a fundamental building block in information security to provide secrecy and robustness services for various cryptographic protocols. According to the definition of (t, n) threshold secret sharing, the secret ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 12, Issue 4

December 2020

156 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/3427631

Editor:
Ryan O'Donnell
Carnegie Mellon University, USA

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 2020

Accepted: 01 August 2020

Revised: 01 July 2020

Received: 01 June 2019

Published in TOCT Volume 12, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

H2020 European Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
107
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Allerstorfer RBuhrman HMay ASpeelman FVerduyn Lunel P(2024)Relating non-local quantum computation to information theoretic cryptographyQuantum10.22331/q-2024-06-27-13878(1387)Online publication date: 27-Jun-2024
https://doi.org/10.22331/q-2024-06-27-1387
Hajiabadi MKhazaei SVahdani B(2024)Randomness Recoverable Secret Sharing SchemesJournal of Cryptology10.1007/s00145-024-09515-437:4Online publication date: 20-Aug-2024
https://dl.acm.org/doi/10.1007/s00145-024-09515-4
Beimel AOthman HPeter N(2023)Quadratic Secret Sharing and Conditional Disclosure of SecretsIEEE Transactions on Information Theory10.1109/TIT.2023.329658869:11(7295-7316)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3296588
Robere RZuiddam J(2022)Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00079(759-769)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00079
Jafari AKhazaei S(2021)On Abelian and Homomorphic Secret Sharing SchemesJournal of Cryptology10.1007/s00145-021-09410-234:4Online publication date: 22-Sep-2021
https://dl.acm.org/doi/10.1007/s00145-021-09410-2
Beimel AOthman HPeter N(2021)Quadratic Secret Sharing and Conditional Disclosure of SecretsAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84252-9_25(748-778)Online publication date: 11-Aug-2021
https://doi.org/10.1007/978-3-030-84252-9_25

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents