Top

Published in:

2020 | OriginalPaper | Chapter

Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles

Authors : Jodie Knapp, Elizabeth A. Quaglia

Published in: Provable and Practical Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Achieving fairness and soundness in non-simultaneous rational secret sharing schemes has proved to be challenging. On the one hand, soundness can be ensured by providing side information related to the secret as a check, but on the other, this can be used by deviant players to compromise fairness. To overcome this, the idea of incorporating a time delay was suggested in the literature: in particular, time-delay encryption based on memory-bound functions has been put forth as a solution. In this paper, we propose a different approach to achieve such delay, namely using homomorphic time-lock puzzles (HTLPs), introduced at CRYPTO 2019, and construct a fair and sound rational secret sharing scheme in the non-simultaneous setting from HTLPs.

HTLPs are used to embed sub-shares of the secret for a predetermined time. This allows to restore fairness of the secret reconstruction phase, despite players having access to information related to the secret which is required to ensure the soundness of the scheme. Key to our construction is the fact that the time-lock puzzles are homomorphic so that players can compactly evaluate sub-shares. Without this efficiency improvement, players would have to independently solve each puzzle sent from the other players to obtain a share of the secret, which would be computationally inefficient. We argue that achieving both fairness and soundness in a non-simultaneous scheme using a time delay based on CPU-bound functions rather than memory-bound functions is more cost-effective and realistic in relation to the implementation of the construction.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Dispelling Myths on Superposition Attacks: Formal Security Model and Attack Analyses

next chapter Optimal Threshold Changeable Secret Sharing with New Threshold Change Range

See Appendices D.1, and D.2 for further discussion on payoff functions and equilibrium concepts.

A CMBF is a family of deterministic algorithms such that an efficiently generated key can decrypt the encrypted input, with a lower-bound on the number of memory-access steps to do so.

Note that [30] works under the assumption that players prefer everyone to obtain the correct output over misleading others, therefore soundness is not an issue that needs to be addressed.

Privacy and authentication of the distribution of shares is a standard cryptographic assumption in secret sharing schemes [34].

Whilst not explicit in the definition, there is an upper bound on how long players can communicate their shares for. Therefore, at the end of their communication, if a player \(P_i\) has not obtained a sufficient number of shares, then they output \(\bot \) at the end of the reconstruction phase.

What \(\varPsi \) is depends on the application the HTLP is being used for. It could be addition, multiplication or XOR for example.

We call the HTLP encryption of the sub-shares sub-puzzles for ease of understanding. They are simply time-lock puzzles that can be homomorphically evaluated to obtain a puzzle of the share which corresponds to the homomorphic evaluation of the given sub-shares.

At least one round of communication is required before players can start processing.

In a standard TLP scheme, the computational complexity of the puzzle-solving algorithm P.Solve is the same as HP.Solve.

Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately hard, memory-bound functions. ACM Trans. Internet Technol. 5, 299–327 (2005)CrossRef

Asharov, G., Lindell, Y.: Utility dependence in correct and fair rational secret sharing. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 559–576. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_33CrossRefMATH

Beimel, A.: Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Technion-Israel Institute of technology, Faculty of computer science, Israel (1996)

Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., et al. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20901-7_2CrossRef

Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the AFIPS National Computer Conference, NCC 1979, vol. 48, pp. 313–318. International Workshop on Managing Requirements Knowledge (MARK). IEEE (1979)

Cathalo, J., Libert, B., Quisquater, J.-J.: Efficient and non-interactive timed-release encryption. In: Qing, S., Mao, W., López, J., Wang, G. (eds.) ICICS 2005. LNCS, vol. 3783, pp. 291–303. Springer, Heidelberg (2005). https://doi.org/10.1007/11602897_25CrossRefMATH

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 11–19. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-48184-2_43CrossRef

Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC 1986, pp. 364–369. Association for Computing Machinery (1986)

Cramer, R., Damgård, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_22CrossRef

10.

De, S.J., Pal, A.K.: Achieving correctness in fair rational secret sharing. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds.) CANS 2013. LNCS, vol. 8257, pp. 139–161. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-02937-5_8CrossRef

11.

Desmedt, Y., Di Crescenzo, G., Burmester, M.: Multiplicative non-abelian sharing schemes and their application to threshold cryptography. In: Pieprzyk, J., Safavi-Naini, R. (eds.) ASIACRYPT 1994. LNCS, vol. 917, pp. 19–32. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0000421CrossRef

12.

Desmedt, Y., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457–469. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_37CrossRef

13.

Desmedt, Y.G., Frankel, Y.: Homomorphic zero-knowledge threshold schemes over any finite abelian group. SIAM J. Dis. Math. 7(4), 667–679 (1994)MathSciNetCrossRef

14.

Dodis, Y., Rabin, T.: Cryptography and game theory. Algorithmic Game Theor. 181–207 (2007)

15.

Doshi, S., Monrose, F., Rubin, A.D.: Efficient memory bound puzzles using pattern databases. In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006. LNCS, vol. 3989, pp. 98–113. Springer, Heidelberg (2006). https://doi.org/10.1007/11767480_7CrossRef

16.

Dwork, C., Goldberg, A., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_25CrossRef

17.

Fuchsbauer, G., Katz, J., Naccache, D.: Efficient rational secret sharing in standard communication networks. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 419–436. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_25CrossRef

18.

Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM (JACM) 58(6), 1–37 (2011)MathSciNetCrossRef

19.

Gordon, S.D., Katz, J.: Rational secret sharing, revisited. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 229–241. Springer, Heidelberg (2006). https://doi.org/10.1007/11832072_16CrossRef

20.

Goyal, V., Pandey, O., Sahai, B., Waters, A.: Attribute-based encryption for fine-grained access control of encrypted data. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, pp. 89–98. Association for Computing Machinery (2006)

21.

Halpern, J., Teague, V.: Rational secret sharing and multiparty computation: extended abstract. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2004, pp. 623–632. Association for Computing Machinery (2004)

22.

Harn, L., Lin, C., Li, Y.: Fair secret reconstruction in (t, n) secret sharing. J. Inf. Secur. Appl. 23, 1–7 (2015)

23.

Katz, J.: Bridging game theory and cryptography: recent results and future directions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 251–272. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_15CrossRefMATH

24.

Knapp, J., Quaglia, E.A.: Fair and sound secret sharing from homomorphic time-lock puzzles. Cryptology ePrint Archive, Report 2020/1078 (2020). https://eprint.iacr.org/2020/1078

25.

Kol, G., Naor, M.: Cryptography and game theory: designing protocols for exchanging information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320–339. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_18CrossRefMATH

26.

Kol, G., Naor, M.: Games for exchanging information. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 423–432. Association for Computing Machinery (2008)

27.

Krawczyk, H.: Secret sharing made short. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 136–146. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_12CrossRef

28.

Laih, C.-S., Lee, Y.-C.: V-fairness (t, n) secret sharing scheme. IEE Proc. Comput. Digit. Tech. 144(4), 245–248 (1997)CrossRef

29.

Lin, H.-Y., Harn, L.: Fair reconstruction of a secret. Inf. Process. Lett. 55(1), 45–47 (1995)CrossRef

30.

Lysyanskaya, A., Segal, A.: Rational secret sharing with side information in point-to-point networks via time-delayed encryption. IACR Cryptology ePrint Archive 2010, 540 (2010)

31.

Malavolta, G., Thyagarajan, S.A.K.: Homomorphic time-lock puzzles and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22CrossRef

32.

May, T.C.: Time-release crypto. In: Manuscript (1993)

33.

Nash, J.: Non-cooperative games. Ann. Math. 286–295 (1951)

34.

Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9CrossRef

35.

Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical Report MIT/LCS/TR-684 (1996)

36.

Rosenthal, D.: On the cost distribution of a memory bound function. arXiv preprint cs/0311005 (2003)

37.

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)MathSciNetCrossRef

38.

Tian, Y., Ma, J., Peng, C., Zhu, J.: Secret sharing scheme with fairness. In: 10th International Conference on Trust, Security and Privacy in Computing and Communications, pp. 494–500. IEEE (2011)

39.

Tompa, M., Woll, H.: How to share a secret with cheaters. J. Cryptol. 1(3), 133–138 (1988). https://doi.org/10.1007/BF02252871MathSciNetCrossRefMATH

40.

Wang, H., Lam, K.Y., Xiao, G.-Z., Zhao, H.: On multiplicative secret sharing schemes. In: Dawson, E.P., Clark, A., Boyd, C. (eds.) ACISP 2000. LNCS, vol. 1841, pp. 342–351. Springer, Heidelberg (2000). https://doi.org/10.1007/10718964_28CrossRef

41.

Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_4CrossRef

Title: Fair and Sound Secret Sharing from Homomorphic Time-Lock Puzzles
Authors: Jodie Knapp
Elizabeth A. Quaglia
Publisher: Springer International Publishing
Book: Provable and Practical Security
Print ISBN: 978-3-030-62575-7

Electronic ISBN: 978-3-030-62576-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62576-4_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner