# What's the minimum message expansion for Digital Signature?

Can we prove a minimal message expansion for a Digital Signature scheme (possibly with Message Recovery), for $b$-bit security (that is expected $O(2^b)$ work to break the system)?

Define message expansion as the maximum over all messages (perhaps at least a certain threshold $t$ in size) of the difference in size between the signed message and the original message, with the constraint that from the signed message and the public key, the public verification procedure must reconstruct the original message.

Message expansion of $2b+O(1)$ is claimed by BLS signature with $t=0$ if I understand correctly, and reached by deterministic RSA-MR (ISO/IEC 9796-2 scheme 3) with $t=\log(N)-2b$ bit where $N$ is the public modulus, large enough to prevent factorization attack.

• I don't see why 'fixed and publishing a private key' would prove that 2b is optimal, even if 2b; if someone (who knew the private key) could find two messages with the same signature in less than $O(2^b)$ time, how could that be used to break the signature (by someone who didn't know the key) is less than $O(2^b)$ time? – poncho Oct 9 '17 at 15:16
• Also, I vaguely recall a torus-based signature system (by Alice Silverberg) that claimed to have signatures of less than 2b in length; however, it's been a long time, and a quick google didn't turn up anything... – poncho Oct 9 '17 at 15:17
• @poncho: you are right; I removed my faulty argument that the bound can't be below $2b$ when $t=0$. I'll actively search for the Alice Silverberg signature scheme. – fgrieu Oct 9 '17 at 16:28
• I think it might be math.uci.edu/~asilverb/bibliography/ceilidh.pdf ; however, the signature there doesn't appear to be as small as I remember... – poncho Oct 9 '17 at 17:23
• I think I heard about a scheme using $1.5 n$ or $\sqrt 2 n$ once, might have been in the Multivariate-quadratic-equations category. – CodesInChaos Oct 9 '17 at 17:25