price ranges $[1,\allowbreak P_{max}]$ and sets of denominations. The results
are summarised in Table 3. We observe that our compact $\mathrm{EC}$ scheme is
more efficient than our divisible $\mathrm{EC}$ scheme for small price ranges
and small sets of denominations.

The major advantage of the compact $\mathrm{EC}$ scheme over the divisible
$\mathrm{EC}$ scheme is a fast _identification_ phase. In the compact
$\mathrm{EC}$ scheme, to detect double-spending, an authority simply needs to
compare serial numbers. In a practical setting, it is likely that double
spending happens infrequently, and so the computation cost for the authority
is negligible. However, in the divisible $\mathrm{EC}$ scheme, the authority
needs to compute the serial numbers of a payment by running
$\mathsf{Identify}$ before the authority can compare them with the serial
numbers of other payments. The computation of a serial number involves two
pairings.

Once double spending is detected, the compact $\mathrm{EC}$ scheme can
identify the user guilty of double spending in $1.61$ ms, independently of the
number of users in the system. However, in the divisible $\mathrm{EC}$ scheme,
the computation is more expensive and it grows linearly with the number of
users in the system. We remark that the timings given in Table 2 are
calculated for 100 users, but in practice this number could be orders of
magnitude bigger, which makes identification in compact e-cash much more
efficient than in divisible e-cash.

Table 3. Average time required to complete a payment in Compact $\mathrm{EC}$ for different values of $D$ and $P_{max}$ $P_{max}$ | $D$ |  Spend [ms]
---|---|---
10 | $[1,2,5]$ | 50.84
100 | $[1,2,5,10,20,50]$ | 90.98
1000 | $[1,2,5,\ldots,100,200,500]$ | 136.46
10000 | $[1,2,5,\ldots,1000,2000,5000]$ | 181.95
100000 | $[1,2,5,\ldots,10000,20000,50000]$ | 227.43
1000000 | $[1,2,5,\ldots,10000,20000,50000]$ | 468.26

##  7\. Integration

In our schemes, deposited payments are verified by the authorities. Double-
spending is detected by storing previous payments on a bulletin board and
checking that serial numbers in a deposited payment are not equal to any
serial number of previously submitted payments. A blockchain can be used to
implement the bulletin board. When a provider wishes to deposit a payment, the
payment is broadcast to authorities, which could also be $n$ validators in a
proof-of-stake blockchain. The consensus mechanism of the blockchain is then
used to agree on whether the payment is valid and, in that case, recorded in
the blockchain. This allows decentralizing also the deposit phase of our
protocols.

Also, note that authorities in this setting may leave and enter the system
dynamically. However, we must take into account that an authority that leaves
the system still possesses a valid share of the secret key, and we assume
that, after leaving the system, the authority becomes corrupt. Similarly to
decentralized e-cash schemes, in our schemes we assume an honest majority,
i.e. if $n=2a+1$, there are at most $a$ corrupt authorities. For our schemes
to be secure, if $a$ is the number of corrupt authorities currently in the
system, and $b$ is the number of authorities that have left, we need that
$a+b<t$, where $t$ is the threshold. Therefore, algorithm $\mathsf{KeyGenV}$
needs to be run periodically to create a new public verification key
$\mathit{pk}$ and new key pairs
$(\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}})_{i\in[1,n]}$
so as to ensure that $a+b<t$. This implies that e-cash expires whenever a new
key is created. A time interval in which users can convert old wallets to use
the new secret key can be given (Chaum et al., 2021). Once this interval ends,
e-cash expiration makes it possible to delete the payments stored for double-
spending detection and reset the bulletin board, which avoids an ever-growing
blockchain (Chawla, 2022). The blockchain can thus be used as a settlement
layer for offline e-cash transactions.

This scheme would get the best of both worlds, that of online blockchain and
offline e-cash, but further research needs to be done to specify this model
formally and parameterize a real-world implementation. Threshold-issuance
offline e-cash may end up solving the pressing problems of privacy and
scalability of payments in both blockchain and even CBDCs as e-cash moves from
theory into practice.

##  8\. Conclusion

In this work, we proposed the first offline anonymous e-cash scheme with
threshold issuance, motivated by the concrete scalability concerns of
blockchains and concerns with centralization in CBDCs (Bank, 2023). We define
the ideal functionality and propose two instantiations based on an improved
compact and a divisible e-cash. We have shown that our schemes realize the
ideal functionality and formally prove their security. We have also
implemented both schemes and compared their efficiency, showing that compact
e-cash is more efficient and feasible for smaller transactions, which would
naturally compose the majority of offline e-cash transactions in application
scenarios such as a user-facing blockchain or CBDC where practical deployment
concerns would necessitate distributed authorities.

## References

  * (1)
  * Abe et al. (2011) Masayuki Abe, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. 2011.  Optimal Structure-Preserving Signatures in Asymmetric Bilinear Groups. In _Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings_. 649–666.  https://doi.org/10.1007/978-3-642-22792-9_37
  * Baldimtsi et al. (2015) Foteini Baldimtsi, Melissa Chase, Georg Fuchsbauer, and Markulf Kohlweiss. 2015.  Anonymous Transferable E-Cash. In _Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings_ _(Lecture Notes in Computer Science, Vol. 9020)_ , Jonathan Katz (Ed.). Springer, 101–124.  https://doi.org/10.1007/978-3-662-46447-2_5
  * Ballard et al. (2005) Lucas Ballard, Matthew Green, Breno de Medeiros, and Fabian Monrose. 2005.  Correlation-Resistant Storage via Keyword-Searchable Encryption.  _IACR Cryptol. ePrint Arch._ (2005), 417.  http://eprint.iacr.org/2005/417
  * Bank (2023) European Central Bank. 2023\.  "Market research on possible technical solutions for a digital euro".  https://www.ecb.europa.eu/paym/intro/news/html/ecb.mipnews230113.en.html.
  * Baudet et al. (2022) Mathieu Baudet, Alberto Sonnino, Mahimna Kelkar, and George Danezis. 2022.  Zef: Low-latency, Scalable, Private Payments.  _IACR Cryptol. ePrint Arch._ (2022), 83.  https://eprint.iacr.org/2022/083
  * Bauer et al. (2021) Balthazar Bauer, Georg Fuchsbauer, and Chen Qian. 2021\.  Transferable E-Cash: A Cleaner Model and the First Practical Instantiation. In _Public-Key Cryptography - PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10-13, 2021, Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 12711)_ , Juan A. Garay (Ed.). Springer, 559–590.  https://doi.org/10.1007/978-3-030-75248-4_20
  * Belenkiy et al. (2009) Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, and Anna Lysyanskaya. 2009.  Compact E-Cash and Simulatable VRFs Revisited. In _Pairing-Based Cryptography - Pairing 2009, Third International Conference, Palo Alto, CA, USA, August 12-14, 2009, Proceedings_ _(Lecture Notes in Computer Science, Vol. 5671)_ , Hovav Shacham and Brent Waters (Eds.). Springer, 114–131.  https://doi.org/10.1007/978-3-642-03298-1_9
  * Boneh and Boyen (2004) Dan Boneh and Xavier Boyen. 2004.  Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles.  _IACR Cryptol. ePrint Arch._ (2004), 172.  http://eprint.iacr.org/2004/172
  * Boneh and Boyen (2008) Dan Boneh and Xavier Boyen. 2008.  Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups.  _J. Cryptol._ 21, 2 (2008), 149–177.  https://doi.org/10.1007/s00145-007-9005-7
  * Bourse et al. (2019) Florian Bourse, David Pointcheval, and Olivier Sanders. 2019\.  Divisible E-Cash from Constrained Pseudo-Random Functions. In _Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I_ _(Lecture Notes in Computer Science, Vol. 11921)_ , Steven D. Galbraith and Shiho Moriai (Eds.). Springer, 679–708.  https://doi.org/10.1007/978-3-030-34578-5_24
  * Boyle et al. (2014) Elette Boyle, Shafi Goldwasser, and Ioana Ivan. 2014\.  Functional Signatures and Pseudorandom Functions. In _Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings_ _(Lecture Notes in Computer Science, Vol. 8383)_ , Hugo Krawczyk (Ed.). Springer, 501–519.  https://doi.org/10.1007/978-3-642-54631-0_29
  * Camenisch et al. (2008) Jan Camenisch, Rafik Chaabouni, and Abhi Shelat. 2008\.  Efficient Protocols for Set Membership and Range Proofs. In _Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008\. Proceedings_ _(Lecture Notes in Computer Science, Vol. 5350)_ , Josef Pieprzyk (Ed.). Springer, 234–252.  https://doi.org/10.1007/978-3-540-89255-7_15
  * Camenisch et al. (2016) Jan Camenisch, Maria Dubovitskaya, and Alfredo Rial. 2016\.  UC Commitments for Modular Protocol Design and Applications to Revocation and Attribute Tokens. In _Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III_. 208–239.  https://doi.org/10.1007/978-3-662-53015-3_8
  * Camenisch et al. (2005) Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. 2005\.  Compact E-Cash. In _Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings_ _(Lecture Notes in Computer Science, Vol. 3494)_ , Ronald Cramer (Ed.). Springer, 302–321.  https://doi.org/10.1007/11426639_18
  * Camenisch et al. (2009) Jan Camenisch, Markulf Kohlweiss, and Claudio Soriente. 2009\.  An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. In _Public Key Cryptography - PKC 2009, 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings_ _(Lecture Notes in Computer Science, Vol. 5443)_ , Stanislaw Jarecki and Gene Tsudik (Eds.). Springer, 481–500.  https://doi.org/10.1007/978-3-642-00468-1_27
  * Camenisch et al. (2014) Jan Camenisch, Anja Lehmann, Gregory Neven, and Alfredo Rial. 2014.  Privacy-Preserving Auditing for Attribute-Based Credentials. In _Computer Security - ESORICS 2014 \- 19th European Symposium on Research in Computer Security, Wroclaw, Poland, September 7-11, 2014. Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 8713)_ , Miroslaw Kutylowski and Jaideep Vaidya (Eds.). Springer, 109–127.  https://doi.org/10.1007/978-3-319-11212-1_7
  * Camenisch and Stadler (1997) Jan Camenisch and Markus Stadler. 1997.  _Proof Systems for General Statements about Discrete Logarithms_.  Technical Report TR 260. Institute for Theoretical Computer Science, ETH Zürich.
  * Canard and Gouget (2007) Sébastien Canard and Aline Gouget. 2007.  Divisible E-Cash Systems Can Be Truly Anonymous. In _Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings_ _(Lecture Notes in Computer Science, Vol. 4515)_ , Moni Naor (Ed.). Springer, 482–497.  https://doi.org/10.1007/978-3-540-72540-4_28
  * Canard et al. (2015a) Sébastien Canard, David Pointcheval, Olivier Sanders, and Jacques Traoré. 2015a.  Divisible E-Cash Made Practical. In _Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings_ _(Lecture Notes in Computer Science, Vol. 9020)_ , Jonathan Katz (Ed.). Springer, 77–100.  https://doi.org/10.1007/978-3-662-46447-2_4
  * Canard et al. (2015b) Sébastien Canard, David Pointcheval, Olivier Sanders, and Jacques Traoré. 2015b.  Scalable Divisible E-cash. In _Applied Cryptography and Network Security - 13th International Conference, ACNS 2015, New York, NY, USA, June 2-5, 2015, Revised Selected Papers_ _(Lecture Notes in Computer Science, Vol. 9092)_ , Tal Malkin, Vladimir Kolesnikov, Allison Bishop Lewko, and Michalis Polychronakis (Eds.). Springer, 287–306.  https://doi.org/10.1007/978-3-319-28166-7_14
  * Canetti (2001) Ran Canetti. 2001\.  Universally Composable Security: A New Paradigm for Cryptographic Protocols. In _42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA_. 136–145.  https://doi.org/10.1109/SFCS.2001.959888
  * Chaum (1982) David Chaum. 1982\.  Blind Signatures for Untraceable Payments. In _Advances in Cryptology: Proceedings of CRYPTO ’82, Santa Barbara, California, USA, August 23-25, 1982_ , David Chaum, Ronald L. Rivest, and Alan T. Sherman (Eds.). Plenum Press, New York, 199–203.  https://doi.org/10.1007/978-1-4757-0602-4_18
  * Chaum et al. (2021) David Chaum, Christian Grothoff, and Thomas Moser. 2021\.  How to issue a central bank digital currency.  _arXiv preprint arXiv:2103.00254_ (2021).
  * Chaum and Pedersen (1992) David Chaum and Torben P. Pedersen. 1992.  Transferred Cash Grows in Size. In _Advances in Cryptology - EUROCRYPT ’92, Workshop on the Theory and Application of of Cryptographic Techniques, Balatonfüred, Hungary, May 24-28, 1992, Proceedings_ _(Lecture Notes in Computer Science, Vol. 658)_ , Rainer A. Rueppel (Ed.). Springer, 390–407.  https://doi.org/10.1007/3-540-47555-9_32
  * Chawla (2022) Vishal Chawla. 2022\.  "Someone is clogging up the Zcash blockchain with a spam attack".  https://www.theblock.co/post/175259/someone-is-clogging-up-the-zcash-blockchain-with-a-spam-attack.
  * Danezis and Meiklejohn (2016) George Danezis and Sarah Meiklejohn. 2016.  Centrally banked cryptocurrencies.  _NDSS Symposium_ (2016).
  * Dmitrienko et al. (2017) Alexandra Dmitrienko, David Noack, and Moti Yung. 2017\.  Secure Wallet-Assisted Offline Bitcoin Payments with Double-Spender Revocation _(ASIA CCS ’17)_. Association for Computing Machinery, New York, NY, USA, 520–531.  https://doi.org/10.1145/3052973.3052980
  * Dodis and Yampolskiy (2005) Yevgeniy Dodis and Aleksandr Yampolskiy. 2005.  A Verifiable Random Function with Short Proofs and Keys. In _Public Key Cryptography - PKC 2005, 8th International Workshop on Theory and Practice in Public Key Cryptography, Les Diablerets, Switzerland, January 23-26, 2005, Proceedings_ _(Lecture Notes in Computer Science, Vol. 3386)_ , Serge Vaudenay (Ed.). Springer, 416–431.  https://doi.org/10.1007/978-3-540-30580-4_28
  * Faust et al. (2012) Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi. 2012.  On the non-malleability of the Fiat-Shamir transform.  In _Progress in Cryptology-INDOCRYPT 2012_. Springer, 60–79.
  * Fiat and Shamir (1987) Amos Fiat and Adi Shamir. 1987.  How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In _CRYPTO ’86_ , Andrew M. Odlyzko (Ed.), Vol. 263. Springer Verlag, 186–194.
  * Goldreich et al. (1986) Oded Goldreich, Shafi Goldwasser, and Silvio Micali. 1986\.  How to construct random functions.  _J. ACM_ 33, 4 (1986), 792–807.  https://doi.org/10.1145/6490.6503
  * Goldwasser et al. (1988) Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. 1988\.  A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks.  _SIAM J. Comput._ 17, 2 (1988), 281–308.
  * Green and Miers (2017) Matthew Green and Ian Miers. 2017.  Bolt: Anonymous Payment Channels for Decentralized Currencies. In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017_ , Bhavani Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM, 473–489.  https://doi.org/10.1145/3133956.3134093
  * Groth (2021) Jens Groth. 2021\.  Non-interactive distributed key generation and key resharing.  Cryptology ePrint Archive, Report 2021/339.  https://eprint.iacr.org/2021/339.
  * Groth and Sahai (2008) Jens Groth and Amit Sahai. 2008.  Efficient Non-interactive Proof Systems for Bilinear Groups. In _Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008\. Proceedings_ _(Lecture Notes in Computer Science, Vol. 4965)_ , Nigel P. Smart (Ed.). Springer, 415–432.  https://doi.org/10.1007/978-3-540-78967-3_24
  * Kappos et al. (2021) George Kappos, Haaroon Yousaf, Ania M. Piotrowska, Sanket Kanjalkar, Sergi Delgado-Segura, Andrew Miller, and Sarah Meiklejohn. 2021\.  An Empirical Analysis of Privacy in the Lightning Network. In _Financial Cryptography and Data Security - 25th International Conference, FC 2021, Virtual Event, March 1-5, 2021, Revised Selected Papers, Part I_ _(Lecture Notes in Computer Science, Vol. 12674)_ , Nikita Borisov and Claudia Díaz (Eds.). Springer, 167–186.  https://doi.org/10.1007/978-3-662-64322-8_8
  * Kate et al. (2012) Aniket Kate, Yizhou Huang, and Ian Goldberg. 2012\.  Distributed Key Generation in the Wild.  _IACR Cryptol. ePrint Arch._ 2012 (2012), 377.  http://eprint.iacr.org/2012/377
  * Kim et al. (2021a) Hyoseung Kim, Youngkyung Lee, Michel Abdalla, and Jong Hwan Park. 2021a.  Practical dynamic group signature with efficient concurrent joins and batch verifications.  _J. Inf. Secur. Appl._ 63 (2021), 103003.  https://doi.org/10.1016/j.jisa.2021.103003
  * Kim et al. (2021b) Hyoseung Kim, Olivier Sanders, Michel Abdalla, and Jong Hwan Park. 2021b.  Practical Dynamic Group Signatures Without Knowledge Extractors.  _IACR Cryptol. ePrint Arch._ (2021), 351.  https://eprint.iacr.org/2021/351
  * Lovejoy et al. (2022) James Lovejoy, Cory Fields, Madars Virza, Tyler Frederick, David Urness, Kevin Karwaski, Anders Brownworth, and Neha Narula. 2022\.  A high performance payment processing system designed for central bank digital currencies.  _Cryptology ePrint Archive_ (2022).
  * Marshall and Rochon (2009) Wesley C Marshall and Louis-Philippe Rochon. 2009.  Financing economic development in Latin America: the Banco del Sur.  _Journal of Post Keynesian Economics_ 32, 2 (2009), 185–198.
  * Miers et al. (2013) Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. 2013.  Zerocoin: Anonymous Distributed E-Cash from Bitcoin. In _2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19-22, 2013_. IEEE Computer Society, 397–411.  https://doi.org/10.1109/SP.2013.34
  * Noether and Mackenzie (2016) Shen Noether and Adam Mackenzie. 2016.  Ring Confidential Transactions.  _Ledger_ 1 (2016), 1–18.  https://ledgerjournal.org/ojs/index.php/ledger/article/view/34
  * Okamoto and Ohta (1989) Tatsuaki Okamoto and Kazuo Ohta. 1989.  Disposable Zero-Knowledge Authentications and Their Applications to Untraceable Electronic Cash. In _Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings_ _(Lecture Notes in Computer Science, Vol. 435)_ , Gilles Brassard (Ed.). Springer, 481–496.  https://doi.org/10.1007/0-387-34805-0_43
  * Okamoto and Ohta (1991) Tatsuaki Okamoto and Kazuo Ohta. 1991.  Universal Electronic Cash. In _Advances in Cryptology - CRYPTO ’91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1991, Proceedings_ _(Lecture Notes in Computer Science, Vol. 576)_ , Joan Feigenbaum (Ed.). Springer, 324–337.  https://doi.org/10.1007/3-540-46766-1_27
  * Pedersen (1991) Torben P. Pedersen. 1991\.  Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In _CRYPTO_ _(Lecture Notes in Computer Science, Vol. 576)_ , Joan Feigenbaum (Ed.). Springer, 129–140.
  * Pointcheval and Sanders (2016) David Pointcheval and Olivier Sanders. 2016.  Short Randomizable Signatures. In _Topics in Cryptology - CT-RSA 2016 - The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 - March 4, 2016, Proceedings_ _(Lecture Notes in Computer Science, Vol. 9610)_ , Kazue Sako (Ed.). Springer, 111–126.  https://doi.org/10.1007/978-3-319-29485-8_7
  * Pointcheval et al. (2017) David Pointcheval, Olivier Sanders, and Jacques Traoré. 2017\.  Cut Down the Tree to Achieve Constant Complexity in Divisible E-cash. In _Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I_ _(Lecture Notes in Computer Science, Vol. 10174)_ , Serge Fehr (Ed.). Springer, 61–90.  https://doi.org/10.1007/978-3-662-54365-8_4
  * Rial and Piotrowska (2022) Alfredo Rial and Ania M. Piotrowska. 2022.  Security Analysis of Coconut, an Attribute-Based Credential Scheme with Threshold Issuance.  Cryptology ePrint Archive, Report 2022/011.  https://ia.cr/2022/011.
  * Sasson et al. (2014) Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014.  Zerocash: Decentralized anonymous payments from bitcoin. In _2014 IEEE symposium on security and privacy_. IEEE, 459–474.
  * Shallit (2003) Jeffrey Shallit. 2003\.  What this country needs is an 18c piece.  _Mathematical Intelligencer_ 25, 2 (2003), 20–23.
  * Sharma et al. (2022) Piyush Kumar Sharma, Devashish Gosain, and Claudia Diaz. 2022\.  On the anonymity of peer-to-peer network anonymity schemes used by cryptocurrencies.  _arXiv preprint arXiv:2201.11860_ (2022).
  * Sonnino et al. (2019) Alberto Sonnino, Mustafa Al-Bassam, Shehar Bano, Sarah Meiklejohn, and George Danezis. 2019\.  Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed Ledgers. In _26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24-27, 2019_. The Internet Society.  https://www.ndss-symposium.org/ndss-paper/coconut-threshold-issuance-selective-disclosure-credentials-with-applications-to-distributed-ledgers/
  * van Saberhagen (2013) Nicolas van Saberhagen. 2013\.  Cryptonote v2.0.  https://cryptonote.org/whitepaper.pdf.
  * Wikström (2004) Douglas Wikström. 2004\.  A Universally Composable Mix-Net. In _Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings_ _(Lecture Notes in Computer Science, Vol. 2951)_ , Moni Naor (Ed.). Springer, 317–335.  https://doi.org/10.1007/978-3-540-24638-1_18
  * Xu (2022) Jianguo Xu. 2022\.  Developments and implications of central bank digital currency: The case of China e-CNY.  _Asian Economic Policy Review_ 17, 2 (2022), 235–250.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019\.  HotStuff: BFT consensus with linearity and responsiveness. In _Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing_. 347–356.
  * Zamyatin et al. (2021) Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J Knottenbelt. 2021.  Sok: Communication across distributed ledgers. In _Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part II 25_. Springer, 3–36.

##  Appendix A Building Blocks

###  A.1. Bilinear Maps

Let $\mathbb{G}$, $\mathbb{\tilde{G}}$ and ${\mathbb{G}_{t}}$ be groups of
prime order $\mathit{p}$. A map
$\mathit{e}:\mathbb{G}\times\mathbb{\tilde{G}}\rightarrow{\mathbb{G}_{t}}$
must satisfy bilinearity, i.e.,
$\mathit{e}(\mathit{g}^{x},\mathit{\tilde{g}}^{y})=e(\mathit{g},\mathit{\tilde{g}})^{xy}$;
non-degeneracy, i.e., for all generators $\mathit{g}\in\mathbb{G}$ and
$\mathit{\tilde{g}}\in\mathbb{\tilde{G}}$,
$\mathit{e}(\mathit{g},\mathit{\tilde{g}})$ generates ${\mathbb{G}_{t}}$; and
efficiency, i.e., there exists an efficient algorithm
$\mathcal{G}(1^{\mathit{k}})$ that outputs the pairing group setup
$(\mathit{p},\mathbb{G},\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\mathit{e},\mathit{g},\mathit{\tilde{g}})$
and an efficient algorithm to compute $\mathit{e}(a,b)$ for any
$a\in\mathbb{G}$, $b\in\mathbb{\tilde{G}}$. In type 3 pairings,
$\mathbb{G}\neq\mathbb{\tilde{G}}$ and there exists no efficiently computable
homomorphism $f:\mathbb{\tilde{G}}\rightarrow\mathbb{G}$.

###  A.2. Assumptions

We recall the assumptions that are needed to prove the security of our
schemes.

###### Definition A.1.

[XDH and SXDH Assumptions (Ballard et al., 2005)] Given
$(\mathit{p},\allowbreak\mathbb{G},\allowbreak\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\allowbreak\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}})$,
the external Diffie-Hellman assumption states that the decisional Diffie-
Hellman problem is intractable in $\mathbb{G}$ or in $\mathbb{\tilde{G}}$. The
symmetric external Diffie-Hellman assumption states that it is intractable in
both $\mathbb{G}$ and $\mathbb{\tilde{G}}$.

###### Definition A.2.

[$q$-SDH Assumption (Boneh and Boyen, 2008)] Given
$(\mathit{g},\allowbreak\mathit{g}^{x},\allowbreak\mathit{g}^{x^{2}},\allowbreak\ldots,\allowbreak\mathit{g}^{x^{q}})\allowbreak\in\allowbreak\mathbb{G}^{q+1}$,
the strong Diffie-Hellman assumption states that it is hard to output a pair
$(m,\allowbreak\mathit{g}^{1/(x+m)})\in\mathbb{Z}_{p}\times\mathbb{G}$.

###### Definition A.3.

[$y$-DDHI Assumption (Camenisch et al., 2005)] Let $\mathbb{G}$ be a group of
prime order $q$ and let $\mathit{g}$ be a generator of $\mathbb{G}$. Given
$(\mathit{g},\allowbreak\mathit{g}^{x},\ldots,\allowbreak\mathit{g}^{(x^{y})},\allowbreak
R)$ for a random $x\leftarrow\mathbb{Z}_{p}$, the decisional Diffie-Hellman
inversion assumption states that it is hard to decide if $R=\mathit{g}^{1/x}$
or not.

###### Definition A.4.

[$N$-BDHI Assumption (Boneh and Boyen, 2004)] Given
$(\mathit{p},\allowbreak\mathbb{G},\allowbreak\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\allowbreak\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}})$
and the tuple
$(\\{\mathit{g}^{y^{i}}\\}_{i=0}^{N},\\{\mathit{\tilde{g}}^{y^{i}}\\}_{i=0}^{N})\in\mathbb{G}^{N+1}\times\mathbb{\tilde{G}}^{N+1}$,
the bilinear Diffie-Hellman inversion assumption states that it is hard to
compute $\mathit{e}(\mathit{g},\mathit{\tilde{g}})^{1/y}\in{\mathbb{G}_{t}}$.

###### Definition A.5.

[$N$-MXDH’ Assumption (Pointcheval et al., 2017)] $\forall
N\in\mathbb{N^{\ast}}$, we define $C=N^{3}-N^{2}$, $S=C+1$, $E=N^{2}-N$,
$D=S+E$, and $P=D+C$. Given
$(\mathit{p},\mathbb{G},\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\mathit{e},\mathit{g},\mathit{\tilde{g}})$
and
$\\{(\mathit{g}^{\gamma^{k}},\allowbreak\mathit{h}^{\gamma^{k}})_{k=0}^{P},\allowbreak(\mathit{g}^{\alpha\delta\gamma^{-k}},\allowbreak\mathit{h}^{\alpha\delta\gamma^{-k}})_{k=0}^{E},\allowbreak(\mathit{g}^{\chi\gamma^{k}},\allowbreak\mathit{h}^{\chi\gamma^{k}})_{k=D+1}^{P},\allowbreak(\mathit{g}^{\alpha\gamma^{-k}},\allowbreak\mathit{g}^{\chi\gamma^{k}/\alpha},\allowbreak\mathit{h}^{\chi\gamma^{k}/\alpha})_{k=0}^{C}\\}\allowbreak\in\allowbreak\mathbb{G}^{2P+5S+2E+2}$,
as well as
$(\mathit{\tilde{g}}^{\gamma^{k}},\mathit{\tilde{g}}^{\alpha\gamma^{-k}})_{k=0}^{C}\in\mathbb{\tilde{G}}^{2S}$
and a pair $(\mathit{g}^{z_{1}},\mathit{h}^{z_{2}})\in\mathbb{G}^{2}$, it is
hard to decide whether $z_{1}=z_{2}=\delta+\chi\gamma^{D}/\alpha$ or
$(z_{1},\allowbreak z_{2})$ is random.

###### Definition A.6.

[$n$-DHE (Camenisch et al., 2009)] Let
$(\mathit{p},\allowbreak\mathbb{G},\allowbreak\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\allowbreak\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}})\allowbreak\leftarrow\allowbreak\mathcal{G}(1^{k})$
and $\alpha\allowbreak\leftarrow\allowbreak\mathbb{Z}_{p}$. Given
$(\mathit{p},\allowbreak\mathbb{G},\allowbreak\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\allowbreak\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}})$
and a tuple
$(\mathit{g}_{1},\allowbreak\mathit{\tilde{g}}_{1},\allowbreak\ldots,\allowbreak\mathit{g}_{n},\allowbreak\mathit{\tilde{g}}_{n},\allowbreak\mathit{g}_{n+2},\allowbreak\ldots,\allowbreak\mathit{g}_{2n})$
such that $\mathit{g}_{i}\allowbreak=\allowbreak\mathit{g}^{(\alpha^{i})}$ and
$\mathit{\tilde{g}}_{i}\allowbreak=\allowbreak\mathit{\tilde{g}}^{(\alpha^{i})}$,
for any p.p.t. adversary $\mathcal{A}$,
$\mathrm{Pr}[\mathit{g}^{(\alpha^{n+1})}\allowbreak\leftarrow\allowbreak\mathcal{A}(\mathit{p},\allowbreak\mathbb{G},\allowbreak\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\allowbreak\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}},\allowbreak\mathit{g}_{1},\allowbreak\mathit{\tilde{g}}_{1},\allowbreak\ldots,\allowbreak\mathit{g}_{n},\allowbreak\mathit{\tilde{g}}_{n},\allowbreak\mathit{g}_{n+2},\allowbreak\ldots,\allowbreak\mathit{g}_{2n})]\allowbreak\leq\allowbreak\epsilon(k)$.

###  A.3. Zero-Knowledge Arguments of Knowledge

Informally speaking, a zero-knowledge argument of knowledge is a two-party
protocol between a prover and a verifier with two properties. First, it should
be a proof of knowledge, i.e., there should exist a knowledge extractor that
extracts the secret input from a successful prover with all but negligible
probability. Second, it should be zero-knowledge, i.e., for all possible
verifiers there exists a simulator that, without knowledge of the secret
input, yields a distribution that cannot be distinguished from the interaction
with a real prover.

To express a zero-knowledge argument of knowledge, we follow the notation
introduced by Camenisch and Stadler (Camenisch and Stadler, 1997), i.e., we
denote as ${\mathsf{ZK}}\\{(w):y=f(w)\\}$ a “zero-knowledge proof of knowledge
of the secret input $w$ such that $y=f(w)$”, where $w$ is a secret input,
while $y$ and the function $f$ are publicly known.

Let $\mathcal{L}$ be a language in NP. We can associate to any NP-language
$\mathcal{L}$ a polynomial time recognizable relation
$\mathcal{R}_{\mathcal{L}}$ defining $\mathcal{L}$ as
$\mathcal{L}=\\{x:\exists w\ \mathrm{s.t.}\
(x,w)\in\mathcal{R}_{\mathcal{L}}\\}$, where $|w|\leq\mathrm{poly}(|x|)$. The
string $w$ is called a witness for membership of $x\in\mathcal{L}$.

A protocol $\Sigma=(\mathcal{P},\mathcal{V})$ for an NP-language $\mathcal{L}$
is an interactive proof system. The prover $\mathcal{P}$ and the verifier
$\mathcal{V}$ know an instance $x$ of the language $\mathcal{L}$. The prover
$\mathcal{P}$ also knows a witness $w$ for membership of $x\in\mathcal{L}$.
$\Sigma$-protocols have a 3-move shape where the first message $\alpha$,
called _commitment_ , is sent by the prover. The second message $\beta$,
called _challenge_ , is chosen randomly and sent by the verifier. The last
message $\gamma$, called _response_ , is sent by the prover. A
$\Sigma$-protocol fulfills the properties of completeness, honest-verifier
zero-knowledge, and special soundness defined in Faust et al. (Faust et al.,
2012).

In our e-cash schemes, zero-knowledge arguments of knowledge based on the
Fiat-Shamir transform (Fiat and Shamir, 1987) are used. The Fiat-Shamir
transform removes the interaction between the prover $\mathcal{P}$ and the
verifier $\mathcal{V}$ of a $\Sigma$ protocol by replacing the challenge with
a hash value $H(\alpha,x)$ computed by the prover, where $H$ is modeled as a
random oracle. (It is possible to include an additional message $m$ as input
to $H$, i.e. $H(\alpha,x,m)$, turning the argument of knowledge into a
_signature of knowledge_ of the message $m$.) An argument $\pi$ consists of
$(\alpha,H(\alpha,x),\gamma)$. The Fiat-Shamir system is denoted by
$(\mathcal{P}^{H},\mathcal{V}^{H})$ and fulfills the properties of zero-
knowledge and weak simulation extractability defined in Faust et al. (Faust et
al., 2012), which we recall below.

###### Definition A.7 (Zero-Knowledge).

Define the zero knowledge simulator $\mathcal{S}$ as follows. $\mathcal{S}$ is
a stateful algorithm that can operate in two modes:
$(h_{i},st)\leftarrow\mathcal{S}(1,st,q_{i})$ answers random oracle queries
$q_{i}$, while $(\pi,st)\leftarrow\mathcal{S}(2,st,x)$ outputs a simulated
proof $\pi$ for an instance $x$. $\mathcal{S}(1,\cdots)$ and
$\mathcal{S}(2,\cdots)$ share the state $st$ that is updated after each
operation.

Let $\mathcal{L}$ be a language in NP. Denote with
$(\mathcal{S}_{1},\mathcal{S}_{2})$ the oracles such that
$\mathcal{S}_{1}(q_{i})$ returns the first output of
$(h_{i},st)\leftarrow\mathcal{S}(1,st,q_{i})$ and $\mathcal{S}_{2}(x,w)$
returns the first output of $(\pi,st)\leftarrow\mathcal{S}(2,st,x)$ if
$(x,w)\in\mathcal{R}_{\mathcal{L}}$. A protocol
$(\mathcal{P}^{H},\mathcal{V}^{H})$ is a non-interactive zero-knowledge proof
for the language $\mathcal{L}$ in the random oracle model if there exists a
ppt simulator $\mathcal{S}$ such that for all ppt distinguishers $\mathcal{D}$
we have

$\textrm{Pr}[\mathcal{D}^{H(\cdot),\mathcal{P}^{H}(\cdot,\cdot)}(1^{k})=1]\approx\textrm{Pr}[\mathcal{D}^{\mathcal{S}_{1}(\cdot),\mathcal{S}_{2}(\cdot,\cdot)}(1^{k})=1],$

where both $\mathcal{P}$ and $\mathcal{S}_{2}$ oracles output $\bot$ if
$(x,w)\notin\mathcal{R}_{\mathcal{L}}$.

###### Definition A.8 (Weak Simulation Extractability).

Let $\mathcal{L}$ be a language in NP. Consider a non-interactive zero-
knowledge proof system $(\mathcal{P}^{H},\mathcal{V}^{H})$ for $\mathcal{L}$
with zero-knowledge simulator $\mathcal{S}$. Let
$(\mathcal{S}_{1},\mathcal{S}^{\prime}_{2})$ be oracles returning the first
output of $(h_{i},st)\leftarrow\mathcal{S}(1,st,q_{i})$ and
$(\pi,st)\leftarrow\mathcal{S}(2,st,x)$ respectively.
$(\mathcal{P}^{H},\mathcal{V}^{H})$ is weakly simulation extractable with
extraction error $\nu$ and with respect to $\mathcal{S}$ in the random oracle
model, if for all ppt adversaries $\mathcal{A}$ there exists an efficient
algorithm $\mathcal{E}_{\mathcal{A}}$ with access to the answers
$(\mathcal{T}_{H},\mathcal{T})$ of
$(\mathcal{S}_{1},\mathcal{S}^{\prime}_{2})$ respectively such that the
following holds. Let

$\displaystyle\mathrm{acc}=\textrm{Pr}[(x^{\ast},\pi^{\ast})\leftarrow\mathcal{A}^{\mathcal{S}_{1}(\cdot),\mathcal{S}^{\prime}_{2}(\cdot)}(1^{k};\rho):$
$\displaystyle(x^{\ast},\pi^{\ast})\notin\mathcal{T};\mathcal{V}^{\mathcal{S}_{1}}(x^{\ast},\pi^{\ast})=1]$
$\displaystyle\mathrm{ext}=\textrm{Pr}[(x^{\ast},\pi^{\ast})\leftarrow\mathcal{A}^{\mathcal{S}_{1}(\cdot),\mathcal{S}^{\prime}_{2}(\cdot)}(1^{k};\rho);$
$\displaystyle\indent
w^{\ast}\leftarrow\mathcal{E}_{\mathcal{A}}(x^{\ast},\pi^{\ast};\rho,\mathcal{T}_{H},\mathcal{T}):(x^{\ast},\pi^{\ast})\notin\mathcal{T};(x^{\ast},w^{\ast})\in\mathcal{R}_{\mathcal{L}}],$

where the probability space in both cases is over the random choices of
$\mathcal{S}$ and the adversary’s random tape $\rho$. Then, there exists a
constant $d>0$ and a polynomial $p$ such that whenever $\mathrm{acc}\geq\nu$,
we have $\mathrm{ext}\geq(1/p)(\mathrm{acc}-\nu)^{d}$.

##### Types of proofs.

We use known results for computing ZK proofs of discrete logarithms (Camenisch
and Stadler, 1997). A protocol proving knowledge of exponents
$(w_{1},\allowbreak\ldots,\allowbreak w_{n})$ that satisfy the formula
$\phi(w_{1},\allowbreak\ldots,\allowbreak w_{n})$ is described as

(1) ${\mathsf{ZK}}\\{(w_{1},\ldots,w_{n}):1=\phi(w_{1},\ldots,w_{n})\\}$

The formula $\phi(w_{1},\ldots,\allowbreak w_{n})$ consists of conjunctions
and disjunctions of “atoms”. An atom expresses group relations, such as

$\prod_{j=1}^{k}g_{j}^{f_{j}}=1$

where the $g_{j}$’s are elements of prime order groups and the $f_{j}$’s are
polynomials in the variables $(w_{1},\allowbreak\ldots,\allowbreak w_{n})$.

A proof system for (1) can be transformed into a proof system for more
expressive statements about secret exponents $\mathit{sexps}$ and secret bases
$\mathit{sbases}$:

(2)
${\mathsf{ZK}}\\{(\mathit{sexps},\mathit{sbases}):1=\phi(\mathit{sexps},\mathit{bases}\cup\mathit{sbases})\\}$

The transformation adds an additional base $h$ to the public bases. For each
$g_{j}\in\mathit{sbases}$, the transformation picks a random exponent
$\rho_{j}$ and computes a blinded base
$g_{j}^{\prime}=g_{j}\mathit{h}^{\rho_{j}}$. The transformation adds
$g^{\prime}_{j}$ to the public bases $\mathit{bases}$, $\rho_{j}$ to the
secret exponents $\mathit{sexps}$, and rewrites $g_{j}^{f_{j}}$ into
${g_{j}^{\prime}}^{f_{j}}h^{-f_{j}\rho_{j}}$.

The proof system supports pairing product equations

(3) $\prod_{j=1}^{k}e(g_{j},\tilde{g}_{j})^{f_{j}}=1$

in groups of prime order with a bilinear map $\mathit{e}$, by treating the
target group ${\mathbb{G}_{t}}$ as the group of the proof system. The
embedding for secret bases is unchanged, except for the case in which both
bases in a pairing are secret. In this case, $e(g_{j},\tilde{g}_{j})^{f_{j}}$
must be transformed into
$e(g^{\prime}_{j},\tilde{g}^{\prime}_{j})^{f_{j}}e(g_{j}^{\prime},\tilde{h})^{-f_{j}\tilde{\rho}_{j}}e(h,\tilde{g}^{\prime}_{j})^{-f_{j}\rho_{j}}\allowbreak
e(h,\tilde{h})^{f_{j}\rho_{j}\tilde{\rho}_{j}}$.

###  A.4. Commitment Schemes

A commitment scheme consists of algorithms $\mathsf{CSetup}$, $\mathsf{Com}$
and $\mathsf{VfCom}$. The algorithm $\mathsf{CSetup}(1^{\mathit{k}})$
generates the parameters of the commitment scheme $\mathit{par_{c}}$, which
include a description of the message space $\mathcal{M}$.
$\mathsf{Com}(\mathit{par_{c}},\mathit{x})$ outputs a commitment
$\mathit{com}$ to $\mathit{x}$ and auxiliary information $\mathit{open}$. A
commitment is opened by revealing $(\mathit{x},\allowbreak\mathit{open})$ and
checking whether
$\mathsf{VfCom}(\mathit{par_{c}},\mathit{com},\mathit{x},\mathit{open})$
outputs $1$ or $0$.

A commitment scheme should fulfill the _correctness_ , _hiding_ and _binding_
properties. We recall the definitions of those properties below.

###### Definition A.9 (Correctness).

Correctness requires that $\mathsf{VfCom}$ accepts all commitments created by
algorithm $\mathsf{Com}$, i.e., for all $\mathit{x}\in\mathcal{M}$

$\textrm{Pr}\left[\begin{array}[]{c}\mathit{par_{c}}\leftarrow\mathsf{CSetup}(1^{\mathit{k}});\
(\mathit{com},\mathit{open})\leftarrow\mathsf{Com}(\mathit{par_{c}},\mathit{x}):\\\
1=\mathsf{VfCom}(\mathit{par_{c}},\mathit{com},\mathit{x},\mathit{open})\end{array}\right]=1~{}.$

###### Definition A.10 (Hiding Property).

The hiding property ensures that a commitment $\mathit{com}$ to $\mathit{x}$
does not reveal any information about $\mathit{x}$. For any ppt adversary
$\mathcal{A}$, the hiding property is defined as follows:

$\textrm{Pr}\left[\begin{array}[]{l}\mathit{par_{c}}\leftarrow\mathsf{CSetup}(1^{\mathit{k}});\\\
(\mathit{x}_{0},\mathit{x}_{1},\mathit{st})\leftarrow\mathcal{A}(\mathit{par_{c}});\\\
\mathit{b}\leftarrow\\{0,1\\};\
(\mathit{com},\mathit{open})\leftarrow\mathsf{Com}(\mathit{par_{c}},\mathit{x}_{\mathit{b}});\\\
\mathit{b}^{\prime}\leftarrow\mathcal{A}(\mathit{st},\mathit{com}):\\\
\mathit{x}_{0}\in\mathcal{M}\ \land\ \mathit{x}_{1}\in\mathcal{M}\ \land\
\mathit{b}=\mathit{b}^{\prime}\end{array}\right]\leq\frac{1}{2}+\mathit{\epsilon}(\mathit{k})~{}.$

###### Definition A.11 (Binding Property).

The binding property ensures that $\mathit{com}$ cannot be opened to another
value $\mathit{x}^{\prime}$. For any ppt adversary $\mathcal{A}$, the binding
property is defined as follows:

$\textrm{Pr}\left[\begin{array}[]{l}\mathit{par_{c}}\leftarrow\mathsf{CSetup}(1^{\mathit{k}});\\\
(\mathit{com},\mathit{x},\mathit{open},\mathit{x}^{\prime},\mathit{open}^{\prime})\leftarrow\mathcal{A}(\mathit{par_{c}}):\\\
\mathit{x}\in\mathcal{M}\ \land\ \mathit{x}^{\prime}\in\mathcal{M}\
\land\mathit{x}\neq\mathit{x}^{\prime}\\\ \land\
1=\mathsf{VfCom}(\mathit{par_{c}},\mathit{com},\mathit{x},\mathit{open})\\\
\land\
1=\mathsf{VfCom}(\mathit{par_{c}},\mathit{com},\mathit{x}^{\prime},\mathit{open}^{\prime})\end{array}\right]\leq\mathit{\epsilon}(\mathit{k})~{}.$

Our e-cash schemes use the commitment scheme by Pedersen (Pedersen, 1991) to
commit to elements $x\in\mathbb{Z}_{p}$, where $p$ is a prime. This commitment
scheme is perfectly hiding and computationally binding under the discrete
logarithm assumption. The Pedersen commitment scheme consists of the following
algorithms.

$\bullet$ $\mathsf{CSetup}(1^{k})$.:

On input the security parameter $1^{k}$, pick random generators
$\mathit{g},\mathit{h}$ of a group $\mathbb{G}_{p}$ of prime order
$\mathit{p}$. Output $\mathit{par_{c}}=(g,h,\mathcal{M})$, where
$\mathcal{M}=\mathbb{Z}_{p}$.

$\bullet$ $\mathsf{Com}(\mathit{par_{c}},x)$.:

Check that $x\in\mathcal{M}$. Pick random value
$\mathit{open}\in\mathbb{Z}_{p}$, compute
$\mathit{com}=\mathit{g}^{\mathit{open}}\mathit{h}^{x}$, and output
$\mathit{com}$.

$\bullet$
$\mathsf{VfCom}(\mathit{par_{c}},\mathit{com},x^{\prime},\mathit{open}^{\prime})$.:

Recompute
$\mathit{com}^{\prime}=\mathit{g}^{\mathit{open}^{\prime}}\mathit{h}^{x^{\prime}}$.
If $\mathit{com}\allowbreak=\allowbreak\mathit{com}^{\prime}$ then output $1$
else $0$.

When committing to a tuple of messages, the Pedersen commitment scheme works
as follows.

$\bullet$ $\mathsf{CSetup}(1^{\mathit{k}},l)$.:

On input the security parameter $1^{\mathit{k}}$ and an upper bound $l$ on the
number of elements to be committed, pick $l+1$ random generators
$\mathit{h}_{1},\ldots,\mathit{h}_{l},\mathit{g}$ of a group $\mathbb{G}_{p}$
of prime order $\mathit{p}$. Output
$\mathit{par_{c}}=(h_{1},\ldots,h_{l},g,\mathcal{M})$, where
$\mathcal{M}=\mathbb{Z}_{p}^{l}$.

$\bullet$ $\mathsf{Com}(\mathit{par_{c}},\langle x_{1},\ldots,x_{l}\rangle)$.:

Pick random value $\mathit{open}\leftarrow\mathbb{Z}_{p}$, compute
$\mathit{com}=\mathit{g}^{\mathit{open}}\prod_{i=1}^{l}\mathit{h}_{i}^{x_{i}}$
and output $\mathit{com}$.

$\bullet$ $\mathsf{VfCom}(\mathit{par_{c}},\mathit{com},\langle
x^{\prime}_{1},\ldots,x^{\prime}_{l}\rangle,\mathit{open}^{\prime})$.:

Recompute commitment
$\mathit{com}^{\prime}=\mathit{g}^{\mathit{open}^{\prime}}\prod_{i=1}^{l}\mathit{h}_{i}^{x^{\prime}_{i}}$.
If it is the case that $\mathit{com}=\mathit{com}^{\prime}$ then output $1$
else $0$.

###  A.5. Signature Schemes

A signature scheme consists of the algorithms $\mathsf{KeyGen}$,
$\mathsf{Sign}$, and $\mathsf{VfSig}$. $\mathsf{KeyGen}(1^{\mathit{k}})$
outputs a secret key $\mathit{sk}$ and a public key $\mathit{pk}$, which
include a description of the message space $\mathcal{M}$.
$\mathsf{Sign}(\mathit{sk},\mathit{m})$ outputs a signature $\mathit{\sigma}$
on message $\mathit{m}\in\mathcal{M}$.
$\mathsf{VfSig}(\mathit{pk},\mathit{\sigma},\mathit{m})$ outputs $1$ if
$\mathit{\sigma}$ is a valid signature on $\mathit{m}$ and $0$ otherwise. This
definition can be extended to blocks of messages
$(\mathit{m}_{1},\ldots,\mathit{m}_{q})$. In this case,
$\mathsf{KeyGen}(1^{\mathit{k}},q)$ receives the maximum number of messages as
input. A signature scheme must fulfill the correctness and existential
unforgeability properties (Goldwasser et al., 1988), which we recall below.

###### Definition A.12 (Correctness).

Correctness ensures that the algorithm $\mathsf{VfSig}$ accepts the signatures
created by the algorithm $\mathsf{Sign}$ on input a secret key computed by
algorithm $\mathsf{KeyGen}$. More formally, correctness is defined as follows.

$\textrm{Pr}\left[\begin{array}[]{l}(\mathit{sk},\mathit{pk})\leftarrow\mathsf{KeyGen}(1^{\mathit{k}});\
\mathit{m}\leftarrow\mathcal{M};\\\
\mathit{\sigma}\leftarrow\mathsf{Sign}(\mathit{sk},\mathit{m}):\
1=\mathsf{VfSig}(\mathit{pk},\mathit{\sigma},\mathit{m})\end{array}\right]=1$

###### Definition A.13 (Existential Unforgeability).

The property of existential unforgeability ensures that it is not feasible to
output a signature on a message without knowledge of the secret key or of
another signature on that message. Let $\mathcal{O}_{s}$ be an oracle that, on
input $\mathit{sk}$ and a message $\mathit{m}\in\mathcal{M}$, outputs
$\mathsf{Sign}(\mathit{sk},\allowbreak\mathit{m})$, and let $\mathit{S}_{s}$
be a set that contains the messages sent to $\mathcal{O}_{s}$. More formally,
for any ppt adversary $\mathcal{A}$, existential unforgeability is defined as
follows.

$\textrm{Pr}\left[\begin{array}[]{l}(\mathit{sk},\mathit{pk})\leftarrow\mathsf{KeyGen}(1^{\mathit{k}});\
(\mathit{m},\mathit{\sigma})\leftarrow\mathcal{A}(\mathit{pk})^{\mathcal{O}_{s}(\mathit{sk},\cdot)}:\\\
1=\mathsf{VfSig}(\mathit{pk},\mathit{\sigma},\mathit{m})\ \land\
\mathit{m}\in\mathcal{M}\ \land\ \mathit{m}\notin\mathit{S}_{s}\\\
\end{array}\right]\leq\epsilon(\mathit{k})$

Pointcheval-Sanders (PS) signatures. The PS signature scheme is defined as
follows (Pointcheval and Sanders, 2016).

$\mathsf{KeyGen}(1^{\mathit{k}},q)$.:

Run $\mathcal{G}(1^{\mathit{k}})$ to obtain a pairing group setup
$\theta=(\mathit{p},\mathbb{G},\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}})$.
Pick random secret key $(x,\allowbreak y_{1},\ldots,\allowbreak
y_{q})\leftarrow\mathbb{Z}_{p}^{q+1}$. Output the secret key
$\mathit{sk}=(\theta,\allowbreak x,\allowbreak
y_{1},\allowbreak\ldots\allowbreak y_{q})$ and the public key
$\mathit{pk}=(\theta,\tilde{\alpha},\beta_{1},\tilde{\beta}_{1},\ldots,\beta_{q},\tilde{\beta}_{q})\leftarrow(\theta,\allowbreak\mathit{\tilde{g}}^{x},\allowbreak\mathit{g}^{y_{1}},\allowbreak\mathit{\tilde{g}}^{y_{1}},\allowbreak\ldots,\allowbreak\mathit{g}^{y_{q}},\allowbreak\mathit{\tilde{g}}^{y_{q}})$.

$\mathsf{Sign}(\mathit{sk},\mathit{m}_{1},\ldots,\mathit{m}_{q})$.:

Parse $\mathit{sk}$ as $(\theta,x,y_{1},\ldots,y_{q})$. Pick up random
$r\leftarrow\mathbb{Z}_{p}$ and set $h\leftarrow\mathit{g}^{r}$. Output the
signature
$\mathit{\sigma}=(h,s)\leftarrow(h,h^{x+y_{1}\mathit{m}_{1}+\ldots+y_{q}\mathit{m}_{q}})$.

$\mathsf{VfSig}(\mathit{pk},\mathit{\sigma},\mathit{m}_{1},\ldots,\mathit{m}_{q})$.:

Output $1$ if
$\mathit{e}(h,\tilde{\alpha}\prod_{j=1}^{q}\tilde{\beta}_{j}^{\mathit{m}_{j}})\allowbreak=\allowbreak\mathit{e}(s,\mathit{\tilde{g}})$
and $h\neq 1$. Otherwise output $0$.

This signature scheme is randomizable. To randomize a signature
$\mathit{\sigma}=(h,\allowbreak s)$, pick random
$r^{\prime}\leftarrow\mathbb{Z}_{p}$ and compute
$\mathit{\sigma}^{\prime}=(h^{r^{\prime}},s^{r^{\prime}})$. The elements
$(\beta_{1},\allowbreak\ldots,\allowbreak\beta_{q})$ in the public key are
needed for the blind signature issuance protocol in (Pointcheval and Sanders,
2016), as well as for the issuance protocols of Coconut and of our e-cash
schemes.

Pointcheval-Sanders signatures in the random oracle model. Coconut and our
e-cash schemes use a variant of PS signatures in which, in algorithm
$\mathsf{Sign}$, the random generator $h$ is computed via a hash function,
which is modeled as a random oracle (RO). This variant has been formalized in
(Rial and Piotrowska, 2022) as PS signatures in the RO model.

In (Rial and Piotrowska, 2022), the syntax of algorithm $\mathsf{Sign}$ is as
follows. $\mathsf{Sign}$ uses a random oracle
$H:\mathcal{M}_{ro}\allowbreak\rightarrow\allowbreak\mathcal{S}$.
$\mathsf{Sign}(\mathit{sk},\allowbreak\mathit{m}_{1},\allowbreak\ldots\allowbreak\mathit{m}_{q},\allowbreak\mathit{r},\allowbreak\mathit{st})$
receives as input a secret key $\mathit{sk}$, a tuple of messages
$(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q})$, a value
$\mathit{r}\allowbreak\in\allowbreak\mathcal{M}_{ro}$ and state information
$\mathit{st}$, which stores tuples of the form
$(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q},\allowbreak\mathit{r})$.
$\mathsf{Sign}$ outputs a signature $\mathit{\sigma}$ on
$(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q})$ if
$\mathit{st}$ does not contain a tuple
$(\mathit{m}^{\prime}_{1},\allowbreak\ldots,\allowbreak\mathit{m}^{\prime}_{q},\allowbreak\mathit{r}^{\prime})$
such that
$(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q})\neq(\mathit{m}^{\prime}_{1},\allowbreak\ldots,\allowbreak\mathit{m}^{\prime}_{q})$
and $\mathit{r}=\mathit{r}^{\prime}$. $\mathsf{Sign}$ also outputs updated
state information $\mathit{st}^{\prime}$.

The PS signature scheme in the RO model scheme works as follows. The
algorithms $\mathsf{KeyGen}$ and $\mathsf{VfSig}$ remain unmodified.

$\mathsf{Sign}(\mathit{sk},\mathit{m}_{1},\ldots,\mathit{m}_{q},\mathit{r},\mathit{st})$.:

Parse $\mathit{sk}$ as $(\theta,x,y_{1},\ldots,y_{q})$. If $\mathit{st}$
contains a tuple
$(\mathit{m}^{\prime}_{1},\allowbreak\ldots,\allowbreak\mathit{m}^{\prime}_{q},\allowbreak\mathit{r}^{\prime})$
such that
$(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q})\neq(\mathit{m}^{\prime}_{1},\allowbreak\ldots,\allowbreak\mathit{m}^{\prime}_{q})$
and $\mathit{r}=\mathit{r}^{\prime}$, output $\mathit{\sigma}=\bot$ and
$\mathit{st}^{\prime}=\mathit{st}$. Otherwise compute $\mathit{h}\leftarrow
H(\mathit{r})$ and output the signature
$\mathit{\sigma}=(h,s)\leftarrow(h,h^{x+y_{1}\mathit{m}_{1}+\ldots+y_{q}\mathit{m}_{q}})$
and the updated state information
$\mathit{st}^{\prime}=\mathit{st}\cup\\{(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q},\mathit{r})\\}$.

We recall the definition of the existential unforgeability property in the RO
model below.

###### Definition A.14 (Existential Unforgeability in the RO (Rial and
Piotrowska, 2022)).

For any ppt adversary $\mathcal{A}$, existential unforgeability in the RO
model is defined as follows.

$\textrm{Pr}\left[\begin{array}[]{l}(\mathit{sk},\mathit{pk})\leftarrow\mathsf{KeyGen}(1^{\mathit{k}});\\\
(\mathit{m},\mathit{\sigma})\leftarrow\mathcal{A}(\mathit{pk})^{\mathcal{O}_{s}(\mathit{sk},\cdot,\cdot),H(\cdot)}:\\\
1=\mathsf{VfSig}(\mathit{pk},\mathit{\sigma},\mathit{m})\ \land\
\mathit{m}\in\mathcal{M}\ \land\ \mathit{m}\notin\mathit{S}_{s}\\\
\end{array}\right]\leq\epsilon(\mathit{k})$

$\mathcal{O}_{s}(\mathit{sk},\cdot,\cdot)$ works as follows. On input
$\mathit{sk}$, a message
$\mathit{m}=(\mathit{m}_{1},\allowbreak\ldots,\allowbreak\mathit{m}_{q})$ and
the value $\mathit{r}$, $\mathcal{O}_{s}$ runs
$(\mathit{\sigma},\mathit{st}^{\prime})\leftarrow\mathsf{Sign}(\mathit{sk},\mathit{m}_{1},\ldots,\mathit{m}_{q},\mathit{r},\mathit{st})$.
$\mathcal{O}_{s}$ replaces $\mathit{st}$ by $\mathit{st}^{\prime}$ and returns
$\mathit{\sigma}$ to $\mathcal{A}$. ($\mathit{st}$ is empty in the first
invocation of $\mathcal{O}_{s}$.) $\mathit{S}_{s}$ is a set that contains the
messages sent to $\mathcal{O}_{s}$.

In comparison to the definition of existential unforgeability (see Definition
A.13), $\mathcal{A}$ has access to the random oracle $H$, and the signing
oracle is modified to follow the new syntax. The PS scheme in the RO model is
existentially unforgeable under the generalized PS assumption proposed in (Kim
et al., 2021a, b).

Structure-Preserving Signature (SPS) scheme. In a SPS scheme, the public key,
the messages, and the signatures are group elements in $\mathbb{G}$ and
$\mathbb{\tilde{G}}$, and verification must consist purely in the checking of
pairing product equations. Our divisible e-cash scheme uses the SPS scheme in
(Abe et al., 2011). In this SPS scheme, $a$ elements in $\mathbb{G}$ and $b$
elements in $\mathbb{\tilde{G}}$ are signed.

$\mathsf{KeyGen}(\mathit{grp},a,b)$.:

Let
$\mathit{grp}\allowbreak\leftarrow\allowbreak(\mathit{p},\allowbreak\mathbb{G},\allowbreak\mathbb{\tilde{G}},\allowbreak{\mathbb{G}_{t}},\allowbreak\mathit{e},\allowbreak\mathit{g},\allowbreak\mathit{\tilde{g}})$
be the bilinear map parameters. Pick at random
$u_{1},\allowbreak\dots,\allowbreak u_{b},\allowbreak y,\allowbreak
w_{1},\dots\allowbreak w_{a},\allowbreak z\leftarrow\mathbb{Z}_{p}^{*}$ and
compute $U_{i}\allowbreak=\allowbreak g^{u_{i}}$,
$i\allowbreak\in\allowbreak[1..b]$,
$Y\allowbreak=\allowbreak\mathit{\tilde{g}}^{y}$,
$W_{i}\allowbreak=\allowbreak\mathit{\tilde{g}}^{w_{i}}$,
$i\allowbreak\in\allowbreak[1..a]$ and
$Z\allowbreak=\allowbreak\mathit{\tilde{g}}^{z}$. Return the verification key
$\mathit{pk}\allowbreak\leftarrow\allowbreak(\mathit{grp},\allowbreak
U_{1},\allowbreak\dots,\allowbreak U_{b},\allowbreak Y,\allowbreak
W_{1},\allowbreak\dots,\allowbreak W_{a},\allowbreak Z)$ and the signing key
$\mathit{sk}\allowbreak\leftarrow\allowbreak(\mathit{pk},\allowbreak
u_{1},\allowbreak\dots,\allowbreak u_{b},\allowbreak y,\allowbreak
w_{1},\allowbreak\dots,\allowbreak w_{a},\allowbreak z)$.

$\mathsf{Sign}(\mathit{sk},\langle m_{1},\dots,m_{a+b}\rangle)$.:

Pick $r\allowbreak\leftarrow\allowbreak\mathbb{Z}_{p}^{*}$, and set

$\displaystyle R\allowbreak\leftarrow\allowbreak\mathit{g}^{r},\quad
S\allowbreak\leftarrow\allowbreak\mathit{g}^{z-ry}\prod_{i=1}^{a}m_{i}^{-w_{i}},\quad
T\allowbreak\leftarrow\allowbreak(\mathit{\tilde{g}}\prod_{i=1}^{b}\allowbreak
m_{a+i}^{-u_{i}})^{1/r},$

and output the signature $\mathit{\sigma}\leftarrow(R,\allowbreak
S,\allowbreak T)$.

$\mathsf{VfSig}(\mathit{pk},\mathit{\sigma},\langle
m_{1},\dots,m_{a+b}\rangle)$.:

Output $1$ if it is satisfied that

$\mathit{e}(R,Y)\allowbreak\mathit{e}(S,\mathit{\tilde{g}})\prod_{i=1}^{a}\mathit{e}(m_{i},\allowbreak
W_{i})\allowbreak=\allowbreak\mathit{e}(g,\allowbreak Z)$

and

$\mathit{e}(R,T)\prod_{i=1}^{b}\mathit{e}(U_{i},m_{a+i})\allowbreak=\allowbreak\mathit{e}(\mathit{g},\allowbreak\mathit{\tilde{g}})$

###  A.6. Pseudorandom Functions

Pseudorandom functions (PF) (Goldreich et al., 1986; Boyle et al., 2014) are a
family of indexed functions $F=\\{F_{s}\\}$ such that: (1) given the index
$s$, $F_{s}$ can be efficiently evaluated on all inputs; (2) no probabilistic
polynomial-time algorithm without $s$ can distinguish evaluations
$F_{s}(x_{i})$ for inputs $x_{i}$ of its choice from random values. We recall
the definition of pseudorandom functions in (Boyle et al., 2014).

###### Definition A.15 (Pseudorandom Function Family).

A family of functions $\mathcal{F}=\\{F_{s}\\}_{s\in S}$, indexed by a set
$S$, and where $F_{s}:D\rightarrow R$ for all $s$, is a pseudorandom function
(PRF) family if for a randomly chosen $s$, and all PPT $\mathcal{A}$, the
distinguishing advantage $\Pr_{s\leftarrow
S}[\mathcal{A}^{f_{s}(\cdot)}\allowbreak=\allowbreak
1]\allowbreak-\Pr_{f\leftarrow(D\rightarrow R)}[\mathcal{A}^{f(\cdot)}=1]$ is
negligible, where $(D\rightarrow R)$ denotes the set of all functions from $D$
to $R$.

Our compact e-cash scheme uses the PF in (Camenisch et al., 2005), which works
as follows. For every $n$, a function $f$ is defined by the tuple
$(\mathbb{G},\mathit{p},\mathit{g},s)$, where $\mathbb{G}$ is a group of order
$\mathit{p}$, $\mathit{p}$ is an $n$-bit prime, $\mathit{g}$ is a generator of
$\mathbb{G}$, and $s$ is a seed in $\mathbb{Z}_{p}$. For any input
$x\in\mathbb{Z}_{p}$ (except for $x=-1\ \mathrm{mod}\ \mathit{p}$), the
function $f_{\mathbb{G},\mathit{p},\mathit{g},s}(\cdot)$, which we denote as
$f_{\mathit{g},s}$ for fixed values of $(\mathbb{G},\mathit{p},\mathit{g})$,
is defined as $f_{\mathit{g},s}(x)=\mathit{g}^{1/(s+x+1)}$. This PF is secure
under the $y$-DDHI assumption in $\mathbb{G}$, which we recall in §A.2. This
PF is based on the verifiable random function in (Dodis and Yampolskiy, 2005),
which is secure under the $y$-DBDHI assumption.

###  A.7. Notation

In Table 4, we summarize the notation used in our paper.

Table 4. Table of symbols Symbol | Meaning
---|---
Bilinear Maps
$\mathit{e}$ | Bilinear map
$\mathcal{G}$ | Bilinear setup
$\mathit{p}$ | Prime number
$\mathbb{G}$ |  Group of order $\mathit{p}$
$\mathbb{\tilde{G}}$ |  Group of order $\mathit{p}$
${\mathbb{G}_{t}}$ |  Group of order $\mathit{p}$
$\mathit{g}$ |  Generator of $\mathbb{G}$
$\mathit{\tilde{g}}$ |  Generator of $\mathbb{\tilde{G}}$
$\mathbb{Z}_{p}$ |  Integers modulo $\mathit{p}$
Security Definitions
$\mathcal{A}$ | Adversary
$\mathcal{Z}$ | Environment
$\mathcal{S}$ | Simulator
$\mathcal{F}$ | Ideal Functionality
$\mathit{pid}$ | Party identifier
$\mathit{sid}$ | Session identifier
$\mathit{qid}$ | Query identifier
Pr | Probability
$\mathcal{O}$ | Oracle
$\mathit{k}$ | Security parameter
$\mathit{\epsilon}$ | Negligible function
E-cash
$\mathrm{EC}$ | Threshold issuance offline anonymous e-cash
$\mathcal{U}$ | User
$\mathcal{P}$ | Provider
$\mathcal{V}$ | Authority
$n$ | Number of authorities
$t$ | Threshold
$L$ | Number of coins in a full wallet
$V$ | Number of coins spent in a payment
$\mathit{params}$ | Parameters
$\mathit{sk}_{\mathcal{V}}$ | Authority secret key
$\mathit{pk}_{\mathcal{V}}$ | Authority public key
$\mathit{sk}_{\mathcal{U}}$ | User secret key
$\mathit{pk}_{\mathcal{U}}$ | User public key
$\mathit{req}$ | Withdrawal request
$\mathit{res}$ | Withdrawal response
$\mathit{W}$ | Wallet
$\mathit{pay}$ | Payment
$\mathit{payinfo}$ | Payment information
$\mathrm{BB}$ | Bulletin Board

##  Appendix B Ideal-World/Real-World Paradigm

The security of a protocol $\varphi$ is analyzed by comparing the view of an
environment $\mathcal{Z}$ in a real execution of $\varphi$ against that of
$\mathcal{Z}$ in the ideal protocol defined in $\mathcal{F}_{\varphi}$.
$\mathcal{Z}$ chooses the inputs of the parties and collects their outputs. In
the real world, $\mathcal{Z}$ can communicate freely with an adversary
$\mathcal{A}$ who controls both the network and any corrupt parties. In the
ideal world, $\mathcal{Z}$ interacts with dummy parties, who simply relay
inputs and outputs between $\mathcal{Z}$ and $\mathcal{F}_{\varphi}$, and a
simulator $\mathcal{S}$. We say that a protocol $\varphi$ securely realizes
$\mathcal{F}_{\varphi}$ if $\mathcal{Z}$ cannot distinguish the real world
from the ideal world, i.e., $\mathcal{Z}$ cannot distinguish whether it is
interacting with $\mathcal{A}$ and parties running protocol $\varphi$ or with
$\mathcal{S}$ and dummy parties relaying to $\mathcal{F}_{\varphi}$

A protocol $\varphi^{\mathcal{G}}$ securely realizes $\mathcal{F}$ in the
$\mathcal{G}$-hybrid model when $\varphi$ is allowed to invoke the ideal
functionality $\mathcal{G}$. Therefore, for any protocol $\psi$ that securely
realizes $\mathcal{G}$, the composed protocol $\varphi^{\psi}$, which is
obtained by replacing each invocation of an instance of $\mathcal{G}$ with an
invocation of an instance of $\psi$, securely realizes $\mathcal{F}$.

In the ideal functionalities described in this paper, we consider static
corruptions. When describing ideal functionalities, we use the conventions
introduced in (Camenisch et al., 2016), which are summarised in B.

Interface Naming Convention.:

An ideal functionality can be invoked by using one or more interfaces. The
name of a message in an interface consists of three fields separated by dots,
e.g., $\mathsf{ec.setup.ini}$ in $\mathcal{F}_{\mathrm{EC}}$ in §3.3. The
first field indicates the name of the functionality and is the same in all
interfaces of the functionality. This field is useful for distinguishing
between invocations of different functionalities in a hybrid protocol that
uses two or more different functionalities. The second field indicates the
kind of action performed by the functionality and is the same in all messages
that the functionality exchanges within the same interface. The third field
distinguishes between the messages that belong to the same interface, and can
take the following different values. A message $\mathsf{ec.setup.ini}$ is the
incoming message received by the functionality, i.e., the message through
which the interface is invoked. A message $\mathsf{ec.setup.end}$ is the
outgoing message sent by the functionality, i.e., the message that ends the
execution of the interface. The message $\mathsf{ec.setup.sim}$ is used by the
functionality to send a message to $\mathcal{S}$, and the message
$\mathsf{ec.setup.rep}$ is used to receive a message from $\mathcal{S}$.

Network vs local communication.:

The identity of an interactive Turing machine instance (ITI) consists of a
party identifier $\mathit{pid}$ and a session identifier $\mathit{sid}$. A set
of parties in an execution of a system of interactive Turing machines is a
protocol instance if they have the same session identifier $\mathit{sid}$.
ITIs can pass direct inputs to and outputs from “local” ITIs that have the
same $\mathit{pid}$. An ideal functionality $\mathcal{F}$ has
$\mathit{pid}=\bot$ and is considered local to all parties. An instance of
$\mathcal{F}$ with the session identifier $\mathit{sid}$ only accepts inputs
from and passes outputs to machines with the same session identifier
$\mathit{sid}$. Some functionalities require the session identifier to have
some structure. Those functionalities check whether the session identifier
possesses the required structure in the first message that invokes the
functionality. For the subsequent messages, the functionality implicitly
checks that the session identifier equals the session identifier used in the
first message. Communication between ITIs with different party identifiers
must take place over the network. The network is controlled by $\mathcal{A}$,
meaning that he can arbitrarily delay, modify, drop, or insert messages.

Query identifiers.:

Some interfaces in a functionality can be invoked more than once. When the
functionality sends a message $\mathsf{ec.setup.sim}$ to $\mathcal{S}$ in such
an interface, a query identifier $\mathit{qid}$ is included in the message.
The query identifier must also be included in the response
$\mathsf{ec.setup.rep}$ sent by $\mathcal{S}$. The query identifier is used to
identify the message $\mathsf{ec.setup.sim}$ to which $\mathcal{S}$ replies
with a message $\mathsf{ec.setup.rep}$. We note that, typically, $\mathcal{S}$
in the security proof may not be able to provide an immediate answer to the
functionality after receiving a message $\mathsf{ec.setup.sim}$. The reason is
that $\mathcal{S}$ typically needs to interact with the copy of $\mathcal{A}$
it runs in order to produce the message $\mathsf{ec.setup.rep}$, but
$\mathcal{A}$ may not provide the desired answer or may provide a delayed
answer. In such cases, when the functionality sends more than one message
$\mathsf{ec.setup.sim}$ to $\mathcal{S}$, $\mathcal{S}$ may provide delayed
replies, and the order of those replies may not follow the order of the
messages received.

Aborts.:

When an ideal functionality $\mathcal{F}$ aborts after being activated with a
message sent by a party, we mean that $\mathcal{F}$ halts the execution of its
program and sends a special abortion message to the party that invoked the
functionality. When an ideal functionality $\mathcal{F}$ aborts after being
activated with a message sent by $\mathcal{S}$, we mean that $\mathcal{F}$
halts the execution of its program and sends a special abortion message to the
party that receives the outgoing message from $\mathcal{F}$ after
$\mathcal{F}$ is activated by $\mathcal{S}$.

##  Appendix C Definitions of Ideal Functionalities

###  C.1. Secure Message Transmission

Our e-cash schemes use the functionality $\mathcal{F}_{\mathrm{SMT}}$ for
secure message transmission described in (Canetti, 2001).
$\mathcal{F}_{\mathrm{SMT}}$ interacts with a sender $\mathcal{T}$ and a
receiver $\mathcal{R}$, and consists of one interface $\mathsf{smt.send}$.
$\mathcal{T}$ uses the $\mathsf{smt.send}$ interface to send a message
$\mathit{m}$ to $\mathcal{F}_{\mathrm{SMT}}$. $\mathcal{F}_{\mathrm{SMT}}$
leaks $\mathit{l}(\mathit{m})$, where
$\mathit{l}:\mathcal{M}\rightarrow\mathbb{N}$ is a function that leaks the
message length, to the simulator $\mathcal{S}$. After receiving a response
from $\mathcal{S}$, $\mathcal{F}_{\mathrm{SMT}}$ sends $\mathit{m}$ to
$\mathcal{R}$. $\mathcal{S}$ cannot modify $\mathit{m}$. The session
identifier $\mathit{sid}$ contains the identities of $\mathcal{T}$ and
$\mathcal{R}$.

Ideal Functionality $\mathcal{F}_{\mathrm{SMT}}$. $\mathcal{F}_{\mathrm{SMT}}$
is parameterized by a message space $\mathcal{M}$ and by a leakage function
$\mathit{l}:\mathcal{M}\rightarrow\mathbb{N}$, which leaks the message length.

  1. (1)

On input
$(\mathsf{smt.send.ini},\allowbreak\mathit{sid},\allowbreak\mathit{m})$ from a
party $\mathcal{T}$:

     * •

Abort if $\mathit{sid}\neq(\mathcal{T},\mathcal{R},\mathit{sid}^{\prime})$ or
if $\mathit{m}\notin\mathcal{M}$.

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\mathcal{R},\mathit{m})$.

     * •

Send
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$
to $\mathcal{S}$.

  2. S.

On input
$(\mathsf{smt.send.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ from
$\mathcal{S}$:

     * •

Abort if $(\mathit{qid},\mathcal{R},\mathit{m})$ is not stored.

     * •

Delete the record $(\mathit{qid},\mathcal{R},\mathit{m})$.

     * •

Send $(\mathsf{smt.send.end},\allowbreak\mathit{sid},\allowbreak\mathit{m})$
to $\mathcal{R}$.

###  C.2. Key Genearation

In our e-cash constructions, the setup phase generates the parameters
$\mathit{params}$ through algorithm $\mathsf{Setup}(1^{\mathit{k}},\allowbreak
L)$. Moreover, algorithm $\mathsf{KeyGenV}(\mathit{params},\allowbreak
t,\allowbreak n)$ generates a key pair for the Pointcheval-Sanders signature
scheme in such a way that the shares of the secret key are given to $n$
authorities, so that $t\allowbreak\leq\allowbreak n$ authorities are needed to
produce a signature.

To simplify our security analysis, in a manner similar to (Rial and
Piotrowska, 2022), we define an ideal functionality
$\mathcal{F}_{\mathrm{KG}}$ that runs both algorithms. In our construction in
§4, $\mathcal{F}_{\mathrm{KG}}$ gives $\mathit{params}$ and the public keys
$\mathit{pk}$ and $(\mathit{pk}_{\mathcal{V}_{i}})_{i\in[1,n]}$ to any party
running the protocol, while each authority $\mathcal{V}_{i}$ also receives his
secret key $\mathit{sk}_{\mathcal{V}_{i}}$.

$\mathcal{F}_{\mathrm{KG}}$ could be replaced by an ideal functionality for
distributed key generation (DKG) (Kate et al., 2012; Groth, 2021). DKG would
avoid the need of a trusted party to generate the keys. With that replacement,
our constructions would realize a modified version of our functionality in
§3.3, where authorities cannot finalize the execution of the setup interface
without involvement of other authorities. The security analysis of the
remaining phases of our e-cash schemes is not affected by the fact that the
authorities keys are generated by a trusted party or through a DKG protocol.

$\mathcal{F}_{\mathrm{KG}}$ interacts with $n$ authorities
$(\mathcal{A}_{1},\ldots,\mathcal{A}_{n})$. $\mathcal{F}_{\mathrm{KG}}$
consists of two interfaces $\mathsf{kg.getkey}$ and $\mathsf{kg.retrieve}$.
The interface $\mathsf{kg.getkey}$ is used by $\mathcal{A}_{i}$ to obtain its
public key $\mathit{pk}_{\mathcal{V}_{i}}$ and secret key
$\mathit{sk}_{\mathcal{V}_{i}}$, as well as the public key $\mathit{pk}$ and
the parameters $\mathit{params}$. The interface $\mathsf{kg.retrieve}$ is used
by any party $\mathcal{P}$ to obtain $\mathit{pk}$, $\mathit{params}$ and the
public keys $\langle\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i=1}^{n}$ of each of
the authorities.

Ideal Functionality $\mathcal{F}_{\mathrm{KG}}$. $\mathcal{F}_{\mathrm{KG}}$
is parameterized by probabilistic algorithms $\mathsf{Setup}$ and
$\mathsf{KeyGenV}$, a security parameter $1^{\mathit{k}}$, a threshold $t$ and
a number $L$ of coins in a wallet.

  1. (1)

On input $(\mathsf{kg.getkey.ini},\mathit{sid})$ from an authority
$\mathcal{A}_{i}$:

     * •

Abort if
$\mathit{sid}\neq(\mathcal{A}_{1},\ldots,\mathcal{A}_{n},\mathit{sid}^{\prime})$,
or if $n<t$.

     * •

If
$(\mathit{sid},\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$
is not stored, run
$\mathit{params}\allowbreak\leftarrow\allowbreak\mathsf{Setup}(1^{\mathit{k}},\allowbreak\allowbreak
L)$ and
$(\mathit{pk},\allowbreak\langle\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})\allowbreak\leftarrow\allowbreak\mathsf{KeyGenV}(\mathit{params},\allowbreak
t,\allowbreak n)$ and store
$(\mathit{sid},\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$.

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\allowbreak\mathcal{A}_{i})$.

     * •

Send
$(\mathsf{kg.getkey.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$
to $\mathcal{S}$.

  2. S.

On input
$(\mathsf{kg.getkey.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$
from the simulator $\mathcal{S}$:

     * •

Abort if $(\mathit{qid},\allowbreak\mathcal{A}_{i})$ such that
$\mathit{qid}\allowbreak\neq\allowbreak\mathit{qid}^{\prime}$ is not stored.

     * •

Delete $(\mathit{qid},\allowbreak\mathcal{A}_{i})$.

     * •

Send
$(\mathsf{kg.getkey.end},\allowbreak\mathit{sid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}})$
to $\mathcal{A}_{i}$.

  3. (2)

On input $(\mathsf{kg.retrieve.ini},\allowbreak\mathit{sid})$ from any party
$\mathcal{P}$:

     * •

Abort if
$\mathit{sid}\neq(\mathcal{A}_{1},\ldots,\mathcal{A}_{n},\mathit{sid}^{\prime})$.

     * •

If
$(\mathit{sid},\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$
is stored, set
$\mathit{v}\leftarrow(\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$,
else set $\mathit{v}\leftarrow\bot$.

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\mathcal{P},\mathit{v})$.

     * •

Send
$(\mathsf{kg.retrieve.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{v})$
to $\mathcal{S}$.

  4. S.

On input
$(\mathsf{kg.retrieve.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$
from $\mathcal{S}$:

     * •

Abort if $(\mathit{qid}^{\prime},\mathcal{P},\mathit{v})$ such that
$\mathit{qid}^{\prime}\neq\mathit{qid}$ is not stored.

     * •

Delete the record $(\mathit{qid},\mathcal{P},\mathit{v})$.

     * •

Send
$(\mathsf{kg.retrieve.end},\allowbreak\mathit{sid},\allowbreak\mathit{v})$ to
$\mathcal{P}$.

###  C.3. Registration

Our protocol uses the functionality $\mathcal{F}_{\mathrm{REG}}$ for key
registration by Canetti (Canetti, 2001). $\mathcal{F}_{\mathrm{REG}}$
interacts with any party $\mathcal{T}$ that registers a message $\mathit{v}$
and with any party $\mathcal{P}$ that retrieves the registered message.
$\mathcal{F}_{\mathrm{REG}}$ consists of two interfaces
$\mathsf{reg.register}$ and $\mathsf{reg.retrieve}$. The interface
$\mathsf{reg.register}$ is used by $\mathcal{T}$ to register a message
$\mathit{v}$ with $\mathcal{F}_{\mathrm{REG}}$. A party $\mathcal{P}$ uses
$\mathsf{reg.retrieve}$ to retrieve $\mathit{v}$ from
$\mathcal{F}_{\mathrm{REG}}$.

Ideal Functionality $\mathcal{F}_{\mathrm{REG}}$. $\mathcal{F}_{\mathrm{REG}}$
is parameterized by a message space $\mathcal{M}$.

  1. (1)

On input
$(\mathsf{reg.register.ini},\allowbreak\mathit{sid},\allowbreak\mathit{v})$
from a party $\mathcal{T}$:

     * •

Abort if $\mathit{sid}\neq(\mathcal{T},\mathit{sid}^{\prime})$, or if
$\mathit{v}\notin\mathcal{M}$ or if there is a tuple
$(\mathit{sid},\mathit{v}^{\prime},0)$ stored.

     * •

Store $(\mathit{sid},\mathit{v},0)$.

     * •

Send
$(\mathsf{reg.register.sim},\allowbreak\mathit{sid},\allowbreak\mathit{v})$ to
$\mathcal{S}$.

  2. S.

On input $(\mathsf{reg.register.rep},\allowbreak\mathit{sid})$ from the
simulator $\mathcal{S}$:

     * •

Abort if $(\mathit{sid},\mathit{v},0)$ is not stored or if
$(\mathit{sid},\mathit{v},1)$ is already stored.

     * •

Store $(\mathit{sid},\mathit{v},1)$ and parse $\mathit{sid}$ as
$(\mathcal{T},\mathit{sid}^{\prime})$.

     * •

Send $(\mathsf{reg.register.end},\allowbreak\mathit{sid})$ to $\mathcal{T}$.

  3. (2)

On input $(\mathsf{reg.retrieve.ini},\allowbreak\mathit{sid})$ from any party
$\mathcal{P}$:

     * •

If $(\mathit{sid},\mathit{v},1)$ is stored, set
$\mathit{v}^{\prime}\leftarrow\mathit{v}$; else set
$\mathit{v}^{\prime}\leftarrow\bot$.

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\mathcal{P},\mathit{v}^{\prime})$.

     * •

Send
$(\mathsf{reg.retrieve.sim},\mathit{sid},\mathit{qid},\mathit{v}^{\prime})$ to
$\mathcal{S}$.

  4. S.

On input $(\mathsf{reg.retrieve.rep},\mathit{sid},\mathit{qid})$ from
$\mathcal{S}$:

     * •

Abort if $(\mathit{qid},\mathcal{P},\mathit{v}^{\prime})$ is not stored.

     * •

Delete the record $(\mathit{qid},\mathcal{P},\mathit{v}^{\prime})$.

     * •

Send $(\mathsf{reg.retrieve.end},\mathit{sid},\mathit{v}^{\prime})$ to
$\mathcal{P}$.

###  C.4. Pseudonymous Channel

Our e-cash schemes use the functionality $\mathcal{F}_{\mathrm{NYM}}$ for a
secure idealized pseudonymous channel. We use $\mathcal{F}_{\mathrm{NYM}}$ to
describe our e-cash schemes for simplicity, in order to hide the details of
real-world pseudonymous channels. $\mathcal{F}_{\mathrm{NYM}}$ is similar to
the functionality for anonymous secure message transmission in (Camenisch et
al., 2014). $\mathcal{F}_{\mathrm{NYM}}$ interacts with senders $\mathcal{T}$
and receivers $\mathcal{R}$. $\mathcal{F}_{\mathrm{NYM}}$ is parameterized by
a message space $\mathcal{M}$, a security parameter $\mathit{k}$, a universe
of pseudonyms $\mathbb{U}_{p}$, and a leakage function $\mathit{l}$, which
leaks the message length. $\mathcal{F}_{\mathrm{NYM}}$ consists of one
interfaces $\mathsf{nym.send}$. $\mathcal{T}$ uses the $\mathsf{nym.send}$
interface to send a message $\mathit{m}\in\mathcal{M}$, a pseudonym
$\mathit{P}\in\mathbb{U}_{p}$ and a receiver identifier $\mathcal{R}$ to
$\mathcal{F}_{\mathrm{NYM}}$. $\mathcal{F}_{\mathrm{NYM}}$ sends
$\mathit{l}(\mathit{m})$ to the simulator $\mathcal{S}$. After receiving a
response from $\mathcal{S}$, $\mathcal{F}_{\mathrm{NYM}}$ sends $\mathit{m}$
and $\mathit{P}$ to $\mathcal{R}$.

$\mathcal{R}$ does not learn the identifier $\mathcal{T}$. Instead
$\mathcal{R}$ learns a pseudonym $\mathit{P}$ chosen by $\mathcal{T}$.
$\mathcal{T}$ can choose different pseudonyms to make the messages sent
unlinkable towards $\mathcal{R}$.

Ideal Functionality $\mathcal{F}_{\mathrm{NYM}}$. $\mathcal{F}_{\mathrm{NYM}}$
is parameterized by a message space $\mathcal{M}$, a security parameter
$\mathit{k}$, a universe of pseudonyms $\mathbb{U}_{p}$, and a leakage
function $\mathit{l}$, which leaks the message length.

  1. (1)

On input
$(\mathsf{nym.send.ini},\allowbreak\mathit{sid},\allowbreak\mathit{m},\allowbreak\mathit{P},\allowbreak\mathcal{R})$
from $\mathcal{T}$:

     * •

Abort if $\mathit{m}\allowbreak\notin\allowbreak\mathcal{M}$, or if
$\mathit{P}\allowbreak\notin\allowbreak\mathbb{U}_{p}$.

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\allowbreak\mathit{P},\allowbreak\mathcal{T},\allowbreak\mathit{m},\allowbreak\mathcal{R})$.

     * •

Send
$(\mathsf{nym.send.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$
to $\mathcal{S}$.

  2. S.

On input
$(\mathsf{nym.send.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ from
$\mathcal{S}$:

     * •

Abort if
$(\mathit{qid}^{\prime},\allowbreak\mathit{P},\allowbreak\mathcal{T},\allowbreak\mathit{m},\allowbreak\mathcal{R})$
such that $\mathit{qid}=\mathit{qid}^{\prime}$ is not stored.

     * •

Delete the record
$(\mathit{qid},\allowbreak\mathit{P},\allowbreak\mathcal{T},\allowbreak\mathit{m},\allowbreak\mathcal{R})$.

     * •

Send
$(\mathsf{nym.send.end},\allowbreak\mathit{sid},\allowbreak\mathit{m},\allowbreak\mathit{P})$
to $\mathcal{R}$.

###  C.5. Authenticated Bulletin Board

Our e-cash schemes use the functionality $\mathcal{F}_{\mathrm{BB}}$ for an
authenticated bulletin board BB (Wikström, 2004). A BB is used to store the
payments deposited by providers, and to verify that there are not double
spendings or double deposits. $\mathcal{F}_{\mathrm{BB}}$ interacts with
writers $\mathcal{W}_{j}$ and readers $\mathcal{R}_{k}$. $\mathcal{W}_{j}$
uses the $\mathsf{bb.write}$ interface to send a message $\mathit{m}$ to
$\mathcal{F}_{\mathrm{BB}}$. $\mathcal{F}_{\mathrm{BB}}$ increments a counter
$\mathit{ct}$ of the number of messages stored in BB and appends
$[\mathit{ct},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m}]$ to BB.
$\mathcal{R}_{k}$ uses the $\mathsf{bb.read}$ interface on input an index
$\mathit{i}$. If
$\mathit{i}\allowbreak\in\allowbreak[1,\allowbreak\mathit{ct}]$,
$\mathcal{F}_{\mathrm{BB}}$ takes the tuple
$[\mathit{i},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m}]$ in BB and
sends $(\mathcal{W}_{j},\allowbreak\mathit{m})$ to $\mathcal{R}_{k}$.

Ideal Functionality $\mathcal{F}_{\mathrm{BB}}$. $\mathcal{F}_{\mathrm{BB}}$
is parameterized by a universe of messages $\mathbb{U}_{m}$.
$\mathcal{F}_{\mathrm{BB}}$ interacts with writers $\mathcal{W}_{j}$ and
readers $\mathcal{R}_{k}$.

  1. (1)

On input
$(\mathsf{bb.write.ini},\allowbreak\mathit{sid},\allowbreak\mathit{m})$ from
$\mathcal{W}_{j}$:

     * •

Abort if $\mathit{m}\allowbreak\notin\allowbreak\mathbb{U}_{m}$.

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m})$.

     * •

Send $(\mathsf{bb.write.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$
to $\mathcal{S}$.

  2. S.

On input
$(\mathsf{bb.write.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ from
$\mathcal{S}$:

     * •

Abort if
$(\mathit{qid}^{\prime},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m})$
such that $\mathit{qid}^{\prime}\allowbreak=\allowbreak\mathit{qid}$ is not
stored.

     * •

If $(\mathit{sid},\allowbreak\textsf{BB},\allowbreak\mathit{ct})$ is not
stored, set $\textsf{BB}\leftarrow\bot$ and $\mathit{ct}\leftarrow 0$.

     * •

Increment $\mathit{ct}$, append
$[\mathit{ct},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m}]$ to BB and
update $\mathit{ct}$ and BB in
$(\mathit{sid},\allowbreak\textsf{BB},\allowbreak\mathit{ct})$.

     * •

Delete $(\mathit{qid},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m})$.

     * •

Send $(\mathsf{bb.write.end},\allowbreak\mathit{sid})$ to $\mathcal{W}_{j}$.

  3. (2)

On input
$(\mathsf{bb.read.ini},\allowbreak\mathit{sid},\allowbreak\mathit{i})$ from
$\mathcal{R}_{k}$:

     * •

Create a fresh $\mathit{qid}$ and store
$(\mathit{qid},\allowbreak\mathcal{R}_{k},\allowbreak\mathit{i})$.

     * •

Send $(\mathsf{bb.read.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$
to $\mathcal{S}$.

  4. S.

On input
$(\mathsf{bb.read.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ from
$\mathcal{S}$:

     * •

Abort if $(\mathit{qid}^{\prime},\mathcal{R}_{k},\allowbreak\mathit{i})$ such
that $\mathit{qid}^{\prime}=\mathit{qid}$ is not stored.

     * •

If $(\mathit{sid},\allowbreak\textsf{BB},\allowbreak\mathit{ct})$ is stored
and $\mathit{i}\in[1,\mathit{ct}]$, take
$[\mathit{i},\allowbreak\mathcal{W}_{j},\allowbreak\mathit{m}]$ from BB and
set $\mathit{m}^{\prime}\leftarrow(\mathcal{W}_{j},\allowbreak\mathit{m})$,
else set $\mathit{m}^{\prime}\allowbreak\leftarrow\allowbreak\bot$.

     * •

Send
$(\mathsf{bb.read.end},\allowbreak\mathit{sid},\allowbreak\mathit{m}^{\prime})$
to $\mathcal{R}_{k}$.

##  Appendix D Security Proof for Our Compact E-Cash Scheme

To prove that construction $\mathrm{\Pi}_{\mathrm{EC}}$, instantiated with the
algorithms of the compact e-cash scheme in §5.1, securely realizes the ideal
functionality $\mathcal{F}_{\mathrm{EC}}$, we have to show that for any
environment $\mathcal{Z}$ and any adversary $\mathcal{A}$ there exists a
simulator $\mathcal{S}$ such that $\mathcal{Z}$ cannot distinguish between
whether it is interacting with $\mathcal{A}$ and the protocol in the real
world or with $\mathcal{S}$ and $\mathcal{F}_{\mathrm{EC}}$. The simulator
thereby plays the role of all honest parties in the real world and interacts
with $\mathcal{F}_{\mathrm{EC}}$ for all corrupt parties in the ideal world.

$\mathcal{S}$ runs a copy of any adversary $\mathcal{A}$, which is used to
provide to $\mathcal{Z}$ a view that is indistinguishable from the view given
by $\mathcal{A}$ in the real world. To achieve that, $\mathcal{S}$ must
simulate the real-world protocol towards the copy of $\mathcal{A}$, in such a
way that $\mathcal{A}$ cannot distinguish an interaction with $\mathcal{S}$
from an interaction with the real-world protocol. $\mathcal{S}$ uses the
information provided by $\mathcal{F}_{\mathrm{EC}}$ to provide a simulation of
the real-world protocol.

Our simulator $\mathcal{S}$ runs copies of the functionalities
$\mathcal{F}_{\mathrm{SMT}}$, $\mathcal{F}_{\mathrm{NYM}}$,
$\mathcal{F}_{\mathrm{KG}}$, $\mathcal{F}_{\mathrm{REG}}$ and
$\mathcal{F}_{\mathrm{BB}}$. When any of the copies of these functionalities
aborts, $\mathcal{S}$ implicitly forwards the abortion message to the
adversary if the functionality sends the abortion message to a corrupt party.

$\mathcal{S}$ also runs copies of the extractors $\mathcal{E}_{s}$ and
$\mathcal{E}_{v}$ and simulators $\mathcal{S}_{s}$ and $\mathcal{S}_{v}$ for
the non-interactive zero-knowledge arguments of knowledge $\pi_{s}$ and
$\pi_{v}$, which are computed through the Fiat-Shamir transform. We remark
that they involve calls to the random oracle and rewinding of the adversary.
For simplicity, we omit those details.

##### Challenges in the proof.

Our compact e-cash scheme with threshold issuance is based on an existing
compact e-cash scheme (Camenisch et al., 2005). We instantiate that scheme
with the Pointcheval-Sanders signature scheme, and then we use an existing
threshold issuance protocol for Pointcheval-Sanders signatures (Rial and
Piotrowska, 2022) to provide threshold issuance. Nevertheless, the security
proof does not follow straightforwardly from the proofs in (Camenisch et al.,
2005; Rial and Piotrowska, 2022).

First, in the blind issuance protocol of the compact e-cash scheme in
(Camenisch et al., 2005) one of the coin secrets is chosen jointly between the
user and the bank, i.e. both the bank and the user add randomness to compute
the secret. In a threshold issuance setting, it would be necessary that all
the authorities add the same randomness without communicating between them.
While adding a mechanism to do that is possible, in order to improve
efficiency we decided to have the secret be chosen by the user only. This
implies that, when a corrupt user picks up the secrets of two wallets, the
user could pick up the secrets in such a way that two coins have the same
serial number. Consequently, when those coins are spent, there is a situation
in which double spending is detected (because serial numbers are the same),
although no double spending has happened. In that case, we prove that the
identification algorithm cannot output the public key of an honest user, and
we are able to do that under the discrete logarithm assumption.

Second, to improve efficiency, we use only one coin secret instead of the two
coins secrets used in [14]. When using two coin secrets, it is straightforward
to show that serial numbers and double spending tags do not reveal any
information about the secrets by using the pseudorandomness property of the
pseudorandom function. However, when using the same secret for both, but a
different generator, we need to add an additional reduction to the XDH
assumption.

##### Simulator.

We describe the simulator $\mathcal{S}$ for the case in which a subset of
users $\mathcal{U}_{j}$, a subset of providers $\mathcal{P}_{k}$ and up to
$t-1$ authorities are corrupt. $\mathcal{S}$ simulates the honest parties in
the protocol $\mathrm{\Pi_{\mathrm{EC}}}$ and runs copies of the ideal
functionalities involved.

Honest authority $\mathcal{V}_{i}$ starts setup.:

When the functionality $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.setup.sim},\allowbreak\mathit{sid},\allowbreak\mathcal{V}_{i})$,
the simulator $\mathcal{S}$ runs a copy of the functionality
$\mathcal{F}_{\mathrm{KG}}$ on input
$(\mathsf{kg.getkey.ini},\allowbreak\mathit{sid})$. When the functionality
$\mathcal{F}_{\mathrm{KG}}$ sends the message
$(\mathsf{kg.getkey.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Honest authority $\mathcal{V}_{i}$ ends setup.:

When the adversary $\mathcal{A}$ sends the message
$(\mathsf{kg.getkey.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs a copy of $\mathcal{F}_{\mathrm{KG}}$ on input that
message. When $\mathcal{F}_{\mathrm{KG}}$ sends
$(\mathsf{kg.getkey.end},\allowbreak\mathit{sid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\mathit{sk}_{\mathcal{V}_{i}},\allowbreak\mathit{pk}_{\mathcal{V}_{i}})$,
$\mathcal{S}$ sends
$(\mathsf{ec.setup.rep},\allowbreak\mathit{sid},\allowbreak\mathcal{V}_{i})$
to $\mathcal{F}_{\mathrm{EC}}$.

Corrupt authority $\tilde{\mathcal{V}}_{i}$ starts setup.:

When a corrupt authority $\tilde{\mathcal{V}}_{i}$ sends the message
$(\mathsf{kg.getkey.ini},\allowbreak\mathit{sid})$, $\mathcal{S}$ runs a copy
of $\mathcal{F}_{\mathrm{KG}}$ on input that message. When
$\mathcal{F}_{\mathrm{KG}}$ sends
$(\mathsf{kg.getkey.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\langle\mathit{pk}_{\mathcal{V}_{i}}\rangle_{i\in[1,n]})$,
$\mathcal{S}$ forwards that message to $\tilde{\mathcal{V}}_{i}$.

Corrupt authority $\tilde{\mathcal{V}}_{i}$ ends setup.:

When $\tilde{\mathcal{V}}_{i}$ sends the message
$(\mathsf{kg.getkey.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs a copy of $\mathcal{F}_{\mathrm{KG}}$ on input that
message. When $\mathcal{F}_{\mathrm{KG}}$ sends
$(\mathsf{kg.getkey.end},\allowbreak\mathit{sid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\mathit{sk}_{\tilde{\mathcal{V}}_{i}},\allowbreak\mathit{pk}_{\tilde{\mathcal{V}}_{i}})$,
$\mathcal{S}$ sends $(\mathsf{ec.setup.ini},\allowbreak\mathit{sid})$ to the
functionality $\mathcal{F}_{\mathrm{EC}}$. When $\mathcal{F}_{\mathrm{EC}}$
sends
$(\mathsf{ec.setup.sim},\allowbreak\mathit{sid},\allowbreak\tilde{\mathcal{V}}_{i})$,
the simulator $\mathcal{S}$ sends the message
$(\mathsf{ec.setup.rep},\allowbreak\mathit{sid},\allowbreak\tilde{\mathcal{V}}_{i})$
to $\mathcal{F}_{\mathrm{EC}}$. When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.setup.end},\allowbreak\mathit{sid})$, $\mathcal{S}$ sends the
message
$(\mathsf{kg.getkey.end},\allowbreak\mathit{sid},\allowbreak\mathit{params},\allowbreak\mathit{pk},\allowbreak\mathit{sk}_{\tilde{\mathcal{V}}_{i}},\allowbreak\mathit{pk}_{\tilde{\mathcal{V}}_{i}})$
to $\tilde{\mathcal{V}}_{i}$.

Honest user (or provider) requests keys.:

When $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.register.sim},\allowbreak\mathit{sid},\allowbreak\mathcal{U}_{j})$,
$\mathcal{S}$ runs a copy of $\mathcal{F}_{\mathrm{KG}}$ on input
$(\mathsf{kg.retrieve.ini},\allowbreak\mathit{sid})$. When the functionality
$\mathcal{F}_{\mathrm{KG}}$ sends the message
$(\mathsf{kg.retrieve.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{v})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Honest user (or provider) receives and registers keys.:

When $\mathcal{A}$ sends
$(\mathsf{kg.retrieve.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{KG}}$ on input that message. When the
functionality $\mathcal{F}_{\mathrm{KG}}$ sends
$(\mathsf{kg.retrieve.end},\allowbreak\mathit{sid},\allowbreak\mathit{v})$,
the simulator $\mathcal{S}$ runs
$(\mathit{sk}_{\mathcal{U}_{j}},\allowbreak\mathit{pk}_{\mathcal{U}_{j}})\leftarrow\mathsf{KeyGenU}(\mathit{params})$,
sets
$\mathit{sid}_{\mathrm{REG}}\leftarrow(\mathcal{U}_{j},\mathit{sid}^{\prime})$
and runs a copy of $\mathcal{F}_{\mathrm{REG}}$ on input the message
$(\mathsf{reg.register.ini},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{pk}_{\mathcal{U}_{j}})$.
When $\mathcal{F}_{\mathrm{REG}}$ sends the message
$(\mathsf{reg.register.sim},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{pk}_{\mathcal{U}_{j}})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Honest user (or provider) finalizes the registration of keys.:

When $\mathcal{A}$ sends the message
$(\mathsf{reg.register.rep},\allowbreak\mathit{sid}_{\mathrm{REG}})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{REG}}$ on input that message. When
$\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.register.end},\allowbreak\mathit{sid}_{\mathrm{REG}})$,
$\mathcal{S}$ sends
$(\mathsf{ec.register.rep},\allowbreak\mathit{sid},\allowbreak\mathcal{U}_{j})$
to $\mathcal{F}_{\mathrm{EC}}$.

Corrupt user (or provider) requests keys.:

When $\mathcal{A}$ sends the message
$(\mathsf{kg.retrieve.ini},\allowbreak\mathit{sid})$, $\mathcal{S}$ runs
$\mathcal{F}_{\mathrm{KG}}$ on input that message. When
$\mathcal{F}_{\mathrm{KG}}$ sends
$(\mathsf{kg.retrieve.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{v})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Corrupt user (or provider) receives keys.:

When $\mathcal{A}$ sends the message
$(\mathsf{kg.retrieve.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{KG}}$ on input that message. When
$\mathcal{F}_{\mathrm{KG}}$ sends
$(\mathsf{kg.retrieve.end},\allowbreak\mathit{sid},\allowbreak\mathit{v})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Corrupt user (or provider) registers keys.:

When $\mathcal{A}$ sends the message
$(\mathsf{reg.register.ini},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{pk}_{\mathcal{U}_{j}})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{REG}}$ on input that message. When
the functionality $\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.register.sim},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{pk}_{\mathcal{U}_{j}})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Corrupt user (or provider) finishes the registration of keys.:

When $\mathcal{A}$ sends
$(\mathsf{reg.register.rep},\allowbreak\mathit{sid}_{\mathrm{REG}})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{REG}}$ on input that message. When
$\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.register.end},\allowbreak\mathit{sid}_{\mathrm{REG}})$, the
simulator $\mathcal{S}$, acting as the corrupt user $\mathcal{U}_{j}$, sends
$(\mathsf{ec.register.ini},\allowbreak\mathit{sid})$ to
$\mathcal{F}_{\mathrm{EC}}$. When the functionality
$\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.register.sim},\allowbreak\mathit{sid},\allowbreak\mathcal{U}_{j})$,
the simulator $\mathcal{S}$ sends
$(\mathsf{ec.register.rep},\allowbreak\mathit{sid},\allowbreak\mathcal{U}_{j})$
to $\mathcal{F}_{\mathrm{EC}}$. When $\mathcal{F}_{\mathrm{EC}}$ sends the
message $(\mathsf{ec.register.end},\allowbreak\mathit{sid})$, $\mathcal{S}$
sends $(\mathsf{reg.register.end},\allowbreak\mathit{sid}_{\mathrm{REG}})$ to
$\mathcal{A}$.

Honest user sends a request to honest authority.:

When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.request.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i})$,
the simulator $\mathcal{S}$ parses the session identifier $\mathit{sid}$ as
$(\mathcal{V}_{1},\allowbreak\ldots,\allowbreak\mathcal{V}_{n},\allowbreak\mathit{sid}^{\prime})$,
sets
$\mathit{sid}_{\mathrm{SMT}}\allowbreak\leftarrow\allowbreak(\mathcal{U}_{j},\allowbreak\mathcal{V}_{i},\allowbreak\mathit{sid}^{\prime})$
and sends
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid}_{\mathrm{SMT}},\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$
to $\mathcal{A}$, where $\mathit{l}(\mathit{m})$ is equal to the length of the
message that the honest user sends to an authority in the
$\mathsf{ec.request}$ interface.

Adversary forwards request.:

When the adversary $\mathcal{A}$ sends the message
$(\mathsf{smt.send.rep},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\mathit{qid})$
to reply to
$(\mathsf{ec.request.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i})$,
$\mathcal{S}$ checks if a tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i})$ is
stored. If not, $\mathcal{S}$ runs the procedure in Figure 3. After that,
$\mathcal{S}$ sends the message
$(\mathsf{ec.request.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Honest user sends a request to corrupt authority.:

When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.request.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i},\allowbreak\mathit{wid})$,
$\mathcal{S}$ checks if a tuple
$(\mathit{sid},\allowbreak\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wid}^{\prime},\allowbreak\mathit{wn})$
such that $\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and
$\mathit{wid}^{\prime}\allowbreak=\allowbreak\mathit{wid}$ is stored. If not,
$\mathcal{S}$ does the following:

  * •:

Pick up the stored tuple
$(\mathit{sid},\allowbreak\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wct})$
such that $\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$.
(This tuple is initialized to $\mathit{wct}\allowbreak=\allowbreak 0$.)

  * •:

Set
$\mathit{wct}\allowbreak\leftarrow\allowbreak\mathit{wct}\allowbreak+\allowbreak
1$.

  * •:

Set $\mathit{wn}\allowbreak\leftarrow\allowbreak\mathit{wct}$.

  * •:

Store
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wid},\allowbreak\mathit{wn})$.

  * •:

Update $\mathit{wct}$ in the tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wct})$.

$\mathcal{S}$ parses the session identifier $\mathit{sid}$ as
$(\mathcal{V}_{1},\allowbreak\ldots,\allowbreak\mathcal{V}_{n},\allowbreak\mathit{sid}^{\prime})$,
sets
$\mathit{sid}_{\mathrm{SMT}}\allowbreak\leftarrow\allowbreak(\mathcal{U}_{j},\mathcal{V}_{i},\mathit{sid}^{\prime})$
and sends
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid}_{\mathrm{SMT}},\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$
to $\mathcal{A}$, where $\mathit{l}(\mathit{m})$ is equal to the length of the
message that the honest user sends to an authority in the
$\mathsf{ec.request}$ interface.

Corrupt authority receives request from honest user.:

When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.request.end},\allowbreak\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{reqid})$
to a corrupt authority $\tilde{\mathcal{V}}_{i}$, $\mathcal{S}$ retrieves the
stored tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wid},\allowbreak\mathit{wn})$
such that $\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and
$\mathit{wid}$ was received before in the message
$(\mathsf{ec.request.sim},\ldots)$ associated with the message
$(\mathsf{ec.request.end},\ldots)$ received now. $\mathcal{S}$ runs a copy of
a user on input
$(\mathsf{ec.request.ini},\allowbreak\mathit{sid},\allowbreak\tilde{\mathcal{V}}_{i},\allowbreak\mathit{reqid},\allowbreak\mathit{wn})$.
(We remark that $\mathit{wn}$ used a input to the copy of the user is not
necessarily equal to the value of $\mathit{wn}$ received by the honest user
from the environment. However, it is enough to ensure that the same
$\mathit{wn}$ is used for each $\mathit{wid}$ received from
$\mathcal{F}_{\mathrm{EC}}$, so that the copy of the user produces the same
request for each $\mathit{wid}$.) When the copy of the user runs algorithm
$\mathsf{Request}$, $\mathcal{S}$ uses the public key
$\mathit{pk}_{\mathcal{U}_{j}}$ that was previously computed for user
$\mathcal{U}_{j}$. $\mathcal{S}$ also uses the simulator $\mathcal{S}_{s}$ to
compute a simulated proof $\pi_{s}$, and sets $\mathit{com}$,
$\mathit{com}_{1}$ and $\mathit{com}_{2}$ to be commitments to random
messages. When the copy of the user sends the message
$(\mathsf{smt.send.ini},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\langle\mathit{reqid},\allowbreak\mathit{req}\rangle)$
to $\mathcal{F}_{\mathrm{SMT}}$, $\mathcal{S}$ runs
$\mathcal{F}_{\mathrm{SMT}}$ on input that message. When
$\mathcal{F}_{\mathrm{SMT}}$ sends the message
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{SMT}}$ on input
$(\mathsf{smt.send.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$.
When $\mathcal{F}_{\mathrm{SMT}}$ sends
$(\mathsf{smt.send.end},\allowbreak\mathit{sid},\allowbreak\langle\mathit{reqid},\allowbreak\mathit{req}\rangle)$,
$\mathcal{S}$ forwards that message to $\tilde{\mathcal{V}}_{i}$.

Corrupt authority requests user keys.:

When the adversary $\mathcal{A}$ sends
$(\mathsf{reg.retrieve.ini},\allowbreak\mathit{sid}_{\mathrm{REG}})$,
$\mathcal{S}$ runs a copy of $\mathcal{F}_{\mathrm{REG}}$ on input that
message. When $\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.register.sim},\allowbreak\mathit{sid},\allowbreak\mathit{v})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Corrupt authority receives user keys.:

When the adversary $\mathcal{A}$ sends
$(\mathsf{reg.register.rep},\allowbreak\mathit{sid})$, $\mathcal{S}$ runs
$\mathcal{F}_{\mathrm{REG}}$ on input that message. When
$\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.retrieve.end},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{v})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Corrupt user requests credential.:

When the adversary $\mathcal{A}$ sends the message
$(\mathsf{smt.send.ini},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\langle\mathit{reqid},\allowbreak\mathit{req}\rangle)$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{SMT}}$ on input that message. When
$\mathcal{F}_{\mathrm{SMT}}$ sends
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$,
$\mathcal{S}$ sends that message to $\mathcal{A}$.

Procedure: Retrieve user key

  * •:

The simulator $\mathcal{S}$ sets
$\mathit{sid}_{\mathrm{REG}}\allowbreak\leftarrow\allowbreak(\mathcal{U}_{j},\allowbreak\mathit{sid}^{\prime})$
and runs the functionality $\mathcal{F}_{\mathrm{REG}}$ on input
$(\mathsf{reg.retrieve.ini},\allowbreak\mathit{sid}_{\mathrm{REG}})$. When
$\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.retrieve.sim},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{qid},\allowbreak\mathit{v}^{\prime})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

  * •:

When $\mathcal{A}$ sends
$(\mathsf{reg.retrieve.rep},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{REG}}$ on input that message. When
$\mathcal{F}_{\mathrm{REG}}$ sends
$(\mathsf{reg.retrieve.end},\allowbreak\mathit{sid}_{\mathrm{REG}},\allowbreak\mathit{v}^{\prime})$,
if $\mathit{v}^{\prime}=\bot$, $\mathcal{S}$ aborts, else $\mathcal{S}$ stores
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i})$.

Figure 3. Procedure for simulating user key retrieval.

Honest authority receives request from corrupt user.:

When
the adversary $\mathcal{A}$ sends
$(\mathsf{smt.send.rep},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{SMT}}$ on input that message. When
$\mathcal{F}_{\mathrm{SMT}}$ sends the message
$(\mathsf{smt.send.end},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\mathit{m})$,
$\mathcal{S}$ parses the message $\mathit{m}$ as
$\langle\mathit{reqid},\allowbreak\mathit{req}\rangle$ and
$\mathit{sid}_{\mathrm{SMT}}$ as
$(\mathcal{U}_{j},\allowbreak\mathcal{V}_{i},\allowbreak\mathit{sid}^{\prime})$.
$\mathcal{S}$ does the following:

  * •:

Abort if the authority $\mathcal{V}_{i}$ did not end the setup.

  * •:

Check if a tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i})$ is
stored. If not, $\mathcal{S}$ runs the procedure in Figure 3.

  * •:

Abort if there is a stored tuple
$(\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$ such that
$\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and
$\\{\mathit{reqid},\mathcal{V}_{i}\\}\allowbreak\in\allowbreak\mathbb{R}$.
Here $\mathcal{S}$ aborts because there is a request pending with the same
request identifier $\mathit{reqid}$ from $\mathcal{U}_{j}$ for
$\mathcal{V}_{i}$, like it is done in the real protocol.

  * •:

If there is a stored tuple
$(\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req}^{\prime},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$ such that
$\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and
$\mathit{req}^{\prime}\allowbreak=\allowbreak\mathit{req}$, then update the
set
$\mathbb{R}\allowbreak\leftarrow\allowbreak\mathbb{R}\cup\\{\mathit{reqid},\mathcal{V}_{i}\\}$
in that tuple and take $\mathit{wn}$ from that tuple. Else do the following:

    * –:

Follow the steps of an honest authority in $\mathrm{\Pi}_{\mathrm{EC}}$ to
verify $\mathit{req}$. This involves verifying the request by running the
algorithm
$b\allowbreak\leftarrow\allowbreak\mathsf{RequestVf}(\mathit{params},\allowbreak\mathit{req},\allowbreak\mathit{pk}_{\mathcal{U}_{j}})$.
($\mathcal{S}$ checked before that the corrupt user registered
$\mathit{pk}_{\mathcal{U}_{j}}$ through the procedure in Figure 3.) Abort if
$b\allowbreak=\allowbreak 0$.

    * –:

Parse $\mathit{req}$ as
$(\mathit{h},\allowbreak\mathit{com},\allowbreak\mathit{com}_{1},\allowbreak\mathit{com}_{2},\allowbreak\pi_{s})$.
Run the extractor $\mathcal{E}_{s}$ to extract the witness
$\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak o,\allowbreak
o_{1},\allowbreak o_{2}\rangle$ from $\pi_{s}$.

    * –:

If there is a tuple stored
$(\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\langle\mathit{h},\allowbreak\mathit{com}^{\prime},\allowbreak\mathit{com}_{1},\allowbreak\mathit{com}_{2},\allowbreak\pi_{s}\rangle,\langle\mathit{m}^{\prime}_{1},\allowbreak\mathit{m}^{\prime}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$ such that
$\mathit{com}^{\prime}\allowbreak=\allowbreak\mathit{com}$ but
$(\mathit{m}^{\prime}_{1},\allowbreak\mathit{m}^{\prime}_{2})\allowbreak\neq\allowbreak(\mathit{m}_{1},\allowbreak\mathit{m}_{2})$,
$\mathcal{S}$ outputs failure.

    * –:

If there is a stored tuple
$(\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$ such that
$\mathit{req}\allowbreak=\allowbreak\allowbreak\langle\mathit{h},\allowbreak\mathit{com}^{\prime},\allowbreak\mathit{com}_{1},\allowbreak\mathit{com}_{2},\allowbreak\pi_{s}\rangle$
and $\mathit{com}^{\prime}\allowbreak=\allowbreak\mathit{com}$, then take
$\mathit{wn}$ from that tuple and store a tuple
$(\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$, where
$\mathbb{R}\allowbreak\leftarrow\allowbreak\\{\mathit{reqid},\allowbreak\mathcal{V}_{i}\\}$
and $\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak o,\allowbreak
o_{1},\allowbreak o_{2}\rangle$ is the witness that was output by the
extractor $\mathcal{E}_{s}$. (We remark that $\mathit{wn}$ is the same
because, if $\mathit{com}$ is the same in two requests, the partial signatures
obtained from two different authorities can be aggregated, even if the values
$(\mathit{com}_{1},\allowbreak\mathit{com}_{2},\allowbreak\allowbreak\pi_{s})$
are different.) Else do the following:

      * *:

Pick up the stored tuple
$(\mathit{sid},\allowbreak\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wct})$
such that $\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$.
(This tuple is initialized to $\mathit{wct}\allowbreak=\allowbreak 0$.)

      * *:

Set
$\mathit{wct}\allowbreak\leftarrow\allowbreak\mathit{wct}\allowbreak+\allowbreak
1$.

      * *:

Set $\mathit{wn}\allowbreak\leftarrow\allowbreak\mathit{wct}$.

      * *:

Store
$(\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$, where
$\mathbb{R}\allowbreak\leftarrow\allowbreak\\{\mathit{reqid},\mathcal{V}_{i}\\}$.

      * *:

Update $\mathit{wct}$ in the tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wct})$.

$\mathcal{S}$ sends
$(\mathsf{ec.request.ini},\allowbreak\mathit{sid},\allowbreak\mathcal{V}_{i},\allowbreak\mathit{reqid},\allowbreak\mathit{wn})$
to $\mathcal{F}_{\mathrm{EC}}$. When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.request.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{U}_{j},\allowbreak\mathcal{V}_{i})$,
$\mathcal{S}$ sends the message
$(\mathsf{ec.request.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Honest authority issues attribute.:

When the functionality $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.issue.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{V}_{i},\allowbreak\mathcal{U}_{j})$,
$\mathcal{S}$ parses $\mathit{sid}$ as
$(\mathcal{V}_{1},\allowbreak\ldots,\allowbreak\mathcal{V}_{n},\allowbreak\mathit{sid}^{\prime})$,
sets
$\mathit{sid}_{\mathrm{SMT}}\allowbreak\leftarrow\allowbreak(\mathcal{V}_{i},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{sid}^{\prime})$
and sends the message
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$,
where $\mathit{l}(\mathit{m})$ is the length of the message that an honest
authority sends in the $\mathsf{ec.issue}$ interface.

Adversary forwards issuance.:

When the adversary $\mathcal{A}$ sends the message
$(\mathsf{smt.send.rep},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\mathit{qid})$,
$\mathcal{S}$ sends
$(\mathsf{ec.issue.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Corrupt user receives issuance.:

When $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.issue.end},\allowbreak\mathit{sid},\allowbreak\mathit{reqid},\allowbreak\mathcal{V}_{i})$
to a corrupt user $\mathcal{U}_{j}$, the simulator $\mathcal{S}$ finds the
stored tuple
$(\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$ such that
$\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and there is
element
$\\{\mathit{reqid}^{\prime},\allowbreak\mathcal{V}^{\prime}_{i}\\}\allowbreak\in\allowbreak\mathbb{R}$
such that $\mathit{reqid}^{\prime}\allowbreak=\allowbreak\mathit{reqid}$ and
$\mathcal{V}^{\prime}_{i}\allowbreak=\allowbreak\mathcal{V}_{i}$.
$\mathcal{S}$ parses $\mathit{req}$ as
$(\mathit{h},\allowbreak\mathit{com},\allowbreak\mathit{com}_{1},\allowbreak\mathit{com}_{2},\allowbreak\pi_{s})$.
$\mathcal{S}$ parses the secret key $\mathit{sk}_{\mathcal{V}_{i}}$ as
$(x_{i},\allowbreak y_{i,1},\allowbreak y_{i,2})$, computes
$c=\mathit{h}^{x_{i}}\prod_{j=1}^{2}\mathit{com}_{j}^{y_{i,j}}$ and sets the
blinded signature share
$\hat{\sigma}_{i}\allowbreak\leftarrow\allowbreak(\mathit{h},\allowbreak c)$
as in $\mathrm{\Pi}_{\mathrm{EC}}$. If a tuple
$(\mathit{sid},\allowbreak\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wn}^{\prime},\allowbreak\mathit{\mathbb{S}})$
such that $\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and
$\mathit{wn}^{\prime}\allowbreak=\allowbreak\mathit{wn}$ is not stored,
$\mathcal{S}$ stores a tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\\{i\\})$,
else updates
$\mathit{\mathbb{S}}\allowbreak\leftarrow\allowbreak\mathit{\mathbb{S}}\cup\\{i\\}$
in the tuple
$(\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathit{\mathbb{S}})$.
After that, $\mathcal{S}$ removes
$\\{\mathit{reqid},\allowbreak\mathcal{V}_{i}\\}$ from the set $\mathbb{R}$ in
the tuple
$(\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\mathit{req},\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$. Finally, $\mathcal{S}$ sets
$\mathit{sid}_{\mathrm{SMT}}\allowbreak\leftarrow\allowbreak(\mathcal{V}_{i},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{sid}^{\prime})$,
sets $\mathit{res}\leftarrow\hat{\sigma}_{i}$ and sends
$(\mathsf{smt.send.end},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\langle\mathit{reqid},\allowbreak\mathit{res}\rangle)$
to $\mathcal{A}$.

Corrupt authority issues attribute.:

When a corrupt authority $\tilde{\mathcal{V}}_{i}$ sends the message
$(\mathsf{smt.send.ini},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\langle\mathit{reqid},\allowbreak\mathit{res}\rangle)$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{SMT}}$ on input that message. When
the functionality $\mathcal{F}_{\mathrm{SMT}}$ sends
$(\mathsf{smt.send.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$,
$\mathcal{S}$ sends that message to $\mathcal{A}$.

Honest user receives issuance from corrupt authority.:

After the adversary $\mathcal{A}$ sends the message
$(\mathsf{smt.send.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$, the
simulator $\mathcal{S}$ runs $\mathcal{F}_{\mathrm{SMT}}$ on input that
message. When $\mathcal{F}_{\mathrm{SMT}}$ sends
$(\mathsf{smt.send.end},\allowbreak\mathit{sid}_{\mathrm{SMT}},\allowbreak\langle\mathit{reqid},\allowbreak\mathit{res}\rangle)$,
the simulator $\mathcal{S}$ parses $\mathit{sid}_{\mathrm{SMT}}$ as
$(\mathcal{V}_{i},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{sid}^{\prime})$
and runs the copy of the user $\mathcal{U}_{j}$ on input that message. We
remark that the copy of the user finds the request identifier $\mathit{reqid}$
of the request associated with this issuance message, or aborts if it is not
found. When the copy of the user outputs
$(\mathsf{ec.issue.end},\allowbreak\mathit{sid},\allowbreak\mathit{reqid},\allowbreak\mathcal{V}_{i})$,
$\mathcal{S}$ sends
$(\mathsf{ec.issue.ini},\allowbreak\mathit{sid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{reqid})$
to $\mathcal{F}_{\mathrm{EC}}$. When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.issue.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{V}_{i},\allowbreak\mathcal{U}_{j})$,
$\mathcal{S}$ sends
$(\mathsf{ec.issue.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Honest user begins spending.:

When $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.spend.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ sends
$(\mathsf{nym.send.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$
to $\mathcal{A}$, where $\mathit{l}(\mathit{m})$ is the length of the message
$\langle\mathit{pay},\allowbreak\mathit{payinfo}\rangle$ sent by an honest
user in the spend interface. Here we consider that the length does not change
depending on the number of spent coins. This can be achieved by setting a
maximum number of coins to be spent and sending always messages whose length
is the length of the message when the maximum number of coins is spent.

Adversary forwards spending.:

When $\mathcal{A}$ sends
$(\mathsf{nym.send.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ sends
$(\mathsf{ec.spend.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Corrupt provider receives spending.:

When $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.spend.end},\allowbreak\mathit{payid},\allowbreak
V,\allowbreak\mathit{payinfo},\allowbreak\mathit{P})$, $\mathcal{S}$ sets the
payment
$\mathit{pay}\allowbreak\leftarrow\allowbreak(\kappa,\allowbreak\sigma^{\prime},\allowbreak\langle
S_{k},\allowbreak T_{k},\allowbreak A_{k}\rangle_{k\in[0,V-1]},\allowbreak
V,\allowbreak C,\allowbreak\pi_{v})$ by running the procedure in Figure 4.
$\mathcal{S}$ stores
$(\mathit{sid},\allowbreak\mathit{payid},\allowbreak\mathit{pay},\allowbreak\mathit{payinfo})$
and sends the message
$(\mathsf{nym.send.end},\allowbreak\mathit{sid},\langle\mathit{pay},\mathit{payinfo}\rangle,\allowbreak\mathit{P})$
to $\mathcal{A}$.

Corrupt user begins spending.:

When the adversary $\mathcal{A}$ sends
$(\mathsf{nym.send.ini},\allowbreak\mathit{sid},\allowbreak\langle\mathit{pay},\allowbreak\mathit{payinfo}\rangle,\allowbreak\mathit{P},\allowbreak\mathcal{P}_{k})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{NYM}}$ on input that message. When
$\mathcal{F}_{\mathrm{NYM}}$ sends
$(\mathsf{nym.reply.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathit{l}(\mathit{m}))$,
$\mathcal{S}$ sends that message to $\mathcal{A}$.

Honest provider receives spending from corrupt user.:

After the adversary $\mathcal{A}$ sends the message
$(\mathsf{nym.reply.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
the simulator $\mathcal{S}$ runs $\mathcal{F}_{\mathrm{NYM}}$ on input that
message. When the functionality $\mathcal{F}_{\mathrm{NYM}}$ sends
$(\mathsf{nym.send.end},\allowbreak\mathit{sid},\langle\mathit{pay},\mathit{payinfo}\rangle,\allowbreak\mathit{P})$,
$\mathcal{S}$ runs
$b\allowbreak\leftarrow\allowbreak\mathsf{SpendVf}(\mathit{pk},\allowbreak\mathit{pay},\allowbreak\mathit{payinfo})$.
If $b\allowbreak=\allowbreak 0$, $\mathcal{S}$ aborts. Otherwise $\mathcal{S}$
runs the procedure in Figure 5 to check the payment and store a tuple
$(\mathit{pay},\allowbreak\mathit{payinfo},\langle\mathit{sk}_{\mathcal{U}_{j}},\allowbreak\mathit{v},\allowbreak
r,\allowbreak o_{c},\allowbreak\langle l_{k},\allowbreak
o_{a_{k}},\allowbreak\mu_{k},\allowbreak
o_{\mu_{k}}\rangle_{k=0}^{V-1}\rangle)$. After that, $\mathcal{S}$ checks that
the algorithm for identification of double spenders identifies the double
spender properly by running the procedure in Figure 6.

$\mathcal{S}$ sets
$\mathit{\mathbb{D}}\allowbreak\leftarrow\allowbreak\\{l_{k}|k\in[0,V-1]\\}$
and sends
$(\mathsf{ec.spend.ini},\allowbreak\mathit{sid},\allowbreak\mathit{wn},\allowbreak
V,\allowbreak\mathit{\mathbb{D}},\allowbreak\mathit{payinfo},\allowbreak\mathit{P},\allowbreak\mathcal{P}_{k})$
to $\mathcal{F}_{\mathrm{EC}}$. When the functionality
$\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.spend.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ sends
$(\mathsf{ec.spend.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Honest provider begins deposit of honest user $\mathcal{U}_{j}$ payment.:

If there are not corrupt authorities, $\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.deposit.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$
and $\mathcal{S}$ picks up random
$\mathit{payinfo}\allowbreak\leftarrow\allowbreak\mathit{U_{info}}$ and
$V\allowbreak\leftarrow\allowbreak[1,L]$. If there is at least one corrupt
authority, $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.deposit.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak
V,\allowbreak\mathit{payinfo})$.

After receiving the message from $\mathcal{F}_{\mathrm{EC}}$, $\mathcal{S}$
runs the procedure in Figure 4 to simulate an honest user payment
$\mathit{pay}$. $\mathcal{S}$ runs a copy of $\mathcal{F}_{\mathrm{BB}}$ on
input
$(\mathsf{bb.write.ini},\allowbreak\mathit{sid},\allowbreak\langle\mathit{pay},\allowbreak\mathit{payinfo}\rangle)$.
When $\mathcal{F}_{\mathrm{BB}}$ sends
$(\mathsf{bb.write.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$.

Honest provider starts deposit of corrupt user $\mathcal{U}_{j}$ payment.:

When $\mathcal{F}_{\mathrm{EC}}$ sends the message
$(\mathsf{ec.deposit.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak
V,\allowbreak\mathit{\mathbb{D}},\allowbreak\mathit{payinfo},\allowbreak\mathit{P},\allowbreak\mathcal{P}_{k})$,
$\mathcal{S}$ finds the tuple
$(\mathit{pay},\allowbreak\mathit{payinfo}^{\prime},\langle\mathit{sk}_{\mathcal{U}_{j}},\allowbreak\mathit{v},\allowbreak
r,\allowbreak o_{c},\allowbreak\langle l_{k},\allowbreak
o_{a_{k}},\allowbreak\mu_{k},\allowbreak
o_{\mu_{k}}\rangle_{k=0}^{V-1}\rangle)$, where $\mathit{pay}$ is
$(\kappa,\allowbreak\sigma^{\prime},\allowbreak\langle S_{k},\allowbreak
T_{k},\allowbreak A_{k}\rangle_{k\in[0,V^{\prime}-1]},\allowbreak
V^{\prime},\allowbreak C,\allowbreak\pi_{v})$, such that
$\mathit{sk}_{\mathcal{U}_{j}}$ is the secret key corresponding to the public
key registered by the corrupt user $\mathcal{U}_{j}$, $\mathit{v}$ is the
serial number associated with the wallet $\mathit{wn}$,
$V^{\prime}\allowbreak=\allowbreak V$, $\langle
l_{k}\rangle_{k\in[0,V-1]}=\mathit{\mathbb{D}}$, and
$\mathit{payinfo}^{\prime}\allowbreak=\allowbreak\mathit{payinfo}$.
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{BB}}$ on input
$(\mathsf{bb.write.ini},\allowbreak\mathit{sid},\allowbreak\langle\mathit{pay},\allowbreak\mathit{payinfo}\rangle)$.
When $\mathcal{F}_{\mathrm{BB}}$ sends
$(\mathsf{bb.write.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ forwards that message to $\mathcal{A}$. We remark that
$\mathcal{F}_{\mathrm{EC}}$ sends
$(\mathsf{ec.deposit.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid},\allowbreak\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak
V,\allowbreak\mathit{\mathbb{D}},\allowbreak\mathit{payinfo},\allowbreak\mathit{P},\allowbreak\mathcal{P}_{k})$
instead
$(\mathsf{ec.deposit.sim},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$
when the deposit corresponds to a payment made by a corrupt user and when at
least one authority is corrupt. When all the authorities are honest, the
adversary in the real world does not have access to the information in
$\mathcal{F}_{\mathrm{BB}}$, and thus the simulator does not need to learn
from $\mathcal{F}_{\mathrm{EC}}$ whether a payment made by a corrupt user has
been deposited.

Honest provider ends deposit.:

When the adversary $\mathcal{A}$ sends the message
$(\mathsf{bb.write.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$,
$\mathcal{S}$ runs $\mathcal{F}_{\mathrm{BB}}$ on input that message. When
$\mathcal{F}_{\mathrm{BB}}$ sends
$(\mathsf{bb.write.end},\allowbreak\mathit{sid})$, $\mathcal{S}$ sends
$(\mathsf{ec.deposit.rep},\allowbreak\mathit{sid},\allowbreak\mathit{qid})$ to
$\mathcal{F}_{\mathrm{EC}}$.

Procedure: Simulate honest user payment

  * •:

Pick random $r\leftarrow\mathbb{Z}_{p}$ and
$r^{\prime}\leftarrow\mathbb{Z}_{p}$.

  * •:

Compute
$\sigma^{\prime}=(\mathit{h}^{\prime},s^{\prime})\leftarrow(\mathit{g}^{r^{\prime}},\mathit{g}^{rr^{\prime}})$.

  * •:

Compute $\kappa\leftarrow\mathit{\tilde{g}}^{r}$.

  * •:

For $k\allowbreak\in\allowbreak[0,\allowbreak V-1]$, pick random
$S_{k}\allowbreak\leftarrow\allowbreak\mathbb{G}$,
$T_{k}\allowbreak\leftarrow\allowbreak\mathbb{G}$ and
$A_{k}\allowbreak\leftarrow\allowbreak\mathbb{G}$.

  * •:

Pick random $C\allowbreak\leftarrow\allowbreak\mathbb{G}$.

  * •:

Run the simulator $\mathcal{S}_{v}$ to compute a simulated proof $\pi_{v}$.

Figure 4. Procedure for simulating an honest user payment.

Procedure: Check Corrupt User Payment

  * •:

$\mathcal{S}$ parses $\mathit{pay}$ as
$(\kappa,\allowbreak\sigma^{\prime},\allowbreak\langle S_{k},\allowbreak
T_{k},\allowbreak A_{k}\rangle_{k\in[0,V-1]},\allowbreak V,\allowbreak
C,\allowbreak\pi_{v})$.

  * •:

$\mathcal{S}$ runs the extractor $\mathcal{E}_{v}$ to extract the witness
$(\mathit{sk}_{\mathcal{U}_{j}},\allowbreak\mathit{v},\allowbreak
r,\allowbreak o_{c},\allowbreak\langle l_{k},\allowbreak
o_{a_{k}},\allowbreak\mu_{k},\allowbreak o_{\mu_{k}}\rangle_{k=0}^{V-1})$ from
the proof $\pi_{v}$.

  * •:

$\mathcal{S}$ parses $\sigma^{\prime}$ as $(\mathit{h}^{\prime},\allowbreak
s^{\prime})$ and computes
$\hat{\sigma}\allowbreak=\allowbreak(\hat{\mathit{h}},\allowbreak\hat{s})\allowbreak=\allowbreak(\mathit{h}^{\prime},\allowbreak
s^{\prime}(\mathit{h}^{\prime})^{-r})$.

  * •:

$\mathcal{S}$ runs the verification equation
$\mathit{e}(\hat{\mathit{h}},\allowbreak\tilde{\alpha}\allowbreak\tilde{\beta}_{1}^{\mathit{sk}_{\mathcal{U}_{j}}}\tilde{\beta}_{2}^{\mathit{v}})\allowbreak=\allowbreak\mathit{e}(\hat{s},\allowbreak\mathit{\tilde{g}})$
of the Pointcheval-Sanders signature scheme. If the verification equation does
not hold, $\mathcal{S}$ outputs failure.

  * •:

$\mathcal{S}$ finds a tuple
$(\mathcal{U}_{j},\allowbreak\mathit{wn},\allowbreak\mathbb{R},\allowbreak\langle\mathit{h},\allowbreak\mathit{com},\allowbreak\mathit{com}_{1},\allowbreak\mathit{com}_{2},\allowbreak\pi_{s}\rangle,\allowbreak\langle\mathit{m}_{1},\allowbreak\mathit{m}_{2},\allowbreak
o,\allowbreak o_{1},\allowbreak o_{2}\rangle)$ such that
$\mathit{m}_{1}\allowbreak=\allowbreak\mathit{sk}_{\mathcal{U}_{j}}$ and
$\mathit{m}_{2}\allowbreak=\allowbreak\mathit{v}$. If such a tuple is not
stored, $\mathcal{S}$ outputs failure, else $\mathcal{S}$ takes
$\mathcal{U}_{j}$ and $\mathit{wn}$ from that tuple. We remark that, in this
tuple, $\mathcal{U}_{j}$ is always the identity of a corrupt user.

  * •:

$\mathcal{S}$ finds a tuple
$(\mathit{sid},\allowbreak\mathcal{U}^{\prime}_{j},\allowbreak\mathit{wn}^{\prime},\allowbreak\mathit{\mathbb{S}})$
such that $\mathcal{U}^{\prime}_{j}\allowbreak=\allowbreak\mathcal{U}_{j}$ and
$\mathit{wn}^{\prime}\allowbreak=\allowbreak\mathit{wn}$. $\mathcal{S}$
outputs failure if such a tuple is not stored, or if
$|\mathit{\mathbb{S}}|<t-\tilde{t}$, where $\tilde{t}$ is the number of
corrupt authorities.

  * •:

For $k\in[0,V-1]$, $\mathcal{S}$ checks whether
$S_{k}=\delta^{1/(\mathit{v}+l_{k}+1)}$ and
$T_{k}\allowbreak=\allowbreak\mathit{g}^{\mathit{sk}_{\mathcal{U}_{j}}+R_{k}/(\mathit{v}+l_{k}+1)}$,
where $R_{k}\leftarrow H^{\prime}(\mathit{payinfo},k)$. If any of those checks
fails, $\mathcal{S}$ outputs failure.

  * •:

$\mathcal{S}$ stores the tuple
$(\mathit{pay},\allowbreak\mathit{payinfo},\langle\mathit{sk}_{\mathcal{U}_{j}},\allowbreak\mathit{v},\allowbreak
r,\allowbreak o_{c},\allowbreak\langle l_{k},\allowbreak
o_{a_{k}},\allowbreak\mu_{k},\allowbreak
o_{\mu_{k}}\rangle_{k=0}^{V-1}\rangle)$.

Figure 5. Procedure for checking a corrupt user payment.

Procedure: Check Double Spending

  * •:

$\mathcal{S}$ takes the tuple
$(\mathit{pay},\allowbreak\mathit{payinfo},\langle\mathit{sk}_{\mathcal{U}_{j}},\allowbreak\mathit{v},\allowbreak
r,\allowbreak o_{c},\allowbreak\langle l_{k},\allowbreak
o_{a_{k}},\allowbreak\mu_{k},\allowbreak
o_{\mu_{k}}\rangle_{k=0}^{V-1}\rangle)$ for the payment made by a corrupt
user.

  * •:

For all the stored tuples
$(\mathit{pay}^{\prime},\allowbreak\mathit{payinfo}^{\prime},\langle\mathit{sk}^{\prime}_{\mathcal{U}_{j}},\allowbreak\mathit{v}^{\prime},\allowbreak
r^{\prime},\allowbreak o^{\prime}_{c},\allowbreak\langle
l^{\prime}_{k},\allowbreak
o^{\prime}_{a_{k}},\allowbreak\mu^{\prime}_{k},\allowbreak
o^{\prime}_{\mu_{k}}\rangle_{k=0}^{V^{\prime}-1}\rangle)$, $\mathcal{S}$
checks whether
$\mathit{sk}^{\prime}_{\mathcal{U}_{j}}\allowbreak=\allowbreak\mathit{sk}_{\mathcal{U}_{j}}$,
$\mathit{v}^{\prime}\allowbreak=\allowbreak\mathit{v}$ and $\langle
l^{\prime}_{k}\rangle_{k\in[0,V^{\prime}-1]}\cap\langle
l_{k}\rangle_{k\in[0,V-1]}\allowbreak\neq\allowbreak\emptyset$, which means
that there is a double spending. $\mathcal{S}$ sets $\mathit{PK}$ to contain
all the registered public keys and runs the algorithm
$c\allowbreak\leftarrow\allowbreak\mathsf{Identify}(\mathit{params},\allowbreak\mathit{PK},\allowbreak\mathit{pay},\allowbreak\mathit{pay}^{\prime},\allowbreak\mathit{payinfo},\allowbreak\mathit{payinfo}^{\prime})$.
Then $\mathcal{S}$ proceeds as follows:

    * –:

If there is double spending, $\mathcal{S}$ does the following:

      * *:

If $\mathit{payinfo}\allowbreak=\allowbreak\mathit{payinfo}^{\prime}$ and
$c\allowbreak\neq\allowbreak\mathit{payinfo}$, $\mathcal{S}$ outputs failure.
We note that authorities verify that $\mathit{payinfo}$ contains an identifier
of the provider that deposited the payment. This avoids that an honest
provider can be found guilty when an adversarial provider e.g. double deposits
a payment with payment information $\mathit{payinfo}$ that contains the
identifier of an honest provider.

      * *:

If $\mathit{payinfo}\allowbreak\neq\allowbreak\mathit{payinfo}^{\prime}$ and
$c\allowbreak\neq\allowbreak\mathit{pk}_{\mathcal{U}_{j}}$, where
$\mathit{pk}_{\mathcal{U}_{j}}$ is the public key associated with secret key
$\mathit{sk}_{\mathcal{U}_{j}}$, $\mathcal{S}$ outputs failure.

    * –:

If there is not double spending, and if
$c\allowbreak=\allowbreak\mathit{pk}_{\mathcal{U}_{j}}$, where
$\mathit{pk}_{\mathcal{U}_{j}}$ is a public key associated with an honest
user, $\mathcal{S}$ outputs failure. We remark that it is possible for the
adversary to produce two payments where there is not double-spending, and yet
the algorithm $\mathsf{Identify}$ detects double spending. When that happens,
we must ensure that algorithm $\mathsf{Identify}$ does not output the public
key of an honest user. We recall that authorities verify that
$\mathit{payinfo}$ contains an identifier of the provider that deposited the
payment, which also avoids an honest provider from being framed in this case.

Figure 6. Procedure for checking double spending.

Corrupt provider begins deposit.:

When $\mathcal{A}$ sends
$(\mathsf{bb.write.ini},\allowbreak\mathit{sid},\allowbreak\langle\mathit{pay},\allowbreak\mathit{payinfo}\rangle)$,
the simulator $\mathcal{S}$ checks if a tuple
$(\mathit{sid},\allowbreak\mathit{payid},\allowbreak\mathit{pay}^{\prime},\allowbreak\mathit{payinfo}^{\prime})$
such that $\mathit{pay}^{\prime}\allowbreak=\allowbreak\mathit{pay}$ and
$\mathit{payinfo}^{\prime}\allowbreak=\allowbreak\mathit{payinfo}$ is stored.
If it is stored, which means that this is a payment that was sent to
$\mathcal{A}$ by the simulator acting as an honest user, $\mathcal{S}$ takes
$\mathit{payid}$ from that tuple and proceeds with step 2 below. Otherwise we
are in the case of a payment that a corrupt user sent to a corrupt provider,
and thus $\mathcal{S}$ did not receive it during the spending phase.