Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR17-076 | 31st October 2017 04:57

Conditional Disclosure of Secrets via Non-Linear Reconstruction

RSS-Feed




Revision #2
Authors: Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee
Accepted on: 31st October 2017 04:57
Downloads: 610
Keywords: 


Abstract:

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 $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve $o(N^{1/2})$ communication: the
first achieves $O(N^{1/3})$ communication and the second achieves
sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$
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 $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.

Prior to this work, the best protocols for both primitives required
communication complexity $\tilde{O}(N^{1/2})$.
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(N^{1/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.



Changes to previous version:

The title


Revision #1 to TR17-076 | 1st May 2017 22:20

New Protocols for Conditional Disclosure of Secrets (and More)





Revision #1
Authors: Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee
Accepted on: 1st May 2017 22:20
Downloads: 613
Keywords: 


Abstract:

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 $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$, we present two protocols that achieve $o(N^{1/2})$ communication: the first achieves $O(N^{1/3})$ communication and the second achieves sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$ 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 $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.

Prior to this work, the best protocols for both primitives required communication complexity $\tilde{O}(N^{1/2})$. 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(N^{1/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.


Paper:

TR17-076 | 21st April 2017 00:04

New Protocols for Conditional Disclosure of Secrets (and More)





TR17-076
Authors: Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee
Publication: 30th April 2017 13:01
Downloads: 964
Keywords: 


Abstract:

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 $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve $o(N^{1/2})$ communication: the
first achieves $O(N^{1/3})$ communication and the second achieves
sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$
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 $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.

Prior to this work, the best protocols for both primitives required
communication complexity $\tilde{O}(N^{1/2})$.
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(N^{1/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.



ISSN 1433-8092 | Imprint