2
$\begingroup$

Is there a known black-box construction for the following implication?

non-interactive string commitment that stretches additively by an
amount which does not depend on the string being committed to
$\implies$
sigma-protocol for, equivalently, circuit-SAT or 3-SAT, whose communication
complexity scales subquadratically with the size of the SAT instance



The only methods I know either


use circuit-SAT, commit to the values of enough gates, and then use the code of the commitment scheme to prove that the values committed to are correct and cause
the circuit to output TRUE $\:$ (using the code makes the construction not black box)

or

use a graph with a number of edges that scales linearly with the number of variables
(as the case may be) and commit to each entry in the adjacency matrix, for a
communication complexity that scales quadratically with the size of the SAT instance

or

reduce to 3-coloring and, although the communication for each instance of the "core"
only scales linearly, need a number of parallel executions of the "core" that scales linearly,
for a communication complexity that scales quadratically with the size of the SAT instance


.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy