A method and apparatus are disclosed for compressing Rabin signatures. The disclosed compression scheme compresses a Rabin signature, s, for a user having a public key, n, based on a continued fraction expansion of s/n. The continued fraction expansion of s/n can be performed by (i) computing principal convergents, u.sub.i/v.sub.i, for i equal to 1 to k, of a continued fraction expansion of s/n, where k is a largest integer for which principal convergents are defined; establishing an index l, such that v.sub.l< {square root over (n)}.ltoreq.v.sub.l+1; and generating a compressed Rabin signature (v.sub.l, m) for a message, m.