I have a 64 bit integer. It has some sort of signature so that one can be sure it is valid.

Anyone may increase the integer, update the signature, and remove all trace of the old signature. But it is not permitted to reduce the integer.

Many updates are permitted.

Is there a scheme such that, given $n$ and publicly verifiable signature $S(n)$, we can calculate $n+x$ and $S(n+x)$ but only if $x>0$?


1 Answer 1


Yes, this is possible. Here's one simple scheme:

The scheme. We fix an upper bound $B$ for the maximum allowed value of the counter. Let $H$ be a cryptographic hash function and $\text{Sig}(\cdot)$ be an ordinary signature scheme (e.g., a RSA signature). Use $H^k(x)$ to the $k$-fold iteration of $H$ on $x$, e.g., $H^2(x)=H(H(x))$. The signature $S(n)$ on counter value $n$ is a tuple $(n,x,y,\text{Sig}(y))$ that passes the following verification check.

Signature verification. The signature $(n,x,y,s)$ is valid if $H^{B-n}(x)=y$ and if $s$ is a valid signature on $y$.

Signing. Note that the signer can create an initial signature $S(0)$ by choosing $x_0$ randomly, letting $y=H^B(x_0)$, and signing $y$ to get $S(0)=(0,x_0,y,\text{Sig}(y))$.

Incrementing. Also, given a signature $S(n)=(n,x,y,\text{Sig}(y))$ on counter value $n$, anyone can increment $n$ to get a signature on $n+1$ as follows: $S(n+1)=(n+1,H(x),y,\text{Sig}(y))$.

Performance. Creating a signature takes up to $B$ iterative hashes and one ordinary signature. Verifying a signature $S(n)$ takes $B-n$ iterative hashes and one ordinary signature verification. Therefore, this scheme is only efficient if the bound $B$ can be kept relatively small.

Here are two small improvements on the simple scheme above:

A trick to speed up signature verification. If you want to speed up signature verification, at least for small values of the counter, then you could use the following trick. Let's assume for convenience that $B$ is a power of two. The signer creates the initial signature $S(0)$ as

$$S(0) = (0,x,H^1(x),\text{Sig}(1,H^1(x)),H^2(x),\text{Sig}(2,H^2(x)),H^4(x),\text{Sig}(4,H^4(x)),\dots,H^{2^i}(x),\text{Sig}(2^i,H^{2^i}(x)),\dots,H^B(x),\text{Sig}(B,H^B(x))).$$

In other words, the initial signature $S(0)$ can be written in the form

$$S(0) = (0,x,y_0,\text{Sig}(1,y_0),y_1,\text{Sig}(2,y_1),\dots,y_i,\text{Sig}(2^i,y_i),\dots),$$

where $y_i=H^{2^i}(x)$.

Notice that, as a special case, a verifier can verify the signature $S(0)$ with just one hash application: hash $x$ once to get $H^1(x)$, then check its signature. For larger values of $n$, signature verification will require more iterated hash computations, but not $B-n$ iterated hashes.

To increment the counter, you increment the $n$ part (as before), hash the $x$ part (as before), and throw away any $y_i$ parts where $2^i \le n$ and the corresponding signatures.

Consequently, the signature on $n$ now becomes

$$S(n) = (n,x,y_i,\text{Sig}(2^i,y_i),y_{i+1},\text{Sig}(2^{i+1},y_{i+1}),\dots),$$

where $i=\lfloor \lg n \rfloor + 1$.

With this trick, verifying a signature $S(n)$ now can be done in $O(n)$ time: it requires up to $n$ iterated hashes and one ordinary signature verification. Note that signature verification is not constant time; as the counter gets larger, verification gets slower. This trick does increase the length of the signature by a $\lg B$ factor. One can trade off the length of the signature against the speed of verification, to a certain extent.

A trick to speed up signature creation. If you want to speed up signature creation, the following variant may be useful. However, this variant does not speed up signature verification, so this variant probably won't be very useful on its own in practice. The signer can select a RSA modulus $N$ (whose factorization is kept secret), and use the hash function $H$ given by $H(x)=x^2 \bmod N$. Note that this is a one-way function. However, it has the special property that there's a shortcut that allows the signer to compute $H^B(x)$ with much less effort than iteratively hashing $B$ times: namely, $H^B(x) = x^{2^B} = x^k \bmod N$ where $k=2^B \bmod \varphi(N)$ and $\varphi(N)$ is Euler's totient function applied to $N$. The signer knows the factorization of $N$, so can compute $\varphi(N)$ and then compute $k$ using modular exponentiation mod $\varphi(N)$. This is the shortcut; however, only the signer can use this shortcut, because no one else knows the factorization of $N$. This shortcut can be used to efficiently create an initial signature $S(0)$.

Of course, you can combine both tricks into a single scheme, if you want to speed up both signature verification and signature creation.

Related work. You might also be interested in the following papers:

Cryptographic Counters and Applications to Electronic Voting. Jonathan Katz, Steven Myers, Rafail Ostrovsky. EUROCRYPT 2001.

A Cryptocounter Based on the Paillier PKCS. Adam L. Young and Moti M. Yung. Advances in Cryptovirology, Chapter 6.


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.