Provably secure server-aided verification signatures

A server-aided verification signature scheme consists of a digital signature scheme and a server-aided verification protocol. With the server-aided verification protocol, some computational tasks for a signature verification are carried out by a server, which is generally untrusted; therefore, it is very useful for low-power computational devices. In this paper, we first define three security notions for server-aided verification signatures, i.e., existential unforgeability, security against collusion attacks and security against strong collusion attacks. The definition of existential unforgeability includes the existing security requirements in server-aided verification signatures. We then present, on the basis of existing signature schemes, two novel existentially unforgeable server-aided verification signature schemes. The existential unforgeability of our schemes can be formally proved both without the random oracle model and using the random oracle model. We also consider the security of server-aided verification signatures under collusion attacks and strong collusion attacks. For the first time, we formally define security models for capturing (strong) collusion attacks, and propose concrete server-aided verification signature schemes that are secure against such attacks.