Leakage-Resilient Secret Sharing Against Colluding Parties
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)Leakage-Resilient Secret Sharing Against Colluding Parties Ashutosh Kumar, Raghu Meka and Amit SahaiDepartment of Computer ScienceUniversity of California, Los AngelesLos Angeles, USAEmail: a@ashutoshk.com, raghum@cs.ucla.edu, sahai@cs.ucla.eduschemes that allow any set of t parties, out of n parties total,to reconstruct the secret. Furthermore, crucially, the secret ishidden given less than t shares. For the sake of exposition, inthis introduction we will focus only on t-out-of-n schemes,whereas our results will also apply to more general accessstructures (see Section II for formal definitions).Secret sharing schemes, while originally envisioned withonly the goal of secrecy formulated above, have beenstrengthened in various ways, such as by adding verifiability[4], robustness [5], functionality [6] or non-malleability [7].In this work, our focus is on a stronger secrecy goal—leakage-resilience.Leakage-resilience has a long history in cryptography. Intuitively, the goal of leakage-resilience is to make cryptosystems robust to adversaries who learn additional “leaked”information (via say passive side-channel attacks). Motivatedby the fascinating goal of securing circuit computationagainst an adversary who probes the values of internalwires of the cirucuit, Ishai, Sahai, and Wagner [8] initiatedthe study of private circuits. Micali and Reyzin [9] putforward a very general model for such side-channel attacks.Subsequently, a lot of primitives in cryptography were madeleakage-resilient [7], [10]–[19]. More detailed history can befound in the recent survey of Kalai and Reyzin [20].Leakage-Resilient Secret Sharing.: Focusing now onleakage resilience in the context of secret sharing, oneof the first works to study a question in this vein wasDziembowski and Pietrzak [10] who developed n-out-ofn intrusion-resilient secret sharing schemes that ensure thatthe adversary does not learn anything about the secret evenafter getting access to bounded information from each ofthe shares and supported limited adaptivity 1 ; in addition,they also observed that their results implied certain roundcomplexity separations in communication complexity. Davı̀,Dziembowski and Venturi [14] used two-source extractorsto construct the first 2-out-of-2 secret sharing scheme thatstatistically hides the secret even after an adaptive adversaryexecutes an arbitrary leakage protocol on the two shares withbounded communication.Abstract—In this work, we consider the natural goal ofdesigning secret sharing schemes that ensure security againstan adversary who may learn some “leaked” information aboutall the shares. We say that a secret sharing scheme is pparty leakage-resilient, if the secret remains statistically hiddeneven after a computationally unbounded adversary learnsa bounded amount of leakage, where each bit of leakageadaptively and jointly depends on the shares of an adaptivelychosen subset of p parties. Existing multi-party secret sharingschemes (Dziembowski and Pietrzak FOCS 07), (Goyal andKumar STOC 18) and (Benhamouda, Degwekar, Ishai andRabin CRYPTO 18) have focused on handling non-adaptiveand individual leakage for (limited special cases of) thresholdsecret sharing schemes. We give an unconditional compiler that transforms anysecret sharing scheme on n parties into a p-party leakageresilient one for p upto O(log n). This yields the firstmulti-party secret sharing schemes that are secure againstadaptive or joint leakage. As a natural extension, we initiate the study of leakageresilient non-malleable secret sharing. We empower theadversary to adaptively leak from each of the shares andthen use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakageresilient schemes, we compile any secret sharing schemeinto a non-malleable one ensuring that any such tampering either preserves the secret or completely ‘destroys’it. This improves upon the non-malleable secret sharingscheme of (Goyal and Kumar CRYPTO 18) where noleakage was permitted. Leakage-resilient non-malleablecodes can be seen as 2-out-of-2 schemes satisfying ourguarantee and have already found many applications incryptography. Our constructions rely on a clean connection we draw tocommunication complexity in the well-studied numberon-forehead (NOF) model and rely on functions that havestrong communication-complexity lower bounds in theNOF model (in a black-box way). We get efficient pparty leakage-resilient schemes for p upto O(log n) as ourshare sizes have exponential dependence on p. We observethat improving this exponential dependence, even forsimultaneous, non-adaptive leakage, will lead to progresson longstanding open problems in complexity theory.I. I NTRODUCTIONBlakley [2] and Shamir [3] initiated the study of secretsharing schemes by constructing threshold secret sharing1 The leakage could be in k rounds but had to avoid certain patterns asdictated by their reconstruction function which required k 1 rounds ofalternating extraction. Aprior version appeared as “Leakage-Resilient Secret Sharing” [1]containing the same set of results.2575-8454/19/ 31.00 2019 IEEEDOI 10.1109/FOCS.2019.00045636
A natural first question is whether existing secret sharingschemes such as Shamir’s secret sharing scheme could itselfbe leakage-resilient. Surprisingly, it follows from the workof Guruswami and Wootters [21] (motivated by codingtheoretic questions) that one can learn the secret underShamir’s scheme for most thresholds even with one-bitleakage from each share individually (i.e., the leaked bit foreach party only depends on that party’s share).Recently, Goyal and Kumar [7], [22] defined and constructed an efficient 2-out-of-n secret sharing scheme thathides the secret even when a non-adaptive adversary learnssome bounded amount of information from each of the nshares individually. Concurrently, Benhamouda, Degwekar,Ishai and Rabin [19] showed that Shamir’s t-out-of-n secretsharing scheme for large values of t n o(log n)is leakage-resilient against a non-adaptive adversary whoindependently learns some bounded amount of informationfrom each share individually.Our Work: Adaptive and Joint Leakage.: Therefore thefocus of recent literature on leakage-resilient secret sharingis on handling individual and non-adaptive leakage for(limited special cases of) threshold secret sharing schemes.In this work, we aim to develop a more comprehensivetheory of leakage resilient secret sharing. To this end,our main focus will be on handling joint leakage wherean adaptive adversary can learn information depending onmultiple shares at once. For example, in our model, wewould allow the adversary to adaptively specify an arbitraryleakage function f outputting a bounded number of bits, andobtain the output f (share1 , share2 ), where share1 is theshare given to Party 1, and share2 is the share given toParty 2. Furthermore, we consider secret sharing schemesthat support general access structures.As an important special case consider, for any constantst n, constructing a t-out-of-n secret sharing scheme,which should remain secure even when a non-adaptiveadversary can obtain joint leakages {fi1 ,i2 ,.,it 1 (sharei1 ,. . . , shareit 1 )}i1 ,.,it 1 [n] . Before our work, this problemwas open even for t n 3. We resolve this problem forall constants t, and more! We now elaborate.Modeling adaptive joint leakage.: In particular, wemodel this by viewing leakage as (an adversary) runninga communication protocol, where in each round, any adaptively chosen group of at most p parties (out of a total of n)get together and compute a message based on all messagesin the transcript so far, and the set of shares known to all theparties in the group. This process continues until a limit ofat most μ bits have been communicated (or leaked). We callsuch protocols bounded collusion protocols (BCPs), and wewill call the set of protocols obeying the restrictions above(p, n, μ)-BCP or p-party collusion protocols when n, μ arenot too important.The above definition is motivated by the fundamentalNumber-on-Forehead (NOF) model [23], [24] from com-munication complexity which in its original form studiesthe following problem. There are n parties with each partyseeing all inputs but their own (number written on forehead)and they can communicate by writing on a public blackboard. Their goal is to compute a function of their inputswhile minimizing the total amount of communication. Thisis a very versatile model with many beautiful connectionsto circuit complexity among others (cf. book of [25]).Note that p-party collusion protocols for p n 1correspond exactly to NOF protocols. In a similar vein1-party collusion protocols correspond to the well-studiednumber-in-hand (NIH) model [26]–[28] (a more straightforward extension of two-party communication to multi-partycommunication).Bounded collusion protocols also seem particularly wellsuited to secret sharing as for t-out-of-n threshold secretsharing schemes, leakage-resilience is not possible if t ormore parties can collude as they can just compute the secret.Thus, for the case of (t, n)-threshold schemes, resilienceagainst (t 1)-party collusion protocols is the best one couldhope for.Even more generally, our work is guided by the followingquestion: Given a class of communication protocols P, canwe design P-resilient secret sharing schemes in that thesecret is statistically hidden from an adversary who seesthe entire transcript of a protocol from P executed on theshares?The above discussion leads us to the main notion ofleakage-resilient secret sharing schemes that we study (seeSection II for a more formal definition):Definition 1. (p-party leakage resilience) Let (Share, Rec)be a t-out-of-n secret sharing scheme that shares k bitsecrets into n shares. Let μ be any bound on allowed leakageand 1 p t be any collusion bound. We say that (Share,Rec) is (p, t, n)-leakage-resilient secret sharing scheme(or (p, t, n)-LRSS in short) if for any leakage protocol Leakin (p, n, μ)-BCP, and for every pair of secrets a, b {0, 1}k ,we have Leak(Share(a)) Leak(Share(b)).2We remark that even 3-out-of-3 secret sharing schemesthat are resilient against 2-party collusion protocols protocolswere not known before our work. For a more detailedcomparison with existing works, see the related work sectionbelow.A. Leakage-Resilient Non-Malleable Secret SharingJust as leakage resilience was introduced to combat passive side-channel attacks, an important development in cryptography has been non-malleability introduced in the seminalwork of Dolev, Dwork and Naor [29]. Intuitively, the goalhere is to protect cryptosystems from adversaries who may2 Here A B means A, B are -close in statistical distance; see Section II for more details.637
even tamper with the data (e.g., physical tampering). Thesewere recently introduced in the context of non-malleablecodes and extractors [16], [30]–[38], but have since found avast array of applications (e.g., [39]) and many cryptographicprimitives — including secret sharing as in the recent workof Goyal and Kumar [7] — have been made non-malleable(in various precise senses)).Notice, however, that a leakage attack might be easier toperform than a tampering one in practice. This raises thechallenge of making cryptosystems both leakage resilientand non-malleable3 and we address this question for secretsharing schemes.Following the definitions of [16], [17] (who studyleakage-resilient and non-malleable 2-out-of-2 secret sharingschemes) and [7], [22] (who study non-malleability for moregeneral access structures), we empower the adversary toadaptively leak some bounded amount of information fromall the shares and in addition use this leakage to arbitrarilytamper with each of the shares. We define a secret sharingscheme to be leakage-resilient non-malleable (LR NMSS) ifthe secret reconstructed from the tampered shares is eitherthe original one or a completely “unrelated” one.The well-studied non-malleable codes in two split-statemodel [16], [33]–[38] correspond to the special case of2-out-of-2 NMSSs (see [17] for a proof). [22] give anefficient compiler that converts any standard secret sharingscheme into one that ensures non-malleability against anadversary who tampers with each of the shares arbitrarilyand independently. [7] construct t-out-of-n schemes againsta stronger adversary who chooses any t shares, partitionsthem into two subsets of different cardinality and jointlytampers all the shares within each subset independently.However, these constructions do not consider a leakingadversary, and cannot be made to handle leakage from morethan t shares.The special case of 2-out-of-2 LR NMSS has alreadyreceived considerable attention in the literature under thename of two split-state leakage-resilient non-malleablecodes. Liu and Lysyanskaya [16] defined and constructedsuch codes against computationally bounded adversaries.Aggarwal, Dziembowski, Kazana, and Obremski [17] obtained the first information-theoretic construction of 2-outof-2 LR NMSS. Non-malleable extractors based 2-out-of2 LR NMSS were given by Chattopadhyay and Li [40]and [7]. Goyal et al. [41] and Ostrovsky et al. [42] haveused such leakage-resilient codes to obtain constructions of‘concurrent’ non-malleable commitments and ‘continuous’non-malleable codes respectively.some limitations of current techniques towards achievingthe goals we seek. As mentioned already, classical secretsharing schemes such as Shamir’s secret sharing scheme arenot leakage-resilient (even against simultaneous individualleakage). While [19] overcome this using fields of largecharacteristic for t n o(log n), it is not clear how toextend their results to handle joint or adaptive leakage.Can we use extractors to get 2-party leakage-resilientschemes?: One of the main challenges we address isin handling joint leakage. Indeed, most existing (1, 2, 2)LRSSs are based on two source extractors [7], [10], [14],[17]. These constructions rely on the following simple butpowerful observation: if two shares are independent, thenconditioning on the entire transcript of a 1-party collusionprotocol preserves the conditional independence betweenthem, and therefore independent source extractors can beinvoked for proving leakage-resilience. Unfortunately thisidea has severe problems for 2-party collusion protocolsas among other things, conditioning on a 2-party collusionprotocol will break the independence of the shares.t-out-of-n schemes with leakage from t shares.:Any t-out-of-n scheme is by definition leakage-resilientagainst complete leakage of any t 1 shares. While thet-out-of-n NMSS scheme of Goyal and Kumar [7] doesnot consider leakage, with some work their proof can begeneralized to allow leakage from at most t shares (thatis the adversary gets no information about at least n tshares). Unfortunately, their proof cannot be generalized toeither achieve non-adaptive 1-party leakage-resilient schemefor n t or achieve non-adaptive 2-party leakage-resilientscheme for t n 3.Can we extend the LRSS of Goyal and Kumar?: [7]constructed 2-out-of-n schemes that are resilient againstnon-adaptive individual leakage. With a little work, theirmethods can be extended to yield efficient c-out-of-nschemes that are similarly resilient against non-adaptiveindividual leakage for any constant c. However, apart fromnot being able to handle super-constant thresholds, they arebased on extractors and thus cannot be shown to be 2-partyleakage-resilient.C. Our ResultsLeakage-resilient secret sharing.: As our main result,we give a generic compiler that transforms any secret sharingscheme into a p-party leakage-resilient one.Theorem 1 (Informal). For any collusion bound p 1, anyaccess structure A supported on n 1 parties such thateach authorized set has more than p parties, suppose thereis a perfect (resp. statistical, computational) secret sharingscheme realizing access structure A that shares k bit secretsinto n shares each of length bits. Then for any leakagebound μ, any error 0, there is a perfect (resp. statistical,computational) secret sharing scheme realizing A that isB. Previous WorkBefore we describe our results and techniques in detail,let us first consider previous related work, and discuss3 Note that neither one implies the other and there are systems that satisfyone but not the other.638
Using the computational scheme of Yao (mentioned in[49]), we get:leakage resilient against (p, n, μ)-BCP. The resulting schemeshares secrets of k bits into n shares each of length k(log n)(μ log(1/ ))2O(p) . 4Corollary 4 (Informal). If one-way functions exist, thenfor any access structure that is computable by monotoneboolean circuits of polynomial size for which authorized setshave cardinality greater than p O(log(n)), there exists anefficient computational secret sharing scheme that realizesthis access structure and is p-party leakage-resilient.While we do not focus on rate (the ratio of the length ofold shares to that of new shares) in this work, our rate isessentially Ω(1/ log n) for any constant p.We remark that efficient5 constructions of LRSSs withasymptotically better dependence on the collusion bound pwill lead to breakthroughs in communication complexity ([24], [43]–[45]). In fact, even constructing efficient resilientschemes where p ω(log n), where the leakage is simultaneous and non-adaptive6 would lead to breakthroughs incircuit complexity.Note that the resulting secret sharing scheme featuresstatistical leakage-resilience even though the secrecy iscomputational to begin with. Furthermore, using the secretsharing scheme from Komargodski, Naor, Yogev [50], wearrive at the following:Corollary 1. For single bit secrets, for any number ofparties n, suppose there is (p, p 1, n)-LRSS leakageresilient w.r.t a computationally unbounded adversary wholearns p2 bits of leakage such that each bit of the leakagenon-adaptively depends on at most p shares. If the size ofo(1)each of the shares of this scheme is 2p , then this impliesthat the reconstruction procedure of this scheme does notbelong to ACC0 .Corollary 5 (Informal). If one-way functions andwitness-encryption for NP exist, then for everymonotone NP access structure for which authorizedsets have cardinality greater than p O(log(n)), thereexists an efficient computational secret sharing schemethat realizes this access structure and is p-party leakageresilient.Leakage-resilient non-malleable secret sharing (LRNMSS).: We also define and construct LR NMSS for generalaccess structures, significantly improving the state-of-art thatonly deals with the special case of 2-out-of-2 LR NMSS[7], [16], [17], [40], [41] and t-out-of-n NMSS that can beextended to handle leakage and tampering from at most tshares [7].In particular, if a (n 1, n, n)-LRSS is efficient, thenwe obtain an unconditional separation between ACC0 andP . This would be a major breakthrough as existing breakthrough results [46] (resp. [47]) only separate ACC0 andNEXP (resp. NQP ). We give more precise statementsof such implications in Section VI.We next mention some interesting corollaries of our mainresult. Using Shamir’s t-out-of-n secret sharing scheme [3],we get the first t-out-of-n secret sharing schemes that arep-party leakage-resilient. Note that no such schemes wereknown even for individual leakage (p 1):Theorem 2 (Informal). For any access structure A that doesnot contain singletons, if there exists an efficient statistical(resp. computational) secret sharing scheme realizing accessstructure A, then there exists an efficient statistical (resp.computational) secret sharing scheme realizing A that isstatistically non-malleable against an adversary who obtainsa bounded amount of information by adaptively leaking fromeach of the shares, and then uses this leakage to tamper eachof the shares arbitrarily and independently.Corollary 2 (In
sharing schemes by constructing threshold secret sharing A prior version appeared as “Leakage-Resilient Secret Sharing” [1] containing the same set of results. schemes that allow any set of tparties, out of nparties total, to reconstruct the secret. Furthermore, crucially, the secret is hid
THE SECRET SEVEN is the first adventure of the SECRET SEVEN SOCIETY The other books are called: SECOND The Secret Seven Adventure THIRD Well Done Secret Seven! FOURTH Secret Seven on the Trail FIFTH Go Ahead Secret Seven SIXTH Good Work Secret Seven SEVENTH Secret Seven Win Through EIGHTH Three Cheers Secret Seven NINTH Secret Seven Mystery
View the Secret audit log to see which users have accessed the Secret. Delete the Secret. Change which template is being used to store and display information in this Secret. Secret Server – End User Guide Page 8 Editing a Secret To edit a Secret, navigate to its Secret V
of secret sharing is that the shares must leak absolutely no information about the secret, until the number of shares passes the threshold value. 3.2 A Simple 2-out-of-2 Scheme Believe it or not, we have already seen a simple secret-sharing scheme! In fact, it might even be best to think of one-time pad as the simplest secret-sharing scheme.
cuit techniques for leakage control in logic and memory. Fi-nally, the conclusion of the paper appears in Section IV. II. TRANSISTOR LEAKAGE MECHANISMS We describe six short-channel leakage mechanisms as il-lustrated in Fig. 3. is the reverse-bias pn junction leakage;
Appendix A of the SMACNA HVAC Air Duct Leakage Test Manual gives leakage as a percent of flow in a system by Leakage Class, fan CFM, and static pressure. The leakage in a 1" static pressure system can be as high as 24 percent in Leakage Class 48 to a low of 1.5 percent in Leakage Class 3. With this wide a range, it is very important that the .
Variability of duct leakage is high. About 10% of homes showed little leakage; 10% showed severe leakage. Duct leakage added about 10% to house leakiness, measured by fan pressurization (4 Pa ELA and 50 Pa air exchange). Flow hood tests showed return duct leakage about twice that of supply ducts during normal furnace fan operation. This typically
and protocols behind secret sharing schemes and implement Shamir's scheme using Java. In addition, we have also introduced a new scheme for extending the Shamir's scheme on proactive network. knowledge or power each entity has, t General Terms Cryptography and Network security. Keywords Cryptography, Secret Sharing, Shamir's secret sharing
Introduction 1 Part I Ancient Greek Criticism 7 Classical Literary Criticism: Intellectual and Political Backgrounds 9 1 Plato (428–ca. 347 bc)19 2 Aristotle (384–322 bc)41 Part II The Traditions of Rhetoric 63 3 Greek Rhetoric 65 Protagoras, Gorgias, Antiphon, Lysias, Isocrates, Plato, Aristotle 4 The Hellenistic Period and Roman Rhetoric 80 Rhetorica, Cicero, Quintilian Part III Greek .
