Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Topology-Hiding Computation Beyond Semi-Honest Adversaries Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Secure Computation Using Leaky Correlations (Asymptotically Optimal Constructions)

verfasst von : Alexander R. Block, Divya Gupta, Hemanta K. Maji, Hai H. Nguyen

Erschienen in: Theory of Cryptography

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by adversarial parties, which can compromise the security of the secure computation protocol. The objective, therefore, is to preserve the security of the honest party despite the leakage performed by the adversary on her share.
Prior solutions, starting with n-bit leaky shares, either used 4 messages or enabled the secure computation of only sub-linear size circuits. Our work presents the first 2-message secure computation protocol for 2-party functionalities that have \(\varTheta (n)\) circuit-size despite \(\varTheta (n)\)-bits of leakage, a qualitatively optimal result. We compose a suitable 2-message secure computation protocol in parallel with our new 2-message correlation extractor. Correlation extractors, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS–2009) as a natural generalization of privacy amplification and randomness extraction, recover “fresh” correlations from the leaky ones, which are subsequently used by other cryptographic protocols. We construct the first 2-message correlation extractor that produces \(\varTheta (n)\)-bit fresh correlations even after \(\varTheta (n)\)-bit leakage.
Our principal technical contribution, which is of potential independent interest, is the construction of a family of multiplication-friendly linear secret sharing schemes that is simultaneously a family of small-bias distributions. We construct this family by randomly “twisting then permuting” appropriate Algebraic Geometry codes over constant-size fields.

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 Topology-Hiding Computation Beyond Semi-Honest Adversaries
Nächstes Kapitel Fine-Grained Secure Computation
Fußnoten
1
A semi-honest adversary follows the prescribed protocol but is curious to find additional information.
 
2
Message complexity refers to the number of messages exchanged between Alice and Bob.
 
3
Each sample of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-03810-6_2/476307_1_En_2_IEq19_HTML.gif gives two bits to each party; \((x_0, x_1)\) to the first party and \((b,x_b)\) to the second party. Therefore each party receives m-bit shares.
 
4
That is, the functionality samples secret shares \((r_A,r_B)\) according to the correlation \((R_A,R_B)\). The adversarial party sends a t-bit leakage function \({\mathcal L}\) to the functionality and receives the leakage \({\mathcal L} (r_A,r_B)\) from the functionality. The functionality sends \(r_A\) to Alice and \(r_B\) to Bob. Note that the adversary does not need to know its secret share to construct the leakage function because the leakage function gets the secret shares of both parties as input.
 
5
Once the parameters of the AG code are fixed, it is a one-time cost to construct its generator matrix.
 
6
Even optimistic estimates of the parameters m/n and t/n for the IKOS construction are in the order of \(10^{-6}\).
 
7
A sample \((r_A, r_B)\) is an erroneous sample if it is not in the support of the distribution \((R_A,R_B)\), i.e., it is an incorrect sample. An error-tolerant combiner is a combiner that is secure even if a few of the input samples are erroneous.
 
8
The size of the fields increases with n, the size of the secret shares produced by the preprocessing step.
 
9
Consider a linear code \(C\subseteq {\mathbb F} ^s\). Let \(c=(c_1,\cdots ,c_s)\) and \(c'=(c'_1,\cdots ,c'_s)\) be two codewords in the code C. We define \(c*c' = (c_1c'_1,\cdots ,c_sc'_s)\in {\mathbb F} ^s\). The Schur-product \(C* C\) is defined to be the linear span of all \(c*c'\) such that \(c,c'\in C\).
 
10
In the literature there are multiple definitions for the equivalence of two linear codes. In particular, one such notion (cf., [38]), states that two codes are equivalent to each other if one can be twisted-and-permuted into the other code. For clarity, we have chosen to explicitly define the “twist then permute” operation.
 
11
The weight of \(S\in {\mathbb F} ^s\) is defined as the number of non-zero elements in S.
 
12
Recall that the inner-product correlation \(\mathsf {IP} \big ({{\mathbb K} ^s}\big ) \) over finite field \({\mathbb K} \) samples random \(r_A = (u_1,\cdots ,u_s) \in {\mathbb K} ^s\) and \(r_B = (v_1,\cdots ,v_s)\in {\mathbb K} ^s\) such that \(u_1v_1 + \cdots + u_sv_s = 0\).
 
Literatur
1.
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. In: 31st FOCS, pp. 544–553. IEEE Computer Society Press, October 1990
2.
3.
4.
5.
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC\(^0\). In: 45th FOCS, pp. 166–175. IEEE Computer Society Press, October 2004
6.
7.
Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: a system for secure multi-party computation. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 2008, pp. 257–266. ACM Press, October 2008
8.
9.
10.
Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology 13(1), 143–202 (2000)MathSciNetCrossRef
11.
12.
13.
14.
Chudnovsky, D.V., Chudnovsky, G.V.: Algebraic complexities and algebraic curves over finite fields. Proc. Natl. Acad. Sci. 84(7), 1739–1743 (1987)MathSciNetCrossRef
15.
16.
17.
Dodis, Y., Smith, A.: Correcting errors without leaking partial information. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 654–663. ACM Press, May 2005
18.
Döttling, N., Ghosh, S., Nielsen, J.B., Nilges, T., Trifiletti, R.: TinyOLE: Efficient actively secure two-party computation from oblivious linear function evaluation. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 17, pp. 2263–2276. ACM Press, October/November 2017
19.
Garcia, A., Stichtenoth, H.: On the asymptotic behaviour of some towers of function fields over finite fields. J. Number Theory 61(2), 248–273 (1996)MathSciNetCrossRef
20.
21.
Goppa, V.D.: Codes on algebraic curves. In: Soviet Math. Dokl., pp. 170–172 (1981)
22.
23.
24.
25.
Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Ruiz, F.T., Bueno, R.M., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002). https://​doi.​org/​10.​1007/​3-540-45465-9_​22CrossRef
26.
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Extracting correlations. In: 50th FOCS, pp. 261–270. IEEE Computer Society Press, October 2009
27.
Ishai, Y., Maji, H.K., Sahai, A., Wullschleger, J.: Single-use OT combiners with near-optimal resilience. In: 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, 29 June–4 July 2014, pp. 1544–1548 (2014)
28.
29.
Keller, M., Orsini, E., Scholl, P.: MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 830–842. ACM Press, October 2016
30.
Kilian, J.: A general completeness theorem for two-party games. In: 23rd ACM STOC, pp. 553–560. ACM Press, May 1991
31.
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: Proceedings of the 13th USENIX Security Symposium, 9–13 August 2004, San Diego, pp. 287–302 (2004)
32.
Massey, J.L.: Some applications of coding theory in cryptography. In: Codes and Ciphers: Cryptography and Coding IV, pp. 33–47 (1995)
33.
34.
35.
Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. In: 22nd ACM STOC, pp. 213–223. ACM Press, May 1990
36.
37.
38.
Pless, V.: Introduction to the Theory of Error-Correcting Codes, vol. 48. Wiley (2011)
39.
40.
Rao, A.: An exposition of bourgain’s 2-source extractor. ECCCTR: Electronic Colloquium on Computational Complexity Technical reports (2007)
41.
Vladut, S., Nogin, D., Tsfasman, M.: Algebraic Geometric Codes: Basic Notions. American Mathematical Society, Boston (2007)MATH
42.
Metadaten
Titel
Secure Computation Using Leaky Correlations (Asymptotically Optimal Constructions)
verfasst von
Alexander R. Block
Divya Gupta
Hemanta K. Maji
Hai H. Nguyen
Copyright-Jahr
2018
Buch
Theory of Cryptography

Print ISBN: 978-3-030-03809-0

Electronic ISBN: 978-3-030-03810-6

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-030-03810-6_2

Premium Partner

    Bildnachweise