Article Contents
Article Contents

# Short one-time signatures

• 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.
Mathematics Subject Classification: Primary: 94A60; Secondary: 05B40.

 Citation:

•  [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.