International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Tolerant Combiners: Resilient Cryptographic Design

Amir Herzberg
Search ePrint
Search Google
Abstract: Cryptographic schemes are often designed as a combination of multiple component cryptographic modules. Such a combiner design is tolerant for a (security) specification if it meets the specification, provided that a sufficient subset of the components meet their specifications. A folklore combiner for encryption is cascade; we show that cascade is indeed a tolerant combiner for encryption schemes, under chosen plaintext attack, non-adaptive chosen ciphertext attack (CCA1) and (adaptive) replayable chosen ciphertext attack (rCCA). However, cascade is not tolerant for adaptive CCA (CCA2), and we show it is also not tolerant for generalized CCA (gCCA). This is an interesting difference between rCCA and gCCA. We also analyze few other folklore tolerant combiners, including the parallel combiner for one-way functions, and the copy combiner for integrity tasks such as Message Authentication Codes (MAC) and signature schemes. Cascade is also tolerant for the hiding property of commitment schemes, and the copy combiner is tolerant for the binding property, but neither provides tolerant for both properties. We present (new) tolerant combiners for commitment schemes; these new combiners can be viewed as a composition of the cascade and the copy combiners. We prove tolerance of the composite combiners via a general Composition Lemma, possibly applicable for other tasks. Our combiners are simple, efficient and practical. To ensure practicality, we use concrete security analysis and definitions, in addition to the simpler asymptotic analysis. Our definitions of security may be of independent interest.
  title={Tolerant Combiners: Resilient Cryptographic Design},
  booktitle={IACR Eprint archive},
  keywords={applied cryptography, tolerant cryptography, foundations of cryptography, concrete security, commitment schemes},
  note={Extended abstract version appeared in Topics in Cryptography - CT-RSA 2005, pp. 172-190, Springer LNCS series, Volume 3376, February 2005. 13452 received 29 Aug 2002, last revised 31 Oct 2006},
  author={Amir Herzberg},