Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with round complexity:
TR06-093 | 27th July 2006
Takeshi Koshiba, Yoshiharu Seri

Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>

TR18-150 | 27th August 2018
Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

TR20-076 | 17th May 2020
Benny Applebaum, Eliran Kachlon, Arpita Patra

The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of ... more >>>

ISSN 1433-8092 | Imprint