Private Simultaneous Messages (PSM) is a minimal model for secure computation, where two parties, Alice and Bob, have private inputs x,y and a shared random string. Each of them sends a single message to an external party, Charlie, who can compute f(x,y) for a public function f but learns nothing else. The problem of narrowing the gap between upper and lower bounds on the communication complexity of PSM has been widely studied, but the gap still remains exponential. In this work, we study the communication complexity of PSM from a different perspective and introduce a special class of PSM, referred to as ideal PSM, in which each party’s message length attains the minimum, that is, their messages are taken from the same domain as inputs. We initiate a systematic study of ideal PSM with a complete characterization, several positive results, and applications. First, we provide a characterization of the class of functions that admit ideal PSM, based on permutation groups acting on the input domain. This characterization allows us to derive asymptotic upper bounds on the total number of such functions and a complete list for small domains. We also present several infinite families of functions of practical interest that admit ideal PSM. Interestingly, by simply restricting the input domains of these ideal PSM schemes, we can recover most of the existing PSM schemes that achieve the best known communication complexity in various computation models. As applications, we show that these ideal PSM schemes yield novel communication-efficient PSM schemes for functions with sparse or dense truth-tables and those with low-rank truth-tables. Furthermore, we obtain a PSM scheme for general functions that improves the constant factor in the dominant term of the best known communication complexity. An additional advantage is that our scheme simplifies the existing construction by avoiding the hierarchical design of internally invoking PSM schemes for smaller functions.

The shuffle model of DP (Differential Privacy) provides high utility by introducing a shuffler that randomly shuffles noisy data sent from users. However, recent studies show that existing shuffle protocols suffer from the following two major drawbacks. First, they are vulnerable to local data poisoning attacks, which manipulate the statistics about input data by sending crafted data, especially when the privacy budget$\varepsilon$is small. Second, the actual value of$\varepsilon$is increased by collusion attacks by the data collector and users. In this paper, we address these two issues by thoroughly exploring the potential of the augmented shuffle model, which allows the shuffler to perform additional operations, such as random sampling and dummy data addition. Specifically, we propose a generalized framework for local-noise-free protocols in which users send (encrypted) input data to the shuffler without adding noise. We show that this generalized protocol provides DP and is robust to the above two attacks if a simpler mechanism that performs the same process on binary input data provides DP. Based on this framework, we propose three concrete protocols providing DP and robustness against the two attacks. Our first protocol generates the number of dummy values for each item from a binomial distribution and provides higher utility than several state-of-the-art existing shuffle protocols. Our second protocol significantly improves the utility of our first protocol by introducing a novel dummy-count distribution: asymmetric two-sided geometric distribution. Our third protocol is a special case of our second protocol and provides pure ∊-DP. We show the effectiveness of our protocols through theoretical analysis and comprehensive experiments.

Abstract Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p of what is computed from messages. We design a QR-PSM protocol for any symmetric function $$f: \{0,1\}^n \rightarrow \{0,1\}$$ f : { 0 , 1 } n → { 0 , 1 } of communication complexity $$O(n^2)$$ O ( n 2 ) . As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of $$O(n^2\log n)$$ O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields $$\mathbb {F}_p$$ F p in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p. We show that there is a prime $$p \le (1+o(1))N^22^{2N-2}$$ p ≤ ( 1 + o ( 1 ) ) N 2 2 2 N - 2 such that any length-N pattern of quadratic (non)residues appears modulo p (and hence it can be used for general QR-PSM protocols), which improves the Peralta’s known result (Mathematics of Computation 1992) by a constant factor $$(1+\sqrt{2})^2$$ ( 1 + 2 ) 2 .

To bound information leakage in outputs of protocols, it is important to construct secure multiparty computation protocols which output differentially private values perturbed by the addition of noise. However, previous noise generation protocols have round and communication complexity growing with differential privacy budgets, or require parties to locally generate non-uniform noise, which makes it difficult to guarantee differential privacy against active adversaries. We propose three kinds of protocols for generating noise drawn from certain distributions providing differential privacy. The two of them generate noise from finite-range variants of the discrete Laplace distribution. For$(\epsilon,\delta )$-differential privacy, they only need constant numbers of rounds independent of$\epsilon,\delta$while the previous protocol needs the number of rounds depending on$\delta$. The two protocols are incomparable as they make a trade-off between round and communication complexity. Our third protocol non-interactively generate shares of noise from the binomial distribution by predistributing keys for a pseudorandom function. It achieves communication complexity independent of$\epsilon$or$\delta$for the computational analogue of$(\epsilon,\delta )$-differential privacy while the previous protocols require communication complexity depending on$\epsilon$. We also prove that our protocols can be extended so that they provide differential privacy in the active setting.

A multiple assignment scheme (MAS) is a method to construct secret sharing schemes (SSSs) for general access structures. There are MASs using threshold and ramp SSSs. The paper proposes new MASs using ideal SSSs realizing compartmented access structures and those using SSSs realizing multi-level access structures. Since the ideal SSSs realizing compartmented access structures and SSSs realizing multi-level access structures are natural generalizations of threshold and ramp SSSs, respectively, the new MASs cannot be less efficient than those using threshold or ramp SSSs.

A secret sharing scheme (SSS) is a cryptographic tool to protect a secret from loss and leakage by dividing it into shares. A ramp SSS can improve the efficiency in terms of the sizes of shares by allowing partial information about the secret to leak out. In order to prevent the partial information from being recovered explicitly, the notion of the strong security has been introduced. However, there have been proposed few methods to construct strongly secure ramp SSSs for general access structures and they are not always sufficient. In this paper, we show that any linear ramp SSS can be transformed into a strongly secure scheme with the same access structure preserving the information ratio.