In Security of Blind Discrete Log Signatures Against Interactive Attacks C.P. Schnorr defines the ROS Problem and claims that a $(l+1)$ attack against his blind signature scheme is equivalent to solving this ROS problem. (As an aside, some years later Wagner found a way to solve the ROS problem for typical groups, so unfortunately this represents a break on these blind signatures, though an expensive one which practically only allows forging one signature for every 512, which may represent an acceptable loss in many applications.)

A $(l+1)$ attack on a blind signature system is an attack where an attacker interacts $l$ times with a signer, possibly in parallel, and obtains $(l+1)$ distinct signatures from these interactions. In typical applications these signatures represent some asset whose scarcity the signer maintains, but he should not be able to tell which assets are assigned to which participants in the system. This attack allows an attacker to violate the signer-controlled scarcity and e.g. steal money from a Chaum bank.

The ROS (Random Overdetermined System) problem is defined in the paper by equation (1): $$ a_{k,1} c_1 + \cdots + a_{k,l}c_l = F(a_{k,1}, \ldots, a_{k,l}) $$ where $F$ is a random oracle function. If an attacker can find $a_{k,i}$ and $c_i$ which satisfy $l+1$ instances of the above equation he has solved the ROS problem.

  1. The particular instance of ROS in the paper is defined by equation (2) $$ H(f_k, m_k) = \sum_{\ell=1}^l a_{k,\ell}c_{\ell} $$ where $f_k$ is some collision-resistant function of the coefficients, $m_k$ is chosen by the attacker, and $\{a_{k,\ell}\}_\ell$, $H$ is a random oracle hash function. Already the presence of an attacker-controlled $m_k$ means that this isn't really an instance of the ROS problem as described above, but let's modify equation (1) to give the attacker a family $\{ F_\sigma\}$ of independent random functions rather than just a fixed $F$, and let him choose any $\sigma$. My first question is whether this modification makes sense and is actually necessary.
  2. More seriously, while Schnorr demonstrates an attack based on solving $l+1$ instances of the above equation (2), and Theorem 2 claims that any attacker must do this, his prove actually forces an attacker to solve the following equation (3): $$ H(f_k, m_k) = -a_{k, 0} + \sum_{\ell=1}^l a_{k,\ell}c_{\ell} $$ which differs from equation (2) by the addition of this extra attacker-controlled coefficient $-a_{k,0}$. $f_k$ is modified to be a function of $a_{k,0}$ as well as the other $a_{k,i}$'s, so this problem still appears to be "hard", but it's definitely not an instance of ROS. My second question is whether equation (3) can somehow be recast as an instance of equation (1), and how. If not then it appears Schnorr's proof is wrong (or rather, that ROS needs to be defined differently).

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.