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).