Almost-Total Puzzles and Their Applications

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^∗λ)-round post-quantum non-malleable commitments. 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^∗λ)-round post-quantum non-malleable commitments.