International Association
for Cryptologic Research

Public-coin protocols are cryptographic protocols in which all messages sent by a specific party (typically the receiver or verifier) consist solely of random bits. These protocols have been extensively studied in the classical setting due to their advantageous properties in several scenarios, such as the parallel repetition of interactive arguments, and the design of secure multi-party computation with low round complexity, among others. Curiously, post-quantum constructions of public-coin protocols remain limited, particularly when optimization is sought in additional factors like round complexity or hardness assumptions. We introduce the concept of almost-total puzzles, a novel cryptographic primitive characterized by two key properties: (i) hardness against any efficient adversary, and (ii) an ``almost-total'' guarantee of the existence of solutions, even when the puzzle generator is malicious. We demonstrate that this primitive can be derived from one-way functions in public-coin, requiring only two rounds. By leveraging this primitive, we obtain a family of new public-coin results in both the classical and post-quantum settings, based on the minimal assumption of (post-quantum) one-way functions, including: five-round post-quantum extractable commitments and witness-indistinguishable arguments of knowledge, where the (knowledge) extractors achieve the coherently expected quantum-polynomial-time ($\EQPT_c$) simulation proposed by Lombardi, Ma, and Spooner [FOCS'22]; five-round classical extractable commitments that do not suffer from over extraction; five-round classical delayed-input strong witness-indistinguishable arguments of knowledge, and delayed-input witness-hiding arguments of knowledge; the five-round post-quantum analogue of the last item, but with the difference that (1) the input can be delayed until the third round, and (2) post-quantum arguments of knowledge are again defined w.r.t.\ $\EQPT_c$-simulation; $O(\log^* \secpar)$-round post-quantum non-malleable commitments.

We study secure computation in the plain model against fully concurrent quantum adversaries. While classical simulation-based notions --- such as Super-Polynomial Simulation (SPS) security --- have enabled meaningful forms of concurrent security, very little is known about their quantum counterparts, particularly under standard polynomial-time hardness assumptions. Our main result is the first post-quantum two-party computation protocol that achieves concurrent SPS security, based solely on the minimal assumption of semi-honest post-quantum oblivious transfer (PQ-OT). Moreover, our protocol has constant round complexity when the underlying PQ-OT protocol is constant-round. This can be viewed as a post-quantum analog of the classical result by Garg et al. [Eurocrypt'12], but with a crucial difference: our security proof completely avoids rewinding, making it suitable for quantum settings where rewinding is notoriously challenging due to the no-cloning principle. By leveraging a compiler of Bartusek et al. [Crypto'21], we further extend our result to the fully quantum setting, yielding the first constant-round concurrent SPS two-party computation for {\em quantum} functionalities in the plain model. Additionally, we construct a two-round, public-coin, concurrent SPS post-quantum zero-knowledge protocol for languages in $\NP \cap \coNP$, under the quantum polynomial-time hardness of LWE. This result is notable even in the classical setting.