Document Open Access Logo

Online Mergers and Applications to Registration-Based Encryption and Accumulators

Authors Mohammad Mahmoody, Wei Qi

PDF
Thumbnail PDF

File

LIPIcs.ITC.2023.15.pdf
  • Filesize: 0.8 MB
  • 23 pages

Document Identifiers

Author Details

Mohammad Mahmoody
  • University of Virginia, Charlottesville, VA, USA
Wei Qi
  • University of Virginia, Charlottesville, VA, USA

Funding

  • Mahmoody, Mohammad: Supported by NSF grants CCF-1910681 and CNS193679.
  • Qi, Wei: Supported by NSF grants CCF-1910681 and CNS193679.

Cite AsGet BibTex

Mohammad Mahmoody and Wei Qi. Online Mergers and Applications to Registration-Based Encryption and Accumulators. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITC.2023.15

Abstract

In this work we study a new information theoretic problem, called online merging, that has direct applications for constructing public-state accumulators and registration-based encryption schemes. An {online merger} receives the sequence of sets {1}, {2}, … in an online way, and right after receiving {i}, it can re-partition the elements 1,…,i into T₁,…,T_{m_i} by merging some of these sets. The goal of the merger is to balance the trade-off between the maximum number of sets wid = max_{i ∈ [n]} m_i that co-exist at any moment, called the width of the scheme, with its depth dep = max_{i ∈ [n]} d_i, where d_i is the number of times that the sets that contain i get merged. An online merger can be used to maintain a set of Merkle trees that occasionally get merged. An online merger can be directly used to obtain public-state accumulators (using collision-resistant hashing) and registration-based encryptions (relying on more assumptions). Doing so, the width of an online merger translates into the size of the public-parameter of the constructed scheme, and the depth of the online algorithm corresponds to the number of times that parties need to update their "witness" (for accumulators) or their decryption key (for RBE). In this work, we construct online mergers with poly(log n) width and O(log n / log log n) depth, which can be shown to be optimal for all schemes with poly(log n) width. More generally, we show how to achieve optimal depth for a given fixed width and to achieve a 2-approximate optimal width for a given depth d that can possibly grow as a function of n (e.g., d = 2 or d = log n / log log n). As applications, we obtain accumulators with O(log n / log log n) number of updates for parties' witnesses (which can be shown to be optimal for accumulator digests of length poly(log n)) as well as registration based encryptions that again have an optimal O(log n / log log n) number of decryption updates, resolving the open question of Mahmoody, Rahimi, Qi [TCC'22] who proved that Ω(log n / log log n) number of decryption updates are necessary for any RBE (with public parameter of length poly(log n)). More generally, for any given number of decryption updates d = d(n) (under believable computational assumptions) our online merger implies RBE schemes with public parameters of length that is optimal, up to a constant factor that depends on the security parameter. For example, for any constant number of updates d, we get RBE schemes with public parameters of length O(n^{1/(d+1)}).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Registration-based encryption
  • Accumulators
  • Merkle Trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sattam S Al-Riyami and Kenneth G Paterson. Certificateless public key cryptography. In International Conference on the Theory and Application of Cryptology and Information Security, pages 452-473. Springer, 2003. Google Scholar
  2. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 1-18, Santa Barbara, CA, USA, August 19-23 2001. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-44647-8_1.
  3. Niko Barić and Birgit Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In Walter Fumy, editor, Advances in Cryptology - EUROCRYPT '97, pages 480-494, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. Google Scholar
  4. Josh Benaloh and Michael de Mare. One-way accumulators: A decentralized alternative to digital signatures. In Tor Helleseth, editor, Advances in Cryptology - EUROCRYPT '93, pages 274-285, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg. Google Scholar
  5. Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 213-229, Santa Barbara, CA, USA, August 19-23 2001. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-44647-8_13.
  6. Jan Camenisch and Anna Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002, pages 61-76, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. Google Scholar
  7. Zhaohui Cheng, Richard Comley, and Luminita Vasiu. Remove key escrow from the identity-based encryption system. In Exploring New Frontiers of Theoretical Informatics, pages 37-50. Springer, 2004. Google Scholar
  8. Sherman SM Chow. Removing escrow from identity-based encryption. In International Workshop on Public Key Cryptography, pages 256-276. Springer, 2009. Google Scholar
  9. Kelong Cong, Karim Eldefrawy, and Nigel P Smart. Optimizing registration based encryption. In IMA International Conference on Cryptography and Coding, pages 129-157. Springer, 2021. Google Scholar
  10. Keita Emura, Shuichi Katsumata, and Yohei Watanabe. Identity-based encryption with security against the KGC: a formal model and its instantiation from lattices. In European symposium on research in computer security, pages 113-133. Springer, 2019. Google Scholar
  11. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In 54th Annual Symposium on Foundations of Computer Science, pages 40-49, Berkeley, CA, USA, October 26-29 2013. IEEE Computer Society Press. URL: https://doi.org/10.1109/FOCS.2013.13.
  12. Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, and Ahmadreza Rahimi. Registration-based encryption: Removing private-key generator from ibe. In Theory of Cryptography Conference, pages 689-718. Springer, 2018. Google Scholar
  13. Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi, and Sruthi Sekar. Registration-based encryption from standard assumptions. In Dongdai Lin and Kazue Sako, editors, PKC 2019: 22nd International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 11443 of Lecture Notes in Computer Science, pages 63-93, Beijing, China, April 14-17 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-17259-6_3.
  14. Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi, and Sruthi Sekar. Registration-based encryption from standard assumptions. In Dongdai Lin and Kazue Sako, editors, Public-Key Cryptography - PKC 2019, pages 63-93, Cham, 2019. Springer International Publishing. Google Scholar
  15. Noemi Glaeser, Dimitris Kolonelos, Giulio Malavolta, and Ahmadreza Rahimi. Efficient registration-based encryption. Cryptology ePrint Archive, Paper 2022/1505, 2022. URL: https://eprint.iacr.org/2022/1505.
  16. Rishab Goyal and Satyanarayana Vusirikala. Verifiable registration-based encryption. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020, Part I, volume 12170 of Lecture Notes in Computer Science, pages 621-651, Santa Barbara, CA, USA, August 17-21 2020. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-56784-2_21.
  17. Vipul Goyal. Reducing trust in the PKG in identity based cryptosystems. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, pages 430-447, Santa Barbara, CA, USA, August 19-23 2007. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-540-74143-5_24.
  18. Vipul Goyal, Steve Lu, Amit Sahai, and Brent Waters. Black-box accountable authority identity-based encryption. In Proceedings of the 15th ACM conference on Computer and communications security, pages 427-436. ACM, 2008. Google Scholar
  19. Susan Hohenberger, George Lu, Brent Waters, and David J. Wu. Registered attribute-based encryption. Cryptology ePrint Archive, Paper 2022/1500, 2022. URL: https://eprint.iacr.org/2022/1500.
  20. Pavel Hubacek and Daniel Wichs. On the communication complexity of secure function evaluation with long output. In Tim Roughgarden, editor, ITCS 2015: 6th Conference on Innovations in Theoretical Computer Science, pages 163-172, Rehovot, Israel, January 11-13 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2688073.2688105.
  21. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 60-73, 2021. Google Scholar
  22. Mohammad Mahmoody, Wei Qi, and Ahmadreza Rahimi. Lower bounds for the number of decryption updates in registration-based encryption. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography, pages 559-587, Cham, 2022. Springer Nature Switzerland. Google Scholar
  23. Tatsuaki Okamoto, Krzysztof Pietrzak, Brent Waters, and Daniel Wichs. New realizations of somewhere statistically binding hashing and positional accumulators. In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015, pages 121-145, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  24. Ilker Ozcelik, Sai Medury, Justin Broaddus, and Anthony Skjellum. An overview of cryptographic accumulators. In Proceedings of the 7th International Conference on Information Systems Security and Privacy. SCITEPRESS - Science and Technology Publications, 2021. URL: https://doi.org/10.5220/0010337806610669.
  25. Leonid Reyzin and Sophia Yakoubov. Efficient asynchronous accumulators for distributed pki. In Security and Cryptography for Networks: 10th International Conference, SCN 2016, Amalfi, Italy, August 31-September 2, 2016, Proceedings 10, pages 292-309. Springer, 2016. Google Scholar
  26. Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, Advances in Cryptology - CRYPTO'84, volume 196 of Lecture Notes in Computer Science, pages 47-53, Santa Barbara, CA, USA, August 19-23 1984. Springer, Heidelberg, Germany. Google Scholar
  27. Qin Wang, Rujia Li, David Galindo, Qi Wang, Shiping Chen, and Yang Xiang. Transparent registration-based encryption through blockchain. Distributed Ledger Technologies: Research and Practice, 2022. Google Scholar
  28. Quanyun Wei, Fang Qi, and Zhe Tang. Remove key escrow from the BF and Gentry identity-based encryption with non-interactive key generation. Telecommunication Systems, pages 1-10, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact