Title: Universally composable zero-knowledge sets

Authors: Haixia Xu; Hongda Li; Bao Li

Addresses: State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049, China. ' State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049, China. ' State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049, China

Abstract: We define and construct universally composable (UC) Zero-Knowledge Set (ZKS) protocols. A ZKS protocol allows a prover to commit to a secret set S and prove statements of the form x ∈ S or x ∉ S without revealing any other information about S. The universal composability framework initiated by Canetti is very useful as it ensures stronger security such as concurrent composition, adaptive security and non-malleability. In this paper, we propose a UC ZKS protocol and prove its security in the random oracle model. Simultaneously, we give the negative result that a UC ZKS cannot exist in the standard model (without a random oracle). The negative result shows that the random oracle has both compression and extraction, which is a pair of paradoxical properties. To our knowledge, this is the first time this kind of property has been considered.

Keywords: universally composable ZKS; zero-knowledge sets; ZKS protocols; random oracle; mercurial commitment; extraction; compression; concurrent composition; adaptive security; non-malleability.

DOI: 10.1504/IJGUC.2012.045695

International Journal of Grid and Utility Computing, 2012 Vol.3 No.1, pp.25 - 31

Received: 05 Aug 2011
Accepted: 06 Aug 2011

Published online: 27 Feb 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article