The Crypto conference is an international conference on all aspects of cryptology. The Crypto conference has been held every year since 1981 in Santa Barbara, California, USA.
As blockchains like Ethereum continue to grow, clients with limited resources can no longer store the entire chain.
Light nodes that want to use the blockchain, without verifying that it is in a good state overall, can just download the block headers without the corresponding block contents.
As those light nodes may eventually need some of the block contents, they would like to ensure that they are in principle available.
Data availability sampling, introduced by Bassam et al., is a process that allows light nodes to check the availability of data without download it.
In a recent effort, Hall-Andersen, Simkin, and Wagner have introduced formal definitions and analyzed several constructions.
While their work thoroughly lays the formal foundations for data availability sampling, the constructions are either prohibitively expensive, use a trusted setup, or have a download complexity for light clients scales with a square root of the data size.
In this work, we make a significant step forward by proposing an efficient data availability sampling scheme without a trusted setup and only polylogarithmic overhead.
To this end, we find a novel connection with interactive oracle proofs of proximity (IOPPs).
Specifically, we prove that any IOPP meeting an additional consistency criterion can be turned into an erasure code commitment, and then, leveraging a compiler due to Hall-Andersen, Simkin, and Wagner, into a data availability sampling scheme.
This new connection enables data availability to benefit from future results on IOPPs.
We then show that the widely used FRI IOPP satisfies our consistency criterion and demonstrate that the resulting data availability sampling scheme outperforms the state-of-the-art asymptotically and concretely in multiple parameters.
In this paper, we introduce the subfield bilinear collision problem and use it to construct an identification protocol and a signature scheme. This construction is based on the MPC-in-the-head paradigm and uses the Fiat-Shamir transformation to obtain a signature.