Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from SXDH

Tsz Hon Yuen; Sherman S. M. Chow; Huangting Wu; Cong Zhang; Siu-Ming Yiu

doi:10.62056/ahsdkmp-3y

Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from SXDH

Authors

Tsz Hon Yuen, Sherman S. M. Chow, Huangting Wu, Cong Zhang, Siu-Ming Yiu

Tsz Hon Yuen

Faculty of Information Technology, Monash University, Melbourne, VIC, Australia
john dot tszhonyuen at monash dot edu

Sherman S. M. Chow

Department of Information Engineering, Chinese University of Hong Kong, Shatin, Hong Kong
smchow at ie dot cuhk dot edu dot hk

Huangting Wu

Department of Information Engineering, Chinese University of Hong Kong, Shatin, Hong Kong
wh017 at ie dot cuhk dot edu dot hk

Cong Zhang

The State Key Laboratory of Blockchain and Data Security, Zhejiang University, China
congresearch at zju dot edu dot cn

Siu-Ming Yiu

Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong

Keywords: Dual form signature Dual system encryption Exponent inversion P-Signatures Anonymous credentials Identity-based encryption Black-box accountability Static assumptions Symmetric eXternal Diffie-Hellman

Abstract

Salient in many cryptosystems, the exponent-inversion technique began without randomization in the random oracle model (SCIS '03, PKC '04), evolved into the Boneh-Boyen short signature scheme (JoC '08) and exerted a wide influence. Seen as a notable case, Gentry's (EuroCrypt '06) identity-based encryption (IBE) applies exponent inversion on a randomized base in its identity-based trapdoors. Making use of the non-static q-strong Diffie-Hellman assumption, Boneh-Boyen signatures are shown to be unforgeable against q-chosen-message attacks, while a variant q-type decisional assumption is used to establish the security of Gentry-IBE. Challenges remain in proving their security under weaker static assumptions.

Supported by the dual form/system framework (Crypto '09, AsiaCrypt '12), we propose dual form exponent-inversion Boneh-Boyen signatures and Gentry-IBE, with security proven under the symmetric external Diffie-Hellman (SXDH) assumption. Starting from our signature scheme, we extend it into P-signatures (TCC '08), resulting in the first anonymous credential scheme from the SXDH assumption, serving as a competitive alternative to the static-assumption construction of Abe et al. (JoC '16). Moreover, from our Gentry-IBE variant, we propose an accountable-authority IBE scheme also from SXDH, surpassing the fully secure Sahai-Seyalioglu scheme (PKC '11) in efficiency and the generic Kiayias-Tang transform (ESORICS '15) in security. Collectively, we present a suite of results under static assumptions.

References

[ABB10]

Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE. In CRYPTO, pages 98–115. 2010. DOI: 10.1007/978-3-642-14623-7_6

Google Scholar ePrint

[ACD⁺16]

Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, and Miyako Ohkubo. Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions. J. Cryptol., 29(4):833–878, 2016. DOI: 10.1007/S00145-015-9211-7

Google Scholar ePrint

[ACN13]

Tolga Acar, Sherman S. M. Chow, and Lan Nguyen. Accumulators and U-Prove Revocation. In FC, pages 189–196. 2013. DOI: 10.1007/978-3-642-39884-1_15

Google Scholar ePrint

[AFG⁺10]

Masayuki Abe, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. Structure-Preserving Signatures and Commitments to Group Elements. In CRYPTO, pages 209–236. 2010. DOI: 10.1007/978-3-642-14623-7_12

Google Scholar ePrint

[AIK14]

Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. How to Garble Arithmetic Circuits. SIAM J. Comput., 43(2):905–929, 2014. DOI: 10.1137/120875193

Google Scholar ePrint

[ASMC13]

Man Ho Au, Willy Susilo, Yi Mu, and Sherman S. M. Chow. Constant-Size Dynamic k-Times Anonymous Authentication. IEEE Syst. J., 7(2):249–261, 2013. DOI: 10.1109/JSYST.2012.2221931

Google Scholar ePrint

[BB08]

Dan Boneh and Xavier Boyen. Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups. J. Cryptol., 21(2):149–177, 2008. DOI: 10.1007/S00145-007-9005-7

Google Scholar ePrint

[BBS04]

Dan Boneh, Xavier Boyen, and Hovav Shacham. Short Group Signatures. In CRYPTO, pages 41–55. 2004. DOI: 10.1007/978-3-540-28628-8_3

Google Scholar ePrint

[BCHK07]

Dan Boneh, Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-Ciphertext Security from Identity-Based Encryption. SIAM J. Comput., 36(5):1301–1328, 2007. DOI: 10.1137/S009753970544713X

Google Scholar ePrint

[BCKL08]

Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, and Anna Lysyanskaya. P-signatures and Noninteractive Anonymous Credentials. In TCC, pages 356–374. 2008. DOI: 10.1007/978-3-540-78524-8_20

Google Scholar ePrint

[BF03]

Dan Boneh and Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. SIAM J. Comput., 32(3):586–615, 2003. DOI: 10.1137/S0097539701398521

Google Scholar ePrint

[BHR12]

Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of Garbled Circuits. In CCS, pages 784–796. 2012. DOI: 10.1145/2382196.2382279

Google Scholar ePrint

[BLSV18]

Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan. Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions. In EUROCRYPT Part I, pages 535–564. 2018. DOI: 10.1007/978-3-319-78381-9_20

Google Scholar ePrint

[Boy07]

Xavier Boyen. General Ad Hoc Encryption from Exponent Inversion IBE. In EUROCRYPT, pages 394–411. 2007. DOI: 10.1007/978-3-540-72540-4_23

Google Scholar ePrint

[CCH⁺12]

Sherman S. M. Chow, Cheng-Kang Chu, Xinyi Huang, Jianying Zhou, and Robert H. Deng. Dynamic Secure Cloud Storage with Provenance. In Cryptography and Security: From Theory to Applications - Essays Dedicated to Jean-Jacques Quisquater on the Occasion of His 65th Birthday, pages 442–464. 2012. DOI: 10.1007/978-3-642-28368-0_28

Google Scholar ePrint

[CDRW10]

Sherman S. M. Chow, Yevgeniy Dodis, Yannis Rouselakis, and Brent Waters. Practical Leakage-Resilient Identity-Based Encryption from Simple Assumptions. In CCS, pages 152–161. 2010. DOI: 10.1145/1866307.1866325

Google Scholar ePrint

[CHKP12]

David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai Trees, or How to Delegate a Lattice Basis. J. Cryptol., 25(4):601–639, 2012. DOI: 10.1007/S00145-011-9105-2

Google Scholar ePrint

[Cho09]

Sherman S. M. Chow. Removing Escrow from Identity-Based Encryption. In PKC, pages 256–276. 2009. DOI: 10.1007/978-3-642-00468-1_15

Google Scholar ePrint

[Cho10]

Sherman S. M. Chow. New Privacy-Preserving Architectures for Identity-/Attribute-based Encryption. PhD thesis, New York University, USA, 2010.

Google Scholar ePrint

[CK18]

Sanjit Chatterjee and R. Kabaleeshwaran. Towards Static Assumption Based Cryptosystem in Pairing Setting: Further Applications of DéjàQ and Dual-Form Signature (Extended Abstract). In PROVSEC, pages 220–238. 2018. DOI: 10.1007/978-3-030-01446-9_13

Google Scholar ePrint

[CK19]

Sanjit Chatterjee and R. Kabaleeshwaran. Rerandomizable Signatures Under Standard Assumption. In INDOCRYPT, pages 45–67. 2019. DOI: 10.1007/978-3-030-35423-7_3

Google Scholar ePrint

[CL04]

Jan Camenisch and Anna Lysyanskaya. Signature Schemes and Anonymous Credentials from Bilinear Maps. In CRYPTO, pages 56–72. 2004. DOI: 10.1007/978-3-540-28628-8_4

Google Scholar ePrint

[CLL⁺12]

Jie Chen, Hoon Wei Lim, San Ling, Huaxiong Wang, and Hoeteck Wee. Shorter IBE and Signatures via Asymmetric Pairings. In PAIRING, pages 122–140. 2012. DOI: 10.1007/978-3-642-36334-4_8

Google Scholar ePrint

[CM14]

Melissa Chase and Sarah Meiklejohn. Déjà Q: Using Dual Systems to Revisit q-Type Assumptions. In EUROCRYPT, pages 622–639. 2014. DOI: 10.1007/978-3-642-55220-5_34

Google Scholar ePrint

[CMM16]

Melissa Chase, Mary Maller, and Sarah Meiklejohn. Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions. In ASIACRYPT Part II, pages 655–681. 2016. DOI: 10.1007/978-3-662-53890-6_22

Google Scholar ePrint

[CY11]

Sherman S. M. Chow and Siu-Ming Yiu. Exclusion-Intersection Encryption. Int. J. Secur. Networks, 6(2/3):136–146, 2011. DOI: 10.1504/IJSN.2011.043672

Google Scholar ePrint

[CZZ17]

Sherman S. M. Chow, Haibin Zhang, and Tao Zhang. Real Hidden Identity-Based Signatures. In FC, pages 21–38. 2017. DOI: 10.1007/978-3-319-70972-7_2

Google Scholar ePrint

[Del07]

Cécile Delerablée. Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys. In ASIACRYPT, pages 200–215. 2007. DOI: 10.1007/978-3-540-76900-2_12

Google Scholar ePrint

[DG21]

Nico Döttling and Sanjam Garg. Identity-based Encryption from the Diffie-Hellman Assumption. J. ACM, 68(3):14:1–14:46, 2021. DOI: 10.1145/3422370

Google Scholar ePrint

[DKL⁺23]

Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat, and LaKyah Tyner. Threshold BBS+ Signatures for Distributed Anonymous Credential Issuance. In SP, pages 773–789. 2023. DOI: 10.1109/SP46215.2023.10179470

Google Scholar ePrint

[DP08]

Cécile Delerablée and David Pointcheval. Dynamic Threshold Public-Key Encryption. In CRYPTO, pages 317–334. 2008. DOI: 10.1007/978-3-540-85174-5_18

Google Scholar ePrint

[DY05]

Yevgeniy Dodis and Aleksandr Yampolskiy. A Verifiable Random Function with Short Proofs and Keys. In PKC, pages 416–431. 2005. DOI: 10.1007/978-3-540-30580-4_28

Google Scholar ePrint

[Gen06]

Craig Gentry. Practical Identity-Based Encryption Without Random Oracles. In EUROCRYPT, pages 445–464. 2006. DOI: 10.1007/11761679_27

Google Scholar ePrint

[GH09]

Craig Gentry and Shai Halevi. Hierarchical Identity Based Encryption with Polynomially Many Levels. In TCC, pages 437–456. 2009. DOI: 10.1007/978-3-642-00457-5_26

Google Scholar ePrint

[GLOW12]

Michael Gerbush, Allison B. Lewko, Adam O'Neill, and Brent Waters. Dual Form Signatures: An Approach for Proving Security from Static Assumptions. In ASIACRYPT, pages 25–42. 2012. DOI: 10.1007/978-3-642-34961-4_4

Google Scholar ePrint

[Goy07]

Vipul Goyal. Reducing Trust in the PKG in Identity Based Cryptosystems. In CRYPTO, pages 430–447. 2007. DOI: 10.1007/978-3-540-74143-5_24

Google Scholar ePrint

[Gro07]

Jens Groth. Fully Anonymous Group Signatures Without Random Oracles. In ASIACRYPT, pages 164–180. 2007. DOI: 10.1007/978-3-540-76900-2_10

Google Scholar ePrint

[GS12]

Jens Groth and Amit Sahai. Efficient Noninteractive Proof Systems for Bilinear Groups. SIAM J. Comput., 41(5):1193–1232, 2012. DOI: 10.1137/080725386

Google Scholar ePrint

[JS07]

Stanislaw Jarecki and Vitaly Shmatikov. Efficient Two-Party Secure Computation on Committed Inputs. In EUROCRYPT, pages 97–114. 2007. DOI: 10.1007/978-3-540-72540-4_6

Google Scholar ePrint

[JY09]

David Jao and Kayo Yoshida. Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem. In PAIRING, pages 1–16. 2009. DOI: 10.1007/978-3-642-03298-1_1

Google Scholar ePrint

[KT15]

Aggelos Kiayias and Qiang Tang. Making Any Identity-Based Encryption Accountable, Efficiently. In ESORICS Part I, pages 326–346. 2015. DOI: 10.1007/978-3-319-24174-6_17

Google Scholar ePrint

[LDZW13]

Junzuo Lai, Robert H. Deng, Yunlei Zhao, and Jian Weng. Accountable Authority Identity-Based Encryption with Public Traceability. In CTRSA, pages 326–342. 2013. DOI: 10.1007/978-3-642-36095-4_21

Google Scholar ePrint

[LMPY16]

Benoît Libert, Fabrice Mouhartem, Thomas Peters, and Moti Yung. Practical “Signatures with Efficient Protocols” from Simple Assumptions. In AsiaCCS, pages 511–522. 2016. DOI: 10.1145/2897845.2897898

Google Scholar ePrint

[LV11]

Benoît Libert and Damien Vergnaud. Towards Practical Black-Box Accountable Authority IBE: Weak Black-Box Traceability With Short Ciphertexts and Private Keys. IEEE Trans. Inf. Theory, 57(10):7189–7204, 2011. DOI: 10.1109/TIT.2011.2161958

Google Scholar ePrint

[LW10]

Allison B. Lewko and Brent Waters. New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts. In TCC, pages 455–479. 2010. DOI: 10.1007/978-3-642-11799-2_27

Google Scholar ePrint

[Ngu05]

Lan Nguyen. Accumulators from Bilinear Pairings and Applications. In CTRSA, pages 275–292. 2005. DOI: 10.1007/978-3-540-30574-3_19

Google Scholar ePrint

[OT08]

Tatsuaki Okamoto and Katsuyuki Takashima. Homomorphic Encryption and Signatures from Vector Decomposition. In PAIRING, pages 57–74. 2008. DOI: 10.1007/978-3-540-85538-5_4

Google Scholar ePrint

[PS16]

David Pointcheval and Olivier Sanders. Short Randomizable Signatures. In CTRSA, pages 111–126. 2016. DOI: 10.1007/978-3-319-29485-8_7

Google Scholar ePrint

[PS18]

David Pointcheval and Olivier Sanders. Reassessing Security of Randomizable Signatures. In CTRSA, pages 319–338. 2018. DOI: 10.1007/978-3-319-76953-0_17

Google Scholar ePrint

[PV08]

Rafael Pass and Muthuramakrishnan Venkitasubramaniam. On Constant-Round Concurrent Zero-Knowledge. In TCC, pages 553–570. 2008. DOI: 10.1007/978-3-540-78524-8_30

Google Scholar ePrint

[SK03]

Ryuichi Sakai and Masao Kasahara. Cryptosystems based on Pairing over Elliptic Curve. In Symposium on Cryptography and Information Security. 2003.

Google Scholar ePrint

[SS11]

Amit Sahai and Hakan Seyalioglu. Fully Secure Accountable-Authority Identity-Based Encryption. In PKC, pages 296–316. 2011. DOI: 10.1007/978-3-642-19379-8_19

Google Scholar ePrint

[Wat09]

Brent Waters. Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In CRYPTO, pages 619–636. 2009. DOI: 10.1007/978-3-642-03356-8_36

Google Scholar ePrint

[WC23]

Huangting Wu and Sherman S. M. Chow. Anonymous (Hierarchical) Identity-Based Encryption from Broader Assumptions. In ACNS Part II, pages 366–395. 2023. DOI: 10.1007/978-3-031-33491-7_14

Google Scholar ePrint

[Wee16]

Hoeteck Wee. Déjà Q: Encore! Un Petit IBE. In TCC-A Part II, pages 237–258. 2016. DOI: 10.1007/978-3-662-49099-0_9

Google Scholar ePrint

[WMC24]

Harry W. H. Wong, Jack P. K. Ma, and Sherman S. M. Chow. Secure Multiparty Computation of Threshold Signatures Made More Efficient. In NDSS. 2024. DOI: 10.14722/ndss.2024.24601

Google Scholar ePrint

[YCZY14]

Tsz Hon Yuen, Sherman S. M. Chow, Cong Zhang, and Siu-Ming Yiu. Exponent-inversion Signatures and IBE under Static Assumptions. IACR Cryptol. ePrint Arch. 2014/311. 2014.

Google Scholar ePrint

[YZC22]

Tsz Hon Yuen, Cong Zhang, and Sherman S. M. Chow. Don't Tamper with Dual System Encryption - Beyond Polynomial Related-Key Security of IBE. In ACNS, pages 419–439. 2022. DOI: 10.1007/978-3-031-09234-3_21

Google Scholar ePrint

[YZCL13]

Tsz Hon Yuen, Cong Zhang, Sherman S. M. Chow, and Joseph K. Liu. Towards Anonymous Ciphertext Indistinguishability with Identity Leakage. In PROVSEC, pages 139–153. 2013. DOI: 10.1007/978-3-642-41227-1_8

Google Scholar ePrint

[ZSS04]

Fangguo Zhang, Reihaneh Safavi-Naini, and Willy Susilo. An Efficient Signature Scheme from Bilinear Pairings and Its Applications. In PKC, pages 277–290. 2004. DOI: 10.1007/978-3-540-24632-9_20

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ahsdkmp-3y

History

Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Tsz Hon Yuen, Sherman S. M. Chow, Huangting Wu, Cong Zhang, and Siu-Ming Yiu, Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from SXDH. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ahsdkmp-3y.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-48,
    author = "Yuen, Tsz Hon and Chow, Sherman S. M. and Wu, Huangting and Zhang, Cong and Yiu, Siu-Ming",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from {SXDH}",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ahsdkmp-3y"
}

TY - JOUR
AU - Yuen, Tsz
AU - Chow, Sherman
AU - Wu, Huangting
AU - Zhang, Cong
AU - Yiu, Siu-Ming
PY  - 2024
TI  - Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from SXDH
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/ahsdkmp-3y
UR  - https://doi.org/10.62056/ahsdkmp-3y
AB  - <p>Salient in many cryptosystems, the exponent-inversion technique began without randomization in the random oracle model (SCIS '03, PKC '04), evolved into the Boneh-Boyen short signature scheme (JoC '08) and exerted a wide influence. Seen as a notable case, Gentry's (EuroCrypt '06) identity-based encryption (IBE) applies exponent inversion on a randomized base in its identity-based trapdoors. Making use of the non-static q-strong Diffie-Hellman assumption, Boneh-Boyen signatures are shown to be unforgeable against q-chosen-message attacks, while a variant q-type decisional assumption is used to establish the security of Gentry-IBE. Challenges remain in proving their security under weaker static assumptions.</p><p>Supported by the dual form/system framework (Crypto '09, AsiaCrypt '12), we propose dual form exponent-inversion Boneh-Boyen signatures and Gentry-IBE, with security proven under the symmetric external Diffie-Hellman (SXDH) assumption. Starting from our signature scheme, we extend it into P-signatures (TCC '08), resulting in the first anonymous credential scheme from the SXDH assumption, serving as a competitive alternative to the static-assumption construction of Abe et al. (JoC '16). Moreover, from our Gentry-IBE variant, we propose an accountable-authority IBE scheme also from SXDH, surpassing the fully secure Sahai-Seyalioglu scheme (PKC '11) in efficiency and the generic Kiayias-Tang transform (ESORICS '15) in security. Collectively, we present a suite of results under static assumptions. </p>
ER  -

Tsz Hon Yuen, Sherman S. M. Chow, Huangting Wu, Cong Zhang, and Siu-Ming Yiu, Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from SXDH. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ahsdkmp-3y.