Advanced Search
Article Contents
Article Contents

Short one-time signatures

Abstract Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • [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.


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


    M. Bellare, J. Garay and T. Rabin, Fast batch verification for modular exponentiation and digital signatures, in "Proceedings of EUROCRYPT '98,'' (1998), 236-250.


    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.


    D. J. BernsteinPippenger's exponentiation algorithm, manuscript, available online at http://cr.yp.to/papers.html#pippenger


    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.


    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.


    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.


    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.


    J. Bos and D. Chaum, Provably unforgeable signatures, in "Proceedings of CRYPTO '92,'' (1992), 1-14.


    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.


    J. Camenisch and V. Shoup, Practical verifiable encryption and decryption of discrete logarithms, in "Proceedings of CRYPTO '03,'' (2003), 126-144.


    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.


    R. Canetti, S. Halevi and J. Katz, Chosen-ciphertext security from identity-based encryption, in "Proceedings of EUROCRYPT '04,'' (2004), 207-222.


    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.


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


    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.


    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.


    W. Dai, Crypto++: a free C++ class library of cryptographic schemes, http://www.cryptopp.com/, accessed January 2010.


    I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model, in "Proceedings of EUROCRYPT'00,'' (2000), 418-430.


    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.


    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.


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


    R. Genarro and P. Rohatgi, How to sign digital streams, in "Proceedings of CRYPTO '97,'' (1997), 180-197.


    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.


    J. Groth, Simulation-sound NIZK proofs for a practical language and constant size group signatures, in "Proceedings of ASIACRYPT'06,'' (2006), 444-459.


    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.


    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.


    J. Katz, Signature schemes with bounded leakage resilience, IACR ePrint Archive Report 2009/220, available online at http://eprint.iacr.org/2009/220


    D. L. Kreher and D. R. Stinson, "Combinatorial Algorithms: Generation, Enumeration and Search,'' CRC Press, Boca Raton, FL, 1999.


    L. Lamport, Constructing digital signatures from a one-way function, Technical Report CSL-98, SRI International, Palo Alto, 1979.


    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.


    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.


    R. Merkle, A certified digital signature, in "Proceedings of CRYPTO '89,'' (1989), 218-238.


    P. Mohassel, One-time signatures and Chameleon hash functions, in "Proceedings of Selected Areas in Cryptography (SAC'10),'' (2011), 302-319.


    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


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


    P. Paillier, Public-key cryptosystems based on composite residuosity classes, in "Proceedings of EUROCRYPT '99,'' (1999), 223-239.


    P. Paillier and D. Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log, in "Proceedings of ASIACRYPT '05,'' (2005), 1-20.


    T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in "Proceedings of CRYPTO'91,'' (1992), 129-140.


    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.


    J. Pieprzyk, H. Wang and C. Xing, Multiple-time signature schemes against chosen message attacks, in "Proceedings of SAC '03,'' (2003), 88-100.


    M. O. Rabin, Digitalized signatures, in "Foundations of Secure Computation,'' Academic Press, New York, (1978), 155-168.


    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.


    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.


    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.


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


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


    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.


    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.


    E. van Heyst and T. P. Pedersen, How to make efficient fail-stop signatures, in "Proceedings of EUROCRYPT '92,'' (1993), 366-377.

  • 加载中

Article Metrics

HTML views() PDF downloads(154) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint