Doubly enhanced certified TDP ⇒ Group signatures (BMW)
Statement
If doubly enhanced certified trapdoor permutations exist, then there is a group signature scheme that is fully anonymous and fully traceable — BMW03. The construction combines an IND-CCA-secure PKE scheme, an adaptively sound simulation-sound NIZK proof system for and an EUF-CMA signature scheme, each known from doubly enhanced certified trapdoor permutations (IND-CCA encryption from IND-CPA encryption and NIZK: CPA-secure PKE + NIZK ⇒ CCA2-secure PKE — DDN91, Sah99) — BMW03, GR13. NIZK proofs for are known from trapdoor permutations that are doubly enhanced and certified (Doubly enhanced certified TDP ⇒ NIZK) — FLS90; the hidden-bits construction uses the double enhancement — GR13 — and, against indices a cheating prover chooses, certification — BY96, CL18.
Notes
- Keys have length polynomial in and , and signatures polynomial in , and the message length, where is the number of members (the scheme is compact) — BMW03.
- Conversely, group signatures imply public-key encryption (Group signatures ⇒ PKE) — AW04, whereas digital signatures follow from one-way functions (OWF ⇒ DS) — Rom90.