D. J. Bernstein

Authenticators and signatures

A state-of-the-art public-key signature system
# Compressed signatures

An **compressed signature** of a message m under a public key pq
has four pieces:
- An integer e in {1,-1}.
- An integer f in {1,2}.
- An integer r in {0,1,...,15}.
- An integer v in {0,1,...,2^769-1}.

The pieces satisfy the following rule:
v is nonzero,
and (ef v^2 H0(r,m)) mod pq
is the square of an integer in {0,1,...,2^768-1}.
## How do I encode a compressed signature as a string of bytes?

The standard format is
- 96 bytes: bits 0 through 767 of v in little-endian form.
- 1 byte: r, plus 16 if e=-1, plus 32 if f=2,
plus 128 if bit 768 of v is 1.

## How do I compress a signature?

Starting from a signature (e,f,r,s) and a public key pq,
expand fs/pq into a continued fraction,
obtaining convergents u_0/v_0, u_1/v_1, u_2/v_2, etc.,
with first denominator v_0 = 1 and subsequent denominators increasing.
Find the maximum i such that v_i <= pq/2^768.
The compressed signature is (e,f,r,v) where v = v_i.
Note that v is between 1 and 2^769-1.
Here's why the result (e,f,r,v) is a compressed signature,
i.e., why (ef v^2 H0(r,m)) mod pq is a square.
Recall from continued-fraction theory
that |u_i / v_i - fs / pq| <= 1 / v_i v_{i+1},
so |u_i pq - v fs| <= pq / v_{i+1} < 2^768,
so 0 <= (u_i pq - vfs)^2 < 2^1536 <= pq.
(If v_i is the final denominator then |u_i / v_i - fs / pq| = 0
so the same conclusion holds.)
By definition of a signature,
ef v^2 H0(r,m) is congruent modulo pq to v^2 f^2 s^2,
which is congruent to (u_i pq - vfs)^2,
which is between 0 and pq-1;
so (ef v^2 H0(r,m)) mod pq equals (u_i pq - vfs)^2,
which is the square of an integer |u_i pq - vfs| in {0,1,...,2^768-1}.

## How do I verify a compressed signature?

Given (e,f,r,v) and pq,
compute (ef v^2 H0(r,m)) mod pq,
and verify that it is the square of an integer in {0,1,...,2^768-1}.
Also make sure to check that v is nonzero.
See Algorithm K2 of my powers paper
for a 2-adic square-detection algorithm.

## How do I uncompress a compressed signature?

Given (e,f,r,v) and pq,
compute (ef v^2 H0(r,m)) mod pq;
this is an integer square, say w^2.
Compute s as the quotient w/vf modulo pq,
or as pq minus that quotient, whichever is smaller.
(If v has a factor in common with pq
then you can't divide by v modulo pq;
you must instead use v to factor pq,
and then use the factors of pq to recompute the signature.
Of course, this never happens in practice.)

Here's why (e,f,r,s) is a signature,
i.e., why H0(r,m) = efs^2 mod pq.
By construction, vfs is congruent to +-w;
so v^2 f^2 s^2 is congruent to w^2,
which is congruent to ef v^2 H0(r,m);
so efs^2 is congruent to H0(r,m).