COMPLEXITY-STYLE RESOURCES IN CRYPTOGRAPHY

Abstract. Previously, the author has developed a framework within which to quantify and compare the resources consumed during computational—especially unconventional computational—processes (adding to the familiar resources of run-time and memory space such non-standard resources as precision and energy); it is natural and beneficial in this framework to employ various complexity-theoretic tools and techniques. Here, we seek an analogous treat-ment not of computational processes but of cryptographic protocols and similar, so as to be able to apply the existing arsenal of complexity-theoretic methods in new ways, in the derivation and verification of protocols in a wider, crypto-graphic context. Accordingly, we advocate a framework in which one may view as resources the costs—which may be related to computation, communication, information (including side-channel information) or availability of primitives, for example—incurred when executing cryptographic protocols, coin-tossing schemes, etc. The ultimate aim is to formulate as a resource, and be able to analyse complexity-theoretically, the security of these protocols and schemes. 1