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
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)
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
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