Regev Encryption and Public-Key Encryption of Qubits
Stub. The formal definition of public-key encryption and its security notions (single- vs. multi-message); Regev's LWE-based public-key encryption scheme, with correctness and security proofs; and extending it to encrypt qubits under a public key rather than only a shared private key.
Corresponds to Chapter 18. Reviews the formal definition of public-key encryption and the single-vs-multi-message security distinction (compare public-key-encryption-schemes for the classical RSA/ElGamal treatment of the same definitions) before specializing to Regev encryption: a public-key scheme built directly from the LWE assumption, whose public key is a set of noisy linear equations and whose correctness relies on the same noise-tolerance argument used for the private-key LWE scheme earlier. Extends this to public-key encryption of qubits — using a public (rather than shared secret) key to encrypt a quantum state, still built on the QOTP idea but now needing the public key to somehow let the receiver (and only the receiver) recover the right Pauli corrections, which sets up the homomorphic-evaluation constructions of fully-homomorphic-encryption-classical-and-quantum.
Outline (TODO — flesh out each)
- Definition of public-key encryption
- Multi-message vs. single-message security
- Regev encryption — construction, correctness, security
- Public-key encryption of qubits — correctness and security