  Digital authentication is a mature field, offering a range of solutions with
rigorous mathematical guarantees. Nevertheless, paper documents, where
cryptographic techniques are not directly applicable, are still widely utilized
due to usability and legal reasons. We propose a novel approach to
authenticating paper documents using smartphones by taking short videos of
them. Our solution combines cryptographic and image comparison techniques to
detect and highlight subtle semantic-changing attacks on rich documents,
containing text and graphics, that could go unnoticed by humans. We rigorously
analyze our approach, proving that it is secure against strong adversaries
capable of compromising different system components. We also measure its
accuracy empirically on a set of 128 videos of paper documents, half containing
subtle forgeries. Our algorithm finds all forgeries accurately (no false
alarms) after analyzing 5.13 frames on average (corresponding to 1.28 seconds
of video). Highlighted regions are large enough to be visible to users, but
small enough to precisely locate forgeries. Thus, our approach provides a
promising way for users to authenticate paper documents using conventional
smartphones under realistic conditions.
