TCC 2015: Separations in Circular Security for Arbitrary Length Key Cycles

Alice and Bob are in a committed relationship, so as the kids are doing these days they decide to share their secret keys as a totally healthy and not at all creepy or misguided expression of trust. Since millennials understand the importance of cybersecurity, they don't want to send these keys in the clear. So Alice encrypts her secret key under Bob's public key, and he encrypts his secret key under her public key. This is called a key cycle, and it's a weird situation not covered by the standard IND-CPA security game.

Is this a problem though? Can you spot a key cycle in an IND-CPA secure scheme? The notion of circular security asks an adversary to distinguish a key cycle from encryptions of zero under each of the keys. Alice and Bob might think they're safe encrypting each other's keys. But at Eurocrypt in 2010 Acar et al. showed a scheme that is IND-CPA secure, but isn't circular secure for a key cycle of length 2. So IND-CPA security doesn't imply 2-circular security, and Alice and Bob are going to need an encryption scheme specifically designed to have circular security.

What about for longer key cycles? Luckily this is a TCC blog post, so we can leave Alice and Bob and their ridiculous motivating scenario behind, and simply ask theoretical questions because we're curious about the answers. Koppula, Ramchen and Waters settled this particular question once and for all by showing that for any n there exists an encryption scheme that's IND-CPA secure but not n-circular secure. Of course the solution involves indistinguishability obfuscation.

They take an IND-CPA secure scheme and modify encryption to include an obfuscation of a program that detects key cycles, giving a scheme that's clearly not circular secure. To prove IND-CPA security still holds they modify the scheme again so that secret keys additionally contain a random value and public keys contain the evaluation of a PRG at that point. This separates keys into real and fake public keys, which are indistinguishable without seeing the corresponding secret keys. The obfuscated cycle finding program can then test for a cycle ending in a real key. Hop from the real scheme to one with fake keys by the PRG security, and from the obfuscated cycle detection program to an obfuscation of a program that always outputs 0 by iO security, and reduce to the IND-CPA security of the underlying scheme. The paper explains this all in detail and would be a nice first proof if you want to get to grips with constructions involving iO.