GAO Wen, HU Yupu, WANG Baocang, CHEN Jiangshan, WANG Xin. Efficient Ring Signature Scheme Without Random Oracle from Lattices[J]. Chinese Journal of Electronics, 2019, 28(2): 266-272. doi: 10.1049/cje.2018.12.005
Citation: GAO Wen, HU Yupu, WANG Baocang, CHEN Jiangshan, WANG Xin. Efficient Ring Signature Scheme Without Random Oracle from Lattices[J]. Chinese Journal of Electronics, 2019, 28(2): 266-272. doi: 10.1049/cje.2018.12.005

Efficient Ring Signature Scheme Without Random Oracle from Lattices

doi: 10.1049/cje.2018.12.005
Funds:  This work is supported by the National Natural Science Foundations of China(No.61472309, No.61572390, No.61672412), National Cryptography Development Fund (No.MMJJ20170104) and Provincial Natural Science Foundation Research Project of Shaanxi (No.2017JQ6029).
  • Received Date: 2016-03-07
  • Rev Recd Date: 2018-05-02
  • Publish Date: 2019-03-10
  • Among post-quantum alternatives, latticebased cryptography is the most promising one, due to its simple operations, reduction from aver-age-case to worstcase hardness, and supporting of rich functionalities. Ring signature enables a user to sign anonymously on behalf of an adaptively chosen group, and has multiple applications in anonymous e-voting, anonymous authentication, whistle blowing etc. However, most lattice-based ring signature schemes were constructed in the random oracle model from lattice basis delegation and they suffer large verification key sizes as a common disadvantage. This work proposes an efficient ring signature scheme from lattice basis delegation without random oracle based on the extended split-SIS problem, whose security is approximately as hard as the worst-case SIVP problem. Our scheme is proved to be anonymous and existentially unforgeable under latticebased assumptions. Finally, the verification key size is significantly reduced to a small constant, instead of increasing linearly with the number of ring members.
  • loading
  • C. L. Rivest, A. Shamir and Y. Tauman, “How to leak a secret”, P rocofASIACRY P T ’01, Gold Coast, Australia, pp.552-565, 2001.
    M. Abe, M. Ohkubo and K. Suzuki, “1-out-of-n signature from a variety of keys”, Proc of ASIACRYPT’ 02, Queenstown, New Zealand, pp.415-432, 2002.
    J. Herranz and G. Sáez, “Forking lemmas for ring signature schemes”, Proc of INDOCRYPT’ 03, New Delhi, India, pp.266-279, 2003.
    Y. Dodis, A. Kiayias, A. Nicolosi, et al., “Anonymous identification in ad-hoc groups”, Proc of EUROCRYPT’ 04, Interlaken, Switzerland, pp.609-626, 2004.
    F. Zhang, N. R. Safavi and W. Susilo, “An efficient signature scheme from bilinear pairings and its applications”, Proc of PKC’ 04, Singapore, pp.277-290, 2004.
    A. K. Awasthi and L. Sunder, “ID-based ring signature and proxy ring signature schemes from bilinear pairings”,, 2004
    A. Bender, J. Katz and R. Morselli, “Ring signatures: Stronger definitions, and constructions without random oracles”, Proc. of TCC’ 06, New York, USA, pp.60-79, 2006.
    H. Shacham and B. Waters, “Efficient ring signature without random oracles”, Proc of PKC’ 07, Beijing, China, pp.166-180, 2007.
    X. Boyen, “Mesh signatures”, Proc of EUROCRYPT’ 07, Barcelona, Spain, pp.210-227, 2007.
    X. Boyen, “Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more”, Proc of PKC’ 10, Paris, France, pp.499-517, 2010.
    L. Nguyen, “Accumulator from bilinear pairings and application to ID-based ring signatures and group membership revocation”, Proc of CT-RSA’ 05, San Francisco, CA, USA, pp.275-292, 2005.
    Z. Brakerski and Y. T. Kalai, “A framework for efficient signatures, ring signatures and identity based encryption in the standard model”,, 2010.
    F. Wang, Y. Hu and C. Wang, “A lattice-based ring signature scheme from bonsai trees”, Journal of Electronics and Information Technology, Vol.32, No.2, pp.2400-2403, 2010.
    J. Wang and B. Sun, “Ring signature schemes from lattice basis delegation”, Proc of ICICS’ 11, Singapore, pp.15-28,2011.
    S. Wang and R. Zhao, “Lattice-based ring signature scheme under the random oracle Model”,, 2013.
    C. A. Melchor, S. Bettaieb, X. Boyen, et al., “Adapting lyubashevsky’ s signature schemes to the ring signature setting”, Proc of AFRICACRYPT’ 13, Cairo, Egypt, pp.1-25, 2013.
    P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Rev., Vol.41, No.2, pp.303-332, 1997.
    D. Micciancio and C. Peikert, “Trapdoors for lattices: simpler, tighter, faster, smaller”, Proc of EUROCRYPT’ 12, Cambridge, UK, pp.700-718, 2012
    V. Lyubashevsky, “Towards practical lattice-based cryptography”, PhD thesis, University of California, San Diego, California, USA, 2008.
    M. Ajtai, “Generating hard instances of lattice problems (extended abstract)”, Proc of STOC’ 96, Philadephia, Pennsylvania, USA, pp.99-108, 1996.
    O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, Proc of STOC’ 05, Baltimore, MD, USA, pp.84-93, 2005.
    C. Gentry, C. Peikert and V. Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions”, Proc of STOC’ 08, Victoria, British Columbia, Canada, pp.197-206, 2008.
    O. Regev,“Lattice-based cryptography”, Proc of CRYPTO’ 06, Santa Barbara (CA), USA, pp.131-141, 2006.
    V. Lyubashevsky, “Lattice signatures without trapdoors”, Proc of EUROCRYPT’ 12, Cambridge, UK, pp.738-755, 2012.
    P. Q. Nguyen, J. Zhang and Z. Zhang, “Simpler efficient group signatures from lattices”, Proc of PKC’ 15, Washington, D.C., USA, pp.401-426, 2015.
    D. Cash, D. Hofheinz, E. Kiltz, et al., “Bonsai trees, or how to delegate a lattice basis”, Proc of EUROCRYPT’ 10, Nice, French Riviera, France, pp. 523-552, 2010.
    D. Cash, D. Hofheinz and E. Kiltz, “How to delegate a lattice basis”,, 2009.
    H. Chen, Y. Hu and Z. Lian, “Leveled homomorphic encryption in certificateless cryptosystem”, Chinese Journal of Electronics, Vol.26, No.6, pp.1213-1220, 2017.
    D. Xin, C. GU, Y. Zhang, et al., “Identity-based fully homomorphic encryption from ring learning with errors problem”, Acta Electronica Sinica, Vol.44, No.12, pp.2887-2893,2016. ( in Chinese)
    W. Gao, Y. Hu, B. Wang, et al., “Improved lattice- based ring signature schemes from basis delegation”, Journal of China Universities of Posts & Telecommunications, Vol.23, No.3, pp.11-17, 2016.
    B. Libert, S. Ling, K. Nguyen, et al., “Zero- knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors”, Proc of EUROCRYPT’ 16, Vienna, Austria, pp.1-31, 2016.
  • 加载中


    通讯作者: 陈斌,
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (69) PDF downloads(221) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint