A methodology developed by UT professors will allow the cost of verifying computations to be reduced by batching many separate arguments together.

Brent Waters, a computer science professor and a co-author of the paper, was inspired to find a more efficient way to verify computations by refining techniques that had already come out over a decade ago.

Recent advancements in constructing batch arguments together have relied on tools such as probabilistically checkable proofs or correlation-intractable hash functions. Although these tools are effective, they are computationally intensive.

“Sometimes I get motivated by simplicity,” Waters said. “There's different goals in computer science … just having a simpler or more sensible way of doing something can also be a goal.”

Waters, along with David Wu, a computer science professor and co-author of the study, developed a method to batch arguments by using a new type of proof system. Arguments are verified when a prover uses witnesses to convince the verifier that a batch of statements is correct. When arguments are batched together, multiple statements can be checked at the same time, cutting down on verification costs. Through this method, Wu said that verifying a full computation corresponds to batch verifying the proofs for each step of the computation.

The method of batching arguments can be applied to NP statements, which are statements that are able to be easily verified when an algorithm is given a specific solution to a problem.

“This does not mean that there is necessarily an efficient algorithm that actually allows you to find a solution to the problem, it only says that checking the solution to a problem can be done efficiently,” Wu said.

Wu said that batching arguments can help with delegation and outsourcing of computation, such as when information is sent to and from the cloud.

“Cryptographic tools allow us to … check that the cloud is actually doing the correct computation,“ Wu said. “This is interesting because the cost of checking the computation is much, much smaller than the cost of performing the computation itself.”

Waters said that in the future, the methodology could be expanded to different computational assumptions outside of bilinear maps, as well as used for more practical issues.

“Can we take some of the ideas we had from (the methodology) and translate it to a kind of a different problem in cryptography, not about proofs?” said Waters.  “That’s something we’ve been building … a certain type of new encryption systems where the problem itself doesn't seem to be particularly related to the batch, but some of the ideas translate over.”