Page
%P
-
Chapter and Conference Paper
Plumo: An Ultralight Blockchain Client
Syncing the latest state of a blockchain can be a resource-intensive task, driving (especially mobile) end users towards centralized services offering instant access. To expand full decentralized access to any...
-
Chapter and Conference Paper
Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments
Polynomial commitment schemes (PCS) have recently been in the spotlight for their key role in building SNARKs. A PCS provides the ability to commit to a polynomial over a finite field and prove its evaluation ...
-
Article
Twenty (Short) Questions
A basic combinatorial interpretation of Shannon’s entropy function is via the “20 questions” game. This cooperative game is played by two players, Alice and Bob: Alice picks a distribution π over the numbers {1, ...
-
Chapter and Conference Paper
A Multi-party Protocol for Constructing the Public Parameters of the Pinocchio zk-SNARK
Recent efficient constructions of zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs), require a setup phase in which a common-reference string (CRS) with a certain structure is generate...
-
Chapter and Conference Paper
Almost Optimal Cover-Free Families
Roughly speaking, an (n, (r, s))-Cover Free Family (CFF) is a small set of n-bit strings such that: “in any \(d:=r+s\) ...
-
Chapter and Conference Paper
Zero Knowledge Protocols from Succinct Constraint Detection
We study the problem of constructing proof systems that achieve both soundness and zero knowledge unconditionally (without relying on intractability assumptions). Known techniques for this goal are primarily comb...
-
Chapter and Conference Paper
Computational Integrity with a Public Random String from Quasi-Linear PCPs
A party executing a computation on behalf of others may benefit from misreporting its output. Cryptographic protocols that detect this can facilitate decentralized systems with stringent computational integrit...
-
Chapter and Conference Paper
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson [33] proved that this assumption ...
-
Chapter and Conference Paper
Cryptocurrencies Without Proof of Work
We study decentralized cryptocurrency protocols in which the participants do not deplete physical scarce resources. Such protocols commonly rely on Proof of Stake, i.e., on mechanisms that extend voting power to ...
-
Chapter and Conference Paper
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
In this paper we consider generalized versions of four well-studied problems in parameterized complexity and exact exponential time algorithms: k-Path, Set Packing, Multilinear Monomial Testing and Hamiltonian Pa...
-
Chapter and Conference Paper
On r-Simple k-Path
An r-simple k-path is a path in the graph of length k that passes through each vertex at most r times. The r-SIMPLE k-PATH problem, given a graph G as input, asks whether there exists an r-simple k-path in G. We ...
-
Chapter and Conference Paper
The \(k\) -Distinct Language: Parameterized Automata Constructions
In this paper, we pioneer a study of parameterized automata constructions for languages relevant to the design of parameterized algorithms. We focus on the ...
-
Chapter and Conference Paper
Non-Interactive Secure Multiparty Computation
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function f(x1,…,x n ) is specified by a joint probability dist...
-
Chapter and Conference Paper
Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
A polynomial source of randomness over \(\mathbb F_q^n\) is a random variable X = f(Z) where f is a polynomial map and
-
Chapter and Conference Paper
Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors
Kuznetsov and Tsybakov [11] considered the problem of storing information in a memory where some cells are ‘stuck’ at certain values. More precisely, For 0 < r,p < 1 we want to store a string z ∈ {0,1} ...
-
Book
-
Article
Extractors And Rank Extractors For Polynomial Sources
In this paper we construct explicit deterministic extractors from polynomial sources, which are distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous...
-
Article
Deterministic extractors for affine sources over large fields
An (n,k)-affine source over a finite field \( \mathbb{F} \) is a random variable X = (X 1,......
-
Chapter and Conference Paper
Increasing the Output Length of Zero-Error Dispersers
Let \(\cal C\) be a class of probability distributions over a finite set Ω. A function
