Breaking barriers in secret sharing
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/124114 |
| _version_ | 1826204895335677952 |
|---|---|
| author | Liu, Tianren,Ph. D.Massachusetts Institute of Technology. |
| author2 | Vinod Vaikuntanathan. |
| author_facet | Vinod Vaikuntanathan. Liu, Tianren,Ph. D.Massachusetts Institute of Technology. |
| author_sort | Liu, Tianren,Ph. D.Massachusetts Institute of Technology. |
| collection | MIT |
| description | This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. |
| first_indexed | 2024-09-23T13:02:44Z |
| format | Thesis |
| id | mit-1721.1/124114 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:02:44Z |
| publishDate | 2020 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1241142020-03-10T03:16:09Z Breaking barriers in secret sharing Liu, Tianren,Ph. D.Massachusetts Institute of Technology. Vinod Vaikuntanathan. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 50-53). In this thesis, we study secret sharing schemes for general (non-threshold) access functions. In a secret sharing scheme for n parties associated to a monotone function [mathematical formula], a dealer distributes shares of a secret among n parties. Any subset of parties [mathematical formula] can jointly reconstruct the secret if F(T) = 1, and should have no information about the secret if F(T) = 0. One of the major long-standing questions in information-theoretic cryptography is to determine the minimum size of the shares in a secret-sharing scheme for an access function F. There is an exponential gap between lower and upper bounds for share size: the best known scheme for general monotone functions has shares of size 2[superscript n-o(n)], while the best lower bound is n² / log(n). In this thesis, we improve this more-than-30-year-old upper bound by construct- ing a secret sharing scheme for any access function with shares of size 2[superscript 0.994n] and a linear secret sharing scheme for any access function with shares of size 2[superscript 0.994n]. As a contribution of independent interest, we also construct a secret sharing scheme with shares of size [mathematical formula] for a family of [mathematical formula] monotone access functions, out of a total of [mathematical formula] of them. As an intermediate result, we construct the first conditional disclosure of secrets (CDS) with sub-exponential communication complexity. CDS is a variant of secret sharing, in which a group of parties want to disclose a secret to a referee the parties' respective inputs satisfy some predicate. The key conceptual contribution of this thesis is a novel connection between secret sharing and CDS, and the notion of (2-server, information-theoretic) private information retrieval. by Tianren Liu. Ph. D. Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2020-03-09T18:58:37Z 2020-03-09T18:58:37Z 2019 2019 Thesis https://hdl.handle.net/1721.1/124114 1142177906 eng MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. http://dspace.mit.edu/handle/1721.1/7582 53 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Liu, Tianren,Ph. D.Massachusetts Institute of Technology. Breaking barriers in secret sharing |
| title | Breaking barriers in secret sharing |
| title_full | Breaking barriers in secret sharing |
| title_fullStr | Breaking barriers in secret sharing |
| title_full_unstemmed | Breaking barriers in secret sharing |
| title_short | Breaking barriers in secret sharing |
| title_sort | breaking barriers in secret sharing |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/124114 |
| work_keys_str_mv | AT liutianrenphdmassachusettsinstituteoftechnology breakingbarriersinsecretsharing |