Designated Verifier Signature Schemes: Attacks, New Security Notions and A New Construction

Helger Lipmaa, Guilin Wang and Feng Bao. Designated Verifier Signature Schemes: Attacks, New Security Notions and A New Construction. In Luis Caires, Guiseppe F. Italiano, Luis Monteiro, Catuscia Palamidessi and Moti Yung, editors, The 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005, volume 3580 of Lecture Notes in Computer Science, pages 459--471, Lisboa, Portugal, July 11--15, 2005. Springer, Heidelberg. 10.1007/11523468_38.

File: [.ps.bz2 (48 KB), .pdf (122 KB)] pdf recommended.

Abstract:

We show that the signer can abuse the disavowal protocol in the Jakobsson-Sako-Impagliazzo designated-verifier signature scheme. In addition, we identify a new security property---non-delegatability---that is essential for designated-verifier signatures, and show that several previously proposed designated-verifier schemes are delegatable. We give a rigorous formalisation of the security for designated-verifier signature schemes, and propose a new and efficient designated-verifier signature scheme that is provably unforgeable under a tight reduction to the Decisional Diffie-Hellman problem in the non-programmable random oracle model, and non-delegatable under a loose reduction in the programmable random oracle model. As a direct corollary, we also get a new efficient conventional signature scheme that is provably unforgeable under a tight reduction to the Decisional Diffie-Hellman problem in the non-programmable random oracle plus common reference string model.

Keywords: Designated verifier signature scheme, non-delegatability, non-programmable random oracle model, signature scheme.

Slides:

• Slides from Estonian Theory Days, Feb 4-6, 2005, Koke, Estonia
• Slides from seminar at University of Tartu, May 6 2005, Estonia
• Slides presented at ICALP 2005
• Slides presented at University College London, Feb 23, 2006, UK

Comment: Track C Security and Cryptography Foundations. Note that the proof that the new scheme is unforgeable (Thm 1) is slightly faulty. Namely, it gives less precise security reduction than claimed in the paper. The correct way to do it is to change the roles of Signy and Desmond in the proof, then the reduction will stay practically as precise. (The submitted version was correct, the exchange of Signy and Desmond was done in a hurry when preparing the final version. I became aware of the mistake before the conference and the conference slides point out the mistake.)

More information: Publisher Webpage.

DOI: 10.1007/11523468_38

• Helger Lipmaa
• Guilin Wang
• Feng Bao

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.