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: