Paper documents, where digital signatures are not directly applicable, are still widely utilized due to usability and legal reasons. We propose a novel approach to authenticating paper documents by taking short videos of them with smartphones. Our solution combines cryptographic and image comparison techniques to detect and highlight semantic-changing attacks on rich documents, containing text and graphics. We provide geometrical arguments for the security of our novel comparison algorithm, and prove that its combination with a cryptographic protocol is secure against strong adversaries capable of compromising different system components. We also measure its accuracy on a set of 128 videos of paper documents and a set of 960 synthetically generated warped documents, half containing subtle forgeries. Our algorithm finds all forgeries accurately with no false positives. The highlighted regions are large enough to be visible to users, but small enough to precisely locate forgeries.