August  2011, 5(3): 473-488. doi: 10.3934/amc.2011.5.473

Short one-time signatures

1. 

Certicom Research, 5520 Explorer Drive, Mississauga, ON L4W 5L1, Canada

2. 

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada

Received  July 2010 Revised  December 2010 Published  August 2011

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.
Citation: Gregory M. Zaverucha, Douglas R. Stinson. Short one-time signatures. Advances in Mathematics of Communications, 2011, 5 (3) : 473-488. doi: 10.3934/amc.2011.5.473
References:
[1]

N. Asokan, V. Shoup and M. Waidner, Optimistic fair exchange of digital signatures,, IEEE J. Selected Areas Commun., 18 (2000), 593. doi: 10.1109/49.839935. Google Scholar

[2]

G. Ateniese, Verifiable encryption of digital signatures and applications,, ACM Trans. Inform. Systems Security (TISSEC), 7 (2004), 1. doi: 10.1145/984334.984335. Google Scholar

[3]

M. Bellare, J. Garay and T. Rabin, Fast batch verification for modular exponentiation and digital signatures,, in, (1998), 236. Google Scholar

[4]

M. Bellare and S. Shoup, Two-tier signatures, strongly unforgeable signatures, and Fiat-Shamir without random oracles,, in, (2007), 201. Google Scholar

[5]

D. J. Bernstein, Pippenger's exponentiation algorithm,, manuscript, (). Google Scholar

[6]

K. Bicakci, C. Gamage, B. Crispo and A. S. Tanenbaum, One-time sensors: a novel concept to mitigate node-capture attacks,, in, (2005), 80. Google Scholar

[7]

K. Bicakci, G. Tsudik and B. Tung, How to construct optimal one-time signatures,, Computer Networks, 43 (2003), 339. doi: 10.1016/S1389-1286(03)00285-8. Google Scholar

[8]

D. Boneh, C. Gentry, B. Lynn and H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps,, in, (2003), 416. Google Scholar

[9]

D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing,, J. Cryptology, 17 (2004), 297. doi: 10.1007/s00145-004-0314-9. Google Scholar

[10]

J. Bos and D. Chaum, Provably unforgeable signatures,, in, (1992), 1. Google Scholar

[11]

J. Buchmann, E. Dahmen, E. Klintsevich, K. Okeya and C. Vuillaume, Merkle signatures with virtually unlimited signature capacity,, in, (2007), 31. Google Scholar

[12]

J. Camenisch and V. Shoup, Practical verifiable encryption and decryption of discrete logarithms,, in, (2003), 126. Google Scholar

[13]

J. Camenisch and M. Stadler, Proof systems for general statements about discrete logarithms,, Technical Report \textbf{TR 260}, TR 260 (1997). Google Scholar

[14]

R. Canetti, S. Halevi and J. Katz, Chosen-ciphertext security from identity-based encryption,, in, (2004), 207. Google Scholar

[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. doi: 10.1109/18.21214. Google Scholar

[16]

T. M. Cover, Enumerative source coding,, IEEE Trans. Inform. Theory, 19 (1973), 73. doi: 10.1109/TIT.1973.1054929. Google Scholar

[17]

R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack,, in, (1998), 13. Google Scholar

[18]

E. Dahmen and C. Krauß, Short hash-based signatures for wireless sensor networks,, in, (2009), 463. Google Scholar

[19]

W. Dai, Crypto++: a free C++ class library of cryptographic schemes,, \url{http://www.cryptopp.com/}, (2010). Google Scholar

[20]

I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model,, in, (2000), 418. Google Scholar

[21]

I. Damgård and M. Jurik, A generalisation, a simplification and some applications of Paillier's probabilistic public-key system,, in, (1992), 119. Google Scholar

[22]

C. Dods, N. P. Smart and M. Stam, Hash based digital signature schemes,, in, (2005), 96. doi: 10.1007/11586821_8. Google Scholar

[23]

S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures,, J. Cryptology, 9 (1996), 35. doi: 10.1007/BF02254791. Google Scholar

[24]

R. Genarro and P. Rohatgi, How to sign digital streams,, in, (1997), 180. Google Scholar

[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. doi: 10.1137/0217017. Google Scholar

[26]

J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures,, in, (2006), 444. Google Scholar

[27]

N. Gura, A. Patel, A. Wander, H. Eberle and S. C. Shantz, Comparing elliptic curve cryptography and RSA on 8-bit CPUs,, in, (2004), 118. Google Scholar

[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. doi: 10.1109/MCOM.2008.4689253. Google Scholar

[29]

J. Katz, Signature schemes with bounded leakage resilience,, IACR ePrint Archive Report 2009/220, (2009). Google Scholar

[30]

D. L. Kreher and D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search,'', CRC Press, (1999). Google Scholar

[31]

L. Lamport, Constructing digital signatures from a one-way function,, Technical Report CSL-98, (1979). Google Scholar

[32]

M. Luk, A. Perrig and B. Whillock, Seven cardinal properties of sensor network broadcast authentication,, in, (2006), 147. Google Scholar

[33]

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, "Handbook of Applied Cryptography,'', CRC Press LLC, (1996). doi: 10.1201/9781439821916. Google Scholar

[34]

R. Merkle, A certified digital signature,, in, (1989), 218. Google Scholar

[35]

P. Mohassel, One-time signatures and Chameleon hash functions,, in, (2011), 302. Google Scholar

[36]

D. Naor, A. Shenhav and A. Wool, One-time signatures revisited: have they become practical?,, IACR ePrint Archive Report 2005/442, (2005). Google Scholar

[37]

National Institute of Standards and Technology, Digital signature standard (DSS),, FIPS PUB, 186-2 (2000), 186. Google Scholar

[38]

P. Paillier, Public-key cryptosystems based on composite residuosity classes,, in, (1999), 223. Google Scholar

[39]

P. Paillier and D. Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log,, in, (2005), 1. Google Scholar

[40]

T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing,, in, (1992), 129. Google Scholar

[41]

A. Perrig, The BiBa one time signature and broadcast authentication protocol,, in, (2001), 28. Google Scholar

[42]

J. Pieprzyk, H. Wang and C. Xing, Multiple-time signature schemes against chosen message attacks,, in, (2003), 88. Google Scholar

[43]

M. O. Rabin, Digitalized signatures,, in, (1978), 155. Google Scholar

[44]

L. Reyzin and N. Reyzin, New York: better than BiBa: short one-time signatures with fast signing and verifying,, in, (2002), 144. Google Scholar

[45]

P. Rohatgi, A compact and fast hybrid signature scheme for multicast packet authentication,, in, (1999), 93. Google Scholar

[46]

S. Rohde, T. Eisenbarth, E. Dahmen, J. Buchmann and C. Paar, Fast hash-based signatures on constrained devices,, in, (2008), 104. Google Scholar

[47]

E. Sperner, Ein satz uber untermengen einer endliche menge,, Math. Zeit., 27 (1928), 544. doi: 10.1007/BF01171114. Google Scholar

[48]

D. R. Stinson and R. Wei, Generalized cover-free families,, Disc. Math., 279 (2004), 463. doi: 10.1016/S0012-365X(03)00287-5. Google Scholar

[49]

D. R. Stinson, R. Wei and L. Zhu, Some new bounds for cover-free families,, J. Combin. Theory Ser. A, 90 (2000), 224. doi: 10.1006/jcta.1999.3036. Google Scholar

[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, (2008), 305. Google Scholar

[51]

E. van Heyst and T. P. Pedersen, How to make efficient fail-stop signatures,, in, (1993), 366. Google Scholar

show all references

References:
[1]

N. Asokan, V. Shoup and M. Waidner, Optimistic fair exchange of digital signatures,, IEEE J. Selected Areas Commun., 18 (2000), 593. doi: 10.1109/49.839935. Google Scholar

[2]

G. Ateniese, Verifiable encryption of digital signatures and applications,, ACM Trans. Inform. Systems Security (TISSEC), 7 (2004), 1. doi: 10.1145/984334.984335. Google Scholar

[3]

M. Bellare, J. Garay and T. Rabin, Fast batch verification for modular exponentiation and digital signatures,, in, (1998), 236. Google Scholar

[4]

M. Bellare and S. Shoup, Two-tier signatures, strongly unforgeable signatures, and Fiat-Shamir without random oracles,, in, (2007), 201. Google Scholar

[5]

D. J. Bernstein, Pippenger's exponentiation algorithm,, manuscript, (). Google Scholar

[6]

K. Bicakci, C. Gamage, B. Crispo and A. S. Tanenbaum, One-time sensors: a novel concept to mitigate node-capture attacks,, in, (2005), 80. Google Scholar

[7]

K. Bicakci, G. Tsudik and B. Tung, How to construct optimal one-time signatures,, Computer Networks, 43 (2003), 339. doi: 10.1016/S1389-1286(03)00285-8. Google Scholar

[8]

D. Boneh, C. Gentry, B. Lynn and H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps,, in, (2003), 416. Google Scholar

[9]

D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing,, J. Cryptology, 17 (2004), 297. doi: 10.1007/s00145-004-0314-9. Google Scholar

[10]

J. Bos and D. Chaum, Provably unforgeable signatures,, in, (1992), 1. Google Scholar

[11]

J. Buchmann, E. Dahmen, E. Klintsevich, K. Okeya and C. Vuillaume, Merkle signatures with virtually unlimited signature capacity,, in, (2007), 31. Google Scholar

[12]

J. Camenisch and V. Shoup, Practical verifiable encryption and decryption of discrete logarithms,, in, (2003), 126. Google Scholar

[13]

J. Camenisch and M. Stadler, Proof systems for general statements about discrete logarithms,, Technical Report \textbf{TR 260}, TR 260 (1997). Google Scholar

[14]

R. Canetti, S. Halevi and J. Katz, Chosen-ciphertext security from identity-based encryption,, in, (2004), 207. Google Scholar

[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. doi: 10.1109/18.21214. Google Scholar

[16]

T. M. Cover, Enumerative source coding,, IEEE Trans. Inform. Theory, 19 (1973), 73. doi: 10.1109/TIT.1973.1054929. Google Scholar

[17]

R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack,, in, (1998), 13. Google Scholar

[18]

E. Dahmen and C. Krauß, Short hash-based signatures for wireless sensor networks,, in, (2009), 463. Google Scholar

[19]

W. Dai, Crypto++: a free C++ class library of cryptographic schemes,, \url{http://www.cryptopp.com/}, (2010). Google Scholar

[20]

I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model,, in, (2000), 418. Google Scholar

[21]

I. Damgård and M. Jurik, A generalisation, a simplification and some applications of Paillier's probabilistic public-key system,, in, (1992), 119. Google Scholar

[22]

C. Dods, N. P. Smart and M. Stam, Hash based digital signature schemes,, in, (2005), 96. doi: 10.1007/11586821_8. Google Scholar

[23]

S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures,, J. Cryptology, 9 (1996), 35. doi: 10.1007/BF02254791. Google Scholar

[24]

R. Genarro and P. Rohatgi, How to sign digital streams,, in, (1997), 180. Google Scholar

[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. doi: 10.1137/0217017. Google Scholar

[26]

J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures,, in, (2006), 444. Google Scholar

[27]

N. Gura, A. Patel, A. Wander, H. Eberle and S. C. Shantz, Comparing elliptic curve cryptography and RSA on 8-bit CPUs,, in, (2004), 118. Google Scholar

[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. doi: 10.1109/MCOM.2008.4689253. Google Scholar

[29]

J. Katz, Signature schemes with bounded leakage resilience,, IACR ePrint Archive Report 2009/220, (2009). Google Scholar

[30]

D. L. Kreher and D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search,'', CRC Press, (1999). Google Scholar

[31]

L. Lamport, Constructing digital signatures from a one-way function,, Technical Report CSL-98, (1979). Google Scholar

[32]

M. Luk, A. Perrig and B. Whillock, Seven cardinal properties of sensor network broadcast authentication,, in, (2006), 147. Google Scholar

[33]

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, "Handbook of Applied Cryptography,'', CRC Press LLC, (1996). doi: 10.1201/9781439821916. Google Scholar

[34]

R. Merkle, A certified digital signature,, in, (1989), 218. Google Scholar

[35]

P. Mohassel, One-time signatures and Chameleon hash functions,, in, (2011), 302. Google Scholar

[36]

D. Naor, A. Shenhav and A. Wool, One-time signatures revisited: have they become practical?,, IACR ePrint Archive Report 2005/442, (2005). Google Scholar

[37]

National Institute of Standards and Technology, Digital signature standard (DSS),, FIPS PUB, 186-2 (2000), 186. Google Scholar

[38]

P. Paillier, Public-key cryptosystems based on composite residuosity classes,, in, (1999), 223. Google Scholar

[39]

P. Paillier and D. Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log,, in, (2005), 1. Google Scholar

[40]

T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing,, in, (1992), 129. Google Scholar

[41]

A. Perrig, The BiBa one time signature and broadcast authentication protocol,, in, (2001), 28. Google Scholar

[42]

J. Pieprzyk, H. Wang and C. Xing, Multiple-time signature schemes against chosen message attacks,, in, (2003), 88. Google Scholar

[43]

M. O. Rabin, Digitalized signatures,, in, (1978), 155. Google Scholar

[44]

L. Reyzin and N. Reyzin, New York: better than BiBa: short one-time signatures with fast signing and verifying,, in, (2002), 144. Google Scholar

[45]

P. Rohatgi, A compact and fast hybrid signature scheme for multicast packet authentication,, in, (1999), 93. Google Scholar

[46]

S. Rohde, T. Eisenbarth, E. Dahmen, J. Buchmann and C. Paar, Fast hash-based signatures on constrained devices,, in, (2008), 104. Google Scholar

[47]

E. Sperner, Ein satz uber untermengen einer endliche menge,, Math. Zeit., 27 (1928), 544. doi: 10.1007/BF01171114. Google Scholar

[48]

D. R. Stinson and R. Wei, Generalized cover-free families,, Disc. Math., 279 (2004), 463. doi: 10.1016/S0012-365X(03)00287-5. Google Scholar

[49]

D. R. Stinson, R. Wei and L. Zhu, Some new bounds for cover-free families,, J. Combin. Theory Ser. A, 90 (2000), 224. doi: 10.1006/jcta.1999.3036. Google Scholar

[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, (2008), 305. Google Scholar

[51]

E. van Heyst and T. P. Pedersen, How to make efficient fail-stop signatures,, in, (1993), 366. Google Scholar

[1]

Thais Bardini Idalino, Lucia Moura. Embedding cover-free families and cryptographical applications. Advances in Mathematics of Communications, 2019, 13 (4) : 629-643. doi: 10.3934/amc.2019039

[2]

David Galindo, Javier Herranz, Eike Kiltz. On the generic construction of identity-based signatures with additional properties. Advances in Mathematics of Communications, 2010, 4 (4) : 453-483. doi: 10.3934/amc.2010.4.453

[3]

Sanjit Chatterjee, Berkant Ustaoğlu. Malleability and ownership of proxy signatures: Towards a stronger definition and its limitations. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020015

[4]

Vincent Astier, Thomas Unger. Signatures, sums of hermitian squares and positive cones on algebras with involution. Electronic Research Announcements, 2018, 25: 16-26. doi: 10.3934/era.2018.25.003

[5]

Guofu Lu. Nonexistence and short time asymptotic behavior of source-type solution for porous medium equation with convection in one-dimension. Discrete & Continuous Dynamical Systems - B, 2016, 21 (5) : 1567-1586. doi: 10.3934/dcdsb.2016011

[6]

Jan Haškovec, Dietmar Oelz. A free boundary problem for aggregation by short range sensing and differentiated diffusion. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1461-1480. doi: 10.3934/dcdsb.2015.20.1461

[7]

Daniel Schnellmann. Typical points for one-parameter families of piecewise expanding maps of the interval. Discrete & Continuous Dynamical Systems - A, 2011, 31 (3) : 877-911. doi: 10.3934/dcds.2011.31.877

[8]

Patrick Martinez, Judith Vancostenoble. Exact controllability in "arbitrarily short time" of the semilinear wave equation. Discrete & Continuous Dynamical Systems - A, 2003, 9 (4) : 901-924. doi: 10.3934/dcds.2003.9.901

[9]

Hyung Ju Hwang, Thomas P. Witelski. Short-time pattern formation in thin film equations. Discrete & Continuous Dynamical Systems - A, 2009, 23 (3) : 867-885. doi: 10.3934/dcds.2009.23.867

[10]

Juan Pablo Maldonado López. Discrete time mean field games: The short-stage limit. Journal of Dynamics & Games, 2015, 2 (1) : 89-101. doi: 10.3934/jdg.2015.2.89

[11]

Naoki Sato, Toyohiko Aiki, Yusuke Murase, Ken Shirakawa. A one dimensional free boundary problem for adsorption phenomena. Networks & Heterogeneous Media, 2014, 9 (4) : 655-668. doi: 10.3934/nhm.2014.9.655

[12]

Shouchuan Hu, Xin Lu. Cover page and Preface. Conference Publications, 2015, 2015 (special) : i-i. doi: 10.3934/proc.2015.2015.si

[13]

Jun Hu, Oleg Muzician, Yingqing Xiao. Dynamics of regularly ramified rational maps: Ⅰ. Julia sets of maps in one-parameter families. Discrete & Continuous Dynamical Systems - A, 2018, 38 (7) : 3189-3221. doi: 10.3934/dcds.2018139

[14]

William Ott, Qiudong Wang. Periodic attractors versus nonuniform expansion in singular limits of families of rank one maps. Discrete & Continuous Dynamical Systems - A, 2010, 26 (3) : 1035-1054. doi: 10.3934/dcds.2010.26.1035

[15]

Lambertus A. Peletier, Willem de Winter, An Vermeulen. Dynamics of a two-receptor binding model: How affinities and capacities translate into long and short time behaviour and physiological corollaries. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 2171-2184. doi: 10.3934/dcdsb.2012.17.2171

[16]

Laura Cremaschi, Carlo Mantegazza. Short-time existence of the second order renormalization group flow in dimension three. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 5787-5798. doi: 10.3934/dcds.2015.35.5787

[17]

Giulio G. Giusteri, Alfredo Marzocchi, Alessandro Musesti. Nonlinear free fall of one-dimensional rigid bodies in hyperviscous fluids. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 2145-2157. doi: 10.3934/dcdsb.2014.19.2145

[18]

Marcel Oliver. The Lagrangian averaged Euler equations as the short-time inviscid limit of the Navier–Stokes equations with Besov class data in $\mathbb{R}^2$. Communications on Pure & Applied Analysis, 2002, 1 (2) : 221-235. doi: 10.3934/cpaa.2002.1.221

[19]

Ricardo Almeida. Optimality conditions for fractional variational problems with free terminal time. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 1-19. doi: 10.3934/dcdss.2018001

[20]

Shakoor Pooseh, Ricardo Almeida, Delfim F. M. Torres. Fractional order optimal control problems with free terminal time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 363-381. doi: 10.3934/jimo.2014.10.363

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]