Paper 2002/135

Folklore, Practice and Theory of Robust Combiners

Amir Herzberg


Cryptographic schemes are often designed as a combination of multiple component cryptographic modules. Such a combiner design is {\em robust} 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 {\em cascade}, i.e. $c={\cal E}''_{e''}({\cal E}'_{e'}(m))$. We show that cascade is a robust combiner for cryptosystems, under three important indistinguishability specifications: chosen plaintext attack (IND-CPA), non-adaptive chosen ciphertext attack (IND-CCA1), and replayable chosen ciphertext attack (IND-rCCA). We also show that cascade is not robust for the important specifications adaptive CCA (IND-CCA2) and generalized CCA (IND-gCCA). The IND-rCCA and IND-gCCA specifications are closely related, and this is an interesting difference between them. All specifications are defined within. We also analyze few other basic and folklore combiners. In particular, we show that the following are robust combiners: the {\em parallel combiner} $f(x)=f''(x)||f'(x)$ for one-way functions , the {\em XOR-Input combiner} $c=\left({\cal E}''_{e''}(m\oplus r),{\cal E}'_{e'}(r)\right)$ for cryptosystems, and the {\em copy combiner} $f_{k'',k'}(m)=f''_{k''}(m)||f'_{k'}(m)$ for integrity tasks such as Message Authentication Codes (MAC) and signature schemes. Cascade is also robust for the hiding property of commitment schemes, and the copy combiner is robust for the binding property, but neither is a robust combiner for both properties. We present (new) robust combiners for commitment schemes; these new combiners can be viewed as a composition of the cascade and the copy combiners. Our combiners are simple, efficient and practical.

Note: This is draft of full version, being submitted to journal. Comments will be most appreciated.

Available format(s)
Publication info
Published elsewhere. This is full version. Extended abstract version, titled `On Tolerant Cryptographic Constructions`, was presented in CT-RSA 2005.
applied cryptographytolerant cryptographyfoundations of cryptographyconcrete securitycommitment schemes
Contact author(s)
amir herzberg @ gmail com
2008-03-20: last of 11 revisions
2002-08-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Amir Herzberg},
      title = {Folklore, Practice and Theory of Robust Combiners},
      howpublished = {Cryptology ePrint Archive, Paper 2002/135},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.