Suppose we have a list of signatures $S = [s_1, .., s_n]$ for a list of messages $M = [m_1, .., m_n]$, and we want to verify that $S$ is a valid signature of $M$, so each $s_i$ should be valid for each $m_i$.

If we proceed, instead of verifying all $n$ signatures, by verifying a set of $k \lt n$ messages chosen randomly and uniformly, for a random $k$, we could say that $S$ is valid for $M$ with a "certain probability" depending on how many messages we verify.

My question is: If an attacker wants to forge a list $M'$, say he uses $l$ messages from $M$ with their valid signatures, and adds $n - l$ new messages with invalid signatures, constructing new lists $M'$ and $S'$, hoping that $l \geq k$ and that we would only verify the $l$ valid ones, and assume that $S'$ is valid for $M'$ (which is not the case !).

Will he have a high chance or probability of forging such a list of messages, if he has no information about $k$ ($k$ chosen randomly on each verification)?

  • 1
    $\begingroup$ I believe the answer will depend on the probability distribution that $k$ is chosen from... $\endgroup$
    – poncho
    May 31 '19 at 15:49

If $l<k$, then the attack will be detected with a probability 1.

If $l\ge k$, the probability of the attack not being detected is $$\frac{l}{n}\cdot \frac{l-1}{n-1}\cdots \frac{l-k+1}{n-k+1}\ge (\frac{l-k+1}{n-k+1})^k$$

Whether this is large enough or not depends on $n,k,l$.

If the attacker does not know $k$, the best he can do is to choose $l=n-1$, which gives him the highest probability of not being detected.


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.