Cryptology ePrint Archive: Report 2009/427

Improving Cut-and-Choose in Verifiable Encryption and Fair Exchange Protocols using Trusted Computing Technology

Stephen R. Tate and Roopa Vishwanathan

Abstract: Cut-and-choose is used in interactive zero-knowledge protocols in which a prover answers a series of random challenges that establish with high probability that the prover is honestly following the defined protocol. In this paper, we examine one such protocol and explore the consequences of replacing the statistical trust gained from cut-and-choose with a level of trust that depends on the use of secure, trusted hardware. As a result, previous interactive protocols with multiple rounds can be improved to non-interactive protocols with computational requirements equivalent to a single round of the original protocol. Surprisingly, we accomplish this goal by using hardware that is not designed for our applications, but rather simply provides a generic operation that we call ``certified randomness,'' which produces a one-way image of a random value along with an encrypted version that is signed by the hardware to indicate that these values are properly produced. It is important to stress that while we use this operation to improve cut-and-choose protocols, the trusted operation does not depend in any way on the particular protocol or even data used in the protocol: it operates only with random data that it generates. This functionality can be achieved with minor extensions to the standard Trusted Platform Modules (TPMs) that are being used in many current systems.

We demonstrate our technique through application to cut-and-choose protocols for verifiable group encryption and optimistic fair exchange. In both cases we can remove or drastically reduce the amount of interaction required, as well as decrease the computational requirements significantly.

Category / Keywords: zero knowledge, trusted computing

Publication Info: An abbreviated, preliminary version of this work appeared in the \emph{Proceedings of the 23rd Annual IFIP WG 11.3 Working Conference on Data and Applications Security (DBSec'09)

Date: received 1 Sep 2009

Contact author: vishwanathan roopa at gmail com

Available formats: PDF | BibTeX Citation

Version: 20090904:054036 (All versions of this report)

Discussion forum: Show discussion | Start new discussion