| Abstract: |
Cloud computing centralises storage and computation at a scale no single organisation can protect with its own perimeter, and two of its foundational guarantees confidentiality of data in transit and correctness of outsourced computation - rest on public-key cryptography that a sufficiently large quantum computer can break. This review synthesises past work, from Shor's algorithm to the latest standardisation and deployment studies, on post-quantum cryptography (PQC) and verifiable computing (VC) for cloud systems. The review spans 2009-2023 and codes each artefact by assumption, trust model, cost and maturity. We first taxonomise the lattice-, code- and hash-based primitives produced by the NIST process, including ML-KEM, ML-DSA, SLH-DSA, the draft FN-DSA and HQC, and examine their integration into TLS, X.509 and storage stacks. We then survey the verifiable computing lineage - interactive proofs, probabilistically checkable proofs, succinct non-interactive arguments, homomorphic MACs and verifiable fully homomorphic encryption - and analyse how each family composes with quantum-safe channels, identities and key management. Drawing on a structured corpus of standards, constructions and measurement studies, a critical analysis of past work exposes recurring weaknesses: evaluation bias towards benign benchmarks, neglected side-channel leakage in reference implementations, incomplete treatment of hybrid downgrade risk, unnamed trust assumptions, and the absence of end-to-end quantum-safe publicly verifiable cloud prototypes. Finally, we discuss open problems - cryptographic agility, proof-system agility, cost models for verifiable encrypted computation and migration governance under Mosca's theorem - and outline a phased roadmap towards quantum-safe verifiable clouds. |
