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.

[2]

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

[3]

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

[4]

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

[5]

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

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

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

[8]

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

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

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

[16]

T. M. Cover, Enumerative source coding,, IEEE Trans. Inform. Theory, 19 (1973), 73. 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, (1998), 13.

[18]

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

[19]

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

[20]

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

[21]

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

[22]

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

[23]

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

[24]

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

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

[26]

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

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

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

[29]

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

[30]

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

[31]

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

[32]

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

[33]

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

[34]

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

[35]

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

[36]

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

[37]

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

[38]

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

[39]

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

[40]

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

[41]

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

[42]

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

[43]

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

[44]

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

[45]

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

[46]

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

[47]

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

[48]

D. R. Stinson and R. Wei, Generalized cover-free families,, Disc. Math., 279 (2004), 463. 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. 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, (2008), 305.

[51]

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

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.

[2]

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

[3]

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

[4]

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

[5]

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

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

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

[8]

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

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

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

[16]

T. M. Cover, Enumerative source coding,, IEEE Trans. Inform. Theory, 19 (1973), 73. 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, (1998), 13.

[18]

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

[19]

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

[20]

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

[21]

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

[22]

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

[23]

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

[24]

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

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

[26]

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

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

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

[29]

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

[30]

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

[31]

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

[32]

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

[33]

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

[34]

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

[35]

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

[36]

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

[37]

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

[38]

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

[39]

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

[40]

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

[41]

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

[42]

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

[43]

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

[44]

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

[45]

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

[46]

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

[47]

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

[48]

D. R. Stinson and R. Wei, Generalized cover-free families,, Disc. Math., 279 (2004), 463. 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. 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, (2008), 305.

[51]

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

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Xulong Qin, Zheng-An Yao, Hongxing Zhao. One dimensional compressible Navier-Stokes equations with density-dependent viscosity and free boundaries. Communications on Pure & Applied Analysis, 2008, 7 (2) : 373-381. doi: 10.3934/cpaa.2008.7.373

[20]

Giulio G. Giusteri, Alfredo Marzocchi, Alessandro Musesti. Steady free fall of one-dimensional bodies in a hyperviscous fluid at low Reynolds number. Evolution Equations & Control Theory, 2014, 3 (3) : 429-445. doi: 10.3934/eect.2014.3.429

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]