# Compact digital signature for noisy data

The question asks for a signature scheme, with a public verification procedure, that is tolerant to minor alterations of the signed data during its transmission [possibly in analog form over some noisy channel], where the signature is a small digital appendix sent over a digital channel assumed error-free in the absence of attack.

### External definition

Data to be signed is in set $\mathbb M=\{0,1\}^n$, that is a message $M\in\mathbb M$ has a fixed number $n$ of bits noted $m_i$, $0\le i<n$, with $n$ a given at least in the thousands. The signature is in set $\mathbb S=\{0,1\}^s$, and we want $s$ as small as feasible.

The signature scheme is used exactly as a standard signature scheme with appendix, consisting of public algorithms running in polynomial time to compute three functions:

• a public/private key generation function accepting a uniformly random secret seed, yielding $(K_\text{pub},K_\text{priv})$;
• a signature function accepting $K_\text{priv}$, any $M\in\mathbb M$, and optionally an uniformly random secret seed, yielding signature $S\in\mathbb S$, noted $\mathcal S(M)$ [with $K_\text{priv}$ and optional seed implicit];
• a verification function accepting $K_\text{pub}$, any $M\in\mathbb M$, any $S\in\mathbb S$, yielding $\text{pass}=0$ or $\text{fail}=1$, noted $\mathcal V(M,S)$ [with $K_\text{pub}$ implicit].

### Security goals

It is assumed a public easily computable function $\Delta: \mathbb M^2\to \mathbb N$, with $\Delta(M,X)$ telling how far apart is any message $X$ from any reference message $M$. $\forall M\in\mathbb M,\Delta(M,M)=0$ holds.

It is assumed public thresholds $(\alpha,\beta)\in\mathbb Z^2$, quantifying two independent goals

1. detect forgeries more than $\alpha$ apart from the original,
2. accept messages no more than $\beta$ apart from the original.

For 1 we put ourselves in a chosen messages setup: we are safe if there's no polynomial time algorithm which [for a sizable fraction of generation seeds and odds better than a small fixed bound], given $K_\text{pub}$ and access to a box/oracle implementing $\mathcal S$, outputs an $(X,S)\in\mathbb M\times\mathbb S$ with $\mathcal V(X,S)=\text{pass}$, even though each $M$ the algorithm submitted to the oracle satisfied $\Delta(M,X)>\alpha$.

For 2, the best would be that $\forall(M,X)\in\mathbb M^2,\Delta(M,X)\le\beta\implies\mathcal V(X,\mathcal S(M))=\text{pass}$.
But it would be fine if there's no polynomial time algorithm which outputs a counterexample given the generation seed [protecting from crafted false positives]; or even if that's with input $K_\text{pub}$ [protecting from false positives crafted by adversaries unable to sign].

### A generic but inefficient construction

For any $\Delta$, $\alpha$, $\beta$, we can transform any normal digital signature scheme with appendix having signature procedure $\dot{\mathcal S}$ and verification procedure $\dot{\mathcal V}$ into one satisfying our requirements, albeit with a large $s$:

• we keep the original key generation;
• we define a new signature function $\mathcal S(M)=M\|\dot{\mathcal S}(M)$;
• we define a new verification function that splits the signature $S$ to obtain the alleged message $\dot M$ and signature $\dot S$, and returns $\mathcal V(M,S)=\begin{cases}\dot{\mathcal V}(\dot M,\dot S)&\text{ if }\Delta(\dot M,M)\le(\alpha+\beta)/2\\\text{fail}&\text{ otherwise}\end{cases}$.

When using a signature scheme in PKCS#1 and a $r$-bit RSA modulus with $r\equiv0\pmod8$, that gives $s=n+r$. With trivial adaptation, using scheme 3, or the weaker scheme 1, of the RSA signature with message recovery of ISO/IEC 9796-2 (paywalled with free preview) and some $h$-bit hash, we can improve this to $s=\max(n+h+16,r)$.

### Method for arbitrary $\Delta$?

Question: for arbitrary given $\Delta$ (or perhaps assuming some general property of these), what's a tight lower bound on $s$ as a function of $(n,\alpha,\beta)$? Any scheme approaching that?

### Bound for a $\Delta$ the square of Euclidean distance?

Consider the message $M$ consisting of symbols each $b$-bit [with $n\equiv0\pmod b$] and transmitted as a physical quantity monotonically function of the value $\hat m_j$ coded by the bits of the symbol

$$\hat m_j=\sum_{k=0}^{k<b}2^k\cdot m_{j\cdot b+k}\text{ for }0\le j<n/b$$

and $\Delta$ is the square of Euclidean distance

$$\Delta(M,X)=\sum_{j=0}^{j<n/b}(\hat m_j-\hat x_j)^2$$

Question: for that $\Delta$, what's a tight lower bound on $s$ as a function of $(n,b,\alpha,\beta)$? Any scheme approaching that?

### Extensions

Can we extend to more complex $\Delta$ making practical sense for $M$ consisting of independent multi-bit symbols coding a physical quantity, with strong expected correlation between integers coded by transmitted and received symbol, but disregard for correlation (if any) between adjacent symbols [otherwise said: if we reorder the symbols in both $M$ and $X$ per the same permutation, $\Delta(M,X)$ is unchanged]?

• More generally, one can say that the "trivial" schemes are those in which $S$ consists of a standard signature and (possibly empty) data that together with any data recovered from the signature (which will be empty unless that scheme is with-recovery) is sufficient to recover $M$ from a noisy version of $M$, such as a not-necessarily-secure sketch. $\;$ – user991 Jun 12 '14 at 1:19
• Given that you are willing to accept the overhead of a signature on the transmission, is there a reason you don't want to just use an error-correcting code, capable of correcting up to $\beta$ errors? This is readily implementable and would have the obvious advantage of ensuring you get the original, uncorrupted message. I think a MAC may be more achievable than a signature since it seems more feasible to obtain a secure private locality-sensitive hash than a public one. – jbms Jun 12 '14 at 1:25
• You could only use an ECC that includes the original message in its codewords, since your setting specifies that M must be transmitted anyway. $\:$ Including sketch's_helper_data(M) in the traditional signature's input would preserve any strong unforgeability of the traditional signature scheme, insofar as that is possible in your setting. $\;\;\;\;$ – user991 Jun 12 '14 at 7:36
• Instead of signing the message, or a hash, why don't you sign a fuzzy hash? – Reid Rankin Sep 20 '15 at 23:43
• @fgrieu Take a look at ssdeep. It might be what you need. In any case, I suggest separating the hash and signature steps; instead of rolling your own special crypto that can detect differences, use standard, vetted crypto against a hash function designed for your purposes. That way you have very specific and testable potential failure modes. – Reid Rankin Sep 21 '15 at 6:46

• Probably protocol was described without giving all the details. Two secrets are input to the prover: exact (original) message and signing key. Protocol is a proof for an AND condition: for message and for key. Original message is only required to produce initial commitments, the first step of protocol. "Efficient" here means signature size vs. probability tradeoff; the point is avoiding protocols with $1/2$ soundness, in favor of large-O(inverse challenge space) error probability. – Vadym Fedyukovych Nov 23 '14 at 21:11