Short one-time signatures

Gregory M. Zaverucha; Douglas R. Stinson

doi:10.3934/amc.2011.5.473

Article Contents

2011, Volume 5, Issue 3: 473-488. Doi: 10.3934/amc.2011.5.473

This issue Previous Article Space-time block codes from nonassociative division algebras Next Article On the order bounds for one-point AG codes

Short one-time signatures

Gregory M. Zaverucha^1, and
Douglas R. Stinson^2,

1.
Certicom Research, 5520 Explorer Drive, Mississauga, ON L4W 5L1
2.
David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1

Received: June 30, 2010

Revised: November 30, 2010

Published: July 2011

Abstract Related Papers Cited by

Abstract

We present a new one-time signature scheme having short signatures. Our new scheme is also the first one-time signature scheme that supports aggregation, batch verification, and which admits efficient proofs of knowledge. It has a fast signing algorithm, requiring only modular additions, and its verification cost is comparable to ECDSA verification. These properties make our scheme suitable for applications on resource-constrained devices such as smart cards and sensor nodes.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 05B40.

Citation:

Related Papers

Cited by

References

[1]	N. Asokan, V. Shoup and M. Waidner, Optimistic fair exchange of digital signatures, IEEE J. Selected Areas Commun., 18 (2000), 593-610.doi: 10.1109/49.839935.
[2]	G. Ateniese, Verifiable encryption of digital signatures and applications, ACM Trans. Inform. Systems Security (TISSEC), 7 (2004), 1-20.doi: 10.1145/984334.984335.
[3]	M. Bellare, J. Garay and T. Rabin, Fast batch verification for modular exponentiation and digital signatures, in "Proceedings of EUROCRYPT '98,'' (1998), 236-250.
[4]	M. Bellare and S. Shoup, Two-tier signatures, strongly unforgeable signatures, and Fiat-Shamir without random oracles, in "Public Key Cryptography (PKC'07),'' (2007), 201-216.
[5]	D. J. Bernstein, Pippenger's exponentiation algorithm, manuscript, available online at http://cr.yp.to/papers.html#pippenger
[6]	K. Bicakci, C. Gamage, B. Crispo and A. S. Tanenbaum, One-time sensors: a novel concept to mitigate node-capture attacks, in "Proceedings of Security and Privacy in Ad-hoc and Sensor Networks (ESAS'05),'' (2005), 80-90.
[7]	K. Bicakci, G. Tsudik and B. Tung, How to construct optimal one-time signatures, Computer Networks, 43 (2003), 339-349.doi: 10.1016/S1389-1286(03)00285-8.
[8]	D. Boneh, C. Gentry, B. Lynn and H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in "Proceedings of EUROCRYPT '03,'' (2003), 416-432.
[9]	D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing, J. Cryptology, 17 (2004), 297-319.doi: 10.1007/s00145-004-0314-9.
[10]	J. Bos and D. Chaum, Provably unforgeable signatures, in "Proceedings of CRYPTO '92,'' (1992), 1-14.
[11]	J. Buchmann, E. Dahmen, E. Klintsevich, K. Okeya and C. Vuillaume, Merkle signatures with virtually unlimited signature capacity, in "Proceedings of Applied Cryptography and Network Security (ACNS'07),'' (2007), 31-45.
[12]	J. Camenisch and V. Shoup, Practical verifiable encryption and decryption of discrete logarithms, in "Proceedings of CRYPTO '03,'' (2003), 126-144.
[13]	J. Camenisch and M. Stadler, Proof systems for general statements about discrete logarithms, Technical Report TR 260, Institute for Theoretical Computer Science, ETH Zürich, 1997.
[14]	R. Canetti, S. Halevi and J. Katz, Chosen-ciphertext security from identity-based encryption, in "Proceedings of EUROCRYPT '04,'' (2004), 207-222.
[15]	B. Chor and R. Rivest, A knapsack-type public key cryptosystem based on arithmetic in finite fields, IEEE Trans. Inform. Theory, 34 (1988), 901-909.doi: 10.1109/18.21214.
[16]	T. M. Cover, Enumerative source coding, IEEE Trans. Inform. Theory, 19 (1973), 73-77.doi: 10.1109/TIT.1973.1054929.
[17]	R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in "Proceedings of CRYPTO'98,'' (1998), 13-25.
[18]	E. Dahmen and C. Krauß, Short hash-based signatures for wireless sensor networks, in "Proceedings of Cryptology and Network Security (CANS'09),'' (2009), 463-476.
[19]	W. Dai, Crypto++: a free C++ class library of cryptographic schemes, http://www.cryptopp.com/, accessed January 2010.
[20]	I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model, in "Proceedings of EUROCRYPT'00,'' (2000), 418-430.
[21]	I. Damgård and M. Jurik, A generalisation, a simplification and some applications of Paillier's probabilistic public-key system, in "Proceedings of PKC 2001,'' (1992), 119-136.
[22]	C. Dods, N. P. Smart and M. Stam, Hash based digital signature schemes, in "Proceedings of Cryptography and Coding 2005,'' (2005), 96-115.doi: 10.1007/11586821_8.
[23]	S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures, J. Cryptology, 9 (1996), 35-67.doi: 10.1007/BF02254791.
[24]	R. Genarro and P. Rohatgi, How to sign digital streams, in "Proceedings of CRYPTO '97,'' (1997), 180-197.
[25]	S. Goldwasser, S. Micali and R. L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput., 17 (1988), 281-308.doi: 10.1137/0217017.
[26]	J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in "Proceedings of ASIACRYPT'06,'' (2006), 444-459.
[27]	N. Gura, A. Patel, A. Wander, H. Eberle and S. C. Shantz, Comparing elliptic curve cryptography and RSA on 8-bit CPUs, in "Proceedings of CHES '04,'' (2004), 118-132.
[28]	F. Kargl, P. Papadimitratos, L. Buttyan, M. Müter, E. Schoch, B. Wiedersheim, T.-V. Thong, G. Calandriello, A. Held, A. Kung and J.-P. Hubaux, Secure vehicular communication systems: implementation, performance, and research challenges, IEEE Commun. Magazine, 46 (2008), 110-118.doi: 10.1109/MCOM.2008.4689253.
[29]	J. Katz, Signature schemes with bounded leakage resilience, IACR ePrint Archive Report 2009/220, available online at http://eprint.iacr.org/2009/220
[30]	D. L. Kreher and D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search,'' CRC Press, Boca Raton, FL, 1999.
[31]	L. Lamport, Constructing digital signatures from a one-way function, Technical Report CSL-98, SRI International, Palo Alto, 1979.
[32]	M. Luk, A. Perrig and B. Whillock, Seven cardinal properties of sensor network broadcast authentication, in "SASN '06: Proceedings of the fourth ACM Workshop on Security of ad hoc and Sensor Networks,'' ACM Press, (2006), 147-156.
[33]	A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, "Handbook of Applied Cryptography,'' CRC Press LLC, Boca Raton, FL, 1996.doi: 10.1201/9781439821916.
[34]	R. Merkle, A certified digital signature, in "Proceedings of CRYPTO '89,'' (1989), 218-238.
[35]	P. Mohassel, One-time signatures and Chameleon hash functions, in "Proceedings of Selected Areas in Cryptography (SAC'10),'' (2011), 302-319.
[36]	D. Naor, A. Shenhav and A. Wool, One-time signatures revisited: have they become practical?, IACR ePrint Archive Report 2005/442, available online at http://eprint.iacr.org/2005/442
[37]	National Institute of Standards and Technology, Digital signature standard (DSS), FIPS PUB, 186-2, (2000).
[38]	P. Paillier, Public-key cryptosystems based on composite residuosity classes, in "Proceedings of EUROCRYPT '99,'' (1999), 223-239.
[39]	P. Paillier and D. Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log, in "Proceedings of ASIACRYPT '05,'' (2005), 1-20.
[40]	T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in "Proceedings of CRYPTO'91,'' (1992), 129-140.
[41]	A. Perrig, The BiBa one time signature and broadcast authentication protocol, in "Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS '01),'' ACM Press, New York, (2001), 28-37.
[42]	J. Pieprzyk, H. Wang and C. Xing, Multiple-time signature schemes against chosen message attacks, in "Proceedings of SAC '03,'' (2003), 88-100.
[43]	M. O. Rabin, Digitalized signatures, in "Foundations of Secure Computation,'' Academic Press, New York, (1978), 155-168.
[44]	L. Reyzin and N. Reyzin, New York: better than BiBa: short one-time signatures with fast signing and verifying, in "Proceedings of ACISP '02,'' (2002), 144-153.
[45]	P. Rohatgi, A compact and fast hybrid signature scheme for multicast packet authentication, in "Proceedings of the 6th ACM Conference on Computer and Communications Security (CCS '99),'' ACM Press, New York, (1999), 93-100.
[46]	S. Rohde, T. Eisenbarth, E. Dahmen, J. Buchmann and C. Paar, Fast hash-based signatures on constrained devices, in "Proceedings of CARDIS'08,'' (2008), 104-117.
[47]	E. Sperner, Ein satz uber untermengen einer endliche menge, Math. Zeit., 27 (1928), 544-548.doi: 10.1007/BF01171114.
[48]	D. R. Stinson and R. Wei, Generalized cover-free families, Disc. Math., 279 (2004), 463-477.doi: 10.1016/S0012-365X(03)00287-5.
[49]	D. R. Stinson, R. Wei and L. Zhu, Some new bounds for cover-free families, J. Combin. Theory Ser. A, 90 (2000), 224-234.doi: 10.1006/jcta.1999.3036.
[50]	P. Szczechowiak, L. B. Oliveira, M. Scott, M. Collier and R. Dahab, NanoECC: testing the limits of elliptic curve cryptography in sensor networks, in "Proceedings of EWSN '08,'' (2008), 305-320.
[51]	E. van Heyst and T. P. Pedersen, How to make efficient fail-stop signatures, in "Proceedings of EUROCRYPT '92,'' (1993), 366-377.