server-aided signatures verification secure against collusion attack
Wireless handheld devices which support e-mail and web browsing are increasingly popular. The authenticity of the information received is important, especially for business uses. In server-aided verification (SAV), a substantial part of the verification computation can be offloaded to a powerful but possibly untrusted server. This allows resource-constrained devices to enjoy the security guarantees provided by cryptographic schemes, such as pairing-based signatures, which may be too heavyweight to verify otherwise. To gain unfair advantage, an adversary may bribe the server to launch various kinds of attacks --- to convince that an invalid signature held by a client is a valid one (say for providing false information or repudiable commitment) or to claim that a valid signature is invalid (say for spoiling the offer provided by an opponent). However, these concerns are not properly captured by existing security models. In this paper, we provide a generic pairing-based SAV protocol. Compared with the protocol of Girault and Lefranc in Asiacrypt '05, ours provides a higher level of security yet applicable to a much wider class of pairing-based cryptosystems. In particular, it suggests SAV protocols for short signatures in the standard model and aggregate signatures which have not been studied before.
signatures collusion attack authenticity weak computational device delegation server-aided computation pairings