# Is it ok to send part of digital signature if we have bandwidth constraints?

When creating digital signatures is it ok to send part of it when we have bandwidth constraints?

-
how would you verify ? if you have only part of signature ? –  sashank Jan 31 at 4:44
Recreate the signature and check whether the part is equal. –  user5507 Jan 31 at 4:56
That would require the verifier to have the signing key, in which case it would be better $\hspace{1.07 in}$ to just use a MAC instead of a digital signature. $\;$ –  Ricky Demer Jan 31 at 5:17
@RickyDemer Why MAC is preferred? Since we can have public/private key work in this case. –  user5507 Jan 31 at 5:27
What's the difference between this question, and your other one? How to specify last t bits are only sent when a signature is sent? –  CodesInChaos Jan 31 at 8:37

For any signature scheme, we can remove a few bits of the signature, say $k$, and define a verification scheme that accepts the signature if any of the possible $2^k$ original signatures matching the truncated signature is acceptable. The risk of forgery is increased by at most $2^k$ but might remain acceptable. The work to verify the signature is increased by at most $2^k$ (including not at all, if we count a deterministic secret-key MAC as a signature scheme, for it is just as easy to verify a truncated such MAC as it is to verify the original MAC).

When there's a single bit to trim from an RSA signature (as is often the case when a signature is enciphered using a different modulus having the same number of bits as the modulus used in the signature), there's a standard trick avoiding a doubling of the verifier's work: if the RSA signature is $S$, send $\widetilde S=\min(S,N-S)$, which saves 1 bits, and let the verifier compute $V={\widetilde S}^e\bmod N$; either $V$ or $N-V$ is the normal padded message representative, the right one being determinable by some characteristic of the padded message representative, like being even or having its few high bits clear.

When there are bandwidth constraints, more radical options are:

• Giving up public verification and using a deterministic secret-key MAC, which is king in term of compactness.
• Using a signature scheme allowing message recovery, such that (at least some of) the message is embedded in the signature, saving bandwidth. The standard such RSA schemes are defined by ISO/IEC 9796-2 free partial preview, which allows for example to convey any $b$-byte message as a cryptogram of $\min(256, b+22)$ bytes, when using 2048-bit RSA keys and SHA-1 (but beware that scheme 1, common in the Smart Card industry, could be vulnerable to attack in a chosen-message setup, and has no proven security reduction in other setups).
• Using schemes designed for short signatures with appendix, such a BLS; unfortunately, this is relatively new, and no international standard has emerged, or even is in the work AFAIK.
-
"for it is just as easy to verify a truncated MAC as is it to verify the original" this is of course only true for deterministic MACs with canonical verification. In general the definition of a MAC does not guarantee that that's the case. –  Maeher Jan 31 at 8:19
@Maeher: I'm most familiar with some MACs of the ISO/IEC 9797 family, based on block cipher (9797-1), hash (9797-2); less with those based on universal hash (9797-3); much less any non-deterministic MAC. Any pointer to the general definition of a MAC that you are considering? –  fgrieu Jan 31 at 8:57
To be clear, I'm not aware of any non-deterministic MAC construction actually used anywhere in practice. As with any simple primitive, for a general definition I would refer to "Introduction to Modern Cryptography" by Katz/Lindell. In particular Definition 4.1 on page 114. books.google.de/… –  Maeher Jan 31 at 11:22