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?

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?

share|improve this question
1  
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
4  
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
1  
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

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

share|improve this answer
    
Doesn't the proposed protocols require communication from verifier to prover, contrary to the static signature scheme asked? –  fgrieu Nov 23 at 19:41
1  
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. –  Vadym Fedyukovych Nov 23 at 20:02
    
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. –  fgrieu Nov 23 at 21:06
    
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 at 21:11

Your Answer

 
discard

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

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