Forward-secure signatures with untrusted update

ABSTRACT

In most forward-secure signature constructions, a program that updates a user's private signing key must have full access to the private key. Unfortunately, these schemes are incompatible with several security architectures including Gnu Privacy Guard (GPG) and S/MIME, where the private key is encrypted under a user password as a "second factor" of security, in case the private key storage is corrupted, but the password is not.We introduce the concept of forward-secure signatures with untrusted update, where the key update can be performed on an encrypted version of the key. Forward secure signatures with untrusted update allow us to add forward security to signatures, while still keeping passwords as a second factor of security. We provide a construction that has performance characteristics comparable with the best existing forward-secure signatures. In addition, we describe how to modify the Bellare-Miner forward secure signature scheme to achieve untrusted update.

REFERENCES

• 1: Michel Abdalla , Sara K. Miner , Chanathip Namprempre, Forward-Secure Threshold Signature Schemes, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.441-456, April 08-12, 2001
• 2: Michel Abdalla , Leonid Reyzin, A New Forward-Secure Digital Signature Scheme, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.116-129, December 03-07, 2000
• 3: Ross Anderson. Invited Lecture. 4th ACM Computer and Communications Security, 1997.
• 4: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 5: Dan Boneh and Xavier Boyen. Efficient selective-id secure identity-based encryption without random oracles. In EUROCRYPT, pages 223--238, 2004.
• 6: Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. In Advances in Cryptology---EUROCRYPT 2005, volume 3494 of Lecture Notes in Computer Science, pages 440--456. Berlin: Springer-Verlag, 2005.
• 7: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 8: Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. In EUROCRYPT, pages 255--271, 2003.
• 9: Eric Cronin , Sugih Jamin , Tal Malkin , Patrick McDaniel, On the performance, feasibility, and use of forward-secure signatures, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948130]
• 10: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Key-Insulated Public Key Cryptosystems, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.65-82, May 02, 2002
• 11: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Strong Key-Insulated Signature Schemes, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.130-144, January 06-08, 2003
• 12: Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems.
• 13: Steven Galbraith. Pairings. In IanF. Blake, Gadiel Seroussi, and Nigel Smart, editors, Advances in Elliptic Curve Cryptography, volume 317 of London Mathematical Society Lecture Notes, chapterIX, pages 183--213. Cambridge University Press, 2005.
• 14: Craig Gentry , Alice Silverberg, Hierarchical ID-Based Cryptography, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.548-566, December 01-05, 2002
• 15: Louis C. Guillou , Jean-Jacques Quisquater, A "Paradoxical" Indentity-Based Signature Scheme Resulting from Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.216-231, August 21-25, 1988
• 16: Christoph G. Günther, An identity-based key-exchange protocol, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.29-37, November 1990, Houthalen, Belgium
• 17: Jeremy Horwitz , Ben Lynn, Toward Hierarchical Identity-Based Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.466-481, May 02, 2002
• 18: Gene Itkis, Robert McNerney, and Scott Russell. Intrusion-resilient secure channels. In ACNS, pages 238--253, 2005.
• 19: Gene Itkis , Leonid Reyzin, Forward-Secure Signatures with Optimal Signing and Verifying, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.332-354, August 19-23, 2001
• 20: Gene Itkis , Leonid Reyzin, SiBIR: Signer-Base Intrusion-Resilient Signatures, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.499-514, August 18-22, 2002
• 21: Anton Kozlov and Leonid Reyzin. Forward-secure signatures with fast key update. In SCN, pages 241--256, 2002.
• 22: Hugo Krawczyk, Simple forward-secure signatures from any signature scheme, Proceedings of the 7th ACM conference on Computer and communications security, p.108-115, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352617]
• 23: Ben Laurie and Nicholas Bohm. Signatures: An interface between law and technology, January 2003. Online: http://www.apache-ssl.org/tech-legal.pdf.
• 24: Ben Lynn. PBC library. Online: http://rooster.stanford.edu/ben/pbc/.
• 25: Tal Malkin , Daniele Micciancio , Sara K. Miner, Efficient Generic Forward-Secure Signatures with an Unbounded Number Of Time Periods, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.400-417, May 02, 2002
• 26: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 27: Shigeo Mitsunari, Ryuichi Sakai, and Masao Kasahara. A new traitor tracing. IEICE Transactions on Fundamentals, E850A(2):481--484, 2002.
• 28: H. Ong , C. P. Schnorr, Fast signature generation with a Fiat Shamir—like scheme, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.432-440, February 1991, Aarhus, Denmark
• 29: Kenneth Paterson. Cryptography from pairings. In Ian F. Blake, Gadiel Seroussi, and Nigel Smart, editors, Advances in Elliptic Curve Cryptography, volume 317 of London Mathematical Society Lecture Notes, chapterX, pages 215--51. Cambridge University Press, 2005.
• 30: GMP Project. The Gnu multiprecision arithmetic library. Online: http://www.swox.com/gmp/.
• 31: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 32: Dawn Xiaodong Song, Practical forward secure group signature schemes, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502015]
• 33: Brent Waters. Efficient identity-based encryption without random oracles. In EUROCRYPT, pages 114--127, 2005.
• 34: Philip R. Zimmermann, The official PGP user's guide, MIT Press, Cambridge, MA, 1995

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Performance, Security

Keywords:
digital signatures, forward security, two-factor authentication, untrusted storage