Compact digital signature for noisy data

Question

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]?

Answer 1

Let's assume signature scheme questioned should not provide "cleartext" no-noise message. For Euclidean distance (sum of squares over message components), one would start from a protocol described at ..whether a number is greater than another number without knowing the numbers?

One would follow Fiat-Shamir idea for a non-interactive proof, namely produce a challenge from protocol initial commitments with a hash function. One would include initial commitments for 4-squares proof and for proving knowledge of signing key.

For background, I would refer to a scheme with noisy signing key Argument of knowledge of a bounded error