Date of Degree


Document Type


Degree Name



Computer Science


Rosario Gennaro

Committee Members

Nelly Fazio

William E. Skeith

Tal Rabin

Subject Categories

Information Security


cryptography, security


In this dissertation we investigate Witness-Authenticated Key Exchange (WAKE), a key agreement protocol in which each party is authenticated through knowledge of a witness to an arbitrary NP statement. We provide both game-based and universally composable definitions. Thereby, this thesis presents solutions for the most flexible and general method of authentication for group key exchange, providing simple constructions from (succinct) signatures of knowledge (SOK) and a two round UC-secure protocol.

After a discussion of flaws in previous definitions for WAKE we supply a new and improved game-based definition along with the first definition for witness-authenticated key exchange between groups of parties. The game-based model permits a modular and intuitive approach to WAKE security; we explicitly define each property that a WAKE protocol should achieve in order to be considered secure.

First, we specify the multi-party definition to the two-party unilaterally-authenticated case and provide a construction from any key encapsulation mechanism and SOK. We present a compiler which produces a fully secure WAKE protocol from any standard passively secure key exchange, using succinct signatures of knowledge to introduce witness-authentication. As the result of applying our compiler to the Burmester-Desmedt key exchange we provide a simple three-round WAKE construction satisfying the game-based security requirements. An optimization of this construction is also provided, which allows users to shift heavy computations to an offline phase. Benchmark estimates are provided for the optimized two-party unilaterally authenticated protocol.

We initiate the study of universally composable (UC) WAKE and provide an ideal functionality for WAKE in the UC framework. Security in the UC framework guarantees that the protocol remains secure when arbitrarily composed with other protocols, for example those that would use the secret keys generated by the WAKE. We prove that the compiled protocol above can be transformed again to UC-realize this ideal functionality in the SOK-hybrid model. We present a two-round group WAKE protocol in the SOK-hybrid model and prove that protocol secure against adaptive, malicious adversaries over an adversarially controlled network.

Finally, we compare the game-based and UC definitions provided and prove that game-based WAKE, additionally satisfying straightline black-box extraction, is equivalent to composable WAKE.

This work is embargoed and will be available for download on Thursday, March 30, 2023

Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.

Non-GC Users:
See the GC’s lending policies to learn more.