Distributing the Encryption and Decryption of a Block Cipher

Keith M. Martin, Reihaneh Safavi-Naini, Huaxiong Wang, Peter R. WildIACR ePrint 2003

Abstract

While threshold cryptography is well-established for public-key systems, symmetric-key primitives like block ciphers present unique challenges due to their lack of homomorphic properties. This paper explores methods for distributing the encryption and decryption of block ciphers across multiple nodes to eliminate single points of failure. By utilizing combinatorial structures such as Perfect Hash Families and Cover-Free Families, the authors propose architectures that achieve distributed security and fault tolerance while optimizing for key storage and message expansion.

Introduction

In traditional cryptographic implementations, a single node holding a secret key represents a critical vulnerability. If the node is compromised, the key is lost; if the node fails, the system becomes unavailable. Threshold cryptography mitigates these risks by requiring a specific subset of nodes (e.g., $t$ out of $n$) to cooperate to perform cryptographic operations.

While public-key algorithms (like RSA or ElGamal) lend themselves naturally to threshold schemes due to their underlying algebraic structures, symmetric block ciphers like AES are designed to be "algebraically messy" to ensure security. This lack of structure makes them notoriously difficult to distribute. This paper addresses the challenge of distributing these primitives while minimizing the overhead associated with key storage and message expansion.

Distributed Architectures

The authors evaluate three primary architectures for sharing a block cipher, each offering different trade-offs in terms of efficiency and complexity.

1. Cascade Block Cipher Sharing

In the Cascade model, a message is encrypted in sequential layers, similar to an onion. To decrypt the message, authorized nodes must sequentially "strip" their respective layers. The authors link this approach to "sequence sharing" and demonstrate that it can be optimized using Cumulative Maps. While secure, this method creates a sequential bottleneck, as nodes must process the data in a specific order.

2. XOR Block Cipher Sharing

To address the limitations of the Cascade model, the authors propose XOR-based sharing. In this architecture, nodes use a random nonce ($r$) and their specific share of the key to produce a partial value. These partial values are then XORed with the message. This method is highly efficient because the order of operations is irrelevant, allowing for parallel computation and pre-computation of partial values.

3. Plaintext Sharing

This model involves splitting the message itself into shares using a standard secret-sharing scheme (such as Shamir’s Secret Sharing). Each share is then encrypted separately. While conceptually simple, this approach typically results in significant message expansion, as multiple ciphertexts must be transmitted to represent a single message.

Combinatorial Optimizations

A core contribution of the paper is the introduction of advanced combinatorial tools to optimize the storage and bandwidth requirements of these distributed models:

  • Perfect Hash Families (PHFs): These are used to reduce the number of keys nodes must store in the Cascade and XOR models. By applying PHFs, the authors show that the number of keys can be reduced from an exponential figure to $O(\log n)$.
  • Strong Cover-Free Families (SCFFs): These structures are employed to minimize message expansion within the Plaintext sharing model, making the scheme more viable for bandwidth-constrained environments.

Security and Efficiency Analysis

The paper provides rigorous mathematical proofs for the proposed schemes. A key insight is the application of "cumulative maps" from older secret-sharing literature to prove that their sequence sharing schemes are optimal. Specifically, they prove that for any sequence sharing scheme, the number of components $m(\Gamma)$ must be at least the number of maximal unauthorized sets ($|\Gamma^+|$).

Furthermore, the authors provide security reductions demonstrating that these distributed schemes are as secure as the underlying block cipher. For instance, they prove that Cascade sharing is as secure as the first cipher in the chain, provided the first key remains unknown to the adversary. If an attacker could break the shared scheme without an authorized subset of keys, they would effectively be breaking the original block cipher itself.

Conclusion and Future Work

The research highlights a fundamental trade-off in distributed symmetric cryptography: reducing the number of keys per node typically increases message expansion (bandwidth), and vice versa. While the proposed optimizations significantly improve efficiency, several challenges remain:

  • Message Expansion: Even with SCFFs, ciphertexts remain larger than the original message (often doubling in size in the XOR model).
  • Robustness: The current models assume "honest-but-curious" nodes. Future work is required to add robustness—the ability to detect and ignore nodes that provide false partial results.
  • Primitive Extension: The authors suggest that these techniques could be extended to Message Authentication Codes (MACs) and stream ciphers, representing a promising avenue for future research.

Summary updated

BibTeX
@article{martin2003distributing,
  author = {Keith M. Martin and Reihaneh Safavi-Naini and Huaxiong Wang and Peter R. Wild},
  title = {{Distributing the Encryption and Decryption of a Block Cipher}},
  journal = {IACR ePrint},
  year = {2003},
}
Figure