D. J. Bernstein
Authenticators and signatures
A state-of-the-art public-key signature system

Expanded signatures

An expanded signature of a message m under a public key pq has five pieces:

An integer e in {1,-1}.
An integer f in {1,2}.
An integer r in {0,1,...,15}.
An integer s in {0,1,...,2^1536-1}.
An integer t in {0,1,...,2^1536-1}.

The pieces satisfy the equation e H0(r,m) = fs^2 - pqt.

Signers are actually required to generate s in the smaller interval [0,(pq-1)/2], but verifiers do not need to bother checking for this.

How do I encode an expanded signature as a string of bytes?

The standard format is

192 bytes: t in little-endian form.
192 bytes: s in little-endian form.
1 byte: r, plus 16 if e=-1, plus 32 if f=2; two bits unused.

How do I expand a signature?

Anyone can compute t as (fs^2 - e H0(r,m))/pq. If (e,f,r,s) is a signature, with s in the required range, then the division is exact, and t is in {0,1,...,2^1536-1}. Otherwise the expander can simply set t = 0; the output isn't valid, but the input wasn't valid either.

There are two ways to speed up exact division: first, don't bother computing the remainder; second, compute the bottom half of the quotient 2-adically.

Converting from an expanded signature back to a signature simply means throwing away t.

How do I verify an expanded signature?

The verifier can check the equation e H0(r,m) = fs^2 - pqt modulo a prime v chosen secretly by the verifier. This means computing f(s mod v)^2 - (pq mod v)(t mod v) - e(H0(r,m) mod v) and checking that the result is divisible by v. The same prime v can be reused for many verifications.

If the input is an expanded signature, this procedure says ``yes''; otherwise, this procedure has probability at most 2^{-115} of saying ``yes,'' if v is a uniform random 128-bit prime. This procedure is extremely fast.

Verifiers without a safe source of secret data can instead check the equation modulo several primes v with product larger than 2^{3080}. There are several ways to speed this up.