Paper 2000/019

Threshold Cryptography Secure Against the Adaptive Adversary, Concurrently

Anna Lysyanskaya


A threshold cryptosystem or signature scheme is a system with $n$ participants where an honest majority can successfully decrypt a message or issue a signature, but where the security and functionality properties of the system are retained even as the adversary corrupts up to $t$ players. We present the novel technique of a committed proof, which is a new general tool that enables security of threshold cryptosystems in the presence of the adaptive adversary. We also put forward a new measure of security for threshold schemes secure in the adaptive adversary model: security under concurrent composition. Using committed proofs, we construct concurrently and adaptively secure threshold protocols for a variety of cryptographic applications. In particular, based on the recent scheme by Cramer-Shoup, we construct adaptively secure threshold cryptosystems secure against adaptive chosen ciphertext attack under the DDH intractability assumption.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Part of this paper will appear in Eurocrypt2000
threshold cryptographyadaptive adversary
Contact author(s)
anna @ theory lcs mit edu
2000-05-13: received
Short URL
Creative Commons Attribution


      author = {Anna Lysyanskaya},
      title = {Threshold Cryptography Secure Against the Adaptive Adversary, Concurrently},
      howpublished = {Cryptology ePrint Archive, Paper 2000/019},
      year = {2000},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.