When a signature check is cut off halfway, what has the verifier learned? For RSA or ECDSA, nothing. We define signatures whose verification can be stopped at any step and still reports how valid the signature is. We build one from Lamport–Diffie one-time signatures and a Merkle tree, and we prove how much security each step buys.
1Purdue University · 2Cornell University (this research was completed at Purdue University)
The PDF linked here is the 20-page version with the proofs in Appendix A. Every figure, definition, theorem, equation and table number on this page follows that version. An earlier version is Cryptology ePrint Archive, Report 2018/343.
1 · The puzzle
A Lamport–Diffie signature on a 4-bit digest reveals one secret per bit. Anyone can check a revealed secret by hashing it and comparing with the public key. The signer signed a message $m$ with digest $G(m)=\texttt{1011}$. A forger wants to pass off a different message $m^*$ with digest $\texttt{1001}$. It can reuse the three secrets it has already seen. At position 3 it would need a secret that was never revealed, so it puts garbage there. The verifier checks positions in a random order, and after two checks it is interrupted. How likely is it that the forgery is accepted?
Your guess: the forgery passes with probability …
Every pair of positions the verifier might check
The forger survives unless a check lands on position 3. Three of the six pairs avoid it, so the odds are $\tfrac12$, and the verifier that stopped early returns $\alpha=\tfrac24$. The forger's only lever is the distance between the two digests. At real sizes ($n=256$), digests that differ in just one bit are astronomically expensive to find. That trade-off is the whole paper.
The digest $\texttt{1011}$ and the four verifier outputs $\alpha=\tfrac14,\tfrac12,\tfrac34,1$ come from the 4-bit example in the ESORICS talk. The forger's digest $\texttt{1001}$ is our choice for this puzzle. The odds are Equation (3) of the paper with $n=4$, $d=1$, $k_F=2$.
An interrupted check still says something. Verification returns a validity $\alpha\in[0,1]\cup\{\bot\}$, not a bit. From $\alpha$ the verifier recovers how far it got, and the security definition is stated for each $\alpha$.
Def. 1, Def. 2, §3
See it →Half a Lamport check is worth far more than half. With $n=256$, checking 128 random positions still gives about 92 to 94 bits of security, under the paper's security-level estimate. Signing a 128-bit digest instead would give 64.
Thm. 1, Eq. (1), Fig. 5, §6.1, §6.3
See it →In a Merkle tree, the path check buys security only linearly. Until all $h+1$ levels are checked, a forger with its own key wins with probability $1-k_H/(h+1)$. Verification therefore balances the two kinds of check. With $h=20$, about $\tfrac23$ of the computations give 80 bits.
Thm. 2, Fig. 4, Fig. 6, abstract
See it →2 · Why did that happen? · Figure 2
A forger who saw one signature knows the secret for every position where its digest agrees with the signed one. It fails at each position where the digests differ, unless it breaks the hash function $F$. Call the number of such positions $d$, the Hamming distance between $G(m)$ and $G(m^*)$. The verifier of Figure 2 picks positions uniformly at random without repeats. It returns $\bot$ the moment a check fails. If it is interrupted after $k_F$ checks, it returns $\alpha=k_F/n$. Switch between the two points of view. Neither party sees the whole picture, and that is why partial checking works.
Toy parameters: $n=16$, random digests. The algorithm is Figure 2 (flexible verification) of the paper; the probability is Equation (3). In Theorem 1 the forger can also win by finding a preimage of $F$, which adds the $4n\cdot\epsilon_{ow}$ term. We leave that term out here.
So a forger wants $d$ small: at $d=0$ it would pass every check. But two digests that are close are hard to find. Finding a pair within distance $\ell$ takes at least $t_{\ell\text{-}ncr}=2^{n/2}\big/\sqrt{\sum_{i=0}^{\ell}\binom{n}{i}}$ hash evaluations (Lamberger et al., §2). Section 3 turns that trade-off into a definition and a number.
3 · The definition that falls out · Definitions 1–2, Theorem 1
We keep the three algorithms of a standard signature scheme and change what verification returns. To model an interrupt nobody plans for, we give the verifier an interruption oracle. The oracle says after how many computations $r$ the check will be cut off. The verifier must not use $r$ to bias the order of its checks.
$\Sigma=(\mathsf{Gen},\mathsf{Sign},\mathsf{Ver})$, where $\mathsf{Gen}$ and $\mathsf{Sign}$ are as usual. $\mathsf{Ver}(pk,m,\sigma,\llbracket r\rrbracket)$ is probabilistic. It takes an optional interruption position $r\in\{0,\dots,\mathsf{max}\}$, and if $r$ is not given it asks $\mathsf{iOracle}_\Sigma(1^\lambda)$. It outputs $\alpha\in[0,1]\cup\{\bot\}$, where $\alpha=0$ means no operation was performed. Correctness: an honest signature is never rejected, whatever $r$ is: $\Pr[\mathsf{Ver}(pk,m,\mathsf{Sign}(sk,m),r)=\bot]=0$.
An extracting function $\mathsf{iExtract}_\Sigma(\alpha)$ recovers $r$ from $\alpha$. For the Lamport–Diffie construction it is $\lfloor\alpha\cdot n\rfloor$.
$\Sigma$ is $(t,\epsilon,q)$-EUF-CMA if every $\mathcal A$ running in time $t$ with $q$ queries wins with probability at most $\epsilon$. Here $t$ and $\epsilon$ are functions of $\alpha$ and $\lambda$.
Click positions to mark where the forger's digest differs, and choose how many checks $k_F$ happen before the interrupt. We list every set of $k_F$ positions, which is what the verifier's random order amounts to, and count those that miss every marked position. That count always equals Equation (3), $\Pr[\mathsf{Miss}]=\prod_{i=0}^{k_F-1}\big(1-\frac{d}{n-i}\big)$. The puzzle is the first preset.
Positions (click to mark a difference)
Check-sets
Theorem 1 bounds the forger's time $t$ and success probability $\epsilon$ for every distance $\ell\le n-k_F$ it might aim for. §6.1 turns the bound into a number. It assumes a generic birthday-style near-collision search, and it takes $d$ to be the expected distance of a pair found within $\ell$ (Equation (1)). The security level is the forger's best choice:
Everything below is computed live in your browser from these formulas. The preset buttons are the five percentages of Table 1, and each one reproduces the paper's value once rounded down.
Security level vs. computations
The forger's choice of $\ell$
Fig. 5 is traced from the vector paths of fig/ots-sl.pdf. It has 65 points, drawn at $x=1,5,9,\dots,257$. It agrees with the live curve to within about one bit. §6.1's text says "around 92-bit" at 128 evaluations. Fig. 5 reads 93.9 at that point, and the formula gives 93.6. The "shorter digest" line is the paper's own baseline from §6.3, "a security level equal to half of the length of the hash digest". We plot it at digest length $k_F$, which is our illustration and not a figure from the paper.
One Lamport key signs one message. Real systems need many messages, which means a Merkle tree, and a second kind of check that behaves very differently.
4 · What it buys, part 1 · Figures 3, 4, 6 and Theorem 2
A Merkle signature carries a one-time signature, its one-time public key $\mathsf{PK}_s$, and the authentication path $\mathsf{Auth}_s$ that links $\mathsf{PK}_s$ to the root. We also make the signer send the complement nodes $\mathsf{Auth}^c_s$, which lie on the direct path itself. With both, the verifier can check any level of the tree on its own, in any order. It can even check levels in parallel. There are two kinds of work. Checking a Lamport position with $F$ gives exponential confidence $1-1/2^{k_F/2}$. Checking a tree level with $H$ gives only linear confidence $k_H/(h+1)$, because a forger can bring its own one-time key and break just one level. Figure 4 balances the two by checking with $F$ whenever $1-1/2^{k_F/2}\le k_H/(h+1)$ and with $H$ otherwise.
Figure 3: tree of height $h=3$, signing with $\mathsf{PK}_3$
Tree reproduced from merkle-tree.tex (Figure 3). Red nodes in the paper are drawn here in orange, and blue nodes stay blue. Level $j=1$ checks $a'_1=H(\mathsf{PK}_3)$. Level $j>1$ checks that $a'_j$ is the parent of $a_{j-1}$ and $a'_{j-1}$, with $a'_{h+1}$ the root. The one-time part here uses a toy $n=16$. Figure 4's loop condition reads "$H\neq\emptyset$". We take it to mean the level set $T$, and we keep checking until both $N$ and $T$ are empty.
Theorem 2 carries the linear term into the bound. With $k_H\lt h+1$, $\epsilon_{fms}$ includes $1-\frac{k_H}{h+1}$ and $t_{fms}=\mathcal O(1)$. The forger also gets $2^h$ one-time instances to aim at. Figure 6 shows the result for $n=256$, $h=20$, so $n+h+1=277$ computations in total. The level stays near 1 bit for the first ~76 computations, then climbs to 80 bits at about $\tfrac23$ of the way.
Security level of the flexible Merkle signature, $h=20$
The §6.2 formula for $t_{fms}$, as printed, subtracts two terms that make it collapse to $1$. Read literally, it gives 0 bits at every step:
printed: $t_{fms}=\max\{1,\,t_{\ell\text{-}ncr}-2^{h+\log_2(h+1)n}-2^{h\cdot\log_2 2n}-2^{\log_2(n-h-1)}\}$
our reading: $t_{fms}=\max\{1,\,t_{\ell\text{-}ncr}-2^{h+\log_2(h+1)n}-2^{h+\log_2 2n}-(n+h+1)\}$
Our reading subtracts $2^h t_{sign}$, $t_{gen}$ and $t_{ver}$ from the line above it ($t_{gen}=2^h\cdot 2n+2^{h+1}-1$, $t_{ver}=n+h+1$, $t_{sign}=(h+1)n$). With it, the curve follows Fig. 6 within about 2 bits past the first ~76 computations, but it does not match exactly. So the curve drawn solid is Fig. 6 traced from fig/merkle-sl.pdf (70 points at $x=1,5,\dots,277$). Table 1's Merkle row agrees with the traced figure, read at $p\cdot277$, to within one bit at 20%, 40%, 60% and 80%. At 100% the figure's last point reads 124.0, but the table gives 127.
Security per computation is one axis. The other is time on a real device.
5 · What it buys, part 2 · §6.3, Table 1
We implemented both constructions in C with OpenSSL's SHA-256 and ran them on a Raspberry Pi 3 Model B with 1GB of RAM, verifying messages of size 256. The standard schemes were measured with OpenSSL (RSA with public exponent $2^{16}+1$). A standard verifier has one point on this chart: nothing until it finishes. A flexible verifier has a curve, and wherever it is stopped it knows its security level.
Verification time vs. security level (Table 1)
Table 1, exactly as printed: pairs are (time, security level in bits) at 20%, 40%, 60%, 80% and 100% of the verification computations. Security levels of the standard schemes are from NIST and Buchmann et al., as cited in the paper. The paper's own explanation of the Merkle row is that $H(\mathsf{PK}_{fots})$ and $G(m)$ are costly. SHA-2's Merkle–Damgård structure makes them call the compression function many times, so a shorter partial check saves less time than it does for Lamport.
These are two constructions of a new notion. The paper ends by asking where else the idea applies.
6 · Where this goes next · §5.3, §7
Appendix
The forger's time and the distance it can expect for a target $\ell$. The time is the generic lower bound of Lamberger et al. quoted in §2, and the distance is Equation (1).
| Property | Used for | Generic attack (§2) |
|---|---|---|
| Preimage resistance | $F$: the Lamport public key | time $2^q$ succeeds with probability $1/2^{n-q}$ |
| Collision resistance | $H$: the Merkle tree | time $2^{n/2}$ succeeds with probability $\approx\tfrac12$ |
| $\ell$-near-collision resistance | $G$: the message digest | time $2^{n/2}/\sqrt{\sum_{i=0}^{\ell}\binom{n}{i}}$ for probability $\approx\tfrac12$ |
| Notion | What it offers | Why it is not a flexible signature |
|---|---|---|
| Progressively verifiable MACs (Fischlin) | Spot invalid tags after a reasonable number of computations, with a detection probability | Symmetric-key. We answer its open problem for signatures and reuse its detection-probability idea. |
| Incremental signatures (Bellare, Goldreich, Goldwasser) | A cheaper new signature for a similar document | Helps the signer, not a resource-constrained verifier |
| Batch verification | Verify many signatures at once | Lowers load on a busy server; gives no partial guarantee |
| Randomized verification (Freitag et al.) | Verification takes random coins; security level fixed by the IBE identity space | Formally we are one of these, but our security level is computed efficiently from the verifier's output |
| Short and adjustable signatures (Fan, Garay, Mohassel) | Trade signature length against security; a verification-adjustable variant | Constructions rely on $i\mathcal O$, with one concrete (setup-adjustable, BLS) instance. None tolerates unpredictable interrupts. |
Reference
@inproceedings{le2019flexible,
title = {Flexible Signatures: Making Authentication Suitable
for Real-Time Environments},
author = {Le, Duc V. and Kelkar, Mahimna and Kate, Aniket},
booktitle = {ESORICS},
year = {2019}
}
@misc{le2018flexible,
title = {Flexible Signatures: Towards Making Authentication
Suitable for Real-Time Environments},
author = {Le, Duc Viet and Kelkar, Mahimna and Kate, Aniket},
howpublished = {Cryptology ePrint Archive, Report 2018/343},
year = {2018}
}
Code and data. The paper describes a prototype in C using OpenSSL's SHA-256, run on a Raspberry Pi 3 Model B. It has no data availability statement and no public code release, so none is linked here. Every number on this page comes from the paper's text, theorems, figures and Table 1, or is computed live from its formulas. Traced figure points and our reading of §6.2 are labelled where they appear.