Paper 2005/410

Short (resp. Fast) CCA2-Fully-Anonymous Group Signatures using IND-CPA-Encrypted Escrows

Victor K. Wei

Abstract

In the newest and strongest security models for group signatures \cite{BMW03,BellareShZh05,KiayiasYu04}, attackers are given the capability to query an Open Oracle, $\oo$, in order to obtain the signer identity of the queried signature. This oracle mirrors the Decryption Oracle in security experiments involving encryption schemes, and the security notion of CCA2-full-anonymity for group signatures mirrors the security notion of IND-CCA2-security for encryption schemes. Most group signatures escrows the signer identity to a TTP called the {\em Open Authority (OA)} by encrypting the signer identity to OA. Methods to efficiently instantiate $O(1)$-sized CCA2-fully-anonymous group signatures using IND-CCA2-secure encryptions, such as the Cramer-Shoup scheme or the twin encryption scheme, exist \cite{BMW03,BellareShZh05,KiayiasYu04,NguyenSN04}. However, it has long been suspected that IND-CCA2-secure encryption to OA is an overkill, and that CCA2-fully-anonymous group signature can be constructed using only IND-CPA-secure encryptions. Here, we settle this issue in the positive by constructing CCA2-fully-anonymous group signatures from IND-CPA-secure encryptions for the OA, without ever using IND-CCA2-secure encryptions. Our technique uses a single ElGamal or similar encryption plus Dodis and Yampolskiy \cite{DodisYa05}'s VRF (Verifiable Random Function). The VRF provides a sound signature with zero-knowledge in both the signer secret and the signer identity, while it simultaneously defends active $\oo$-query attacks. The benefits of our theoretical advance is improved efficiency. Instantiations in pairings result in the shortest CCA2-fully-anonymous group signature at 11 rational points or $\approx 1870$ bits for 170-bit curves. It is 27\% shorter (and slightly faster) than the previous fastest \cite{BBS04,KiayiasYu04} at 15 rational points. Instantiations in the strong RSA framework result in the fastest CCA2-fully-anonymous group signature at 4 multi-base exponentiations for 1024-bit RSA. It is 25\% faster than the previous fastest at 5 multi-base exponentiations \cite{ACJT00,CL02,KiayiasYu04}.