Cryptography: A new kind of proof system

An evolution in cryptography has the potential to improve security between the edge and the cloud.

A recent paper by Dr Brent Waters, NTT Research Cryptography & Information Security (CIS) Lab director and Dr David Wu, an assistant professor at University of Texas at Austin, is significant as it develops new techniques for communications and the proof system model.

Proof systems are a useful building block for authentication systems. They consist of a proving party and a verifying party, where the prover is trying to convince the verifier that a ‘statement’ is true. Typically, the verifier relies on the prover to provide a witness. 

For example, when a user authenticates to a website, she would provide a username and password. The password here can be viewed as a ‘proof’ that she is the authorised owner of the associated account. 

Another example is when a software vendor issues a software update, they would include a digital signature on the update. Here, the digital signature functions as a proof that the update was issued by the vendor and not by a malicious third party who might try to include malware as part of the update.

The shift to cloud computing has brought with it a wide range of capabilities, and one notable advantage is enabling less powerful edge devices, such as smartphones, to draw on the processing power and resources that reside in the cloud, for example speech recognition, image processing or analytics.

Given the CPU and battery constraints, it might not be feasible to perform these tasks on the device, so they go to a third-party cloud service that will perform the operation and send the result back to the device. However, outsourcing those computations to a cloud service provider does introduce a potential inroad for bad actors. What if the cloud is compromised and provides incorrect answers? Cryptographic proof systems provide a way to tap into the power of the cloud with trust.

One key problem of delegating computation to the cloud asks, ‘how can I verify that a computation was performed correctly in a more efficient manner than simply performing it myself?’ The work of batch argument systems can be applied to tackle that problem.

The main cryptographic primitive (a low-level algorithm) that Waters and Wu developed is a way to batch verify multiple statements.

“Our work provides a new and direct construction of these cryptographic proof systems from long-standing and well-understood cryptographic assumptions. The core object we construct is a primitive for ‘batch verification’. Namely, they allow a user to check any number of computations at the price of essentially checking just a single computation. This can then be used to obtain an approach to efficiently verify the computations,” the authors note.

At a high level, the approach is often referred to as a ‘commit-and-prove’ approach where the prover first ‘commits’ to the statement being proved (such as the computation being checked). The prover then proves that the commitments are valid; importantly, the size of the proof is short and, moreover, they can be checked efficiently by the verifier.

The previous approaches for this problem relied on heavyweight cryptographic tools or complex probabilistic proof systems to construct these argument systems. “Our work avoids all of these cryptographic tools and takes a very direct approach where we directly argue that each elementary step in the computation is performed correctly. This has the advantage that the system is simple to describe and much more efficient to implement compared to previous constructions,” they say.

Beyond securing computations in the cloud and edge journey, a potential application for the batch verification work of Waters and Wu is in the aggregation of signatures. 

In some applications such as blockchains, each update will consist of several signatures. These signatures represent the various transactions that users want to have processed (such as transferring crypto-currency from one account to another). The default solution is to simply include all signatures from the transaction as part of an update which can incur a significant size overhead. However, with batch verification, these can be aggregated into a single shorter object. Its size will be independent of the number of signatures included with the update.

Here, this approach would save on space for communicating and storing the signatures. Consumer devices that participated in a blockchain protocol might need to use less bandwidth or store less information to participate.