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.