Article

On the performance, feasibility, and use of forward-secure signatures

Authors:

Patrick McDanielAuthors Info & Claims

CCS '03: Proceedings of the 10th ACM conference on Computer and communications security

Pages 131 - 144

https://doi.org/10.1145/948109.948130

Published: 27 October 2003 Publication History

Abstract

Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures face with key exposure. However, no previous works have explored the practical performance of these proposed constructions in real-world applications, nor have they compared FSS to traditional, non-forward-secure, signatures in a non-asymptotic way.We present an empirical evaluation of several FSS schemes that looks at the relative performance among different types of FSS as well as between FSS and traditional signatures. Our study provides the following contributions: first, a new methodology for comparing the performance of signature schemes, and second, a thorough examination of the practical performance of FSS. We show that for many cases the best FSS scheme has essentially identical performance to traditional schemes, and even in the worst case is only 2-4 times slower. On the other hand, we also show that if the wrong FSS configuration is used, the performance can be orders of magnitude slower. Our methodology provides a way to prevent such misconfigurations, and we examine common applications of digital signatures using it.We conclude that not only are forward-secure signatures a useful theoretical construct as previous works have shown, but they are also, when used correctly, a very practical solution to some of the problems associated with key exposure in real-world applications. Through our metrics and our reference implementation we provide the tools necessary for developers to efficiently use FSS.

References

[1]

M. Abdalla and L. Reyzin. A new forward-secure digital signature scheme. Advances in Cryptology -- ASIACRYPT 2000, Lecture Notes in Computer Science, 1976:116--129, Dec. 2000.]]

Digital Library

[2]

R. Anderson. Two remarks on public-key cryptology From Invited Lecture, Fourth ACM Conference on Computer and Communications Security (April, 1997). http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-549.pdf.]]

[3]

ANSI X9.62-1998. Public key cryptography for the financial services industry: Rhe elliptic curve digital signature algorithm (ECDSA), 1998.]]

[4]

M. Bellare and S. K. Miner. A forward-secure digital signature scheme. Advances in Cryptology -- CRYPTO '99, Lecture Notes in Computer Science, 1666:431--448, Aug. 1999.]]

Digital Library

[5]

M. Bellare and B. S. Yee. Forward-security in private-key cryptography. In Topics in Cryptology - CT-RSA '03, The Cryptographers' Track at the RSA Conference 2003, 2003.]]

[6]

M. Blaze and J. Lacy. Simple Unix time quantization package, 1995. http://islab.oregonstate.edu/documents/People/blaze/quantize.shar.]]

[7]

J. N. Bos and D. Chaum. Provably unforgeable signatures. Advances in Cryptology -- CRYPTO '92, Lecture Notes in Computer Science, 740:1--14, 1993.]]

Digital Library

[8]

R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. In Proc. of the thirtieth annual ACM symposium on Theory of computing (STOC '98), 1998.]]

Digital Library

[9]

R. Canetti, S. Halevi, and J. Katz. A forward-secure public-key encryption scheme. In Proc. of the 21st Annual IACR Eurocrypt conference (EUROCRYPT '03), 2003.]]

[10]

Certicom Research. SEC 2: Recommended elliptic curve domain parameters, Sep. 2000. http://www.secg.org/secg_docs.htm.]]

[11]

G. D. Crescenzo, N. Ferguson, R. Impagliazzo, and M. Jakobsson. How to forget a secret. STACS '99, Lecture Notes in Computer Science, 1563:500--509, 1999.]]

[12]

T. Dierks and C. Allen. The TLS protocol. RFC 2246, IETF, January 1999.]]

[13]

W. Diffie and M. E. Hellman. Multiuser cryptographic techniques. In AFIPS Conference Proceedings, volume~45, pages 109--112, 1976.]]

Digital Library

[14]

W. Diffie, P. C. van Oorschot, and M. J. Wiener. Authentication and authenticated key exchanges. Designs, Codes, and Cryptography, 2(2), 1992.]]

Digital Library

[15]

Y. Dodis, J. Katz, S. Xu, and M. Yung. Key-insulated public key cryptosystems. In Proc. of the 20th Annual IACR Eurocrypt conference (EUROCRYPT '02), 2002.]]

Digital Library

[16]

Y. Dodis, J. Katz, S. Xu, and M. Yung. Strong key-insulated signature schemes. In Proc. of the 6th Annual International Workshop on Practice and Theory in Public Key Cryptography (PKC '03), 2003.]]

Digital Library

[17]

A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology - CRYPTO '86, Lecture Notes in Computer Science, 263:181--187, 1986.]]

[18]

L. C. Guillou and J.-J. Quisquater. A "paradoxical" identity-based signature scheme resulting from zero-knowledge. Advances in Cryptology -- CRYPTO '88, Lecture Notes in Computer Science, 403:216--231, Aug. 1988.]]

Digital Library

[19]

C. Gunther. An identity-based key-exchange protocol. In Proc. of the 7th Annual IACR Eurocrypt conference (EUROCRYPT '89), 1989.]]

Digital Library

[20]

P. Gutmann. Secure deletion of data from magnetic and solidstate memory. In Proceedings of 6th USENIX UNIX Security Symposium. USENIX Association, July 1996. San Jose, CA.]]

Digital Library

[21]

G. Itkis and L. Reyzin. Forward-secure signatures with optimal signing and verifying. Advances in Cryptology -- CRYPTO '01, Lecture Notes in Computer Science, 2139:332--354, Aug. 2001.]]

Digital Library

[22]

G. Itkis and L. Reyzin. SiBIR: Signer-base intrusion-resilient signatures. Advances in Cryptology -- CRYPTO '02, Lecture Notes in Computer Science, 2442, Aug. 2002.]]

Digital Library

[23]

B. Kaliski. Timing attacks on cryptosystems. RSA Bulletin, 2, January 1996.]]

[24]

P. C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. Advances in Cryptology -- CRYPTO '96, Lecture Notes in Computer Science, 1109:104--113, 1996.]]

Digital Library

[25]

A. Kozlov and L. Reyzin. Forward-secure signatures with fast key update. In Proc. of the 3rd International Conference on Security in Communication Networks (SCN '02), 2002.]]

Digital Library

[26]

H. Krawczyk. Simple forward-secure signatures from any signature scheme. In Proc. of Seventh ACM Conference on Computer and Communications Security, pages 108--115, Nov. 2000.]]

Digital Library

[27]

T. Malkin, D. Micciancio, and S. Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In Proc. of the 20th Annual IACR Eurocrypt conference (EUROCRYPT '02), 2002.]]

Digital Library

[28]

R. C. Merkle. A digital signature based on a conventional encryption function. Advances in Cryptology -- CRYPTO '89, Lecture Notes in Computer Science, pages 428--446, 1989.]]

[29]

National Institute of Standards and Technology. Digital signature standard, FIPS 186-2, 2000.]]

[30]

National Institute of Standards and Technology. Advanced encryption standard, FIPS 197, 2001.]]

[31]

NESSIE consortium. Portfolio of recommended cryptographic primitives, February 2003. http://www.cryptonessie.org.]]

[32]

H. Ong and C. P. Schnorr. Fast signature generation with a fiat-shamir-like scheme. In Proc. of the 8th Annual IACR Eurocrypt conference (EUROCRYPT '90), 1990.]]

Digital Library

[33]

N. Provos. Encrypting virtual memory. In Proceedings of the 9th USENIX Security Symposium, pages 35--44. USENIX Association, Aug. 2000. Denver, CO.]]

Digital Library

[34]

R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, Feb. 1978.]]

Digital Library

[35]

D. X. Song. Practical forward secure group signature schemes. In Proc. of the 8th ACM Conference on Computer and Communications Security (CCS '01), 2001.]]

Digital Library

[36]

The OpenSSL Group. OpenSLL, Oct 2003. http://http://www.openssl.org/.]]

[37]

J. Viega, M. Messier, and P. Chandra. Network Security with OpenSSL. O'Reilly & Associates, Inc., 2002.]]

Digital Library

[38]

M. J. Wiener. Performance comparison of public-key cryptosystems. CryptoBytes, 4(1), Summer 1998.]]

Cited By

Abou Haidar CPasselègue AStehlé D(2023)Efficient Updatable Public-Key Encryption from LatticesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_11(342-373)Online publication date: 18-Dec-2023
https://doi.org/10.1007/978-981-99-8733-7_11
Tackmann BVisconti IAnta AGeorgiou CHerlihy MPotop-Butucaru M(2022)Cryptographic Tools for BlockchainsPrinciples of Blockchain Systems10.1007/978-3-031-01807-7_1(1-25)Online publication date: 18-Mar-2022
https://doi.org/10.1007/978-3-031-01807-7_1
Xiang TLi XChen FMu YChen XWang XHuang X(2016)Bilateral-secure Signature by Key EvolvingProceedings of the 11th ACM on Asia Conference on Computer and Communications Security10.1145/2897845.2897864(523-533)Online publication date: 30-May-2016
https://dl.acm.org/doi/10.1145/2897845.2897864
Show More Cited By

Index Terms

On the performance, feasibility, and use of forward-secure signatures
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Forward-secure signatures in untrusted update environments: efficient and generic constructions
CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

Forward-secure signatures (FSS) prevent forgeries for past time periods when an attacker obtains full access to the signer's storage. To simplify the integration of these primitives into standard security architectures, Boyen, Shacham, Shen and Waters ...
Forward-secure signatures with untrusted update
CCS '06: Proceedings of the 13th ACM conference on Computer and communications security

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 (...
Forward-Secure Multi-signatures
ICDCIT '08: Proceedings of the 5th International Conference on Distributed Computing and Internet Technology

In many applications a document needs to be signed by more than one signer. When a signature depends on more than one signer we call it a multi-signature. Further, ordinary digital signatures have an inherent weakness: if the secret key is leaked, then ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '03: Proceedings of the 10th ACM conference on Computer and communications security

October 2003

374 pages

ISBN:1581137389

DOI:10.1145/948109

General Chair:
Sushil Jajodia
George Mason University
,
Program Chairs:
Vijay Atluri
Rutgers University
,
Trent Jaeger
IBM Watson

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS03

Sponsor:

SIGSAC

CCS03: Tenth ACM Conference on Computer and Communications Security 2003

October 27 - 30, 2003

Washington D.C., USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
1,461
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abou Haidar CPasselègue AStehlé D(2023)Efficient Updatable Public-Key Encryption from LatticesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_11(342-373)Online publication date: 18-Dec-2023
https://doi.org/10.1007/978-981-99-8733-7_11
Tackmann BVisconti IAnta AGeorgiou CHerlihy MPotop-Butucaru M(2022)Cryptographic Tools for BlockchainsPrinciples of Blockchain Systems10.1007/978-3-031-01807-7_1(1-25)Online publication date: 18-Mar-2022
https://doi.org/10.1007/978-3-031-01807-7_1
Xiang TLi XChen FMu YChen XWang XHuang X(2016)Bilateral-secure Signature by Key EvolvingProceedings of the 11th ACM on Asia Conference on Computer and Communications Security10.1145/2897845.2897864(523-533)Online publication date: 30-May-2016
https://dl.acm.org/doi/10.1145/2897845.2897864
Hülsing ABusold CBuchmann J(2013)Forward Secure Signatures on Smart CardsSelected Areas in Cryptography10.1007/978-3-642-35999-6_5(66-80)Online publication date: 2013
https://doi.org/10.1007/978-3-642-35999-6_5
Al Ebri NBaek JShoufan AVu Q(2012)Efficient Generic Construction of Forward-Secure Identity-Based SignatureProceedings of the 2012 Seventh International Conference on Availability, Reliability and Security10.1109/ARES.2012.53(55-64)Online publication date: 20-Aug-2012
https://dl.acm.org/doi/10.1109/ARES.2012.53
Rifà-Pous HHerrera-Joancomartí J(2011)Computational and Energy Costs of Cryptographic Algorithms on Handheld DevicesFuture Internet10.3390/fi30100313:1(31-48)Online publication date: 14-Feb-2011
https://doi.org/10.3390/fi3010031
Pirretti MTraynor PMcdaniel PWaters B(2010)Secure attribute-based systemsJournal of Computer Security10.5555/1841962.184196618:5(799-837)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/1841962.1841966
Libert BQuisquater JYung M(2010)Key Evolution Systems in Untrusted Update EnvironmentsACM Transactions on Information and System Security10.1145/1880022.188003113:4(1-34)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1145/1880022.1880031
Berbecaru DAlbertalli LLioy A(2010)The ForwardDiffsig scheme for multicast authenticationIEEE/ACM Transactions on Networking10.1109/TNET.2010.205292718:6(1855-1868)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/TNET.2010.2052927
Butler KFarley TMcDaniel PRexford J(2010)A Survey of BGP Security Issues and SolutionsProceedings of the IEEE10.1109/JPROC.2009.203403198:1(100-122)Online publication date: Jan-2010
https://doi.org/10.1109/JPROC.2009.2034031
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten