Securely Simulating a Trusted Dealer. As just noted, the key idea is for the parties to use the MPC protocol from Section 5 to simulate a trusted dealer. In that case the parties are evaluating a no-input (randomized) MPC functionality, and so do not need any output quality; let ΠMPC = Π0 . Importantly, ΠMPC has communication complexity subquadratic in n. Using ΠMPC to simulate a dealer, however, requires us to address several technicalities. As described, ΠMPC evaluates a functionality for which all parties receive the same output. But simulating a dealer requires the parties to compute a functionality where parties receive different outputs. The standard approach for adapting MPC protocols to provide parties with different outputs does not work in our context: specifically, using symmetric-key en- cryption to encrypt the output of each party Pi using a key that Pi provides as part of its MPC input does not work since ΠMPC has no output quality (and even Πl only guarantees l-output quality for l < n). Assuming a PKI, we can fix this by using public-key encryption instead (in the same way); this works since the public keys of the parties can be incorpo- rated into the functionality being computed—since they are common knowledge—rather than being provided as inputs to the computation. Even when using public-key encryption as just described, however, additional issues re- main. ΠMPC has (expected) subquadratic communication complexity only when the output length O of the functionality being computed is sublinear in the number of parties. Even if the dealer algorithm generates output whose length is independent of n, naively encrypting output for every party (encrypting a “null” value of the appropriate length for parties whose output is empty) would result in output of total length linear in n. Encrypting the output only for parties with non-empty output does not work either since, in general, this might reveal which parties get output, which in our case would defeat the purpose of the setup! We can address this difficulty by using anonymous public-key encryption [3]. Roughly, an anonymous public-key encryption (APKE) scheme has the property that a ciphertext leaks no information about the public key pk used for encryption, except to the party holding the corresponding secret key sk (who is able to decrypt the ciphertext using that key). Using APKE to encrypt the output for each party who obtains non-empty output, and then randomly permuting the resulting ciphertexts, allows us to compute a func...
