Paper 2019/807

Provable Security for PKI Schemes

Hemi Leibowitz and Amir Herzberg and Ewa Syta

Abstract

In this work we apply the systematic approach of game-based security specifications and proofs by reductions, to the design and evaluation of public key infrastructure (PKI) schemes. The importance of rigorous definitions and reduction based proofs for cryptographic primitives is well-recognized, but this approach has not yet been applied to PKI schemes, despite their importance and pervasive use. This is most problematic in case of the advanced PKI properties such as transparency, revocation transparency and non-equivocation, which are nontrivial to define, analyze and prove. In response, we propose the first Public Identity Infrastructure (PII) framework that offers rigorous yet flexible game-based security for PKI schemes. We show the feasibility of the PII framework by presenting United-$\Large \pi$, a simple, efficient and provably secure ‘proof of concept’ PKI scheme, that provably achieves all security properties we define.