Security assumptions in post-quantum cryptography

Thesis

This thesis analyses the assumptions present in security proofs of post-quantum cryptosystems using Koblitz and Menezes' critique to guide the focus points. The classical analysis focusses in particular on isogeny-based and multivariate polynomial cryptosystems. Firstly, we present attacks against hardness assumptions on derivative computational problems arising in protocols for isogeny-based undeniable signature schemes. Secondly, we provide upper bounds on the solving degree of over-determined systems of n+l multivariate polynomials in n variables as an alternative to the degree of regularity, which gives a heuristic upper bound. We finish with an analysis of the resources of a quantum adversary, providing an improved method for quantum gate approximation that gives shorter sequences by a factor of 9/7.

Authors: Minko, R

• DOI: 10.5287/ora-wr0av4de6
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: cryptography
• Subjects: Mathematics; Cyber security