Algebraic Adversaries in the Universal Composability Framework | SpringerLink
Skip to main content
Springer Nature Link
Log in

Algebraic Adversaries in the Universal Composability Framework

  • Conference paper
  • First Online:
Advances in Cryptology – ASIACRYPT 2021 (ASIACRYPT 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 13092))

Abstract

The algebraic-group model (AGM), which lies between the generic group model and the standard model of computation, provides a means by which to analyze the security of cryptosystems against so-called algebraic adversaries. We formalize the AGM within the framework of universal composability, providing formal definitions for this setting and proving an appropriate composition theorem. This extends the applicability of the AGM to more-complex protocols, and lays the foundations for analyzing algebraic adversaries in a composable fashion. Our results also clarify the meaning of composing proofs in the AGM with other proofs and they highlight a natural form of independence between idealized groups that seems inherent to the AGM and has not been made formal before—these insights also apply to the composition of game-based proofs in the AGM. We show the utility of our model by proving several important protocols universally composable for algebraic adversaries, specifically: (1) the Chou-Orlandi protocol for oblivious transfer, and (2) the SPAKE2 and CPace protocols for password-based authenticated key exchange.

J. Loss—Work done while at the University of Maryland.

J. Xu—Work done while at George Mason University.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    One can consider formalizing the AGM within the UC framework by introducing a functionality \(\mathcal {F}_\mathsf{AGM}\) that “forces” arbitrary algorithms to behave algebraically by registering group elements and their representations in a central repository. This has a number of disadvantages that we discuss in the full version [3]. Our approach is closer to the spirit of the AGM, which idealizes groups by quantifying over restricted classes of adversaries.

  2. 2.

    For a review of the security proofs available for both protocols at the time, see https://mailarchive.ietf.org/arch/msg/cfrg/47pnOSsrVS8uozXbAuM-alEk0-s.

  3. 3.

    Formally, we assume an encoding of group elements that distinguishes them from arbitrary strings. This can be done by simply prefixing any group element with a 0 and any other string (not necessarily representing a group element) with a 1. Following prior work [19], we use bold capital letters to denote group elements (except for the generator g).

  4. 4.

    Formally, we consider protocols having access to a \(\mathcal {F}_{\mathrm {CRS}}\) functionality, where \(\mathcal {F}_{\mathrm {CRS}}\) runs a group-generation algorithm to obtain \(\mathcal {G}\) (and possibly additional group elements), and then sends \(\mathcal {G}\) (and any other elements) to parties that request it. Note that the protocol may use other groups, but we only require the adversary to be algebraic with respect to \(\mathcal {G}\).

  5. 5.

    Note that this \(\mathcal {S}_\pi \) is an imaginary machine supposed to run inside \(\mathcal {S}\), whereas the “actual” \(\mathcal {S}_\pi \) is the simulator in the execution of \(\phi \). Same with step 3 below.

  6. 6.

    This step could be replaced with a search for a consistent entry using a DDH oracle to the fixed basis \(\mathbf {A}\), resulting in a tighter reduction to Strong SqDH where the \(q_{\mathrm {H}}\) factor disappears.

References

  1. Abdalla, M., Barbosa, M.: Perfect forward security of SPAKE2. Cryptology ePrint Archive, Report 2019/1194 (2019). https://eprint.iacr.org/2019/1194

  2. Abdalla, M., Barbosa, M., Bradley, T., Jarecki, S., Katz, J., Xu, J.: Universally composable relaxed password authenticated key exchange. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part I. LNCS, vol. 12170, pp. 278–307. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_10

    Chapter  Google Scholar 

  3. Abdalla, M., Barbosa, M., Katz, J., Loss, J., Xu, J.: Algebraic adversaries in the universal composability framework. Cryptology ePrint Archive, Report 2021/3878 (2021). https://ia.cr/2021/3878

  4. Abdalla, M., Benhamouda, F., MacKenzie, P.: Security of the J-PAKE password-authenticated key exchange protocol. In: 2015 IEEE Symposium on Security and Privacy, pp. 571–587. IEEE (2015)

    Google Scholar 

  5. Abdalla, M., Pointcheval, D.: Simple password-based encrypted key exchange protocols. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 191–208. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30574-3_14

    Chapter  Google Scholar 

  6. Auerbach, B., Giacon, F., Kiltz, E.: Everybody’s a target: scalability in public-key encryption. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part III. LNCS, vol. 12107, pp. 475–506. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_16

    Chapter  Google Scholar 

  7. Bauer, B., Fuchsbauer, G., Loss, J.: A classification of computational assumptions in the algebraic group model. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 121–151. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_5

    Chapter  Google Scholar 

  8. Baum, C., David, B., Dowsley, R., Nielsen, J.B., Oechsner, S.: TARDIS: a foundation of time-lock puzzles in UC. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 429–459. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_15. Cryptology ePrint Archive, Report 2020/537, https://ia.cr/2020/537

  9. Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73. ACM Press (1993)

    Google Scholar 

  10. Bradley, T., Jarecki, S., Xu, J.: Strong asymmetric PAKE based on trapdoor CKEM. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 798–825. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_26

    Chapter  Google Scholar 

  11. Byali, M., Patra, A., Ravi, D., Sarkar, P.: Fast and universally-composable oblivious transfer and commitment scheme with adaptive security. Cryptology ePrint Archive, Report 2017/1165 (2017). https://eprint.iacr.org/2017/1165

  12. Camenisch, J., Drijvers, M., Gagliardoni, T., Lehmann, A., Neven, G.: The wonderful world of global random oracles. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 280–312. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_11

    Chapter  Google Scholar 

  13. Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 136–145. IEEE (2001)

    Google Scholar 

  14. Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_4

    Chapter  Google Scholar 

  15. Canetti, R., Halevi, S., Katz, J., Lindell, Y., MacKenzie, P.: Universally composable password-based key exchange. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 404–421. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_24

    Chapter  Google Scholar 

  16. Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: ACM Conference on Computer and Communications Security (CCS), pp. 597–608. ACM Press (2014)

    Google Scholar 

  17. Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N.: Marlin: preprocessing zkSNARKs with universal and updatable SRS. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part I. LNCS, vol. 12105, pp. 738–768. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_26

    Chapter  Google Scholar 

  18. Chou, T., Orlandi, C.: The simplest protocol for oblivious transfer. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 40–58. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8_3

    Chapter  Google Scholar 

  19. Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2

    Chapter  Google Scholar 

  20. Fuchsbauer, G., Plouviez, A., Seurin, Y.: Blind schnorr signatures and signed elgamal encryption in the algebraic group model. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 63–95. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_3

    Chapter  Google Scholar 

  21. Genç, Z.A., Iovino, V., Rial, A.: The simplest protocol for oblivious transfer revisited. Cryptology ePrint Archive, Report 2017/370 (2017). http://eprint.iacr.org/2017/370

  22. Haase, B., Labrique, B.: AuCPace: efficient verifier-based PAKE protocol tailored for the IIoT. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019(2), 1–48 (2019). https://tches.iacr.org/index.php/TCHES/article/view/7384

  23. Hauck, E., Loss, J.: Efficient and universally composable protocols for oblivious transfer from the CDH assumption. Cryptology ePrint Archive, Report 2017/1011 (2017). http://eprint.iacr.org/2017/1011

  24. Katz, J., Loss, J., Xu, J.: On the security of time-locked puzzles and timed commitments. Cryptology ePrint Archive, Report 2020/730 (2020). https://eprint.iacr.org/2020/730

  25. Kerber, T., Kiayias, A., Kohlweiss, M.: Composition with knowledge assumptions. Cryptology ePrint Archive, Report 2021/165 (2021). https://eprint.iacr.org/2021/165

  26. Larangeira, M., Tanaka, K.: Programmability in the generic ring and group models. J. Internet Serv. Inf. Secur. 1(2/3), 57–73 (2011)

    Google Scholar 

  27. Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In: ACM Conference on Computer and Communications Security (CCS), pp. 2111–2128. ACM Press (2019)

    Google Scholar 

  28. Naor, M., Paz, S., Ronen, E.: CRISP: Compromise resilient identity-based symmetric PAKE. Cryptology ePrint Archive, Report 2020/529 (2020). https://eprint.iacr.org/2020/529

  29. Nechaev, V.I.: Complexity of a determinate algorithm for the discrete logarithm. Math. Notes 55(2), 165–172 (1994)

    Article  MathSciNet  Google Scholar 

  30. Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DIENS, École normale supérieure, CNRS, PSL University, Paris, France

    Michel Abdalla

  2. DFINITY, Zürich, Switzerland

    Michel Abdalla

  3. University of Porto (FCUP) and INESC TEC, Porto, Portugal

    Manuel Barbosa

  4. University of Maryland, College Park, USA

    Jonathan Katz

  5. CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

    Julian Loss

  6. Algorand, Boston, USA

    Jiayu Xu

Authors
  1. Michel Abdalla
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manuel Barbosa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jonathan Katz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Julian Loss
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jiayu Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. NTT Corporation, Tokyo, Japan

    Mehdi Tibouchi

  2. Nanyang Technological University, Singapore, Singapore

    Huaxiong Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Abdalla, M., Barbosa, M., Katz, J., Loss, J., Xu, J. (2021). Algebraic Adversaries in the Universal Composability Framework. In: Tibouchi, M., Wang, H. (eds) Advances in Cryptology – ASIACRYPT 2021. ASIACRYPT 2021. Lecture Notes in Computer Science(), vol 13092. Springer, Cham. https://doi.org/10.1007/978-3-030-92078-4_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92078-4_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92077-7

  • Online ISBN: 978-3-030-92078-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation