Round-Optimal Blind Signatures in the Generic Group and Random Oracle Model

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

A round-optimal blind signature exchanges one message each way, so the signer keeps no per-session state. In pairing-free groups every known scheme needs at least three messages; round-optimal ones exist only from RSA, lattices, pairings, or expensive generic transformations. The source paper asks whether the three-move barrier is real for schemes that touch the group only through generic operations and treat the hash as a random oracle, and proves that it is — provided the user’s final step and verification together make only logarithmically many oracle queries. Conjectured here is that the restriction is an artifact of the attack rather than a feature of the world.

View PDF · Download LaTeX source

Fix a family of groups \(\mathbb{G} = \mathbb{G}(\lambda)\) of prime order \(p = p(\lambda)\), together with a random oracle \(\mathcal{H}\) whose outputs may contain group elements. A generic algorithm accesses \(\mathbb{G}\) only through an oracle \(\mathcal{O}_{\mathrm{grp}}\) offering the group operation and equality testing on handles, never through representations; a scheme’s algorithms are transformations of GGM algorithms when each is obtained from such a generic algorithm in the standard way.

A round-optimal blind signature is \(\mathsf{BS} = (\mathsf{KeyGen}, \mathsf{User}_1, \mathsf{Sig}, \mathsf{User}_2, \mathsf{Ver})\) with message space \(\mathcal{M} = \mathcal{M}(\lambda)\): the user sends one message, the signer replies once, and \(\mathsf{User}_2\) produces the signature. Blindness is the usual indistinguishability of which of two messages was signed; one-more unforgeability is that no adversary completing \(\ell\) signing sessions outputs \(\ell + 1\) valid signatures on distinct messages.

Conjecture. There is no round-optimal blind signature scheme \(\mathsf{BS}\) in the ROM with message space \(\mathcal{M}\) for which all of the following hold at once:

  1. \(\mathsf{BS}\) is correct;
  2. \(\mathsf{User}_1\), \(\mathsf{User}_2\) and \(\mathsf{Ver}\) are transformations of GGM algorithms;
  3. \(|\mathcal{M}(\lambda)|\) is superpolynomial, \(|\mathcal{M}(\lambda)| = \lambda^{\omega(1)}\);
  4. every ppt GGM blindness adversary has negligible advantage;
  5. every computationally unbounded GGM one-more-unforgeability adversary making at most polynomially many oracle calls has negligible advantage.

Four parts of the quantification are the statement rather than decoration.

  • The query budget in item 5 is the open cell. The source proves the same statement with the adversary restricted so that \(\mathsf{User}_2\) and \(\mathsf{Ver}\) together make \(O(\log \lambda)\) random-oracle queries. Replacing that with any polynomial is the whole content of the conjecture.
  • The adversary is unbounded but query-efficient. This is what makes the result an impossibility in the idealised model rather than a statement about a computational assumption: no assumption appears anywhere.
  • Only \(\mathsf{User}_1\), \(\mathsf{User}_2\) and \(\mathsf{Ver}\) must be generic. \(\mathsf{KeyGen}\) and \(\mathsf{Sig}\) are not constrained, which makes the impossibility stronger than a fully generic one.
  • A superpolynomial message space is required, and is not relaxed. With a polynomial message space the user could enumerate, and the attack has nothing to exploit.

Open for superlogarithmic, polynomially bounded query budgets. Proved below that.

What is proved. The source establishes the full statement for \(q \leq O(\log \lambda)\), where \(q\) counts the random-oracle queries of \(\mathsf{User}_2\) and \(\mathsf{Ver}\) together. The adversary runs a learning phase that accumulates linear relations on a growing pile of group elements, then a forging phase that searches over simulated signer messages for one whose simulated \(\mathsf{User}_2 + \mathsf{Ver}\) execution accepts with probability at least \(1/4\). Blindness is converted into the statement that the verifier essentially never repeats a signer hash query except on “irrelevant” queries, of which there are few and which the attacker can harvest. Section 3.10 of the source extends everything to random oracles whose outputs contain group elements, so that restriction is already gone.

Where the logarithm enters. The attack re-runs finalization and verification against re-randomized hash answers. To do that it must decide, for each hash query, whether \(\mathsf{KeyGen}\) or the signer already made that query in this session. It cannot tell, so it guesses, and all guesses are simultaneously right only with probability exponentially small in the number of queries. The technical lemma carrying this — of independent interest — bounds by \(2^{q} \cdot p\) the probability that a \(q\)-query procedure with failure probability \(p\) can be made to fail once an adversarially chosen set of oracle outputs is fixed. The \(2^{q}\) is the barrier, and it is a property of the proof strategy.

No progress is reported toward superlogarithmic \(q\). The source states the restriction and leaves it.

What a refutation would be. Not a proof technique but a construction: a round-optimal pairing-free blind signature, generic in the group, correct, blind and one-more unforgeable. That would be a significant positive result in its own right, which is part of why the conjecture is interesting either way.

This is the exact remaining gap in the only formal evidence that the three-move barrier for pairing-free blind signatures is real. An affirmative answer closes round-optimality for the entire natural class of schemes that use the group as a black box, and says that anyone who wants a round-optimal pairing-free blind signature must leave that world — through pairings, lattices, RSA, or a non-generic use of the group.

The conjecture is unusually well positioned for adaptation rather than invention. The obstruction is localised in a single lemma whose loss is \(2^{q}\), and the question is whether the guessing step it accounts for can be replaced by something that does not pay per query. That is a different task from finding a new attack.