All reports by Author Ariel Gabizon:

__
TR16-156
| 12th October 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

__
TR16-149
| 23rd September 2016
__

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev#### A security analysis of Probabilistically Checkable Proofs

Comments: 1

__
TR16-073
| 7th May 2016
__

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev#### Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

Revisions: 1
,
Comments: 1

__
TR16-046
| 23rd March 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck

Revisions: 2

__
TR16-001
| 9th January 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza#### Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Revisions: 1

__
TR14-004
| 30th November 2013
__

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty#### On $r$-Simple $k$-Path

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

__
TR11-129
| 22nd September 2011
__

Eli Ben-Sasson, Ariel Gabizon#### Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

__
TR09-063
| 29th July 2009
__

Matt DeVos, Ariel Gabizon#### Simple Affine Extractors using Dimension Expansion

Revisions: 2

__
TR07-056
| 10th July 2007
__

Zeev Dvir, Ariel Gabizon, Avi Wigderson#### Extractors and Rank Extractors for Polynomial Sources

__
TR05-109
| 28th September 2005
__

Ariel Gabizon, Ran Raz, Ronen Shaltiel#### Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

__
TR05-108
| 28th September 2005
__

Ariel Gabizon, Ran Raz#### Deterministic Extractors for Affine Sources over Large Fields

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.

PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ...
more >>>

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

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 (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

An $r$-simple $k$-path is a {path} in the graph of length $k$ that

passes through each vertex at most $r$ times. The \simpath{r}{k}

problem, given a graph $G$ as input, asks whether there exists an

$r$-simple $k$-path in $G$. We first show that this problem is

NP-Complete. We then show ...
more >>>

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

Eli Ben-Sasson, Ariel Gabizon

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>

Matt DeVos, Ariel Gabizon

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ...
more >>>

Zeev Dvir, Ariel Gabizon, Avi Wigderson

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Ariel Gabizon, Ran Raz, Ronen Shaltiel

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that

there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly

distributed and independent of each other, and the remaining $n-k$ variables

are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n

\ar \B^m$ which on ...
more >>>

Ariel Gabizon, Ran Raz

An $(n,k)$-affine source over a finite field $F$ is a random

variable $X=(X_1,...,X_n) \in F^n$, which is uniformly

distributed over an (unknown) $k$-dimensional affine subspace of $

F^n$. We show how to (deterministically) extract practically all

the randomness from affine sources, for any field of size larger

than $n^c$ (where ...
more >>>