Generic Construction of Decentralized Attribute-Based Σ-Protocol and Its Applications

doi:10.3778/j.issn.1673-9418.2006103

Abstract

Abstract:

Attribute-based cryptography becomes one of the hot topics in cryptography, since it can provide fine-grained access control and good privacy. Σ-protocol is a 3-move public-coin honest verifier zero-knowledge proof protocol, and has important applications in many fields of cryptography. Firstly, combining the concept of attribute-based cryptography with the zero-knowledge proof, a notion of attribute-based Σ-protocol is introduced with its formal security model. Secondly, based on the standard Σ-protocol, the trapdoor samplable relation and the smooth secret sharing, a general construction of decentralized attribute-based Σ-protocol and corresponding scheme are proposed with the proofs of its securities. Finally, as the applications of decentralized attribute-based Σ-protocol, general constructions of decentralized attribute-based signature and decentralized attribute-based two-tier signature are presented by Fiat-Shamir transformation, respectively. Some concrete schemes are also presented. Performance analysis shows that the proposed attribute-based two-tier signature scheme has obvious advantages in both sizes and computation costs compared with existing schemes.

Key words: Σ-protocol, decentralized attribute-based Σ-protocol, decentralized attribute-based signature, decentralized attribute-based two-tier signature, generic construction

摘要：

基于属性密码因能提供细粒度访问控制和良好的隐私性而成为密码学的研究热点之一。[Σ]协议是一种三轮公开抛硬币诚实验证者零知识证明协议，在密码学的许多领域有重要应用。首先，将基于属性密码引入到零知识证明领域，研究基于属性[Σ]协议，给出其定义，刻画其安全模型；其次，基于标准[Σ]协议、陷门可取样关系和平滑秘密共享方案，给出一个去中心基于属性[Σ]协议的一般性构造和相应的例子，并证明其安全性；最后，作为去中心基于属性[Σ]协议的应用，利用Fiat-Shamir转换，得到去中心基于属性签名和去中心基于属性双层签名的一般性构造和相应的例子。效率分析表明，基于属性双层签名方案相比已有的方案在数据长度和计算开销两方面都具有显著的优势。

关键词: &Sigma, 协议；去中心基于属性&Sigma, 协议；去中心基于属性签名；去中心基于属性双层签名；一般性构造

YANG Xiaoli, HUANG Zhenjie. Generic Construction of Decentralized Attribute-Based Σ-Protocol and Its Applications[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1667-1679.

杨晓莉, 黄振杰. 去中心基于属性Σ协议的一般性构造及其应用[J]. 计算机科学与探索, 2021, 15(9): 1667-1679.

References

[1] SAHAI A, WATERS B R. Fuzzy identity based encryption [C]//LNCS 3494: Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, May 22-26, 2005. Berlin, Heidelberg:Springer, 2005: 457-473.
[2] MAJI H, PRABHAKARAN M, ROSULEK M. Attribute-based signatures: achieving attribute-privacy and collusion-resistance[EB/OL]. (2008-07-29) [2020-07-01]. http://eprint.iacr.org/2008/328.
[3] ANADA H, ARITA S, HANDA S, et al. Attribute-based identification: definitions and efficient constructions[C]//LNCS 7959: Proceedings of the 18th Australasian Conference on Information Security and Privacy, Brisbane, Jul 1-3, 2013. Berlin, Heidelberg: Springer, 2013: 168-186.
[4] DONG X T, ZHANGY H, WANG B C, et al. Server-aided revocable attribute-based encryption from lattices[J]. Security & Communication Networks, 2020: 1-13.
[5] ISHIZAKA M, SAKAI Y, HANAOKA G, et al. Generic construction of adaptively secure anonymous key-policy attr-ibute-based encryption from public-key searchable encryp-tion[J]. IEICE Transactions on Fundamentals of Electro-nics, Communications and Computer Sciences, 2020, 103-A(1): 107-113.
[6] CUI H, DENG R H, QIN B D, et al. Key regeneration-free ciphertext-policy attribute-based encryption and its applica-tion[J]. Information Sciences, 2020, 517: 217-229.
[7] ALI M, MOHAJERI J, SADEGHI M R, et al. A fully distributed hierarchical attribute-based encryption scheme[J]. Theoretical Computer Science, 2020, 815: 25-46.
[8] DENG H, QIN Z, WU Q H, et al. Flexible attribute-based proxy re-encryption for efficient data sharing[J]. Informa-tion Sciences, 2020, 511: 94-113.
[9] LE M H, TRAN V D, TRINH V A, et al. Compacting cip-hertext in multi-channel broadcast encryption and attribute-based encryption[J]. Theoretical Computer Science, 2020, 804: 219-235.
[10] TAKASHIMA K. Expressive attribute-based encryption with constant-size ciphertexts from the decisional linear assumption[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2020, 103-A(1): 74-106.
[11] ZHAO Q Q, WU G F, MA H, et al. Black-box and public traceability in multi-authority attribute based encryption[J]. Chinese Journal of Electronics, 2020, 29(1): 106-113.
[12] OKAMOTO T, TAKASHIMA K. Decentralized attribute-based encryption and signatures[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2020, 103-A(1): 41-73.
[13] CHASE M, CHOW S S. Improving privacy and security in multi-authority attribute-based encryption[C]//Proceedings of the 16th ACM Conference on Computer and Communications Security, Chicago, Nov, 2009. New York: ACM, 2009: 121-130.
[14] CAO D, ZHAO B K, WANG X F, et al. Flexible multi-authority attribute-based signature schemes for expressive policy[J]. Mobile Information Systems, 2012, 8(3): 255-274.
[15] XIAO S Y, GE A J, MA C G, et al. Decentralized attribute-based encryption scheme with constant-size ciphertexts[J]. Journal of Computer Research and Development, 2016, 53(10): 2207-2215.
肖思煜, 葛爱军, 马传贵, 等. 去中心化且固定密文长度的基于属性加密方案[J]. 计算机研究与发展, 2016, 53(10): 2207-2215.
[16] OKAMOTO T, TAKASHIMA K. Decentralized attribute-based signatures[C]//LNCS 7778: Proceedings of the 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Feb 26-Mar 1, 2013. Berlin, Heidel-berg: Springer, 2013: 125-142.
[17] GOLDWASSER S, MICALI S, RACKOFF C. The know-ledge complexity of interactive proof systems[C]//Procee-dings of the 17th ACM Symposium on Theory of Computa-tion, Providence,?May, 1985. New York: ACM, 1985: 291-304.
[18] CRAMER R, DAMG?RD I, SCHOENMAKERS B. Proofs of partial knowledge and simplified design of witness hiding protocols[C]//LNCS 839: Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, California, Aug 21-25, 1994. Berlin, Heidelberg: Springer, 1994: 174-187.
[19] CRAMER R. Modular design of secure yet practical cypto-graphic protocols[D]. Amsterdam: Universiteit van Amster-dam, 1997.
[20] SCHNORR C P. Efficient identification and signatures for smart cards[C]//LNCS 435: Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryp-tology, Santa Barbara, Aug 20-24, 1989. Berlin, Heidelberg:Springer, 1989: 239-252.
[21] BETH T. Efficient zero-knowledge identification scheme for smart cards[C]//LNCS 330: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Davos, May 25-27, 1988. Berlin, Heidelberg: Springer, 1988: 77-84.
[22] ONG H, SCHNORR C P. Fast signature generation with a Fiat-Shamir-like scheme[C]//LNCS 473: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Aarhus, May 21-24, 1990. Berlin, Heidelberg: Springer, 1991: 432-440.
[23] GUILLOU L C, QUISQUATER J J. A paradoxical identity-based signature scheme resulting from zero-knowledge[C]//Proceedings of the 1990 Conference on the Theory and Application of Cryptography, New York, Feb, 1990. Berlin, Heidelberg: Springer, 1990: 216-231.
[24] SHAMIR A. Identity-based cryptosystems and signature schemes[C]//LNCS 196: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, New York, Aug 19-22, 1984. Berlin, Heidelberg: Springer, 1985: 47-53.
[25] OKAMOTO T. Provably secure and practical identification schemes and corresponding signature schemes[C]//LNCS 740: Proceedings of the 12th Annual International Crypto-logy Conference, Santa Barbara, Aug 16-20, 1992. Berlin, Heidelberg: Springer, 1992: 31-53.
[26] GIRAULT M. An identity-based identification scheme based on discrete logarithms modulo a composite number[C]//LNCS 473: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Aarhus, May 21-24, 1990. Berlin, Heidelberg: Springer, 1990: 481-486.
[27] HESS F. Efficient identity based signature schemes based on pairings[C]//LNCS 2595: Proceedings of the 9th Annual International Workshop on Selected Areas in Cryptography, St. John??s, Aug 15-16, 2020. Berlin, Heidelberg: Springer, 2002: 310-324.
[28] CHA J C, CHEON J H. An identity-based signature from gap Diffie-Hellman groups[C]//LNCS 2567: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, Jan 6-8, 2003. Berlin, Heidelberg: Springer, 2003: 18-30.
[29] ANADA H, ARITA S, SAKURAI K. Proof of knowledge on monotone predicates and its application to attribute-based identifications and signatures[EB/OL]. (2016)[2020-07-01]. https://eprint.iacr.org/2016/483.
[30] ANADA H, ARITA S. Anonymous authentication scheme with decentralized multi-authorities[C]//Proceedings of the 2017 IEEE International Conference on Smart Computing, Hong Kong, China, May 29-31, 2017. Washington: IEEE Computer Society, 2017: 1-6.
[31] BELLARE M, SHOUP S. Two-tier signatures, strongly un-forgeable signatures, and Fiat-Shamir without random ora-cles[C]//Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, Apr 16-20, 2007. Berlin, Heidelberg: Springer, 2007: 201-216.
[32] ANADA H, ARITA S, SAKURAI K. Attribute-based two-tier signatures: definition and construction[C]//LNCS 9558: Proceedings of the 18th International Conference on Informa-tion Security and Cryptology, Seoul, Nov 25-27, 2015. Cham: Springer, 2016: 36-49.
[33] HERRANZ J. Attribute-based versions of Schnorr and Elgamal[J]. Applicable Algebra in Engineering, Communication and Computing, 2016, 27(1): 17-57.
[34] HERRANZ J. Attribute-based signatures from RSA[J]. Theoretical Computer Science, 2014, 527(3): 73-82.
[35] ANADA H, ARITA S, SAKURAI K. Attribute-based signa-tures without pairings via the Fiat-Shamir paradigm[C]// Proceedings of the 2nd ACM Workshop on ASIA Public-Key Cryptography, Kyoto, Jun 3, 2014. New York: ACM, 2014: 49-58．