Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden.
powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden.
powered by
Abstract
Correlated private randomness, or correlation in short, is a fundamental cryptographic resource that helps parties compute securely over their private data. An offline preprocessing step, which is independent of the eventual secure computation, generates correlated secret shares for the parties and the parties use these shares during the final secure computation step. However, these secret shares are vulnerable to leakage attacks.
Inspired by the quintessential problem of privacy amplification, Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS 2009) introduced the concept of correlation extractors. Correlation extractors are interactive protocols that take leaky correlations as input and produce secure independent copies of oblivious transfer (OT), the building blocks of secure computation protocols. Although their initial feasibility result is resilient to linear leakage and produces a linear number of “fresh” OTs, the constants involved are minuscule. The output of this correlation extractor can be used to perform only small secure computation tasks, because the number of OTs needed to evaluate a functionality securely is roughly proportional to its circuit size. Recently, Gupta, Ishai, Maji, and Sahai (CRYPTO 2015) constructed an extractor that is resilient to 1/4 fractional leakage and has near-linear production rate. They also constructed an extractor from a large correlation that has 1/2 fractional resilience but produces only one OT, which does not suffice to compute even constant size functionalities securely.
In this paper, we show the existence of a correlation that produces n-bit shares for the parties and allows the extraction of \(n^{1-o(1)}\) secure OTs, despite n/2 bits of leakage. The key technical idea is to embed several multiplications over a field into one multiplication over an extension field. The packing efficiency of this embedding directly translates into the production rate of our correlation extractor. Our work establishes a connection between this problem and a rich vein of research in additive combinatorics on constructing dense sets of integers that are free of arithmetic progressions, a.k.a. 3-free sets. We introduce a new combinatorial problem that suffices for our multiplication embedding, and produces concrete embeddings that beat the efficiency of the embeddings inspired by the reduction to 3-free sets.
Finally, the paper introduces a graph-theoretic measure to upper-bound the leakage resilience of correlations, namely the simple partition number. This measure is similar in spirit to graph covering problems like the biclique partition number. If the simple partition number of a correlation is \(2^\lambda \), then it is impossible to extract even one OT if parties can perform \(\lambda \)-bits of leakage. We compute tight estimates of the simple partition number of several correlations that are relevant to this paper, and, in particular, show that our extractor and the extractor for the large correlation by Gupta et al. have optimal leakage resilience and (qualitatively) optimal simulation error.
Anzeige
Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.
The actual inner-product correlation is defined slightly differently. Parties get shares \((x_0,x_1,\cdots ,x_n)\) and \((y_0,y_1,\cdots ,y_n)\) such that \(x_0+y_0 = \sum _{i=1}^n x_iy_i\). That is, \(x_0\) and \(y_0\) are additive secret shares of the inner product of \((x_1,\cdots ,x_n)\) and \((y_1,\cdots ,y_n)\). But for intuition, it suffices to consider the correlation where the secret shares of the parties are orthogonal vectors instead.
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.
The problem of characterizing correlations whose single sample suffice to construct \( \mathsf {OT} \) is a fascinating open problem that lies beyond the purview of this study.
This definition naturally generalizes to weighted graphs. Suppose \(p(r_A,r_B)\) represents the probability of jointly sampling \((r_A,r_B)\) from the correlation \((R_A,R_B)\). Then a simple graph has \(p(r_A,r_B)=p(r_A)\cdot p(r_B)\), for every \((r_A,r_B)\) edge with positive weight.