Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (6): 1366-1379.doi: 10.1007/s11390-019-1980-2

Special Issue: Theory and Algorithms

• Theory and Algorithms • Previous Articles     Next Articles

Tightly Secure Public-Key Cryptographic Schemes from One-More Assumptions

Ge Wu1,2,3, Jian-Chang Lai4,*, Fu-Chun Guo2, Willy Susilo2, Senior Member, IEEE, Fu-Tai Zhang5   

  1. 1 School of Cyber Science and Engineering, Southeast University, Nanjing 211189, China;
    2 Institute of Cybersecurity and Cryptology, School of Computing and Information Technology University of Wollongong, Wollongong 2522, Australia;
    3 Purple Mountain Laboratories, Nanjing 211111, China;
    4 School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350117, China;
    5 School of Computer Science and Technology, Nanjing Normal University, Nanjing 210023, China
  • Received:2018-12-17 Revised:2019-09-25 Online:2019-11-16 Published:2019-11-16
  • Contact: Jian-Chang Lai E-mail:laijianchangchn@gmail.com
  • About author:Ge Wu received his Ph.D. degree in computer science from University of Wollongong, Wollongong, in 2019. He is currently a lecturer with School of Cyber Science and Engineering, Southeast University, Nanjing. His research interests are cryptography and information security.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61672289, 61972094, 61802195, and 61902191, the Natural Science Foundation of Jiangsu Province under Grant No. BK20190696, and the Purple Mountain Laboratories

PDF (PC)

63

Supplement

1

A tightly secure cryptographic scheme refers to a construction with a tight security reduction to a hardness assumption, where the reduction loss is a small constant. A scheme with tight security is preferred in practice since it could be implemented using a smaller parameter to improve efficiency. Recently, Bader et al. (EUROCRYPT 2016) have proposed a comprehensive study on the impossible tight security reductions for certain (e.g., key-unique) public-key cryptographic schemes in the multi-user with adaptive corruptions (MU-C) setting built upon non-interactive assumptions. The assumptions of one-more version, such as one-more computational Diffie-Hellman (n-CDH), are variants of the standard assumptions and have found various applications. However, whether it is possible to have tightly secure key-unique schemes from the one-more assumptions or the impossible tight reduction results also hold for these assumptions remains unknown. In this paper, we give affirmative answers to the above question, i.e., we can have efficient key-unique public-key cryptographic schemes with tight security built upon the one-more assumptions. Specifically, we propose a digital signature scheme and an encryption scheme, both of which are key-unique and have tight MU-C security under the one-more computational Diffie-Hellman (n-CDH) assumption. Our results also reflect from another aspect that there indeed exists a gap between the standard assumptions and their one-more version counterparts.

Key words: public-key cryptography; multi-user setting; tight security; one-more assumption;

[1] Hofheinz D, Nguyen N. On tightly secure primitives in the multi-instance setting. In Proc. the 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, April 2019, pp.581-611.
[2] Han J, Yang Y, Liu J, Li J, Liang K, Shen J. Expressive attribute-based keyword search with constant-size ciphertext. Soft Comput., 2018, 22(15):5163-5177.
[3] Lai J, Huang Z, Au M, Mao X. Constant-size CCA-secure multi-hop unidirectional proxy re-encryption from indistinguishability obfuscation. In Proc. the 23rd Australasian Conference, July 2018, pp.805-812.
[4] Yang Y, Liu X, Deng R. Lightweight break-glass access control system for healthcare internet-of-things. IEEE Trans. Industrial Informatics, 2018, 14(8):3610-3617.
[5] Galbraith S D, Malone-Lee J, Smart N P. Public key signatures in the multi-user setting. Inf. Process. Lett., 2002, 83(5):263-266.
[6] Bellare M, Boldyreva A, Micali S. Public-key encryption in a multi-user setting:Security proofs and improvements. In Proc. the 19th Int. Conference on the Theory and Application of Cryptographic Techniques, May 2000, pp.259-274.
[7] Bader C, Hofheinz D, Jager T, Kiltz E, Li Y. Tightly-secure authenticated key exchange. In Proc. the 12th Theory of Cryptography Conference, March 2015, pp.629-658.
[8] Bader C, Jager T, Li Y, Schäge S. On the impossibility of tight cryptographic reductions. In Proc. the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2016, pp.273-304.
[9] Gjøsteen K, Jager T. Practical and tightly-secure digital signatures and authenticated key exchange. In Proc. the 38th Annual International Cryptology Conference, August 2018, pp.95-125.
[10] Bader C. Efficient signatures with tight real world security in the random-oracle model. In Proc. the 13th Int. Conference on Cryptology and Network Security, October 2014, pp.370-383.
[11] Hofheinz D, Jager T. Tightly secure signatures and publickey encryption. Des. Codes Cryptography, 2016, 80(1):29-61.
[12] Libert B, Joye M, Yung M, Peters T. Concise multichallenge CCA-secure encryption and signatures with almost tight security. In Proc. the 20th Int. Conference on the Theory and Application of Cryptology and Information Security, December 2014, pp.1-21.
[13] Libert B, Peters T, Joye M, Yung M. Compactly hiding linear spans-Tightly secure constant-size simulation-sound QA-NIZK proofs and applications. In Proc. the 21st Int. Conference on the Theory and Application of Cryptology and Information Security, December 2015, pp.681-707.
[14] Attrapadung N, Hanaoka G, Yamada S. A framework for identity-based encryption with almost tight security. In Proc. the 21st Int. Conference on the Theory and Application of Cryptology and Information Security, December 2015, pp.521-549.
[15] Blazy O, Kiltz E, Pan J. (Hierarchical) identity-based encryption from affine message authentication. In Proc. the 34th Annual Cryptology Conference, August 2014, pp.408-425.
[16] Chen J, Gong J, Weng J. Tightly secure IBE under constant-size master public key. In Proc. the 20th Int. IACR International Conference on Practice and Theory in Public-Key Cryptography, March 2017, pp.207-231.
[17] Chen J, Wee H. Fully, (almost) tightly secure IBE and dual system groups. In Proc. the 33rd Annual Cryptology Conference, August 2013, pp.435-460.
[18] Gong J, Chen J, Dong X, Cao Z, Tang S. Extended nested dual system groups, revisited. In Proc. the 19th IACR International Conference on Practice and Theory in PublicKey Cryptography, March 2016, pp.133-163.
[19] Gong J, Dong X, Chen J, Cao Z. Efficient IBE with tight reduction to standard assumption in the multi-challenge setting. In Proc. the 22nd Int. Conference on the Theory and Application of Cryptology and Information Security, December 2016, pp.624-654.
[20] Hofheinz D, Jia D, Pan J. Identity-based encryption tightly secure under chosen-ciphertext attacks. In Proc. the 24th Int. Conference on the Theory and Application of Cryptology and Information Security, December 2018, pp.190-220.
[21] Hofheinz D, Koch J, Striecks C. Identity-based encryption with (almost) tight security in the multi-instance, multiciphertext setting. In Proc. the 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, March 2015, pp.799-822.
[22] Coron J. Optimal security proofs for PSS and other signature schemes. In Proc. the 21st Int. Conference on the Theory and Applications of Cryptographic Techniques, April 2002, pp.272-287.
[23] Hofheinz D, Jager T, Knapp E. Waters signatures with optimal security reduction. In Proc. the 15th Int. Conference on Practice and Theory in Public Key Cryptography, May 2012, pp.66-83.
[24] Kakvi S, Kiltz E. Optimal security proofs for full domain hash, revisited. J. Cryptology, 2018, 31(1):276-306.
[25] Bellare M, Namprempre C, Pointcheval D, Semanko M. The power of RSA inversion oracles and the security of Chaum's RSA-based blind signature scheme. In Proc. the 5th Int. Conference on Financial Cryptography, February 2002, pp.309-328.
[26] Boldyreva A. Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme. In Proc. the 6th Int. Workshop on Theory and Practice in Public Key Cryptography, January 2003, pp.31-46.
[27] Bellare M, Neven G. Transitive signatures:New schemes and proofs. IEEE Trans. Information Theory, 2005, 51(6):2133-2151.
[28] Bellare M, Namprempre C, Neven G. Security proofs for identity-based identification and signature schemes. J. Cryptology, 2009, 22(1):1-61.
[29] de Cristofaro E, Tsudik G. Practical private set intersection protocols with linear complexity. In Proc. the 14th Int. Conference on Financial Cryptography and Data Security, January 2010, pp.143-159.
[30] Fischlin M, Fleischhacker N. Limitations of the metareduction technique:The case of Schnorr signatures. In Proc. the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2013, pp.444-460.
[31] Garg S, Bhaskar R, Lokam S. Improved bounds on security reductions for discrete log based signatures. In Proc. the 28th Annual International Cryptology Conference, August 2008, pp.93-107.
[32] Seurin Y. On the exact security of Schnorr-type signatures in the Random Oracle Model. In Proc. the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, April 2012, pp.554-571.
[33] Bresson E, Monnerat J, Vergnaud D. Separation results on the "one-more" computational problems. In Proc. the 2008 the Cryptographers' Track at the RSA Conference, April 2008, pp.71-87.
[34] Pass R. Limits of provable security from standard assumptions. In Proc. the 43rd ACM Symposium on Theory of Computing, June 2011, pp.109-118.
[35] Zhang J, Zhang Z, Chen Y, Guo Y, Zhang Z. Black-box separations for one-more (static) CDH and its generalization. In Proc. the 20th Int. Conference on the Theory and Application of Cryptology and Information Security, December 2014, pp.366-385.
[36] Boneh D, Lynn B, Shacham H. Short signatures from the Weil pairing. In Proc. the 7th Int. Conference on the Theory and Application of Cryptology and Information Security, December 2001, pp.514-532.
[37] Abdalla M, Bellare M, Rogaway P. The Oracle DiffieHellman assumptions and an analysis of DHIES. In Proc. the 1st Cryptographer's Track at RSA Conference, April 2001, pp.143-158.
[38] Wang Y, Matsuda T, Hanaoka G, Tanaka K. Impossibility on tamper-resilient cryptography with uniqueness properties. IACR ePrint Archive, 2018, 2018:Article No. 564.
[39] Boneh D, Boyen X. Efficient selective-ID secure identitybased encryption without random oracles. In Proc. the 23rd Int. Conference on the Theory and Applications of Cryptographic Techniques, May 2004, pp.223-238.
[40] Katz J, Wang N. Efficiency improvements for signature schemes with tight security reductions. In Proc. the 10th ACM Conference on Computer and Communications Security, October 2003, pp.155-164.
[41] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Information Theory, 1985, 31(4):469-472.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhu Mingyuan;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[2] Zhang Bo; Zhang Ling;. On Memory Capacity of the Probabilistic Logic Neuron Network[J]. , 1993, 8(3): 62 -66 .
[3] Zhou Jianqiang; Xie Li; Dai Fei; Sun Zhongxiu;. Adaptive Memory Coherence Algorithms in DSVM[J]. , 1994, 9(4): 365 -372 .
[4] Yao Shu; Zhang Bo;. Situated Learning of a Behavior-Based Mobile Robot Path Planner[J]. , 1995, 10(4): 375 -379 .
[5] Jiang Chanaiun;. Net Operations (Ⅱ)-The Iterated Addition Operation of Petri Nets[J]. , 1995, 10(6): 509 -517 .
[6] Xu Dianxiang; Zheng Guoliang;. Towards a Declarative Semantics of Inheritance with Exceptions[J]. , 1996, 11(1): 61 -71 .
[7] Hu Weiwu; Shi Weisong; Tang Zhimin; Li Ming;. A Lock-Based Cache Coherence Protocol for Scope Consistency[J]. , 1998, 13(2): 97 -109 .
[8] CHEN Haiming;. Function Definition Language FDL andIts Implementation[J]. , 1999, 14(4): 414 -421 .
[9] ZHAN Yongzhao; SONG Snunlin; XIE Li;. Demand Priority Protocol Simulation and Evaluation[J]. , 1999, 14(6): 599 -605 .
[10] HE Taosong;. Volumetric Virtual Environments[J]. , 2000, 15(1): 37 -46 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved