I am looking for a way to have a 'did it expired' key.

There's a similar question here, but I have to prevent reusing of the 'did it expired' signature .

A possible solution would be a two one-way functions f,g such that-

  • Faythe generate key=f(private key,some date) and send it to Alice.
  • Alice send g(key,hash(message)) to Bob.
  • Bob can verify that the message is up to date with the public key.

I thought of doing this with the Yao's Millionaires' Problem saying Alice has a signed value which only Bob can decrypt, but couldn't figure how to extend it.

Can Someone help me find f,g or perhaps a better idea?

  • 1
    $\begingroup$ Since you don't seem to rule out having a trusted third party involved, is there any other reason why you can't use standard signature algorithms, X.509 certificates and PKCS#7 with external time stamping by the trusted third party? $\endgroup$ May 18, 2016 at 23:36

1 Answer 1


The simplest solution is to rely on identity-based signatures.

A trusted third party (TTP) defines a set of RSA keys $\mathit{mpk} = \{N,e\}$ and $\mathit{msk} = \{p,q,d\}$ where $N = pq$ for two large primes $p,q$ and $e,d$ such that $e \cdot d \equiv 1 \pmod {(p-1)(q-1)}$. Key $\mathit{mpk}$ is public and is used to check the correctness of signatures; key $\mathit{msk}$ is secret and is used by the TTP to generate signing keys for a given time period. Let also $H$ be a cryptographic hash function.

If Alice wishes to obtain a signing key valid up to, say, May 30, 2016, the TTP computes the signing $\mathit{sk}_A = [H(Alice\|05302016)]^d \bmod N$ and gives it to Alice.

Alice can now sign a message $M$ using $\mathit{sk}_A$ as

  1. choose a random $t \in \mathbb{Z}_N$;
  2. compute $T = t^e \bmod N$, $c = H(T\|M)$, $s = \mathit{sk}_A \cdot t^c \bmod N$;
  3. return the signature $\sigma=(T,s)$.

Anyone can check that $\sigma=(T,s)$ is Alice's signature on message $M$ with expiry date $05/30/2016$ using the verification key $\mathit{mpk}$ by checking that $s^e \equiv H(Alice\|05302016) \cdot T^{H(T\|M)} \pmod N$.

  • $\begingroup$ Whats Alice under the hash stands for?Her pub key? $\endgroup$
    – Shu ba
    May 19, 2016 at 17:57
  • $\begingroup$ Great! By the way in you're implementation we can say Faythe is the TTP CA. $\endgroup$
    – Shu ba
    May 19, 2016 at 18:09
  • $\begingroup$ @Shoham Baris: In identity-based signature schemes, the identity plays the role of the public key. So, if you wish, Alice may be seen as Alice's public key. For your second question, Faythe can be the TTP. $\endgroup$
    – user94293
    May 19, 2016 at 19:48

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.