Skip to main content
SpringerLink
Log in

Divisible E-Cash from Constrained Pseudo-Random Functions

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

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

Abstract

Electronic cash (e-cash) is the digital analogue of regular cash which aims at preserving users’ privacy. Following Chaum’s seminal work, several new features were proposed for e-cash to address the practical issues of the original primitive. Among them, divisibility has proved very useful to enable efficient storage and spendings. Unfortunately, it is also very difficult to achieve and, to date, quite a few constructions exist, all of them relying on complex mechanisms that can only be instantiated in one specific setting. In addition security models are incomplete and proofs sometimes hand-wavy.

In this work, we first provide a complete security model for divisible e-cash, and we study the links with constrained pseudo-random functions (PRFs), a primitive recently formalized by Boneh and Waters. We exhibit two frameworks of divisible e-cash systems from constrained PRFs achieving some specific properties: either key homomorphism or delegability. We then formally prove these frameworks, and address two main issues in previous constructions: two essential security notions were either not considered at all or not fully proven. Indeed, we introduce the notion of clearing, which should guarantee that only the recipient of a transaction should be able to do the deposit, and we show the exculpability, that should prevent an honest user to be falsely accused, was wrong in most proofs of the previous constructions. Some can easily be repaired, but this is not the case for most complex settings such as constructions in the standard model. Consequently, we provide the first construction secure in the standard model, as a direct instantiation of our framework.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 39.99
Price excludes VAT (USA)
Softcover Book
USD 54.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Actually, this specific terminology appeared later [21] but this notion is implicit in the Chaum’s paper.

  2. 2.

    The terminology can be confusing here: the “divisible coin” considered by most of the papers corresponds to the “wallet” of a compact e-cash system. In particular, the divisible coin contains several coins that are all associated to a serial number.

  3. 3.

    Our comment obviously only applies to papers that provide a security proof.

  4. 4.

    We stress that the problem is located in the proofs and not in the definition of the exculpability property.

  5. 5.

    Identification of the spender is not possible in this case because the two transcripts received by the bank (the one sent by the spender and the one sent by the merchant) are exactly the same.

  6. 6.

    Although the general definition in [10] allows randomized \(\mathtt {CKey}\) algorithm, all our constructions will require this algorithm to be deterministic.

  7. 7.

    We note that our privacy requirements are weaker than the ones of [7, 9] since we allow the constrained keys to leak the size of the subsets.

  8. 8.

    We do not make any assumption on the indices \(i_0,\ldots ,i_{V-1}\), contrarily to some previous works that assume they are consecutive.

  9. 9.

    The “correctness for merchant”, informally defined in [1], is related to this issue. It ensures that the transcript deposited by an honest merchant will be accepted, even if the spender is dishonest and double-spends his coin. However, it only considers an honest bank and it does not consider situations where the transcript would be deposited by another entity. In particular, the scheme in [1] does not ensure that the merchant is the only one able to clear his coins.

  10. 10.

    Actually the size of \(\mathcal {X}\) can leak as it corresponds to the public amount of the transaction.

  11. 11.

    For sake of clarity, we assume here that the elements associated with the users’ identity live in the right spaces. Our formal definition will make use of suitable maps to ensure this fact.

  12. 12.

    We need to apply the exponent R on the identity itself instead of the constrained key to rely on the correctness of \(\mathtt {CEval}\), but the principle is the same.

  13. 13.

    The requirements placed on these functions are specified in the full version [11].

  14. 14.

    We nevertheless note that the cut-and-choose technique used during withdrawal in [1] is very specific to this work and does not fit our framework.

  15. 15.

    This string can simply be a counter incremented by the merchant after each transaction, or include information that uniquely identifies the transaction such as the date and the hour.

References

  1. Au, M.H., Susilo, W., Mu, Y.: Practical anonymous divisible e-cash from bounded accumulators. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 287–301. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85230-8_26

    Chapter  Google Scholar 

  2. Baldimtsi, F., Chase, M., Fuchsbauer, G., Kohlweiss, M.: Anonymous transferable e-cash. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 101–124. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_5

    Chapter  Google Scholar 

  3. Banerjee, A., Fuchsbauer, G., Peikert, C., Pietrzak, K., Stevens, S.: Key-homomorphic constrained pseudorandom functions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 31–60. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_2

    Chapter  Google Scholar 

  4. Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614–629. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_38

    Chapter  Google Scholar 

  5. Bellare, M., Shi, H., Zhang, C.: Foundations of group signatures: the case of dynamic groups. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 136–153. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30574-3_11

    Chapter  Google Scholar 

  6. Blazy, O., Canard, S., Fuchsbauer, G., Gouget, A., Sibert, H., Traoré, J.: Achieving optimal anonymity in transferable e-cash with a judge. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 206–223. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21969-6_13

    Chapter  MATH  Google Scholar 

  7. Boneh, D., Kim, S., Montgomery, H.: Private puncturable PRFs from standard lattice assumptions. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 415–445. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_15

    Chapter  Google Scholar 

  8. Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23

    Chapter  Google Scholar 

  9. Boneh, D., Lewi, K., Wu, D.J.: Constraining pseudorandom functions privately. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10175, pp. 494–524. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_17

    Chapter  Google Scholar 

  10. Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 280–300. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_15

    Chapter  Google Scholar 

  11. Bourse, F., Pointcheval, D., Sanders, O.: Divisible e-cash from constrained pseudo-random functions. IACR Cryptology ePrint Archive, vol. 136 (2019)

    Google Scholar 

  12. Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_29

    Chapter  Google Scholar 

  13. Camenisch, J., Hohenberger, S., Lysyanskaya, A.: Compact e-cash. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 302–321. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_18

    Chapter  Google Scholar 

  14. Canard, S., Gouget, A.: Divisible e-cash systems can be truly anonymous. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 482–497. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72540-4_28

    Chapter  Google Scholar 

  15. Canard, S., Gouget, A.: Anonymity in transferable e-cash. In: Bellovin, S.M., Gennaro, R., Keromytis, A., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 207–223. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68914-0_13

    Chapter  Google Scholar 

  16. Canard, S., Gouget, A.: Multiple denominations in e-cash with compact transaction data. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 82–97. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14577-3_9

    Chapter  Google Scholar 

  17. Canard, S., Gouget, A., Traoré, J.: Improvement of efficiency in (unconditional) anonymous transferable e-cash. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 202–214. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85230-8_19

    Chapter  Google Scholar 

  18. Canard, S., Pointcheval, D., Sanders, O., Traoré, J.: Divisible e-cash made practical. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 77–100. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_4

    Chapter  Google Scholar 

  19. Canard, S., Pointcheval, D., Sanders, O., Traoré, J.: Scalable divisible e-cash. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 287–306. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28166-7_14

    Chapter  Google Scholar 

  20. Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology, pp. 199–203. Springer, Boston, MA (1983). https://doi.org/10.1007/978-1-4757-0602-4_18

    Chapter  Google Scholar 

  21. Chaum, D., Fiat, A., Naor, M.: Untraceable electronic cash. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 319–327. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_25

    Chapter  Google Scholar 

  22. Chaum, D., Pedersen, T.P.: Transferred cash grows in size. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 390–407. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-47555-9_32

    Chapter  MATH  Google Scholar 

  23. Fuchsbauer, G., Pointcheval, D., Vergnaud, D.: Transferable constant-size fair e-cash. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 226–247. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10433-6_15

    Chapter  Google Scholar 

  24. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)

    Article  MathSciNet  Google Scholar 

  25. Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_24

    Chapter  Google Scholar 

  26. Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 13, pp. 669–684. ACM Press, November 2013

    Google Scholar 

  27. Libert, B., Ling, S., Nguyen, K., Wang, H.: Zero-knowledge arguments for lattice-based PRFs and applications to e-cash. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 304–335. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_11

    Chapter  Google Scholar 

  28. Märtens, P.: Practical divisible e-cash. IACR Cryptology ePrint Archive 2015, 318 (2015)

    Google Scholar 

  29. Okamoto, T., Ohta, K.: Universal electronic cash. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 324–337. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_27

    Chapter  Google Scholar 

  30. Pointcheval, D., Sanders, O., Traoré, J.: Cut down the tree to achieve constant complexity in divisible e-cash. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 61–90. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54365-8_4

    Chapter  Google Scholar 

  31. Pointcheval, D., Stern, J.: Provably secure blind signature schemes. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 252–265. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0034852

    Chapter  Google Scholar 

  32. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000)

    Article  Google Scholar 

Download references

Acknowledgements

We thank Benoît Libert for very helpful discussions on the exculpability issue of previous works. This work is supported in part by the European Union PROMETHEUS Project (Horizon 2020 Research and Innovation Program, Grant Agreement no. 780701) and the European Community’s Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 – CryptoCloud).

Author information

Authors and Affiliations

  1. Orange Labs, Applied Crypto Group, Cesson-Sévigné, France

    Florian Bourse & Olivier Sanders

  2. DIENS, Ecole normale supérieure, CNRS, PSL University, Paris, France

    David Pointcheval

  3. INRIA, Paris, France

    David Pointcheval

Authors
  1. Florian Bourse
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Pointcheval
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olivier Sanders
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Olivier Sanders .

Editor information

Editors and Affiliations

  1. University of Auckland, Auckland, New Zealand

    Steven D. Galbraith

  2. Security Fundamentals Lab, NICT, Tokyo, Japan

    Shiho Moriai

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bourse, F., Pointcheval, D., Sanders, O. (2019). Divisible E-Cash from Constrained Pseudo-Random Functions. In: Galbraith, S., Moriai, S. (eds) Advances in Cryptology – ASIACRYPT 2019. ASIACRYPT 2019. Lecture Notes in Computer Science(), vol 11921. Springer, Cham. https://doi.org/10.1007/978-3-030-34578-5_24

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-34578-5_24

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-34577-8

  • Online ISBN: 978-3-030-34578-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation