CWI Cryptology Group

Abstract: The measure-and-reprogram technique (Don, Fehr, Majenz and Schaffner, Crypto 2019) is a proof technique for security reductions in the quantum random-oracle model (QROM). In the original application, the technique is used to prove the Fiat-Shamir transformation secure in the QROM. For the FS reduction, we need to inject a challenge from the sigma-protocol challenger into one of the adversary's queries (chosen at random), and hope that the adversary will solve the challenge for us. In the QROM, apart from reprogramming the oracle, this strategy requires us to measure the chosen query. The obstacle to overcome here is then the disturbance to the adversary's quantum state caused by the measurement, which in general makes it hard to predict the adversary's behavior from the measurement on.
In this talk we will recap the technique and give an intuition for why, in the right context, we are able to bound the disturbance mentioned above. We will then highlight some more recent results that apply the technique in a conceptually novel way. In particular, we will see that it can be applied in contexts where challenge injection is not the goal.

Abstract: The task of non-local quantum computation (NLQC) involves having two parties, Alice and Bob, jointly performing a quantum operation used a single round of simultaneous communication and pre-shared entanglement. This is a scenario which is studied in several settings and arises naturally in the context of quantum position verification. One well-studied class of such tasks, f-routing, involves a mixture of classical information and a single quantum bit that has to be routed somewhere as a function of the classical information.
In information-theoretic cryptography, the conditional disclosure of secrets (CDS) task has been previously studied in the context of private information retrieval. I will present recent results which show that the natural quantum analogue to CDS turns out to be equivalent to f-routing, connecting these disparate topics and letting us translate results in both directions.

Abstract: Compressed oracles (Zhandry, Crypto 2019) are a powerful technique to reason about quantum random oracles, enabling a sort of lazy sampling in the presence of superposition queries. A long-standing open question is whether a similar technique can also be used to reason about random (efficiently invertible) permutations.
In this work, we make a step towards answering this question. We first define the compressed permutation oracle and illustrate its use. While the soundness of this technique (i.e., the indistinguishability from a random permutation) remains a conjecture, we show a curious 2-for-1 theorem: If we use the compressed permutation oracle methodology to show that some construction (e.g., Luby-Rackoff) implements a random permutation (or strong qPRP), then we get the fact that this methodology is actually sound for free.