Elette Boyle

Communication Lower Bounds for Cryptographic Broadcast Protocols

2023 · arXiv (Cornell University)

Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication …

Memory Checking Requires Logarithmic Overhead

2024

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.