Interactive hashing, introduced by Naor et al. [NOVY98], plays
an important role in many cryptographic protocols. In particular, it
is a major component in all known constructions of
statistically-hiding commitment schemes and of zero-knowledge
arguments based on general one-way permutations and on one-way
functions. Interactive hashing with respect to a ...
more >>>
In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>>
A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>
In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83],
the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate ...
more >>>
We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective random sources for which it is known that extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks $\mathbf{X} = (\mathbf{X}_1, \dots, \mathbf{X}_{\ell})\sim (\{0, 1\}^{n})^{\ell}$, where ... more >>>