Assume we can prove security of digital signature scheme against key-only (no message) attacks.

Now we want to prove security against adaptive chosen message attack. We use random oracle model. The standard proving technique seems to be to replace signer with a simulator and then we have an adversary which is capable of performing no message attack.

Assume $A^{\mathcal{O},\mathrm{Sig}}$ is an adversary which uses random oracle $\mathcal{O}$ and real signer $\mathrm{Sig}$. If we replace signer $\mathrm{Sig}$ with a simulator $S$, we get algorithm $A^{\mathcal{O},S}$.

The proof usually involves two steps:

Step 1. First we prove $P(A^{\mathcal{O},\mathrm{Sig}}\;\text{succeeds})= P(A^{\mathcal{O},\mathrm{S}}\;\text{succeeds})$.

Step 2. However, if $A^{\mathcal{O},\mathrm{S}}\;\text{succeeds}$ this doesn't necessarily mean its executing path equals to the execution path of some $A^{\mathcal{O}', \mathrm{Sig}}$ for some other oracle $\mathcal{O}'$. If we want to achieve this, we must find collisions of queries to the oracle.

Example of this technique is lemma 4 in paper Security Arguments for Digital Signatures and Blind Signatures by Pointcheval and Stern.

My question is: how do we prove Step 1 in general? Adversary could always check if the signature from the signer (or from the simulator) is valid signature using the oracle $\mathcal{O}$. Therefore we must prove equality in the form

$P(A^{\mathcal{O},\mathrm{Sig}}\;\text{succeeds})= P(A^{\mathcal{O}^*,\mathrm{S}}\;\text{succeeds})$

where $\mathcal{O}^*$ is some modified oracle. However, I still don't see how in general these two probabilities are the same because other papers seem to use the same proof technique but they somehow assume that

$P(A^{\mathcal{O},\mathrm{Sig}}\;\text{succeeds})= P(A^{\mathcal{O}^*,\mathrm{S}}\;\text{succeeds})$

holds without any explanation. This could be probably justified using the computational indistinguishability, but then we would need sequence of algorithms which we don't have.

  • 1
    $\begingroup$ Usually, ​ $\langle \mathcal{O}^*\hspace{-0.04 in},\hspace{-0.02 in}S\rangle$ ​ will be provably statistically indistinguishable from ​ $\langle \mathcal{O},\operatorname{Sig}\rangle$ . ​ ​ ​ ​ $\endgroup$ – user991 Jul 21 '16 at 11:46
  • $\begingroup$ @RickyDemer, but statistical indistinguishability implies computational indistinguishability. For computational indistinguishability we need to have an algorithm that is capable of succeeding at arbitrary large values of security parameter. However, this is not always the case. $\endgroup$ – Student20 Jul 21 '16 at 12:19

Your Answer

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

Browse other questions tagged or ask your own question.