Obfuscation ==> (IND-CPA Security =/=> Circular Security)

Antonio Marcedone, Claudio Orlandi

TL;DR

This paper demonstrates that standard public-key encryption schemes secure against chosen-plaintext attacks (IND-CPA) are not necessarily "circularly secure." They achieve this by constructing IND-CPA secure schemes that are vulnerable to adversaries who are given encryptions of secret keys, proving a fundamental separation between these security notions.

What Problem Does This Paper Address?

In cryptography, we often rely on encryption schemes to protect sensitive information. A fundamental notion of security for public-key encryption is IND-CPA security, which essentially means an adversary, even with access to a decryption oracle, cannot distinguish between the encryption of two different messages.

However, some cryptographic protocols require a stronger notion called circular security. This is particularly relevant when secret keys themselves need to be encrypted. For instance, in fully homomorphic encryption (FHE), a secret key is encrypted under its own public key (a "1-cycle"). In other scenarios, two parties might exchange encryptions of each other's secret keys (a "2-cycle"). Circular security ensures that even if an adversary obtains such "cycles" of encrypted secret keys, the encryption scheme remains secure.

The core question this paper addresses is: Does IND-CPA security imply circular security? While it's easy to show that IND-CPA security doesn't imply 1-circular security, proving or disproving the implication for n-circular security (where n is any number of chained secret key encryptions) has been a long-standing open problem. Previous work showed separations for n=2 under specific assumptions (like bilinear groups), but a general separation for any n was missing.

Methods

The paper's key contribution lies in constructing IND-CPA secure encryption schemes that are not n-circular secure, for any n. They achieve this by leveraging the power of cryptographic obfuscation.

The authors first build a simple IND-CPA secure encryption scheme based on Virtual Black-Box (VBB) obfuscation. In this scheme:

  • Key Generation: A secret key s is chosen, and the public key is an obfuscated circuit P that essentially checks if an input x matches s.
  • Encryption: A message m is encrypted by creating an obfuscated circuit C that, when given an input x that decrypts to s (i.e., P(x)=1), outputs m; otherwise, it outputs a default value.
  • Decryption: This is straightforward: use the secret key s to evaluate the obfuscated circuit C(s).

The IND-CPA security of this scheme relies on the VBB property of the obfuscator, which allows replacing the public key circuit with a functionally equivalent but simpler one (e.g., one that always outputs a default value) without the adversary noticing.

To break n-circular security, they modify this scheme by adding another component to the ciphertext. This new component is an obfuscated circuit R that "remembers" the message m and checks if an input circuit B (which is part of a circular encryption) evaluates to the secret key. If it does, R reveals m. This addition makes the scheme vulnerable to circular attacks.

The paper then shows how to achieve a similar separation using the weaker notion of Indistinguishability Obfuscation (iO), by modifying the public key to be a pseudorandom generator (PRG) output. This allows for a similar "fake public key" argument, but relies on the indistinguishability of obfuscated circuits that compute the same function.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • IND-CPA Security is Not Enough for Circular Security: This is the central takeaway. The paper provides concrete constructions that demonstrate this separation for any arbitrary number of cycles (n).
  • Obfuscation as a Powerful Tool for Separations: The authors highlight how cryptographic obfuscation, particularly VBB and iO, provides a flexible framework for constructing such security separations. It allows for building complex functionalities into ciphertexts that can be exploited for circular attacks while maintaining IND-CPA security.
  • The Role of "Remembering" Circuits: The introduction of the circuit R that "remembers" the message m and checks for secret key matches is a clever way to break circular security. It effectively turns the ciphertext into a trapdoor that can be sprung by a cycle of secret key encryptions.
  • Generalization to n-Cycles: The constructions are designed to generalize from 1-cycle and 2-cycle attacks to arbitrary n-cycles, solidifying the separation for all n.

Key Results

  • The paper presents a construction of an IND-CPA secure public-key encryption scheme that is not n-circular secure for any n, assuming the existence of VBB obfuscators.
  • They also provide a construction that achieves the same separation using the weaker assumption of indistinguishability obfuscation (iO).
  • The constructions are shown to be secure against IND-CPA attacks by leveraging the properties of the respective obfuscation models.

Limitations and Future Work

  • Assumptions: The constructions rely on the existence of VBB or iO obfuscators, which are strong cryptographic primitives. While candidate obfuscators exist, their practical implementation and security are still active areas of research.
  • Efficiency: The paper mentions that the size of the "functional ciphertexts" used in the circular attack can grow with n. While they argue that an upper bound can be found, efficiency is likely a concern for practical applications.
  • Future Work: The paper implicitly suggests further exploration into the precise relationships between different notions of security and the capabilities of various obfuscation models. The authors also point to existing work on circular and leakage-resilient encryption schemes that can be proven secure under certain assumptions, suggesting that understanding the boundaries of these security notions is crucial for designing robust cryptographic systems.

Summary updated

BibTeX
@article{marcedone2013obfuscation,
  author = {Antonio Marcedone and Claudio Orlandi},
  title = {{Obfuscation ==> (IND-CPA Security =/=> Circular Security)}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2013},
}

Loading related content...

Figure