Combined scheme security proof

Let CS be a combined scheme of $$n$$ public key subschemes.

CS is composed of two algorithms Setup and KeyGen, that all the subschemes share, plus all the other algorithms of each subscheme.

Suppose that each one of the subschemes is individually secure in the Random Oracle Model (ROM).

I want to prove that CS is secure, with the following definition: CS is secure if all its subschemes are jointly secure, meaning that each subscheme is secure in the presence of the others.

$$Proof$$. Suppose an adversary A is able to break the security of subscheme $$i \in n$$ in the presence of the others.

We can construct an adversary B that simulates subscheme $$j \neq i \in n$$ by programming random oracles, in a game that is indistinguishable from the real experiment.

B will then use the attack of A to break the standalone security of subscheme $$i$$, which we assumed to be secure. We prove, by contradiction, that CS is secure.

Does this make sense? If not, how can I prove that CS is secure?

• You don't really say what you're schemes actually do. But assuming there exist key pairs, let KeyGen output two of those. Have two schemes: The first one is a secure scheme that always uses the first keypair and leaks the second private key. The second one works the other way round. Clearly the combination of the two would be insecure for pretty much any security definition I can think of. Mar 3 at 15:18
• But I assume that all subschemes are individually secure. Of course it depends on the security definition, but one that allows private keys leakage is not a very good security definition... Mar 3 at 16:03
• They are individually secure. The partd of the key that's leaked is irrelevant die the security of the individual schemes. Mar 3 at 17:39
• What if the schemes are zero-knowledge? Mar 4 at 11:54
• You really need to define both functionality and security to get a useful response. Mar 4 at 17:23

No, it's not so simple. In particular, you have to be much more precise about what do you mean by combine. if you want a good example about how to combine insecure things could become secure you can read : Let's consider the following one-time-signature scheme $$\Sigma_1, \Sigma_2$$ both which are equal to https://eprint.iacr.org/2010/446.pdf . with message space $$\{0, 1\}^4$$.

Remark that these two schemes are proven secure (the fact they are the same is not relevant in the hypothesis you made).

Now let's consider the Signature scheme $$\Sigma_3$$ over $$\{0, 1\}^8$$, which is the concatenation of $$\Sigma_1$$ and $$\Sigma_2$$. i.e :

$$\Sigma_3.\texttt{KeyGen} = \Sigma_1.\texttt{KeyGen}$$, and $$\Sigma_3.\texttt{Sign} ( sk, m_1 || m_2) =\Sigma_1.\texttt{Sign} (sk, m_1)||\Sigma_2.\texttt{Sign} (sk, m_2)$$. $$\Sigma_3.\texttt{Verify} ( vk, \sigma_1 || \sigma_2) =\Sigma_1.\texttt{Verify} (vk, \sigma_1)\wedge\Sigma_2.\texttt{Verify} (vk, \sigma_2)$$.

Then, if you obtain the signature of $$00001111$$, you can sign every message in $$\{0, 1\}^8$$ which contradicts the one-time-unforgeability.QED

To "combine schemes" people are using universable-composability :

https://en.wikipedia.org/wiki/Universal_composability

What is universal composability guaranteeing, specifically? Where does it apply, and where does it not?

But :

1)It's not enough for your schemes to be secure, they have to be UC-secure.

2)You have to be sure your combination is captured by the formalism of UC.

To conclude, it's a little bit like cooking. It's not because two meals are good separately, that combining both would create a good meal.

About the error in your reasoning " Suppose an adversary A is able to break the security of CS by breaking the security of subscheme", you don't have to suppose how the adversary breaks your scheme, when you are doing a security proof.

• I understand it is not that easy, but can you tell me what's wrong with my reasoning and why it doesn't work? Mar 3 at 14:04
• As I wrote at the end of my comment. In a security proof, you have to assume the attacker is breaking your scheme, not an attacker is breaking your scheme "by breaking the security of subscheme". Mar 3 at 14:07
• Ok, what if you simply assume that the adversary A is able to break the security of the subscheme $i$ in the presence of the other subschemes? Adversary B would still be able to break the standalone security of subscheme $i$ by forwarding the attack of A. Mar 3 at 14:25
• how can you assume that A is able to break scheme $i$, if scheme $i$ is is supposed to be secure? If you have more question, you can ask it on chat.stackexchange.com/rooms/120369/combination Mar 3 at 14:40
• A is able to break scheme $i$ in the presence of the others, but not its standalone security. Mar 3 at 16:04