Akira Takahashi

Time-based cryptographic primitives unlock efficient realizations of several functionalities including Randomness Beacons, Proof of Replicated Storage, Encryption to the Future, and MultiParty Computation with partial fairness. Existing constructions derive time-delays from the average hardness of sequential computational problems, a measure that is susceptible to algorithmic and hardware improvements. Therefore time-based systems secure at deployment date are at constant risk to turn insecure. A way to combat this intrinsic drawback is to ground time-delays on assumptions that are not affected by scientific advancement such as trust (in a subset of parties) and physical communication delays. This paper builds on Baum et al.’s (SCN 2024) work on “CaSCaDE: (Time-Based) Cryptography from Space Communications DElay”, and provides concrete realizations and detailed security proofs of: a Time Lock Puzzle, a stateless Verifiable Random Function, a Delay Encryption scheme, and a Randomness Beacon from proofs of Sequential Communication Delays (SCD) and trust assumptions on subsets of parties. Notably, our SCD-based Delay Encryption construction constitutes the first alternative to existing supersingular isogenies Delay Encryption schemes.

Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations. In this work, we propose a novel framework that realizes VE protocols using zero-knowledge proof systems based on the MPC-in-the-head paradigm (Ishai et al. STOC 2007). Our generic compiler can turn a large class of zero-knowledge proofs into secure VE protocols for any secure public-key encryption scheme with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme. Our framework is versatile: because the circuit proven by the MPC-in-the-head prover is decoupled from a complex encryption function, the work of the prover is focused on proving the encrypted data satisfies the relation, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about the encrypted data and encryption functions. We then consider concrete applications, to demonstrate the efficiency of our framework, by first giving a new approach and implementation to verifiably encrypt discrete logarithms in any prime order group more efficiently than was previously known. Then we give the first practical verifiable encryption scheme for AES keys with post-quantum security, along with an implementation and benchmarks.