The private simultaneous messages (PSM) model is a simple variant of the secure multiparty computation (MPC). In the k-party PSM model, each party $P_{\imath}$ has a private input $x_{i}$ for $i=1, \ldots, k$. For a function f, each $\lt p\gt P_{i}$ encrypts $x_{i}$ into a message $m_{i}$ with a random string r shared among $\lt p\gt P_{1}, \ldots, P_{k}$, and sends $m_{i}$ to the referee $R. R$ computes $f\left(x_{1}, \ldots, x_{k}\right)$ from their respective messages $m_{1}, \ldots, m_{k}$. Then, R learns nothing from $m_{1}, \ldots, m_{k}$ except for the output value $f\left(x_{1}, \ldots, x_{k}\right)$. This simple model provides interesting cryptographic applications and is essential for understanding the intrinsic costs (e.g., of communication $\left|m_{1}\right|+\ldots+\left|m_{k}\right|$ and randomness $|r|$) to achieve MPC. This study surveys recent results associated with the PSM and closely related models.

A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t, whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t-Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t-Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t-Garden-Of-Eden Problem, a variant of the t-Predecessor Problem that asks whether a configuration has a t-predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems.

We present a protocol compiler of rational secret-sharing that converts any rational secret-sharing protocol to a protocol with an expected constant-round reconstruction. Our compiler can be applied to protocols for synchronous channels, and preserves a strict Nash equilibrium of the original protocol. Combining with an existing protocol, we obtain the first expected constant-round protocol that achieves a strict Nash equilibrium with the optimal coalition resilience ⌈n2⌉−1⁠, where n is the number of players. Our compiler can be extended to one that preserves the immunity to unexpectedly behaving players. For any constant m≥1⁠, we obtain an expected constant-round protocol that achieves a Nash equilibrium with the optimal coalition resilience ⌈n2⌉−m−1 in the presence of m unexpectedly behaving players. The protocol also achieves a strict Nash equilibrium. As a negative result, we show that if an expected constant-round protocol has immunity m>0⁠, then it cannot achieve a strict Nash equilibrium with the coalition resilience 2. Thus, our protocol with immunity achieves the optimal coalition resilience with respect to both Nash and strict Nash equilibrium.

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if prAM ⊆ PNPthen there is a Boolean function in ENPthat requires circuits of size 2Ω(n). prAM is the class of promise problems that have Arthur-Merlin protocols, Pνρ is the class of functions that can be computed in deterministic polynomial-time with an NP oracle and ENPis its exponential analogue. The lower bound in the conclusion of our theorem suffices to construct very strong pseudorandom generators. We also show that the same conclusion holds if the problem of approximate counting the number of accepting paths of a nondeterministic Turing machine up to multiplicative factors can be done in nondeterministic polynomial-time. In other words, showing nondeterministic fully polynomial-time approximation schemes for #P-complete problems require proving exponential-size circuit lower bounds. A few works have already shown that if we can find efficient deterministic solutions to some specific tasks (or classes) that are known to be solvable efficiently by randomized algorithms (or proofs), then we obtain lower bounds against certain circuit models. These lower bounds were only with respect to polynomial-size circuits even if full derandomization is assumed' Thus they only implied fairly weak pseudorandom generators (if at all). A key ingredient in our proof is a connection between computational learning theory and exponential-size lower bounds. We show that the existence of deterministic learning algorithms with certain properties implies exponential-size lower bounds, where the complexity of the hard function is related to the complexity of the learning algorithm.

Hardcore functions have been used as a technical tool to construct secure cryptographic systems; however, little is known on their quantum counterpart, called quantum hardcore functions. With a new insight into fundamental properties of quantum hardcores, we present three new quantum hardcore functions for any (strong) quantum one-way function. We also give a “quantum” solution to Damgård's question [Advances in Cryptology, Lecture Notes in Comput. Sci. 403, Springer, Berlin, 1990, pp. 163–172] on a classical hardcore property of his pseudorandom generator by proving its quantum hardcore property. Our major technical tool is the new notion of quantum list-decoding of “classical” error-correcting codes (rather than “quantum” error-correcting codes), which is defined on the platform of computational complexity theory and computational cryptography (rather than information theory). In particular, we give a simple but powerful criterion that makes a polynomial-time computable classical block code (seen as a function) a quantum hardcore for all quantum one-way functions. On their own interest, we construct efficient quantum list-decoding algorithms for classical block codes whose associated quantum states (called codeword states) form a nearly phase-orthogonal basis.

No abstract available.