 Publication Date:
 NSFPAR ID:
 10253441
 Journal Name:
 Financial Cryptography and Data Security
 Sponsoring Org:
 National Science Foundation
More Like this

Raz, Ran (Ed.)We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the wellstudied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proofcomplexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proofmore »

null (Ed.)Zeroknowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention, because such protocols can easily prove very large computation with a small memory requirement. Such ZK protocol only needs O(M) memory for both parties, where M is the memory required to verify the statement in the clear. In this paper, we propose several new ZK protocols in this setting, which improve the concrete efficiency and, at the same time, enable sublinear amortized communication for circuits with some notion of relaxed uniformity. 1. In the circuitbased model, where the computation is represented as a circuit over a field, our ZK protocol achieves a communication complexity of 1 field element per nonlinear gate for any field size while keeping the computation very cheap. We implemented our protocol, which shows extremely high efficiency and affordability. Compared to the previous bestknown implementation, we achieve 6×–7× improvement in computation and 3×– 7× improvement in communication. When running on introlevel AWS instances, our protocol only needs one US dollar to prove one trillion AND gates (or 2.5 US dollars for one trillion multiplication gates over a 61bit field). 2. In the setting where part of the computation can be represented as amore »

Amir Hashemi (Ed.)The proofofwork interactive protocol by Shafi Goldwasser, Yael T. Kalai and Guy N. Rothblum (GKR) [STOC 2008, JACM 2015] certifies the execution of an algorithm via the evaluation of a corresponding boolean or arithmetic circuit whose structure is known to the verifier by circuit wiring algorithms that define the uniformity of the circuit. Here we study protocols whose prover time and spacecomplexities are within a polylogarithmic factor of the time and spacecomplexity of the algorithm; we call those protocols `prover efficient.' We show that the uniformity assumptions can be relaxed from LOGSPACE to polynomialtime in the bitlengths of the labels which enumerate the nodes in the circuit. Our protocol applies GKR recursively to the arising sumcheck problems on each level of the circuit whose values are verified, and deploys any of the prover efficient versions of GKR on the constructed sorting/prefix circuits with logdepth wiring functions. The verifier timecomplexity of GKR grows linearly in the depth of the circuit. For deep circuits such as the MillerRabin integer primality test of an nbit integer, the large number of rounds may interfere with soundness guarantees after the application of the FiatShamir heuristic. We rearrange the circuit evaluation problem by the babysteps/giantsteps methodmore »

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottomlevel gates. Let f be an m bit Boolean function and consider an n bit function F obtained by applying f to conjunctions of possibly overlapping subsets of n variables. If f has quantum query complexity Q ( f ) , we give an algorithm for evaluating F using O ~ ( Q ( f ) ⋅ n ) quantum queries. This improves on the bound of O ( Q ( f ) ⋅ n ) that follows by treating each conjunction independently, and our bound is tight for worstcase choices of f . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of f .By recursively applying our composition theorems, we obtain a nearly optimal O ~ ( n 1 − 2 − d ) upper bound on the quantum query complexity and approximate degree of linearsize depth d AC 0 circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponentialtime algorithm was not known even for linearsize depth3 AC 0 circuits.As anmore »

Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in
and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathsf {Quasi}\text {}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ $\mathrm{Quasi}\mathrm{NP}=\mathrm{NTIME}\left[{n}^{{\left(\mathrm{log}n\right)}^{O\left(1\right)}}\right]$ , by showing that$\mathcal { C}$ $C$ admits nontrivial satisfiability and/or$\mathcal { C}$ $C$# SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a nontrivial# SAT algorithm for a circuit class . Say that a symmetric Boolean function${\mathcal C}$ $C$f (x _{1},…,x _{n}) issparse if it outputs 1 onO (1) values of . We show that for every sparse${\sum }_{i} x_{i}$ ${\sum}_{i}{x}_{i}$f , and for all “typical” , faster$\mathcal { C}$ $C$# SAT algorithms for circuits imply lower bounds against the circuit class$\mathcal { C}$ $C$ , which may be$f \circ \mathcal { C}$ $f\circ C$stronger than itself. In particular:$\mathcal { C}$ $C$# SAT algorithms forn ^{k}size circuits running in 2^{n}/$\mathcal { C}$ $C$n ^{k}time (for allk ) implyN E X P does not have circuits of polynomial size.$(f \circ \mathcal { C})$ $(f\circ C)$# SAT algorithms for size$2^{n^{{\varepsilon }}}$ ${2}^{{n}^{\epsilon}}$ circuits running in$\mathcal { C}$ $C$ time (for some$2^{nn^{{\varepsilon }}}$ ${2}^{n{n}^{\epsilon}}$ε > 0) implyQ u a s i N P does not have circuits of polynomial size.$(f \circ \mathcal { C})$ $(f\circ C)$Applying
# SAT algorithms from the literature, one immediate corollary of our results is thatQ u a s i N P does not haveE M A J ∘A C C ^{0}∘T H R circuits of polynomialmore »