Private Simultaneous Messages (PSM) is a kind of secure multiparty computation with minimal interaction pattern and minimal security requirement. A PSM protocol is said to be with universal reconstruction for a given function family if the algorithm of the referee (the output party) is independent of a function to be computed and the referee cannot infer the function from a protocol execution. In a recent work by Eriguchi and Shinagawa (EUROCRYPT 2025), they proposed a compiler to obtain a...

Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $(m_1, \ldots, m_n)$ and their tags $(\sigma_1, \ldots, \sigma_n)$, anyone can evaluate a circuit $C$ on the data and tags to produce a succinct tag authenticating the output $C(m_1, \ldots, m_n)$. Importantly, tags remain succinc -- of size polynomial in the security parameter $\lambda$ -- regardless of the size of $C$....

The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs $(H, G)$, where $G$ is an Erdos-Renyi random graph on $n$ vertices, and $H$ is a random induced subgraph of $G$ on $k$ vertices. Assuming the hardness of distinguishing these two distributions (with two leaked vertices), Abram et al. construct communication-efficient, computationally secure (1) 2-party private simultaneous messages (PSM) and (2) secret sharing for...

We study the following broad question about cryptographic primitives: is it possible to achieve security against an arbitrary $\mathsf{poly}(n)$-time adversary with $O(\log n)$-size messages? It is common knowledge that the answer is ``no'' unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security. We obtain the following results, assuming variants of well-studied...

Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been...

In this note, we introduce a class of card-based protocols called single-shuffle full-open (SSFO) protocols and show that any SSFO protocol for a function $f: \{0,1\}^n \rightarrow [d]$ using $k$ cards is generically converted to a private simultaneous messages (PSM) protocol for $f$ with $(nk)$-bit communication. As an example application, we obtain an 18-bit PSM protocol for the three-bit equality function from the six-card trick (Heather-Schneider-Teague, Formal Aspects of Computing...

In cryptography, the private simultaneous messages (PSM) and conditional disclosure of secrets (CDS) are closely related fundamental primitives. We consider $k$-party PSM and CDS protocols for a function $f$ with a common random string, where each party $P_i$ generates a message and sends it to a referee $P_0$. We consider bounds for the optimal length $\rho$ of the common random string among $k$ parties (or, {\it randomness complexity}) in PSM and CDS protocols with perfect and statistical...

The private simultaneous messages (PSM) model is a non-interactive version of the multiparty secure computation (MPC), which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common random string (or...

We introduce a new primitive in information-theoretic cryptography, namely zero-communication reductions (ZCR), with different levels of security. We relate ZCR to several other important primitives, and obtain new results on upper and lower bounds. In particular, we obtain new upper bounds for PSM, CDS and OT complexity of functions, which are exponential in the information complexity of the functions. These upper bounds complement the results of Beimel et al. (2014) which broke the...

We improve the communication complexity in the Private Simultaneous Messages (PSM) model, which is a minimal model of non-interactive information-theoretic multi-party computation. The state-of-the-art PSM protocols were recently constructed by Beimel, Kushilevitz and Nissim (EUROCRYPT 2018). We present new constructions of $k$-party PSM protocols. The new protocols match the previous upper bounds when $k=2$ or $3$ and improve the upper bounds for larger $k$. We also construct $2$-party PSM...

A secret-sharing scheme allows some authorized sets of parties to reconstruct a secret; the collection of authorized sets is called the access structure. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $2^{n-o(n)}$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $O(2^{0.994n})$. Our first contribution...

We study the efficiency of computing arbitrary k-argument functions in the Private Simultaneous Messages (PSM) model of (Feige et al. STOC'94, Ishai and Kushilevitz ISTCS'97). This question was recently studied by (Beimel et al. TCC'14), in the two-party case (k = 2). We tackle this question in the general case of PSM protocols for k > 2 parties. Our motivation is two-fold: On one hand, there are various applications (old and new) of PSM protocols for constructing other cryptographic...

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the best known (non-explicit) lower-bound is $3k-O(1)$ bits. To prove this lower-bound, FKN identified a set of simple...

Private Set-Intersection (PSI) is one of the most popular and practically relevant secure two-party computation (2PC) tasks. Therefore, designing special-purpose PSI protocols (which are more efficient than generic 2PC solutions) is a very active line of research. In particular, a recent line of work has proposed PSI protocols based on oblivious transfer (OT) which, thanks to recent advances in OT-extension techniques, is nowadays a very cheap cryptographic building block. Unfortunately,...

We present new protocols for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. - For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$, we present two protocols that achieve $o(N^{1/2})$ communication: the first achieves $O(N^{1/3})$ communication and the second achieves sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$ communication. - As a...

We study the notion of {\em ad hoc secure computation}, recently introduced by Beimel et al. (ITCS 2016), in the context of the {\em Private Simultaneous Messages} (PSM) model of Feige et al.\ (STOC 2004). In ad hoc secure computation we have $n$ parties that may potentially participate in a protocol but, at the actual time of execution, only $k$ of them, whose identity is {\em not} known in advance, actually participate. This situation is particularly challenging in the PSM setting, where...

Göös, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of \emph{Zero-Information Arthur-Merlin Protocols} (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the prover, attempts to convince them that some public function $f$ evaluates to 1 on $(x,y)$. In addition to standard completeness and soundness, Göös et al.,...