Complexity Analysis of Representative Cryptographic Protocols:

Abstract

Cryptographic protocols are evaluated not only by the security properties they achieve, but also by the resources required to execute them. Unlike conventional algorithm analysis, where a single running-time function may be sufficient, protocol analysis usually separates computational complexity, bit complexity, communication complexity, storage complexity, and round complexity. This article develops a systematic methodology for such analysis through three representative case studies: the Schnorr zero-knowledge proof of knowledge, a Diffie–Hellman-based one-out-of-two oblivious-transfer protocol, and Regev-style public-key encryption based on the Learning With Errors problem. For each construction, the protocol is stated formally, correctness is derived, and the dominant computational, communication, and memory costs are calculated step by step. The examples illustrate three qualitatively different bottlenecks: group exponentiation in discrete-logarithm protocols, amortized public-key cost in oblivious transfer, and dense matrix–vector arithmetic in lattice-based cryptography.