Topology-Hiding Computation Beyond Semi-Honest Adversaries Rio LaVigne1?, Chen-Da Liu-Zhang2, Ueli Maurer2, Tal Moran3??, Marta Mularczyk2???, and Daniel Tschudi4† 1 [email protected], MIT 2 {lichen,maurer,mumarta}@inf.ethz.ch, ETH Zurich 3 [email protected], IDC Herzliya 4 [email protected], Aarhus University Abstract. Topology-hiding communication protocols allow a set of parties, connected by an in- completenetworkwithunknowncommunicationgraph,whereeachpartyonlyknowsitsneighbors, to construct a complete communication network such that the network topology remains hidden evenfromapowerfuladversarywhocancorruptparties.Thiscommunicationnetworkcanthenbe usedtoperformarbitrarytasks,forexamplesecuremulti-partycomputation,inatopology-hiding manner. Previouslyproposedprotocolscouldonlytoleratepassivecorruption.Thispaperproposesprotocols that can also tolerate fail-corruption (i.e., the adversary can crash any party at any point in time) and so-called semi-malicious corruption (i.e., the adversary can control a corrupted party’s randomness),withoutleakingmorethananarbitrarilysmallfractionofabitofinformationabout thetopology.Asmall-leakageprotocolwasrecentlyproposedbyBalletal.[Eurocrypt’18],butonly undertheunrealisticset-upassumptionthateachpartyhasatrustedhardwaremodulecontaining secret correlated pre-set keys, and with the further two restrictions that only passively corrupted parties can be crashed by the adversary, and semi-malicious corruption is not tolerated. Since leaking a small amount of information is unavoidable, as is the need to abort the protocol in case of failures, our protocols seem to achieve the best possible goal in a model with fail-corruption. FurthercontributionsofthepaperareapplicationsoftheprotocoltoobtainsecureMPCprotocols, which requires a way to bound the aggregated leakage when multiple small-leakage protocols are executed in parallel or sequentially. Moreover, while previous protocols are based on the DDH assumption, a new so-called PKCR public-key encryption scheme based on the LWE assumption isproposed,allowingtobasetopology-hidingcomputationonLWE.Furthermore,aprotocolusing fully-homomorphic encryption achieving very low round complexity is proposed. 1 Introduction 1.1 Topology-Hiding Computation Secure communication over an insecure network is one of the fundamental goals of cryptog- raphy. The security goal can be to hide different aspects of the communication, ranging from the content (secrecy), the participants’ identity (anonymity), the existence of communication (steganography), to hiding the topology of the underlying network in case it is not complete. Incomplete networks arise in many contexts, such as the Internet of Things (IoT) or ad-hoc vehicular networks. Hiding the topology can, for example, be important because the position of a node within the network depends on the node’s location. This could in information about the ? ThismaterialisbaseduponworksupportedbytheNationalScienceFoundationGraduateResearchFellowship under Grant No. 1122374. Any opinion, findings, and conclusions or recommendations expressed in this materialarethoseoftheauthors(s)anddonotnecessarilyreflecttheviewsoftheNationalScienceFoundation. ResearchalsosupportedinpartbyNSFGrantsCNS-1350619andCNS-1414119,andbytheDefenseAdvanced Research ProjectsAgency(DARPA)andtheU.S.ArmyResearchOfficeundercontractsW911NF-15-C-0226 and W911NF-15-C-0236. ?? Supported in part by ISF grant no. 1790/13 and by the Bar-Ilan Cyber-center. ??? Research was supported by the Zurich Information Security and Privacy Center (ZISC). † WorkpartlydonewhileauthorwasatETHZurich.AuthorwassupportedbyadvancedERCgrantMPCPRO. node’s identity or other confidential parameters. The goal is that parties, and even colluding sets of parties, can not learn anything about the network, except their immediate neighbors. Incompletenetworkshavebeenstudiedinthecontextofcommunicationsecurity,referredto assecuremessagetransmission(see,e.g.[DDWY90]),wherethegoalistoenablecommunication between any pair of entities, despite an incomplete communication graph. Also, anonymous communication has been studied extensively (see, e.g. [Cha81, RC88, SGR97]). Here, the goal is tohidetheidentityofthesenderandreceiverinamessagetransmission.Aclassicaltechniqueto achieve anonymity is the so-called mix-net technique, introduced by Chaum [Cha81]. Here, mix serversareusedasproxieswhichshufflemessagessentbetweenpeerstodisableaneavesdropper from following a message’s path. The onion routing technique [SGR97, RC88] is perhaps the most known instantiation of the mix-technique. Another anonymity technique known as Dining Cryptographers networks, in short DC-nets, was introduced in [Cha88] (see also [Bd90, GJ04]). However, none of these approaches can be used to hide the network topology. In fact, message transmission protocols assume (for their execution) that the network graph is public knowledge. The problem of topology-hiding communication was introduced by Moran et al. [MOR15]. The authors propose a broadcast protocol in the cryptographic setting, which does not reveal any additional information about the network topology to an adversary who can access the in- ternal state of any number of passively corrupted parties (that is, they consider the semi-honest setting). This allows to achieve topology-hiding MPC using standard techniques to transform broadcast channels into secure point-to-point channels. At a very high level, [MOR15] uses a series of nested multi-party computations, in which each node is emulated by a secure computa- tion of its neighbor. This emulation then extends to the entire graph recursively. In [HMTZ16], the authors improve this result and provide a construction that makes only black-box use of encryption and where the security is based on the DDH assumption. However, both results are feasible only for graphs with logarithmic diameter. Topology hiding communication for certain classes of graphs with large diameter was described in [AM17]. This result was finally extended to allow for arbitrary (connected) graphs in [ALM17a]. A natural next step is to extend these results to settings with more powerful adversaries. Unfortunately,evenaprotocolinthesettingwithfail-corruptions(inadditiontopassivecorrup- tions) turns out to be difficult to achieve. In fact, as shown already in [MOR15], some leakage in the fail-stop setting is inherent. It is therefore no surprise that all previous protocols (secure against passive corruptions) leak information about the network topology if the adversary can crash parties. The core problem is that crashes can interrupt the communication flow of the protocol at any point and at any time. If not properly dealt with by the protocol, those out- ages cause shock waves of miscommunication, which allows the adversary to probe the network topology. A first step in this direction was recently achieved in [BBMM18] where a protocol for topology-hiding communication secure against a fail-stop adversary is given. However, the re- silience against crashes comes at a hefty price; the protocol requires that parties have access to secure hardware modules which are initialized with correlated, pre-shared keys. Their protocol provides security with abort and the leakage is arbitrarily small. In the information-theoretic setting, the main result is negative [HJ07]: any MPC protocol intheinformation-theoreticsettinginherentlyleaksinformationaboutthenetworkgraph.They also show that if the routing table is leaked, one can construct an MPC protocol which leaks no additional information. 1.2 Comparison to Previous Work In [ALM17a] the authors present a broadcast protocol for the semi-honest setting based on randomwalks.Thisbroadcastprotocolisthencompiledintoafulltopology-hidingcomputation protocol. However, the random walk protocol fails spectacularly in the presence of fail-stop adversaries, leaking a lot of information about the structure of the graph. Every time a node 2 aborts, any number of walks get cut, meaning that they no longer carry any information. When this happens, adversarial nodes get to see which walks fail along which edges, and can get a good idea of where the aborting nodes are in the graph. Wealsonotethat,whileweuseideasfrom[BBMM18],whichachievesthedesiredresultina trusted-hardwaremodel,wecannotsimplyusetheirprotocolandsubstitutethesecurehardware box for a standard primitive. In particular, they use the fact that each node can maintain an encrypted “image” of the entire graph by combining information from all neighbors, and use that information to decide whether to give output or abort. This appears to require both some form of obfuscation and a trusted setup, whereas our protocol uses neither. 1.3 Contributions Inthispaperweproposethefirsttopology-hidingMPCprotocolsecureagainstpassiveandfail- stop adversaries (with arbitrarily small leakage) that is based on standard assumptions. Our protocol does not require setup, and its security can be based on either the DDH, QR or LWE assumptions. A comparison of our results to previous works in topology-hiding communication is found in Table 1. Theorem 1 (informal). If DDH, QR or LWE is hard, then for any MPC functionality F, there exists a topology-hiding protocol realizing F for any network graph G leaking at most an arbitrarily small fraction p of a bit, which is secure against an adversary that does any number of static passive corruptions and adaptive crashes. The round and communication complexity is polynomial in the security parameter κ and 1/p. Table 1.Adversarialmodelandsecurityassumptionsofexistingtopology-hidingbroadcastprotocols.Thetable alsoshowstheclassofgraphsforwhichtheprotocolshavepolynomialcommunicationcomplexityinthesecurity parameter and the number of parties. Adversary Graph Hardness Asm. Model Reference log diam. Trapdoor Perm. Standard [MOR15] log diam. DDH Standard [HMTZ16] semi-honest cycles, trees, DDH Standard [AM17] log circum. arbitrary DDH or QR Standard [ALM17a] fail-stop arbitrary OWF Trusted Hardware [BBMM18] semi-malicious DDH or QR arbitrary Standard [This work] & fail-stop or LWE Our topology-hiding MPC protocol is obtained by compiling a MPC protocol from a topo- logy-hiding broadcast protocol leaking at most a fraction p of a bit. We note that although it is well known that without leakage any functionality can be implemented on top of secure communication, this statement cannot be directly lifted to the setting with leakage. In essence, if a communication protocol is used multiple times, it leaks multiple bits. However, we show that our broadcast protocol, leaking at most a fraction p of a bit, can be executed sequentially and in parallel, such that the result leaks also at most the same fraction p. As a consequence, any protocol can be compiled into one that hides topology and known results on implementing any multiparty computation can be lifted to the topology hiding setting. However, this incurs a multiplicative overhead in the round complexity. We then present a topology hiding protocol to evaluate any poly-time function using FHE whose round complexity will amount to that of a single broadcast execution. To do that, we first define an enhanced encryption scheme, which we call Deeply Fully-Homomorphic Public- Key Encryption (DFH-PKE), with similar properties as the PKCR scheme presented in [AM17, 3 ALM17a] and provide an instantiation of DFH-PKE under FHE. Next, we show how to obtain a protocol using DFH-PKE to evaluate any poly-time function in a topology hiding manner. We also explore another natural extension of semi-honest corruption, the so-called semi- malicious setting. As for passive corruption, the adversary selects a set of parties and gets access to their internal state. But in addition, the adversary can also set their randomness during the protocol execution. This models the setting where a party uses an untrusted source of randomness which could be under the control of the adversary. This scenario is of interest as tampered randomness sources have caused many security breaches in the past [HDWH12, CNE+14]. In this paper, we propose a general compiler that enhances the security of protocols that tolerate passive corruption with crashes to semi-malicious corruption with crashes. 2 Preliminaries 2.1 Notation For a public-key pk and a message m, we denote the encryption of m under pk by [m] . pk Furthermore, for k messages m ,...,m , we denote by [m ,...,m ] a vector, containing the 1 k 1 k pk k encryptions of messages m under the same key pk. i For an algorithm A(·), we write A(· ;U∗) whenever the randomness used in A(·) should be made explicit and comes from a uniform distribution. By ≈ we denote that two distribution c ensembles are computationally indistinguishable. 2.2 Model of Topology-Hiding Communication Adversary. Most of our results concern an adversary, who can statically passively corrupt an arbitrary set of parties Zp, with (cid:12)(cid:12)Zp(cid:12)(cid:12) < n. Passively corrupted parties follow the protocol instructions (this includes the generation of randomness), but the adversary can access their internal state during the protocol. A semi-malicious corruption (see, e.g., [AJL+12]) is a stronger variant of a passive corrup- tion. Again, we assume that the adversary selects any set of semi-malicious parties Zs with (cid:12)(cid:12)Zs(cid:12)(cid:12) < n before the protocol execution. These parties follow the protocol instructions, but the adversary can access their internal state and can additionally choose their randomness. Afail-stopadversarycanadaptivelycrashparties.Afterbeingcrashed,apartystopssending messages. Note that crashed parties are not necessarily corrupted. In particular, the adversary has no access to the internal state of a crashed party unless it is in the set of corrupted parties. This type of fail-stop adversary is stronger and more general than the one used in [BBMM18], whereonlypassivelycorruptedpartiescanbecrashed.Inparticular,inourmodeltheadversary does not necessarily learn the neighbors of crashed parties, whereas in [BBMM18] they are revealed to it by definition. Communication Model. We state our results in the UC framework. We consider a syn- chronous communication network. Following the approach in [MOR15], to model the restricted communication network we define the Fnet-hybrid model. The Fnet functionality takes as in- put a description of the graph network from a special “graph party” P and then returns graph to each party P a description of its neighborhood. After that, the functionality acts as an i “ideal channel” that allows parties to communicate with their neighbors according to the graph network. Similarly to [BBMM18], we change the Fnet functionality from [MOR15] to deal with a fail-stop adversary. 4 Functionality Fnet The functionality keeps the following variables: the set of crashed parties C and the graph G. Initially, C =∅ and G=(∅,∅). Initialization Step: 1: The party Pgraph sends graph G0 to Fnet. Fnet sets G=G0. 2: Fnet sends to each party Pi its neighborhood NG(Pi). Communication Step: 1: If the adversary crashes party Pi, then Fnet sets C =C∪{Pi}. 2: If a party Pi sends the command (Send,j,m), where Pj ∈ NG(Pi) and m is the message to Pj, to Fnet and Pi ∈/ C, then Fnet outputs (i,m) to party Pj. Observe that since Fnet gives local information about the network graph to all corrupted parties, any ideal-world adversary should also have access to this information. For this reason, similar to [MOR15], we use in the ideal-world the functionality Finfo, which contains only the Initialization Step of Fnet. To model leakage we extend Finfo by a leakage phase, where the adversary can query a (possibly probabilistic) leakage function L once. The inputs to L include the network graph, the set of crashed parties and arbitrary input from the adversary. We say that a protocol leaks one bit of information if the leakage function L outputs one bit. We also consider the notion of leaking a fraction p of a bit. This is modeled by having L output the bit only with probability p (otherwise, L outputs a special symbol ⊥). Here our model differs from the one in [BBMM18], where in case of the fractional leakage, L always gives the output, but the simulator is restricted to query its oracle with probability p over its randomness. As noted there, the formulation we use is stronger. We denote by FL the info information functionality with leakage function L. Functionality FiLnfo The functionality keeps the following variables: the set of crashed parties C and the graph G. Initially, C =∅ and G=(∅,∅). Initialization Step: 1: The party Pgraph sends graph G0 =(V,E) to FiLnfo. FiLnfo sets G=G0. 2: FiLnfo sends to each party Pi its neighborhood NG(Pi). Leakage Step: 1: If the adversary crashes party Pi, then FiLnfo sets C =C∪{Pi}. 2: If the adversary sends the command (Leak,q) to FiLnfo for the first time, then FiLnfo outputs L(q,C,G) to the adversary. Security Model. Our protocols provide security with abort. In particular, the adversary can choose some parties, who do not receive the output (while the others still do). That is, no guaranteed output delivery and no fairness is provided. Moreover, the adversary sees the output before the honest parties and can later decide which of them should receive it. Technically, we model such ability in the UC framework as follows: First, the ideal world adversary receives from the ideal functionality the outputs of the corrupted parties. Then, it inputs to the functionality an abort vector containing a list of parties who do not receive the output. Definition 1. We say that a protocol Π topology-hidingly realizes a functionality F with L- leakage, in the presence of an adversary who can statically passive corrupt and adaptively crash any number of parties, if it UC-realizes (FiLnfo k F) in the Fnet-hybrid model. 5 2.3 Background Graphs and Random Walks. In an undirected graph G = (V,E) we denote by N (P ) the G i neighborhood of P ∈ V. The k-neighborhood of a party P ∈ V is the set of all parties in V i i within distance k to P . i In our work we use the following lemma from [ALM17a]. It states that in an undirected connected graph G, the probability that a random walk of length 8|V|3τ covers G is at least 1− 1 . 2τ Lemma 1 ([ALM17a]). Let G = (V,E) be an undirected connected graph. Further let W(u,τ) be a random variable whose value is the set of nodes covered by a random walk starting from u and taking 8|V|3τ steps. We have 1 Pr[W(u,τ) = V] ≥ 1− . W 2τ PKCR Encryption. As in [ALM17a], our protocols require a public key encryption scheme with additional properties, called Privately Key Commutative and Rerandomizable encryption. Weassumethatthemessagespaceisbits.Then,aPKCRencryptionschemeshouldbe:privately keycommutativeandhomomorphicwithrespecttotheORoperation5.Weformallydefinethese properties below. Let PK, SK and C denote the public key, secret key and ciphertext spaces. As any public key encryption scheme, a PKCR scheme contains the algorithms KeyGen : {0,1}∗ → PK×SK, Encrypt : {0,1}×PK → C and Decrypt : C ×SK → {0,1} for key generation, encryption and decryption respectively (where KeyGen takes as input the security parameter). Privately Key-Commutative. We require PK to form a commutative group under the oper- ation (cid:126). So, given any pk ,pk ∈ PK, we can efficiently compute pk = pk (cid:126)pk ∈ PK and 1 2 3 1 2 for every pk, there exists an inverse denoted pk−1. This group must interact well with ciphertexts; there exists a pair of efficiently computable algorithms AddLayer : C ×SK → C and DelLayer : C ×SK → C such that – Foreverypublickeypairpk ,pk ∈ PKwithcorrespondingsecretkeyssk andsk ,message 1 2 1 2 m ∈ M, and ciphertext c = [m] , pk 1 AddLayer(c,sk2) = [m]pk (cid:126)pk . 1 2 – Foreverypublickeypairpk ,pk ∈ PKwithcorrespondingsecretkeyssk andsk ,message 1 2 1 2 m ∈ M, and ciphertext c = [m] , pk 1 DelLayer(c,sk ) = [m] . 2 pk (cid:126)pk−1 1 2 Notice that we need the secret key to perform these operations, hence the property is called privately key-commutative. OR-Homomorphic. We also require the encryption scheme to be OR-homomorphic, but in such a way that parties cannot tell how many 1’s or 0’s were OR’d (or who OR’d them). We need an efficiently-evaluatable homomorphic-OR algorithm, HomOR : C×C → C, to satisfy the following: for every two messages m,m0 ∈ {0,1} and every two ciphertexts c,c0 ∈ C such that Decrypt(c,sk) = m and Decrypt(c,sk) = m0, (cid:8)(m,m0,c,c0,pk,Encrypt(m∨m0,pk;U∗))(cid:9) ≈ c (cid:8)(m,m0,c,c0,pk,HomOR(c,c0,pk;U∗))(cid:9) 5 PKCRencryptionwasintroducedin[AM17,ALM17a],whereithadthreeadditionalproperties:keycommuta- tivity, homomorphism and rerandomization, hence, it was called Privately Key Commutative and Rerandom- izableencryption.However,rerandomizationisactuallyimpliedbythestrengthenednotionofhomomorphism. Therefore, we decided to not include the property, but keep the name. 6 Note that this is a stronger definition for homomorphism than usual; usually we only require correctness, not computational indistinguishability. In [HMTZ16], [AM17] and [ALM17a], the authors discuss how to get this kind of homo- morphic OR under the DDH assumption, and later [ALM17b] show how to get it with the QR assumption. For more details on other kinds of homomorphic cryptosystems that can be compiled into OR-homomorphic cryptosystems, see [ALM17b]. RandomWalkApproach[ALM17a]. Ourprotocolbuildsupontheprotocolfrom[ALM17a]. Wegiveahighleveloverview.Toachievebroadcast,theprotocolcomputestheOR.Everyparty has an input bit: the sender inputs the broadcast bit and all other parties use 0 as input bit. Computing the OR of all those bits is thus equivalent to broadcasting the sender’s message. First, let us explain a simplified version of the protocol that is unfortunately not sound, but gets the basic principal across. Each node encrypts its bit under a public key and forwards it to a random neighbor. The neighbor OR’s its own bit, adds a fresh public key layer, and it forwards the ciphertext to a randomly chosen neighbor. Eventually, after about O(κn3) steps, the random walk of every message visits every node in the graph, and therefore, every message will contain the OR of all bits in the network. Now we start the backwards phase, reversing the walk and peeling off layers of encryption. This scheme is not sound because seeing where the random walks are coming from reveals information about the graph! So, we need to disguise that information. We will do so by using correlated random walks, and will have a walk running down each direction of each edge at each step (so 2× number of edges number of walks total). The walks are correlated, but still random. This way, at each step, each node just sees encrypted messages all under new and different keys from each of its neighbors. So, intuitively, there is no way for a node to tell anything about where a walk came from. 3 Topology-Hiding Broadcast In this section we present a protocol, which securely realizes the broadcast functionality FBC (withabort)intheFnet-hybridworldandleaksatmostanarbitrarilysmall(butnotnegligible) fraction of a bit. If no crashes occur, the protocol does not leak any information. The protocol is secure against an adversary that (a) controls an arbitrary static set of passively corrupted parties and (b) adaptively crashes any number of parties. Security can be based either on the DDH, the QR or the LWE assumption. To build intuition we first present the simple protocol variant which leaks at most one bit. Functionality FBC When a party Pi sends a bit b∈{0,1} to the functionality FBC, then FBC sends b to each party Pj ∈P. 3.1 Protocol Leaking One Bit WefirstintroducethebroadcastprotocolvariantBC-OBwhichleaksatmostone-bit.Theproto- colisdividedintonconsecutivephases,where,ineachphase,thepartiesexecuteamodification of the random-walk protocol from [ALM17a]. More specifically, we introduce the following mod- ifications: Single Output Party: There will be n phases. In each phase only one party, P , gets the o output. Moreover, it learns the output from exactly one of the random walks it starts. To implement this, in the respective phase all parties except P start their random walks o with encryptions of 1 instead of their input bits. This ensures that the outputs they get 7 from the random walks will always be 1. We call these walks dummy since the contain no information. Party P , on the other hand, starts exactly one random walk with its actual o input bit (the other walks it starts with encryptions of 1). This ensures (in case no party crashes) that P actually learns the broadcast bit. o Happiness Indicator: Every party P holds an unhappy-bit u . Initially, every P is happy, i i i i.e., u = 0. If a neighbor of P crashes, then in the next phase P becomes unhappy and i i i sets u = 1. The idea is that an unhappy party makes all phases following the crash become i dummy. This is implemented by having the parties send along the random walk, instead of a single bit, an encrypted tuple [b,u] . The bit u is the OR of the unhappy-bits of the parties in the pk walk, while b is the OR of their input bits and their unhappy-bits. In other words, a party P on the walk homomorphically ORs b ∨u to b and u to u. i i i i Intuitively, if all parties on the walk were happy at the time of adding their bits, b will actually contain the OR of their input bits and u will be set to 0. On the other hand, if any party was unhappy, b will always be set to 1, and u = 1 will indicate an abort. Intuitively, the adversary learns a bit of information only if it manages to break the one random walk which P started with its input bit (all other walks contain the tuple [1,1]). o Moreover, if it crashes a party, then all phases following the one with the crash abort, hence, they do not leak any information. More formally, parties execute, in each phase, protocol RandomWalkPhase. This protocol takes as global inputs the length T of the random walk and the P which should get output. o Additionally, each party P has input (d ,b ,u ) where d is its number of neighbors, u is its i i i i i i unhappy-bit, and b is its input bit. i Protocol RandomWalkPhase(T,P ,(d ,b ,u ) ) o i i i Pi∈P Initialization Stage: 1: Each party P generates T· d keypairs (pk(r) ,sk(r) ) (cid:17) KeyGen(1κ) where r ∈ {1,...,T} and j ∈ i i i→j i→j {1,...,d }. i n o 2: Each party P generates T−1 random permutations on d elements π(2),...,π(T) i i i i 3: For each party P , if any of P ’s neighbors crashed in any phase before the current one, then P becomes i i i unhappy, i.e., sets u =1. i Aggregate Stage: Each party P does the following: i 1: if P is the recipient P then i o 2: Party P sends to the first neighbor the ciphertext [b ∨u ,u ] and the public key pk(1) , and to i i i i pk(1) i→1 i→1 any other neighbor P it sends ciphertext [1,1] and the public key pk(1) . j pk(1) i→j i→j 3: else 4: Party P sends to each neighbor P ciphertext [1,1] and the key pk(1) . i j pk(1) i→j i→j 5: end if 6: // Add layer while ORing own input bit 7: for any round r from 2 to T do 8: For each neighbor P of P , do the following (let k=π(r)(j)): j i i 9: if P did not receive a message from P then i j 10: Party P sends ciphertext [1,1] and key pk(r) to neighbor P . i pk(r) i→k k i→k 11: else // AddLayer and HomOR are applied component-wise 12: Letc(r−1)andpk(r−1)betheciphertextandthepublickeyP receivedfromP .PartyP computes j→i j→i i j i pk(r) =pk(r−1)(cid:126)pk(r) and i→k j→i i→k (cid:16) (cid:17) cˆ(r) ←AddLayer c(r−1),sk(r) . i→k j→i i→k 13: P computes [b ∨u ,u ] and i i i i pk(r) (cid:16) i→k (cid:17) c(r) =HomOR [b ∨u ,u ] ,cˆ(r) ,pk(r) . i→k i i i pk(r) i→k i→k i→k 8 14: Party P sends ciphertext c(r) and public key pk(r) to neighbor P . i i→k i→k k 15: end if 16: end for Decrypt Stage: Each party P does the following: i 1: For each neighbor P of P , if P did not receive a message from P at round T of the Aggre- j i i j gate Stage, then it sends ciphertext e(T) = [1,1] to P . Otherwise, P sends to P e(T) = i→j pk(T) j i j i→j (cid:18) (cid:19) j→i HomOR [b ∨u ,u ] ,c(T) ,pk(T) . i i i pk(T) j→i j→i j→i 2: for any round r from T to 2 do 3: For each neighbor P of P : k i 4: if P did not receive a message from P then i k 5: Party P sends e(r−1) =[1,1] to neighbor P , where k=π(r)(j). i i→j pk(r−1) j i j→i 6: else 7: Denote by e(r) the ciphertext P received from P , where k = π(r)(j). Party P sends e(r−1) = k→i i k i i i→j (cid:16) (cid:17) DelLayer e(r) ,sk(r) to neighbor P . k→i i→k j 8: end if 9: end for 10: IfP istherecipientP ,thenitcomputes(b,u)=Decrypt(e(1) ,sk(1) )andoutputs(b,u,u ).Otherwise, i o 1→i i→1 i it outputs (1,0,u ). i TheactualprotocolBC-OBconsistsofnconsecutiverunsoftherandomwalkphaseprotocol RandomWalkPhase. Protocol BC-OB(T,(d ,b ) ) i i Pi∈P Each party P keeps bits bout, uout and u , and sets u =0. i i i i i for o from 1 to n do Parties jointly execute (cid:0)(btmp,vtmp,utmp) (cid:1)=RandomWalkPhase(T,P ,(d ,b ,u ) ). i i i Pi∈P o i i i Pi∈P Each party P sets u =utmp. i i i Party P sets bout =btmp, uout =vtmp. o o o o o end for For each party P , if uout =0 then party P outputs bout. i i i i TheprotocolBC-OBleaksinformationaboutthetopologyofthegraphduringtheexecution of RandomWalkPhase, in which the first crash occurs. (Every execution before the first crash proceedsalmostexactlyastheprotocolin[ALM17a]andineveryexecutionafterwardsallvalues are blinded by the unhappy-bit u.) We model the leaked information by a query to the leakage function L . The function outputs only one bit and, since the functionality FL allows for OB info only one query to the leakage function, the protocol leaks overall one bit of information. The inputs passed to L are: the graph G and the set C of crashed parties, passed to the OB functionbyFL ,andatriple(F,P ,T0),passedbythesimulator.Theideaisthatthesimulator info s needs to know whether the walk carrying the output succeeded or not, and this depends on the graph G. More precisely, the set F contains a list of pairs (P ,r), where r is the number of f rounds in the execution of RandomWalkPhase, at which P crashed. L tells the simulator f OB whether any of the crashes in F disconnected a freshly generated random walk of length T0, starting at given party P . s Function L ((F,P ,T0),C,G) OB s if for any (P ,r)∈F, P 6∈C then Return 0. f f else Generate in G a random walk of length T0 starting at P . s 9 Return1ifforany(P ,r)∈F removingpartyP afterr roundsdisconnectsthewalkand0otherwise. f f end if We prove the following theorem in Section A.1. Theorem 2. For κ security parameter and T = 8n3(log(n)+κ) protocol BC-OB(T,(d ,b ) )) i i Pi∈P topology-hidingly realizes FiLnOfoB||FBC (with abort) in the Fnet hybrid-world, where the leakage function L is the one defined as above. If no crashes occur, then there is no abort and there OB is no leakage. 3.2 Protocol Leaking a Fraction of a Bit We now show how to go from BC-OB to the actual broadcast protocol BC-FB which leaks only p a fraction p of a bit. The leakage parameter p can be arbitrarily small. However, the complexity of the protocol is proportional to 1/p. As a consequence, 1/p must be polynomial and p cannot be negligible. Theideaistoleveragethefactthattheadversarycangaininformationinonlyoneexecution of RandomWalkPhase. Imagine that RandomWalkPhase succeeds only with a small probability p, and otherwise the output bit b is 1. Moreover, assume that during RandomWalkPhase the adversary does not learn whether it will fail until it can decrypt the output. We can now, for each phase, repeat RandomWalkPhase ρ times, so that with overwhelming probability one of the repetitions does not fail. A party P can then compute its output as the o AND of outputs from all repetitions (or abort if any repetition aborted). On the other hand, the adversary can choose only one execution of RandomWalkPhase, in which it learns one bit of information (all subsequent repetitions will abort). Moreover, it must choose it before it knows whether the execution succeeds. Hence, the adversary learns one bit of information only with probability p. What is left is to modify RandomWalkPhase, so that it succeeds only with probability p, and so that the adversary does not know whether it will succeed. We only change the Aggregate Stage. Instead of an encrypted tuple [b,u], the parties send along the walk b1/pc+1 encrypted bits [b1,...,bb1/pc,u], where u again is the OR of the unhappy-bits, and every bk is a copy the bit b in RandomWalkPhase, with some caveats. For each phase o, and for every party P 6= P , i o all bk are copies of b in the walk and they all contain 1. For P , only one of the bits, bk, contains o the OR, while the rest is initially set to 1. During the Aggregate Stage, the parties process every ciphertext corresponding to a bit bk the same way they processed the encryption of b in the RandomWalkPhase. Then, before sending the ciphertexts to the next party on the walk, the encryptions of the bits bk are randomly shuffled. (This way, as long as the walk traverses an honest party, the adversary does not know which of the ciphertexts contain dummy values.) At the end of the Aggregate Stage (after T rounds), the last party chooses uniformly at random one of the b1/pc ciphertexts and uses it, together with the encryption of the unhappy-bit, to execute the Decrypt Stage as in RandomWalkPhase. The information leaked by BC-FB is modeled by the following function L . p FBp Function L ((F,P ,T0),C,G) FBp s Let p0 =1/b1/pc. With probability p0, return L ((F,P ,T0),C,G) and with probability 1−p0 return ⊥. OB s A formal description of the modified protocol ProbabilisticRandomWalkPhase and a proof p of the following theorem can be found in Section A.2. Theorem 3. Let κ be the security parameter. For τ = log(n) + κ, T = 8n3τ, and ρ = τ/(p0 −2−τ), where p0 = 1/b1/pc, protocol BC-FB (T,ρ,(d ,b ) )) topology-hidingly realizes p i i Pi∈P 10