Abstract:

Cryptographic schemes are often constructed using multiple component
cryptographic modules. A construction is {\em tolerant} for a (security)
specification if it meets the specification, provided a majority (or
other threshold) of the components meet their specifications. We define
tolerant constructions, and investigate `folklore', practical cascade
and parallel constructions. In particular, we show that cascading
encryption schemes provides tolerance under chosen plaintext attack,
non-adaptive chosen ciphertext attack (CCA1) and a weak form of adaptive
chosen ciphertext attack (weak CCA2), but not under the `standard' CCA2
attack. Similarly, certain parallel constructions ensure tolerance for
unforgeability of Signature/MAC schemes, one-way functions, certain
collision-resistant hash functions, and other functions. We present
(new) tolerant constructions for (several variants of) commitment
schemes, by composing simple constructions, and general method of
composing tolerant constructions. Our constructions are simple,
efficient and practical. To ensure practicality, we use concrete
security analysis (in addition to the simpler asymptotic analysis).