Welcome to the resource topic for 2024/316
Title:
Threshold Garbled Circuits with Low Overhead
Authors: Schuyler Rosefield, abhi shelat, LaKyah Tyner
Abstract:The folklore approach to designing a threshold variant of symmetric
cryptographic algorithms involves applying generic MPC methods to se-
cret sharing techniques: the MPC first combines participant input shares
using the secret sharing scheme, and then evaluates the cryptographic
function on the reconstructed key. Hardening this secure against n − 1
malicious parties requires some mechanism to ensure input consistency,
e.g., adding MACs to inputs, which consequently, increases the number
of inputs and gates to the MPC. In many cases, this extra overhead is
substantially more than the underlying cost of evaluating the symmetric
cryptographic algorithm.
We present a scheme that can convert any suitable maliciously secure
dishonest majority boolean-circuit FMPC into a threshold scheme Fthresh
with almost no overhead. Specifically, we present an SUC-secure scheme
that allows for reactive threshold t-of-n boolean circuit evaluation amongst
a group of n parties P , for any t ≤ n, against a malicious adversary that
corrupts any number of parties less than the threshold t. Moreover, mul-
tiple circuits can be evaluated sequentially with the secret-shared authen-
ticated outputs of a circuit to be used subsequently as inputs for a new
circuit by any S ⊆ P of size |S| ≥ t.
Building upon the works of Wang et al, Hazay et al, and Yang et al,
[WRK17, HSSV17, YWZ20] for dishonest majority FMPC, our key insight
is to create threshold versions of the “authenticated bits” used to han-
dle input in these recent n-party garbled circuits protocols. The resulting
design incurs a small overhead to produce the reusable “threshold authen-
ticated bits” during preprocessing, and adds no extra communication to
evaluate with the authenticated input during the online phase.
Using our methods, thresholdizing a boolean circuit has essentially no
performance overhead. For example, to compute HMAC, a full Setup+Eval
execution of the (n − 2)-out-of-n thresholdized version is approximately
4% more expensive than the state-of-the-art n-party MPC. In contrast,
using the folklore method is approximately 100% more expensive. This is
especially true for small circuits such as AES which has 6800 gates and
thus incurs the most overhead for thresholdizing. Simply considering the
online Eval cost, our approach can evaluate AES blocks at 2.3/s with 16 parties, exceeding the baseline MPC cost without preprocessing, and sur-
passing the folklore method that only achieves .33/s blocks. Ultimately,
this result makes threshold boolean circuit MPC as feasible as any MPC
application.
ePrint: https://eprint.iacr.org/2024/316
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .