Three-Move Pairing-Free Blind Signatures from Discrete Log

–

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

Discrete log is the weakest and oldest assumption available in a pairing-free group, and three moves is the fewest possible for a scheme that treats the group as a black box. The source paper reaches three moves in the random oracle model alone — removing the algebraic group model that every previous three-move scheme needed — but under decisional Diffie–Hellman rather than plain discrete log. One cell of the table is therefore still empty, and the source paper calls filling it the dream result of the area.

View PDF · Download LaTeX source

A three-move blind signature is a tuple \(\mathsf{BS} = (\mathsf{Setup}, \mathsf{KeyGen}, \mathsf{Sign}_1, \mathsf{U}_1, \mathsf{Sign}_2, \mathsf{U}_2, \mathsf{Ver})\) in which the signer speaks first, the user replies, and the signer speaks once more, after which \(\mathsf{U}_2\) outputs the signature. It makes black-box use of the group when its algorithms access \((\mathbb{G}, p, G)\) only through the group operation and equality testing, never through representations of elements. \(\mathsf{GGen}\) is a pairing-free group generator, and \(\mathsf{BS}[\mathsf{GGen}]\) is the scheme obtained by sampling \((\mathbb{G}, p, G) \gets \mathsf{GGen}(1^\lambda)\) and running \(\mathsf{BS}\) on that description.

Conjecture. There exist oracle PPT algorithms \(\mathsf{BS}\) forming a three-move blind signature scheme, making black-box use of the group, with access to a random oracle \(\mathcal{H}\), such that for every pairing-free group generator \(\mathsf{GGen}\):

  1. (Correctness.) \(\mathsf{BS}[\mathsf{GGen}]\) is correct.
  2. (Blindness from DL.) If the discrete logarithm assumption holds relative to \(\mathsf{GGen}\), then every PPT adversary with access to \(\mathcal{H}\) has negligible blindness advantage.
  3. (One-more unforgeability from DL.) If the discrete logarithm assumption holds relative to \(\mathsf{GGen}\), then every PPT adversary has negligible one-more-unforgeability advantage, under unbounded concurrency.

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

  • One scheme, every generator. The algorithms are quantified outside \(\mathsf{GGen}\), so a single scheme must work for every pairing-free group. A scheme tailored to a particular family would not answer the question.
  • Blindness is conditioned on DL too. Asking for blindness unconditionally would demand it even relative to generators where discrete log is easy, which is stronger than the source’s own guarantee. Both security clauses carry the same hypothesis.
  • Black-box in the group is the whole point. Dropping it makes the question easy in the wrong way: the three-move floor is a theorem about group-black-box schemes, and a non-generic scheme is not competing in the same class.
  • Correctness here is the standard notion, not the source’s. The source paper requires perfect correctness and proves exactly that for its scheme. This statement asks only for correctness in the usual sense, so it is the weaker and therefore easier target; a scheme meeting the source’s stronger bar would also settle this.

Open. The surrounding cells are all settled, which is what makes this one sharp.

What the source achieves. Three moves, pairing-free, black-box in the group, random oracle model only, with full unbounded-concurrency one-more strong unforgeability — but under DDH. Two instantiations: one with computational blindness and signatures of \(15\) group elements plus \(22\) scalars, and one with statistical blindness and signatures of \(21\) group elements plus \(35\) scalars; communication is \(17\) group elements plus \(14\) scalars in both.

Concurrent work reaches the same cell. Chen achieves three moves in the ROM from DDH by a different route, via one-time signatures plus encrypted-message blind signatures.

What is known from DL alone. In the ROM, the best is four moves (Klooß, Lai and Reichle). At three moves, DL suffices only with the algebraic group model on top of the ROM (Abe; Tessaro and Zhu; Snowblind).

Why three is the floor. Two moves is impossible for group-black-box schemes in GGM+ROM, at least for logarithmic query budgets — see c/0013, which is the open form of that impossibility. So this statement asks for the optimal round complexity under the minimal assumption.

The two named obstructions. The source does not present this as a gap to be closed by assembling existing pieces, and says so explicitly:

  • Its algebraic MAC and its linearly-homomorphic extractable commitment are known from DDH but not black-box from DL.
  • The message-dependent punctured statement that makes the four-move DL scheme work forces the message into the first move, and that is precisely what costs the extra rounds.

This is the last empty cell of an otherwise complete table, and both outcomes are substantial. A construction would give the area its round-optimal scheme under its minimal assumption, in the weakest idealisation the community accepts for these schemes. An impossibility would be the first separation between DL and DDH for a natural primitive at fixed round complexity, which is a considerably stronger statement than anything currently known in that direction.

The gap is exactly one assumption wide and one round deep, and the two obstructions the source names are concrete enough to attack separately: either build the missing algebraic MAC and commitment from DL black-box, or find a punctured statement that does not need the message in the first move.