3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Maeher
    Mar 3, 2021 at 15:18
  • 1
    $\begingroup$ 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... $\endgroup$
    – Fiono
    Mar 3, 2021 at 16:03
  • $\begingroup$ They are individually secure. The partd of the key that's leaked is irrelevant die the security of the individual schemes. $\endgroup$
    – Maeher
    Mar 3, 2021 at 17:39
  • $\begingroup$ What if the schemes are zero-knowledge? $\endgroup$
    – Fiono
    Mar 4, 2021 at 11:54
  • $\begingroup$ You really need to define both functionality and security to get a useful response. $\endgroup$
    – Maeher
    Mar 4, 2021 at 17:23

2 Answers 2

Reset to default
1
$\begingroup$

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 this scheme 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, you can look this link to better understand how it works:

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

But:

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

  • 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 shouldn't suppose how the adversary breaks your scheme, when you are doing a security proof.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I understand it is not that easy, but can you tell me what's wrong with my reasoning and why it doesn't work? $\endgroup$
    – Fiono
    Mar 3, 2021 at 14:04
  • $\begingroup$ 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". $\endgroup$
    – Ievgeni
    Mar 3, 2021 at 14:07
  • $\begingroup$ 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. $\endgroup$
    – Fiono
    Mar 3, 2021 at 14:25
  • $\begingroup$ 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 $\endgroup$
    – Ievgeni
    Mar 3, 2021 at 14:40
  • $\begingroup$ A is able to break scheme $i$ in the presence of the others, but not its standalone security. $\endgroup$
    – Fiono
    Mar 3, 2021 at 16:04
0
$\begingroup$

If both secure schemes are UC-secure, combining them to design a new secure scheme is also secure in terms of the security properties defined in the original secure schemes. It has been proved in the UC framework.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.