搜索结果: 1-15 共查到“Communication Complexity”相关记录29条 . 查询时间(0.156 秒)
Transparent Polynomial Commitment Scheme with Polylogarithmic Communication Complexity
polynomial commitments zero-knowledge proofs proximity testing
<
2019/9/16
We introduce novel efficient and transparent construction of the polynomial commitment scheme. A polynomial commitment scheme allows one side (the prover) to commit to a polynomial of predefined degre...
The Communication Complexity of Threshold Private Set Intersection
Communication Complexity Private Set Intersection
<
2019/3/1
Threshold private set intersection enables Alice and Bob who hold sets AA and BB of size nn to compute the intersection A∩BA∩B if the sets do not differ by more than some threshold parameter tt. In th...
Adaptively Secure MPC with Sublinear Communication Complexity
secure multiparty computation adaptive security sublinear communication
<
2018/12/3
A central challenge in the study of MPC is to balance between security guarantees, hardness assumptions, and resources required for the protocol. In this work, we study the cost of tolerating adaptive...
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
information theoretic cryptography communication complexity
<
2018/12/3
In the Conditional Disclosure of Secrets (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold nn-bit inputs xx and yy respectively, wish to release a common secret zz to...
A Note on the Communication Complexity of Multiparty Computation in the Correlated Randomness Model
multiparty computation correlated randomness model information- theoretic security
<
2018/5/22
Secure multiparty computation (MPC) addresses the challenge of evaluating functions on secret inputs without compromising their privacy. An central question in multiparty communication is to understan...
The Communication Complexity of Private Simultaneous Messages, Revisited
Secure Computation Information Theoretic Security
<
2018/2/9
We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields...
How to Meet Big Data When Private Set Intersection Realizes Constatnt Communication Complexity
cryptographic protocols secure tow-party protocol
<
2017/1/3
Electronic information is increasingly often shared among unreliable entities. In this context, one interesting problem involves two parties that secretly want to determine intersection of their respe...
Position-Based Cryptography and Multiparty Communication Complexity
Position based cryptography construct secure
<
2016/6/2
Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal,
Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes
in which the identit...
On the Communication Complexity of Secure Function Evaluation with Long Output
Secure Function Evaluation Communication Complexity Indistinguishability Obfuscation
<
2016/1/7
We study the communication complexity of secure function evaluation (SFE). Consider
a setting where Alice has a short input xA, Bob has an input xB and we want Bob to learn
some function y = f(xA, x...
On the Communication Complexity of Secure Computation
Secure Multi-party Computation Information Theory Communication Complexity
<
2015/12/31
Information theoretically secure multi-party computation (MPC)
is a central primitive of modern cryptography. However, relatively little
is known about the communication complexity of this primitive...
Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption.
communication complexity conditional disclosure of secrets attribute-based encryption
<
2015/12/29
We initiate a systematic treatment of the communication complexity of conditional disclosure of
secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respec...
Average and Randomized Communication Complexity
Average Randomized Communication Complexity
<
2015/8/14
The communication complexity of a two-variable function f(x, y) is the number of information bits two communicators need to exchange to compute f when, initially, each knows only one of the variables....
Communication Complexity of Computing the Hamming Distance
communication complexity randomized protocol Hamming distance combinatorial
<
2015/8/14
Let x, y {0, 1} n. Persons A and B are given x and y respectively. They communicate in order that both find the Hamming Distance d(x,y). Three communication models, viz, deterministic, e-error and e-r...
COMMUNICATION COMPLEXITY OF COMPUTING THE HAMMING DISTANCE
communication complexity randomized protocol Hamming distance combinatorial extremal problem
<
2015/8/12
Let x, y {0, 1} n. Persons A and B are given x and y respectively. They communicate in order that both find the Hamming Distance d(x,y). Three communication models, viz, deterministic, e-error and e-r...
Communication Complexity and Coordination by Authority
Authority Complexity and Coordination
<
2015/7/31
We prove that the simplest communication allowing two players to coordinate on a course
of action is authority (letting one player choose an action). We also consider the case where
each player poss...