nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

On the Local Leakage Resilience of Linear Secret Sharing Schemes

verfasst von : Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, Tal Rabin

Erschienen in: Advances in Cryptology – CRYPTO 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider the following basic question: to what extent are standard secret sharing schemes and protocols for secure multiparty computation that build on them resilient to leakage? We focus on a simple local leakage model, where the adversary can apply an arbitrary function of a bounded output length to the secret state of each party, but cannot otherwise learn joint information about the states.

We show that additive secret sharing schemes and high-threshold instances of Shamir’s secret sharing scheme are secure under local leakage attacks when the underlying field is of a large prime order and the number of parties is sufficiently large. This should be contrasted with the fact that any linear secret sharing scheme over a small characteristic field is clearly insecure under local leakage attacks, regardless of the number of parties. Our results are obtained via tools from Fourier analysis and additive combinatorics.

We present two types of applications of the above results and techniques. As a positive application, we show that the “GMW protocol” for honest-but-curious parties, when implemented using shared products of random field elements (so-called “Beaver Triples”), is resilient in the local leakage model for sufficiently many parties and over certain fields. This holds even when the adversary has full access to a constant fraction of the views. As a negative application, we rule out multi-party variants of the share conversion scheme used in the 2-party homomorphic secret sharing scheme of Boyle et al. (Crypto 2016).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Non-malleable Secret Sharing for General Access Structures

Nächstes Kapitel Threshold Cryptosystems from Threshold Fully Homomorphic Encryption

In the whole paper, a (n, t)-Shamir secret sharing scheme or Shamir secret sharing scheme with thereshold t uses polynomials of degree t, so that the secret cannot be recovered from a collusion of up to t parties. The secret can be recovered from \(t+1\) parties.

This can be done by locally adding shares of a random \( (n,c'n) \)-Shamir share of 0 to the given (n, cn) - Shamir shares.

A Beaver triple consists of (a, b, ab) where a, b are randomly chosen field elements.

To recall, in the quotient group

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-96884-1_18/471488_1_En_18_IEq104_HTML.gif

, the elements are the cosets \( A_0, A_1 \). The sum of two cosets is the coset formed by the sum of elements of the first cosets with elements of the second coset. Because of the structure, \( A_0 + A_0 = A_0 \), \( A_0 + A_1 = A_1 \) and so on.

A relation is trivial if no matter what secret is shared, a constant output by the conversion scheme would satisfy correctness. Or put another way, in a non-trivial relation R, there exist \( s_0 \) and \( s_1 \) such that \( s_0 \) has to be mapped to 0 and \( s_1 \) has to be mapped to 1 in the relation R.

We consider more general case in the full version which also tolerates a higher error probability of 1 / 6.

Both complexity measures do not assign complexity to all possible linear forms. To give an example, the linear form \(( L_1(x) = x, L_2(x) = x+2 )\), which corresponds to the twin primes conjecture, is not assigned a complexity value and the twin primes conjecture is still open.

\( z_1 \circ z_2 = x_1x_2 + y_1y_2 \) where \( z_b = x_b + i\cdot y_b \) is the dot product of \( z_1 \) and \( z_2 \). Equivalently, \( z_1 \circ z_2 = |z_1| |z_2| \cos \theta \) where \( \theta \) is the angle between \( z_1 \) and \( z_2 \).

Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous hardcore bits and cryptography against memory attacks. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 474–495. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_28CrossRefMATH

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: CCS (2016)

Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34CrossRef

Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share conversion and private information retrieval. In: CCC (2012)

Ben-Or, M., Coppersmith, D., Luby, M., Rubinfeld, R.: Non-abelian homomorphism testing, and distributions close to their self-convolutions. Random Struct. Algorithms (2008)

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC (1988)

Bitansky, N., Dachman-Soled, D., Lin, H.: Leakage-tolerant computation with input-independent preprocessing. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 146–163. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_9CrossRef

Blakley, G.: Safeguarding cryptographic keys. In: AFIPS National Computer Conference (1979)

Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 549–595 (1993)MathSciNetCrossRef

10.

Bogdanov, A., Ishai, Y., Viola, E., Williamson, C.: Bounded indistinguishability and the complexity of recovering secrets. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 593–618. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_21CrossRef

11.

Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 509–539. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_19CrossRef

12.

Boyle, E., Goldwasser, S., Kalai, Y.T.: Leakage-resilient coin tossing. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 181–196. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24100-0_16CrossRef

13.

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

14.

Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_19CrossRef

15.

Dachman-Soled, D., Liu, F., Zhou, H.: Leakage-resilient circuits revisited – optimal number of computing components without leak-free hardware. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 131–158. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_5CrossRef

16.

Damgård, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_38CrossRef

17.

Dodis, Y., Halevi, S., Rothblum, R.D., Wichs, D.: Spooky encryption and its applications. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 93–122. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_4CrossRef

18.

Duc, A., Dziembowski, S., Faust, S.: Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 423–440. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_24CrossRef

19.

Dziembowski, S., Faust, S.: Leakage-resilient circuits without computational assumptions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 230–247. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_13CrossRef

20.

Dziembowski, S., Pietrzak, K.: Intrusion-resilient secret sharing. In: FOCS (2007)

21.

Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: FOCS (2008)

22.

Faust, S., Rabin, T., Reyzin, L., Tromer, E., Vaikuntanathan, V.: Protecting circuits from leakage: the computationally-bounded and noisy cases. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 135–156. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_7CrossRef

23.

Fazio, N., Gennaro, R., Jafarikhah, T., Skeith III, W.E.: Homomorphic secret sharing from paillier encryption. In: Okamoto, T., Yu, Y., Au, M.H., Li, Y. (eds.) ProvSec 2017. LNCS, vol. 10592, pp. 381–399. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68637-0_23CrossRef

24.

Genkin, D., Ishai, Y., Weiss, M.: How to construct a leakage-resilient (stateless) trusted party. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 209–244. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_7CrossRef

25.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC 1987 (1987)

26.

Goldwasser, S., Rothblum, G.N.: How to compute in the presence of leakage. SICOMP (2015). https://doi.org/10.1137/130931461

27.

Gowers, W.T.: A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11, 465–588 (2001)MathSciNetCrossRef

28.

Gowers, W.T., Wolf, J.: The true complexity of a system of linear equations. Proc. London Math. Soc. 100, 155–176 (2010)MathSciNetCrossRef

29.

Gowers, W.T., Wolf, J.: Linear forms and higher-degree uniformity for functions on \( \mathbb{F}_n^p \). Geom. Funct. Anal. 21, 36–39 (2011)MathSciNetCrossRef

30.

Gowers, W.T., Wolf, J.: Linear forms and quadratic uniformity for functions on \( \mathbb{F}_n^p \). Mathematika 57, 215–237 (2011)MathSciNetCrossRef

31.

Goyal, V., Ishai, Y., Maji, H.K., Sahai, A., Sherstov, A.A.: Bounded-communication leakage resilience via parity-resilient circuits. In: FOCS (2016)

32.

Green, B.: Montréal notes on quadratic Fourier analysis. Add. Comb. 43, 69–102 (2007)MATH

33.

Green, B., Tao, T.: Linear equations in primes. Ann. Math. 171, 1753–1850 (2010)MathSciNetCrossRef

34.

Guruswami, V., Wootters, M.: Repairing reed-solomon codes. IEEE Trans. Inf. Theory 63, 5684–5698 (2017)MathSciNetMATH

35.

Ishai, Y., Sahai, A., Wagner, D.A.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_27CrossRef

36.

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: CCS (2016)

37.

Kiltz, E., Pietrzak, K.: Leakage resilient elgamal encryption. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 595–612. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_34CrossRef

38.

Kocher, P., Genkin, D., Gruss, D., Haas, W., Hamburg, M., Lipp, M., Mangard, S., Prescher, T., Schwarz, M., Yarom, Y.: Spectre attacks: exploiting speculative execution. ArXiv e-prints, January 2018

39.

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9CrossRef

40.

Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25CrossRef

41.

Lipp, M., Schwarz, M., Gruss, D., Prescher, T., Haas, W., Mangard, S., Kocher, P., Genkin, D., Yarom, Y., Hamburg, M.: Meltdown. ArXiv e-prints

42.

Micali, S., Reyzin, L.: Physically observable cryptography. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 278–296. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_16CrossRefMATH

43.

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

44.

Tao, T., Vu, V.H.: Additive Combinatorics. Cambridge University Press, Cambridge (2006)CrossRef

45.

Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986)

Titel: On the Local Leakage Resilience of Linear Secret Sharing Schemes
verfasst von: Fabrice Benhamouda
Akshay Degwekar
Yuval Ishai
Tal Rabin
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2018
Print ISBN: 978-3-319-96883-4

Electronic ISBN: 978-3-319-96884-1

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-96884-1_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner