Conditional Disclosure of Secrets via Non-linear Reconstruction
© International Association for Cryptologic Research 2017. We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. – For general predicates (Formula Presented.),...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137871 |
| _version_ | 1811088917434204160 |
|---|---|
| author | Liu, Tianren Vaikuntanathan, Vinod Wee, Hoeteck |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Liu, Tianren Vaikuntanathan, Vinod Wee, Hoeteck |
| author_sort | Liu, Tianren |
| collection | MIT |
| description | © International Association for Cryptologic Research 2017. We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. – For general predicates (Formula Presented.), we present two protocols that achieve o(N1/2) communication: the first achieves O(N1/3) communication and the second achieves sub-polynomial (Formula Presented.) communication. – As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on N vertices, there is a secret-sharing scheme for N parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in G are connected, and where each party gets a share of size (Formula Presented.). Prior to this work, the best protocols for both primitives required communication complexity (Formula Presented.). Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called “linear reconstruction”. This is the first work to break this O(N1/2) “linear reconstruction” barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval. We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials. |
| first_indexed | 2024-09-23T14:09:59Z |
| format | Article |
| id | mit-1721.1/137871 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:09:59Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1378712023-06-21T18:41:36Z Conditional Disclosure of Secrets via Non-linear Reconstruction Liu, Tianren Vaikuntanathan, Vinod Wee, Hoeteck Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © International Association for Cryptologic Research 2017. We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. – For general predicates (Formula Presented.), we present two protocols that achieve o(N1/2) communication: the first achieves O(N1/3) communication and the second achieves sub-polynomial (Formula Presented.) communication. – As a corollary, we obtain improved share complexity for forbidden graph access structures. Namely, for every graph on N vertices, there is a secret-sharing scheme for N parties in which each pair of parties can reconstruct the secret if and only if the corresponding vertices in G are connected, and where each party gets a share of size (Formula Presented.). Prior to this work, the best protocols for both primitives required communication complexity (Formula Presented.). Indeed, this is essentially the best that all prior techniques could hope to achieve as they were limited to so-called “linear reconstruction”. This is the first work to break this O(N1/2) “linear reconstruction” barrier in settings related to secret sharing. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval. We further extend our results to the setting of private simultaneous messages (PSM), and provide applications such as an improved attribute-based encryption (ABE) for quadratic polynomials. 2021-11-09T14:03:34Z 2021-11-09T14:03:34Z 2017 2019-07-09T16:10:28Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137871 Liu, Tianren, Vaikuntanathan, Vinod and Wee, Hoeteck. 2017. "Conditional Disclosure of Secrets via Non-linear Reconstruction." en 10.1007/978-3-319-63688-7_25 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing Other repository |
| spellingShingle | Liu, Tianren Vaikuntanathan, Vinod Wee, Hoeteck Conditional Disclosure of Secrets via Non-linear Reconstruction |
| title | Conditional Disclosure of Secrets via Non-linear Reconstruction |
| title_full | Conditional Disclosure of Secrets via Non-linear Reconstruction |
| title_fullStr | Conditional Disclosure of Secrets via Non-linear Reconstruction |
| title_full_unstemmed | Conditional Disclosure of Secrets via Non-linear Reconstruction |
| title_short | Conditional Disclosure of Secrets via Non-linear Reconstruction |
| title_sort | conditional disclosure of secrets via non linear reconstruction |
| url | https://hdl.handle.net/1721.1/137871 |
| work_keys_str_mv | AT liutianren conditionaldisclosureofsecretsvianonlinearreconstruction AT vaikuntanathanvinod conditionaldisclosureofsecretsvianonlinearreconstruction AT weehoeteck conditionaldisclosureofsecretsvianonlinearreconstruction |