On Access Control Encryption without Sanitization

Cecilia Boschini, Ivan Damgård, Claudio Orlandi

TL;DR

This paper introduces new cryptographic primitives for Access Control Encryption (ACE) that work without a trusted "sanitizer" component. They achieve this by limiting the bandwidth of covert channels available to malicious parties, a significant step towards more practical and robust information flow control in decentralized systems.

What Problem Does This Paper Address?

Traditional Access Control Encryption (ACE) schemes rely on a trusted third party, a "sanitizer," to enforce access policies. This sanitizer re-encrypts messages, ensuring only authorized recipients can decrypt them. However, this centralized component is a single point of failure and can be a bottleneck. The authors investigate whether ACE can be achieved without this sanitizer, a natural question given the desire for more decentralized and resilient systems. The challenge is that without a sanitizer, malicious parties might exploit the system to leak information through "subliminal channels" – hidden communication pathways not intended by the policy. The paper aims to find a way to prevent or significantly limit such leaks, even when parties can communicate directly.

Methods

The paper introduces two main models:

  • ACE without Sanitizer (ACEnoS): This model removes the sanitizer but still assumes parties communicate only through a bulletin board. The core idea is to enforce a "No Secret Write Rule" (NSWR), meaning that if parties communicate against policy, their communication is public. This is achieved by carefully designing key generation and encryption/decryption algorithms, crucially assuming parties do not have pre-shared randomness.
  • Verifiable ACE (VACE): This model adds "ciphertext verifiability." This allows anyone to check if a ciphertext is well-formed according to the encryption algorithm. While not preventing subliminal channels entirely, it significantly limits their bandwidth. This is achieved by introducing a new, weaker definition of obfuscation called "Game-Specific Obfuscation" (GSO).

The authors provide formal definitions for these models and construct schemes based on standard cryptographic primitives like Public Key Encryption (PKE) and symmetric encryption. They also introduce a new primitive called "key-indistinguishable predicate encryption" to construct ACEnoS.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • No Sanitizer, Still Secure: The most significant insight is that meaningful security properties can be achieved even without a trusted sanitizer, by focusing on limiting the bandwidth of covert channels rather than eliminating them entirely.
  • The Power of Verifiability: Adding ciphertext verifiability, even without a sanitizer, is surprisingly powerful. It forces malicious parties to embed information in a structured way, which can be detected or limited.
  • Game-Specific Obfuscation (GSO): The introduction of GSO is a novel contribution. It's a weaker, more practical definition of obfuscation that is sufficient for their VACE construction, potentially opening doors for other applications where full VBB obfuscation is too strong.
  • Subliminal Channels are Hard to Eliminate: The paper acknowledges that completely preventing subliminal channels without some form of sanitization is likely impossible. The focus shifts to making them insecure or very low bandwidth.

Key Results

  • ACEnoS Construction: The paper presents constructions for ACEnoS that satisfy the No-Read Rule (confidentiality and sender anonymity) and a novel No Secret Write Rule (NSWR), limiting unauthorized communication to insecure subliminal channels.
  • VACE Construction: They construct a VACE scheme that, using GSO, limits the bandwidth of subliminal channels to O(log λ) bits, where λ is the security parameter. This is shown to be optimal without a sanitizer.
  • Efficiency: The constructions are shown to be efficient, with ciphertext lengths and computational complexities that are practical.

Limitations and Future Work

  • Subliminal Channels: The paper acknowledges that completely preventing subliminal channels without a sanitizer is impossible. The focus is on limiting their bandwidth.
  • Standard Assumptions: While the constructions rely on standard cryptographic assumptions (like IND-CPA for PKE), the VACE construction relies on the new GSO assumption, which is still a strong assumption.
  • Open Problems: The authors leave it as an open problem whether ACE without sanitization and sender anonymity can be achieved using only PKE. They also suggest exploring solutions based on standard assumptions for limiting subliminal channel bandwidth. Future work could also investigate updatable policies and policy confidentiality within these new models.

Summary updated

Abstract

Access Control Encryption (ACE) [4] allows to control information flow between parties by enforcing a policy that specifies which user can send messages to whom. The core of the scheme is a sanitizer, i.e., an entity that “sanitizes” all messages by essentially re-encrypting the ciphertexts under its key. In this work we investigate the natural question of whether it is still possible to achieve some meaningful security properties in scenarios when such a sanitization step is not possible. We answer positively by showing that it is possible to limit corrupted users to communicate only through insecure subliminal channels, under the necessary assumption that parties do not have pre-shared randomness. Moreover, we show that the bandwidth of such channels can be limited to be $$\text {O} (\log (\lambda ))$$ by adding public ciphertext verifiability to the scheme under computational assumptions. In particular, we rely on a new security definition for obfuscation, Game Specific Obfuscation (GSO), which is a weaker definition than VBB, as it only requires the obfuscator to obfuscate programs in a specific family of programs, and limited to a fixed security game.
BibTeX
@article{boschini2022access,
  author = {Cecilia Boschini and Ivan Damgård and Claudio Orlandi},
  title = {{On Access Control Encryption without Sanitization}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2022},
}
Figure