Rad HAZU, Matematičke znanosti, Vol. 25 (2021), 107-141.

HIERARCHICAL AND DYNAMIC THRESHOLD PAILLIER CRYPTOSYSTEM WITHOUT TRUSTED DEALER

Andreas Klinger, Stefan Wüller, Giulia Traverso and Ulrike Meyer

RWTH Aachen University, Templergraben 55, 52062 Aachen, Germany
e-mail: klinger@itsec.rwth-aachen.de

RWTH Aachen University, Templergraben 55, 52062 Aachen, Germany
e-mail: wueller@itsec.rwth-aachen.de

EY Switzerland, Rue du Simplon 35, 1006 Lausanne, Switzerland
e-mail: giutra90@icloud.com

RWTH Aachen University, Templergraben 55, 52062 Aachen, Germany
e-mail: meyer@itsec.rwth-aachen.de

Abstract.   We propose the first hierarchical and dynamic threshold Paillier cryptosystem without trusted dealer and prove its security in the malicious adversary model. The new cryptosystem is fully distributed, i. e., public and private key generation is performed without a trusted dealer. The private key is shared with a hierarchical and dynamic secret sharing scheme over the integers. In such a scheme not only the amount of shareholders, but also their levels in the hierarchy decide whether or not they can reconstruct the secret and new shareholders can be added or removed without reconstruction of the secret.

2020 Mathematics Subject Classification.   94A60, 94A62.

Key words and phrases.   Homomorphic cryptosystem, threshold cryptosystem, hierarchical secret sharing, dynamic secret sharing, Paillier, SMPC, Birkhoff interpolation.

Full text (PDF) (free access)

DOI: https://doi.org/10.21857/mnlqgc582y

References:

  1. S. G. Akl and P. D. Taylor, Cryptographic solution to a problem of access control in a hierarchy, ACM Trans. Comput. Syst. 1 (3) (1983), 239-248.
    CrossRef

  2. A. Beimel, T. Tassa and E. Weinreb, Characterizing ideal weighted threshold secret sharing, in: Theory of Cryptography, Lecture Notes in Comput. Sci. 3378, Springer, Berlin, 2005, pp. 600-619.
    MathSciNet     CrossRef

  3. J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, in: Advances in Cryptology – CRYPTO 88, Lecture Notes in Comput. Sci. 403, Springer, New York, 1990, pp. 27-35.
    MathSciNet     CrossRef

  4. G. R. Blakley, Safeguarding cryptographic keys, in: Proceedings of International Workshop on Managing Requirements Knowledge, 1979, pp. 313-317.
    CrossRef

  5. P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft, Secure multiparty computation goes live, in: Financial Cryptography and Data Security, Lecture Notes in Comput. Sci. 5628, Springer, Berlin, 2009, pp. 325-343.
    CrossRef

  6. D. Boneh and M. Franklin, Efficient generation of shared RSA keys, in: Advances in Cryptology - CRYPTO '97, Lecture Notes in Comput. Sci. 1294, Springer, Berlin, 1997, pp. 425-439.
    CrossRef

  7. E. F. Brickell, Some ideal secret sharing schemes, in: Advances in Cryptology - EUROCRYPT 89, Lecture Notes in Comput. Sci. 434, Springer, Berlin, 1990, pp. 468-475.
    MathSciNet     CrossRef

  8. C. Clifton, M. Kantarcioglu, A. Doan, G. Schadow, J. Vaidya, A. Elmagarmid and D. Suciu, Privacy-preserving data integration and sharing, in: Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery - DMKD ’04, ACM Press, 2004, pp. 19-26.
    CrossRef

  9. R. Cramer, I. Damgård and J. B. Nielsen, Multiparty computation from threshold homomorphic encryption, in: Advances in Cryptology – EUROCRYPT 2001, Lecture Notes in Comput. Sci. 2045, Springer, Berlin, 2001, pp. 280-300.
    MathSciNet     CrossRef

  10. I. Damgård and M. Jurik, A length-flexible threshold cryptosystem with applications, in: Information Security and Privacy, Lecture Notes in Comput. Sci. 2727, Springer, Berlin, 2003, pp. 350-364.
    CrossRef

  11. I. Damgård and M. Koprowski, Practical threshold RSA signatures without a trusted dealer, in: Advances in Cryptology - EUROCRYPT 2001, Lecture Notes in Comput. Sci. 2045, Springer, Berlin, 2001, pp. 152-165.
    MathSciNet     CrossRef

  12. I. Damgård and J. B. Nielsen, Universally composable efficient multiparty computation from threshold homomorphic encryption, in: Advances in Cryptology - CRYPTO 2003, Lecture Notes in Comput. Sci. 2729, Springer, Berlin, 2003, pp. 247-264.
    MathSciNet     CrossRef

  13. Y. Desmedt, Society and group oriented cryptography: a new concept, in: Advances in Cryptology - CRYPTO 87, Lecture Notes in Comput. Sci. 293, Springer, Berlin, 1988, pp. 120-127.
    CrossRef

  14. Y. Desmedt and Y. Frankel, Threshold cryptosystems, in: Advances in Cryptology - CRYPTO 89 Proceedings, Lecture Notes in Comput. Sci. 435, Springer, New York, 1990, pp. 307-315.
    CrossRef

  15. O. Farràs and C. Padró, Ideal hierarchical secret sharing schemes, in: Theory of Cryptography, Lecture Notes in Comput. Sci. 5978, Springer, Berlin, 2010, pp. 219-236.
    MathSciNet     CrossRef

  16. P.-A. Fouque, G. Poupard and J. Stern, Sharing decryption in the context of voting or lotteries, in: Financial Cryptography, Lecture Notes in Comput. Sci. 1962, Springer, Berlin, 2001, pp. 90-104.
    CrossRef

  17. R. Gennaro, S. Halevi, H. Krawczyk and T. Rabin, Threshold RSA for dynamic and ad-hoc groups, in: Advances in Cryptology - EUROCRYPT 2008, Lecture Notes in Comput. Sci. 4965, Springer, Berlin, 2008, pp. 88-107.
    MathSciNet     CrossRef

  18. H. Ghodosi, J. Pieprzyk and R. Safavi-Naini, Dynamic threshold cryptosystems (A new scheme in group oriented cryptography), in: Proceedings of PRAGOCRYPT 96 (1996), pp. 370-379.

  19. H. Ghodosi, J. Pieprzyk and R. Safavi-Naini, Secret sharing in multilevel and compartmented groups, in: Information Security and Privacy, Lecture Notes in Comput. Sci. 1438, Springer, Berlin, 1998, pp. 367-378.
    MathSciNet     CrossRef

  20. O. Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, 2003.
    MathSciNet     CrossRef

  21. O. Goldreich, Foundations of Cryptography: Basic Applications, Cambridge University Press, 2004.
    CrossRef

  22. D. Grigoriev and I. Ponomarenko, Homomorphic public-key cryptosystems and encrypting Boolean circuits, Appl. Algebra Engrg. Comm. Comput. 17 (2006), 239-255.
    MathSciNet     CrossRef

  23. L. Harn, H. Lin and S. Yang, Threshold cryptosystem with multiple secret sharing policies, IEE Proceedings - Computers and Digital Techniques 141 (1994), 142-144.

  24. C. Hazay and Y. Lindell, Efficient Secure Two-Party Protocols, Springer, Berlin, 2010.
    CrossRef

  25. M. Ito, A. Saito and T. Nishizeki, Secret sharing scheme realizing general access structure, Electron. Comm. Japan Part III Fund. Electron. Sci. 72 (9) (1989), 56-64.
    MathSciNet     CrossRef

  26. C. S. Laih and L. Harn, Generalized threshold cryptosystems, in: Advances in Cryptology – ASIACRYPT '91, Lecture Notes in Comput. Sci. 2894, Springer, Berlin, 1993, pp. 159-166.
    MathSciNet     CrossRef

  27. G. G. Lorentz, K. Jetter and S. Riemenschneider, Birkhoff Interpolation, Encyclopedia of Mathematics and its Applications 19, Cambridge University Press, 1983.
    MathSciNet     CrossRef

  28. R. Mendes and J. P. Vilela, Privacy-preserving data mining: Methods, metrics, and applications, IEEE Access 5 (2017), 10562–10582.
    CrossRef

  29. T. Nishide and K. Sakurai, Distributed Paillier cryptosystem without trusted dealer, in: Information Security Applications, Lecture Notes in Comput. Sci. 6513, Springer, Berlin, 2010, pp. 44-60.
    CrossRef

  30. T. Okamoto, An efficient divisible electronic cash scheme, in: Advances in Cryptology - CRYPTO '95, Lecture Notes in Comput. Sci. 963, Springer, Berlin, 1995, pp. 438-451.
    CrossRef

  31. P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: Advances in Cryptology - EUROCRYPT 99, Lecture Notes in Comput. Sci. 1592, Springer, Berlin, 1999, pp. 223-238.
    MathSciNet     CrossRef

  32. N. Pakniat, M. Noroozi and Z. Eslami, Distributed key generation protocol with hierarchical threshold access structure, IET Information Security 9 (2015), 248-255.
    CrossRef

  33. T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in: Advances in Cryptology - CRYPTO 91, Lecture Notes in Comput. Sci. 576, Springer, Berlin, 1991, pp. 129-140.
    MathSciNet     CrossRef

  34. T. P. Pedersen, A threshold cryptosystem without a trusted party, in: Advances in Cryptology - EUROCRYPT 91, Lecture Notes in Comput. Sci. 547, Springer, Berlin, 1991, pp. 522-526.
    CrossRef

  35. T. Rabin, A simplified approach to threshold and proactive RSA, in: Advances in Cryptology - CRYPTO ’98, Lecture Notes in Comput. Sci. 1462, Springer, Berlin, 1998, pp. 89-104.
    CrossRef

  36. A. Shamir, How to share a secret, Commun. ACM 22 (1979), 612-613.
    MathSciNet     CrossRef

  37. G. J. Simmons, How to (really) share a secret, in: Advances in Cryptology - CRYPTO 88, Lecture Notes in Comput. Sci. 403, Springer, New York, 1990, pp. 390-448.
    MathSciNet     CrossRef

  38. T. Tassa, Hierarchical threshold secret sharing, J. Cryptology 20 (2007), 237-264.
    MathSciNet     CrossRef

  39. G. Traverso, D. Demirel and J. Buchmann, Dynamic and verifiable hierarchical secret sharing, in: Information Theoretic Security, Lecture Notes in Comput. Sci. 10015, Springer, Cham, 2016, pp. 24-43.
    MathSciNet     CrossRef

  40. G. Traverso, D. Demirel and J. Buchmann, Performing computations on hierarchically shared secrets, in: Progress in Cryptology - AFRICACRYPT 2018, Lecture Notes in Comput. Sci. 10831, Springer, Cham, 2018, pp. 141-161.
    MathSciNet     CrossRef

Rad HAZU Home Page