Certified Randomness with Optimal Rate

The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate the ratio of min-entropy to bitlength is 1. However, existing protocols for...

Classical Verifier Position Verification from Non-Local Games

Secure position verification certifies that a remote prover occupies a claimed location, a task that is provably impossible with classical resources alone against colluding adversaries. Most existing quantum position verification schemes require transmitting quantum states between verifiers and...

Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release...

An Operator-Norm Approach to Security with Quantum Advice

Non-uniform security allows an adversary to receive bounded advice about an oracle before attempting a fresh challenge. This captures the most realistic attacks and has already been studied extensively in prior work. In this work, we introduce an operator-norm approach for non-uniform security in...

Certified Randomness without Structure against Shallow-Query Adversaries

In a recent breakthrough, Yamakawa and Zhandry J. ACM 2024 constructed a proof of quantumness in the quantum random oracle model QROM in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample the...

Cryptanalysis of LC-MUME: a Lightweight Certificateless Multi-User Matchmaking Encryption for Mobile Devices

Yang et al. proposed a lightweight certificateless multiuser matchmaking encryption LC-MUME scheme for mobile devices, published in IEEE Transactions on Information Forensics and Security TIFS DOI: 10.1109/TIFS.2023.3321961. Their construction aims to reduce computational and communication overhe...

Black-Box Crypto Is Useless for Pseudorandom Codes

A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reduction...