Deniable RSA Signature | SpringerLink
Skip to main content
Springer Nature Link
Log in

Deniable RSA Signature

The Raise and Fall of Ali Baba

  • Chapter
Cryptography and Security: From Theory to Applications

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 6805))

  • 1994 Accesses

Abstract

The 40 thieves realize that the fortune in their cave is vanishing. A rumor says that Ali Baba has been granted access (in the form of a certificate) to the cave but they need evidence to get justice from the Caliph. On the other hand, Ali Baba wants to be able to securely access to the cave without leaking any evidence. A similar scenario holds in the biometric passport application: Ali Baba wants to be able to prove his identity securely but do not want to leak any transferable evidence of, say, his date of birth.

In this paper we discuss the notion of offline non-transferable authentication protocol (ONTAP). We review a construction based on the GQ protocol which could accommodate authentication based on any standard RSA certificate. We also discuss on the fragility of this deniability property with respect to set up assumptions. Namely, if tamper resistance exist, any ONTAP protocol in the standard model collapses.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Machine Readable Travel Documents. PKI for Machine Readable Travel Documents offering ICC Read-Only Access. Version 1.1. International Civil Aviation Organization (2004), http://www.icao.int/mrtd/download/technical.cfm

  2. Baek, J., Safavi-Naini, R., Susilo, W.: Universal Designated Verifier Signature Proof (or How to Efficiently Prove Knowledge of a Signature). In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 644–661. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  3. Bellare, M., Palacio, A.: GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 162–177. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. Bellare, M., Ristov, T.: Hash Functions from Sigma Protocols and Improvements to VSH. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 125–142. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  5. Brassard, G., Chaum, D., Crépeau, C.: Minimum Disclosure Proofs of Knowledge. Journal of Computer and System Sciences 37, 156–189 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  6. Camenisch, J.L., Michels, M.: Confirmer Signature Schemes Secure against Adaptive Adversaries (Extended Abstract). In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 243–258. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  7. Chaum, D.: Designated Confirmer Signatures. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 86–91. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  8. Chaum, D., van Antwerpen, H.: Undeniable signatures. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 212–217. Springer, Heidelberg (1990)

    Google Scholar 

  9. Cramer, R., Damgård, I.B., MacKenzie, P.D.: Efficient Zero-Knowledge Proofs of Knowledge without Intractability Assumptions. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 354–373. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  10. Desmedt, Y.: Subliminal-free authentication and signature(Extended Abstract). In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 23–33. Springer, Heidelberg (1988)

    Google Scholar 

  11. Dolev, D., Dwork, C., Naor, M.: Nonmalleable Cryptography. SIAM Reviews 45(4), 727–784 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)

    Google Scholar 

  13. Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing but their Validity or all Languages in NP have Zero-Knowledge Proof Systems. Communications of the ACM 38, 690–728 (1991)

    MathSciNet  Google Scholar 

  14. Guillou, L.C., Quisquater, J.-J.: A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123–128. Springer, Heidelberg (1988)

    Google Scholar 

  15. Guillou, L.C., Quisquater, J.-J.: A Paradoxical Identity-Based Signature Scheme Resulting from Zero-Knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 216–231. Springer, Heidelberg (1990)

    Google Scholar 

  16. Jakobsson, M., Sako, K., Impagliazzo, R.: Designated Verifier Proofs and Their Applications. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 143–154. Springer, Heidelberg (1996)

    Google Scholar 

  17. Monnerat, J., Pasini, S., Vaudenay, S.: Efficient Deniable Authentication for Signatures: Application to Machine-Readable Travel Document. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 272–291. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  18. Mateus, P., Vaudenay, S.: On Privacy Losses in the Trusted Agent Model. Presented at the EUROCRYPT 2009 Conference (2009), http://eprint.iacr.org/2009/286.pdf

  19. Mateus, P., Vaudenay, S.: On Tamper-Resistance from a Theoretical Viewpoint. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 411–428. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  20. Monnerat, J., Vaudenay, S., Vuagnoux, M.: About Machine-Readable Travel Documents: Privacy Enhancement Using (Weakly) Non-Transferable Data Authentication. In: International Conference on RFID Security 2007, pp. 13–26. University of Malaga, Malaga (2008)

    Google Scholar 

  21. Okamoto, T., Ohta, K.: How to Utilize the Randomness of Zero-Knowledge Proofs. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 456–475. Springer, Heidelberg (1991)

    Google Scholar 

  22. Pass, R.: On deniability in the common reference string and random oracle model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 316–337. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  23. Quisquater, J.-J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G., Guillou, S., Berson, T.A.: How to Explain Zero-Knowledge Protocols to Your Children. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 628–631. Springer, Heidelberg (1990)

    Google Scholar 

  24. Schnorr, C.-P.: Efficient Identification and Signatures for Smart Cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)

    Google Scholar 

  25. Schnorr, C.-P.: Efficient Signature Generation by Smart Cards. Journal of Cryptology 4, 161–174 (1991)

    Article  MATH  Google Scholar 

  26. Shahandashti, S.F., Safavi-Naini, R., Baek, J.: Concurrently-Secure Credential Ownership Proofs. In: ACM Symposium on Information, Computer and Communications Security (ASIACCS 2007), pp. 161–172. ACM Press, Singapore (2007)

    Chapter  Google Scholar 

  27. Steinfeld, R., Bull, L., Wang, H., Pieprzyk, J.: Universal Designated-Verifier Signatures. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 523–542. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  28. Vaudenay, S.: E-Passport Threats. IEEE Security & Privacy 5(6), 61–64 (2007)

    Article  Google Scholar 

  29. Vaudenay, S.: La Fracture Cryptographique, Focus Science, Presses Polytechniques et Universitaires Romandes (2010)

    Google Scholar 

  30. Vaudenay, S., Vuagnoux, M.: About Machine-Readable Travel Documents. Journal of Physics: Conference Series 77(012006) (2007), http://www.iop.org/EJ/article/1742-6596/77/1/012006/jpconf7i_77_012006.pdf

Download references

Author information

Authors and Affiliations

  1. EPFL, CH-1015, Lausanne, Switzerland

    Serge Vaudenay

Authors
  1. Serge Vaudenay
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Département d’informatique, École normale supérieure, 45 Rue d’Ulm, 75231, Paris Cedex 05, France

    David Naccache

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Vaudenay, S. (2012). Deniable RSA Signature. In: Naccache, D. (eds) Cryptography and Security: From Theory to Applications. Lecture Notes in Computer Science, vol 6805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28368-0_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-28368-0_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-28367-3

  • Online ISBN: 978-3-642-28368-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation