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 instanceThe only methods I know eitheruse 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 causethe circuit to output TRUE $\:$ (using the code makes the construction not black box)oruse 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 acommunication complexity that scales quadratically with the size of the SAT instanceorreduce to 3-coloring and, although the communication for each instance of the coreonly 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.
Are there efficient black-box constructions of sigma-protocols for SAT?
cr.crypto security;communication complexity;zero knowledge;black box