Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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. $\;$ –  Ricky Demer Jun 12 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 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. $\;\;\;\;$ –  Ricky Demer Jun 12 at 7:36
@Ricky Demer: I now understand; thank you! Yes, noisetolerantsignature(M) = sketch's_helper_data(M) || standardsignature(M) works, including with the sketch an ECC (as suggested by @jbms) consisting of an appendix (e.g. Reed-Salomon), if that has error-correction capacity matching $β$. The recovery procedure computes the alleged $M$ from the noisy $X$ and helper data, checks standardsignature(M), and checks $Δ(M,X)\leβ$ where $X$ is the noisy message. We get property 1 regardless of $α$. Optionally we can sign the helper data, or/and the verifier can recompute and check it. –  fgrieu Jun 12 at 8:23
@jbms: Yes, that works (provided the ECC scheme adds extra information to the original message, as does Reed-Solomon). The ECC is used in an unusual setup where the added ECC info is never damaged, but that's a minor loss of bandwidth. However the ECCs I know are intended to correct individual bit errors, and would work quite poorly (take a lot of space) for the $M$ consisting of symbols each $b$-bit, because a minor error on one symbol affects many bits, perhaps all (e.g. 127->128 changes 8 bits). –  fgrieu Jun 12 at 15:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.