Suppose $\Pi=(Gen,Sign,Vrfy)$ is a secure signature scheme, is the following signature scheme $\Pi'$ secure?

  • $Gen'$: The same as $Gen$, output public-private key pair $pk,sk$ on input $1^n$
  • $Sign'$: On input a private key $sk$ and message $m\in\{0,1\}^n$, choose uniform $r\gets \{0,1\}^n$. Output $\sigma=(r,\sigma_0,\sigma_1)$ where $\sigma_0=Sign_{sk}(m\oplus r)$ and $\sigma_1=Sign_{sk}(r)$.
  • $Vrfy'$: On input public key $pk$, message $m$ and signature $(\sigma_0,\sigma_1)$, output $Vrfy_{pk}(m\oplus r,\sigma_0)\wedge Vrfy_{pk}(r,\sigma_1)$.

I speculate (but am not sure if) that this new scheme is secure. I tried to do the following reduction:

Suppose a PPT adversary $A'$ makes a forgery for $\Pi'$, we construct a PPT adversary $A$ for $\Pi$ as:

When $A'$ makes a query to the $Sign_{sk}$ oracle on $m$, choose uniform $r\gets\{0,1\}^n$, make queries to $Sign_{sk}$ on $m\oplus r$ and $r$, and get back $\sigma_0,\sigma_1$. Then feed $\sigma_0,\sigma_1$ back to $A'$.

However, I am then stuck. When $A'$ finally makes a forgery $(m,\sigma_0,\sigma_1)$, what should $A$ do? Possibly $A'$ has never made a query on $m$, but $A$ have made a query on some $m'\oplus r=m\oplus r$ or some $r'=r$. This cannot be avoided because $r'$ is chosen uniformly by $A$. On the other hand, we cannot make any assumption on $A'$ that it also generates a random $r$ (possibly $A'$ utilizes the past $r$'s given by $A$, we can make no assumption on the properties of the black-box $A'$). So how to solve (or bypass) this problem? Or this new scheme is in fact not secure?


2 Answers 2


The scheme is insecure; someone can, with two valid signatures, generate a valid signature to a different message.

Suppose we have the signatures:

  • $(r, \sigma_0, \sigma_1)$ a valid signature for the message $M$

  • $(r', \sigma'_0, \sigma'_1)$ a valid signature for the message $M'$

Then $(r, \sigma'_0, \sigma_1)$ is a valid signature for the message $M' \oplus r \oplus r'$


This is a partial answer. The desired security goal (existential vs strong unforgeability or others?) hasn't been explicitly stated. Without restrictions, we can assume that (any) unforgeability is the target.

In general, this scheme does not need to be secure. In particular it doesn't need to be SUF-CMA secure. Consider an adversary $A$, who makes a signing query for $m = 0^n$; they receive the signature $(r, \sigma_0, \sigma_1)$. Both $\sigma_i$ are signatures over $r$, produced with $\Pi$. Now, if $\Pi$ was a probabilistic SUF-CMA secure scheme, then with high probability $\sigma_0 \neq \sigma_1$. It follows that $(r, \sigma_1, \sigma_0)$ is a valid forgery on $0^n$.

Edit The text below is kept for completeness, but Poncho's answer shows that this scheme is always insecure, even in EUF-CMA settings.

Caveat: The text above isn't meant to say that this construction is always insecure. I have a feeling that with appropriate restrictions (e.g., restricting EUF-CMA), it would be possible to prove things. But I haven't tried.

  • $\begingroup$ I meant existential unforgeability. Thank you for the answer. $\endgroup$ Dec 1, 2023 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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