Threshold and Revocation Cryptosystems
via Extractable Hash Proofs
Hoeteck Wee
⋆
Queens College, CUNY
hoeteck@cs.qc.cuny.edu
Abstract. We present a new unifying framework for constructing non-interactive
threshold encryption and signature schemes, as well as broadcast encryption
schemes, and in particular, derive several new cryptosystems based on hardness
of factoring, including:
– a threshold signature scheme (in the random oracle model) that supports
ad-hoc groups (i.e., exponential number of identities and the set-up is
independent of the total number of parties) and implements the standard
Rabin signature;
– a threshold encryption scheme that supports ad-hoc groups, where encryp-
tion is the same as that in the Blum-Goldwasser cryptosystem and therefore
more efficient than RSA-based implementations;
– a CCA-secure threshold encryption scheme in the random oracle model;
– a broadcast encryption scheme (more precisely, a revocation cryptosystem)
that supports ad-hoc groups, whose complexity is comparable to that of the
Naor-Pinkas scheme; moreover, we provide a variant of the construction that
is CCA-secure in the random oracle model.
Our framework rests on a new notion of threshold extractable hash proofs. The
latter can be viewed as a generalization of the extractable hash proofs, which are
a special kind of non-interactive zero-knowledge proof of knowledge.
1 Introduction
As the old saying goes, “Do not put all your eggs in one basket”. Indeed, this
is the basic principle underlying threshold cryptography, which distributes some
cryptographic functionality amongst many users in such a way that: (1) any t + 1
parties can collectively compute the functionality; and (2) no colluding subset of t
parties can compromise the security of the functionality. The two canonical applications
of threshold cryptography are in public-key encryption and signature schemes, where
the functionalities in consideration correspond to decryption and signing respectively.
The approach was initiated in [19, 20, 21], and there is now a large body of work on
threshold signature schemes [18, 27, 40, 26, 28, 29, 8, 34, 30] and threshold encryption
schemes [41, 11, 24, 34, 9, 10].
⋆
Supported by NSF CAREER Award CNS-0953626, and the US Army Research laboratory
and the UK Ministry of Defence under agreement number W911NF-06-3-0001.
