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?
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 &quot;combine schemes&quot; 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 &quot; Suppose an adversary A is able to break the security of CS by breaking the security of subscheme&quot;, you don't have to suppose how the adversary breaks your scheme, when you are doing a security proof.