International Association
for Cryptologic Research

Updatable Signature (US) schemes allow updating signatures so that they can be verified using a new key. This updating feature is useful for key rotation in practice. Cini et al. (PKC'21) first formalised this primitive. However, their post-quantum-secure US scheme does not satisfy their security definition, i.e., without unlinkability and only bounded unforgeability. This paper aims to solve this problem by providing a new fully secure construction. First, we simplify the definition of unlinkability by a hybrid argument, and reduce the update oracle of the unforgeability experiment by assuming unlinkability. Then, we construct our US scheme from verifiable encryption and the SIS assumption. This scheme is fully unlinkable and unforgeable, but also a unique signature scheme in each epoch, allowing only one signature for each message during one epoch and rendering a stateful signer/proxy. This is sufficient for many applications.