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?


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

  • 1
    $\begingroup$ 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. $\;$ $\endgroup$
    – user991
    Jun 12, 2014 at 1:19
  • 7
    $\begingroup$ 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. $\endgroup$
    – jbms
    Jun 12, 2014 at 1:25
  • 2
    $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Jun 12, 2014 at 7:36
  • 1
    $\begingroup$ Instead of signing the message, or a hash, why don't you sign a fuzzy hash? $\endgroup$ Sep 20, 2015 at 23:43
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 21, 2015 at 6:46

1 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

  • $\begingroup$ Doesn't the proposed protocols require communication from verifier to prover, contrary to the static signature scheme asked? $\endgroup$
    – fgrieu
    Nov 23, 2014 at 19:41
  • 1
    $\begingroup$ For an interactive proof, yes, communication is required to get the challenge. It should be unpredictable for the prover. For a signature, prover produces challenge himself with a one-way hash function from all previous protocol messages. $\endgroup$ Nov 23, 2014 at 20:02
  • 1
    $\begingroup$ Yes. But unless I miss something, if we use a conventional hash, it seems the verifier will need the exact same message as the prover in order to produce (or check) the hash; thus the scheme won't be more efficient than the "generic but inefficient construction" given, I'm afraid. $\endgroup$
    – fgrieu
    Nov 23, 2014 at 21:06
  • $\begingroup$ 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. $\endgroup$ Nov 23, 2014 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.