On the Necessary and Sufficient Assumptions for UC Computation

Ivan Damgård, Jesper Buus Nielsen, Claudio Orlandi

Abstract

Universally Composable (UC) security represents the gold standard for protocol security, ensuring robustness even under concurrent execution with unknown protocols. However, achieving UC security is impossible in a "plain" model where parties share no prior trusted information. This paper maps the minimal setup assumptions and mathematical primitives required for UC computation. The authors demonstrate that minimal key-registration models enable UC-secure commitments and zero-knowledge proofs using only one-way functions (OWFs), bridging the gap between high-level security and the "Minicrypt" world.

Introduction

In theoretical cryptography, the Universally Composable (UC) security framework provides the strongest guarantees for protocol security. Despite its benefits, it is mathematically impossible to achieve in a "plain" model. Consequently, researchers must rely on setup assumptions, such as a Common Reference String (CRS).

This paper addresses two fundamental questions:

  1. How minimal can a setup be? Can UC security be achieved with a setup that is nearly "useless"?
  2. What are the necessary mathematical assumptions? Is heavy-duty public-key encryption required, or are simple one-way functions (OWFs) sufficient?

The authors specifically contrast the Common Reference String (CRS) model, where all parties observe a trusted string, with the Key-Registration Authority (KRA) model, where parties register public keys.

Methods

The authors define and analyze several variations of setup models, ranging from "Chosen" (where the protocol defines the setup) to "Any" (where the adversary can pick the setup distribution, provided it remains "meaningful").

Key technical contributions include:

  • $Σ$-Protocols and OR-Constructions: Utilizing standard zero-knowledge building blocks to prove statements such as "I followed the protocol OR I know the secret key of the registration authority."
  • UC-Compilers: Developing a method to "compile" protocols secure in a stand-alone setting into UC-secure protocols by leveraging the KRA setup.
  • Authenticated Channels from Scratch: Showing how to build authenticated communication in a KRA model where public keys lack special structure (e.g., they are simply outputs of a one-way function).

Key Insights and Ideas

UC Security in Minicrypt

Traditionally, UC-secure tasks were believed to require "Public-key" primitives like RSA or Diffie-Hellman. This work proves that in the KRA model, One-Way Functions (Minicrypt) are sufficient for UC commitments and zero-knowledge proofs.

The "Uselessness" Threshold

The authors define a "minimal meaningful KRA" as one where computing a secret key from a public key is computationally hard. They prove that any such non-trivial KRA is sufficient for full UC computation, provided stand-alone oblivious transfer (SA-OT) exists.

Setup Separation

A fundamental difference exists between CRS and KRA models. In the CRS model, Oblivious Transfer is a prerequisite for UC commitments. In the KRA model, only One-Way Functions are needed. This demonstrates that the choice of setup model fundamentally alters the computational "price" of security.

Structureless Public Keys

The paper demonstrates that fancy digital signatures are not required for authentication. If a public key is defined as $y = f(x)$, zero-knowledge proofs of knowledge of $x$ can be used to establish authenticated channels.

Key Results

The paper provides a comprehensive mapping of the feasibility of UC primitives across different models, illustrating where assumptions like OWFs or SA-OT are necessary or sufficient.

Implication diagrams for UC primitives across different setup models.

The core findings are summarized as follows:

  • Full Feasibility: If a "meaningful" KRA exists and stand-alone Oblivious Transfer (SA-OT) is possible, then any polynomial-time functionality can be UC-securely computed.
  • OWF Sufficiency: In the KRA model, One-Way Functions are sufficient for UC-Commitment and UC-Zero Knowledge.
  • Necessary Assumptions: SA-OT is a necessary assumption for UC-Commitment in the CRS model, but notably, it is not required in the KRA model.

Limitations and Future Work

  • Static vs. Adaptive Security: The current proofs focus on static adversaries who corrupt parties before the protocol begins. Extending these results to adaptive adversaries remains a significant challenge.
  • The C-CRS Gap: Questions regarding the "Chosen CRS" model (where the string has specific mathematical structure) remain open. These may require "Knowledge of Exponent" assumptions.
  • Non-Black-Box Techniques: Some sufficiency results rely on non-black-box constructions, which can be computationally expensive. Finding efficient black-box alternatives is a key area for future research.

Summary updated

BibTeX
@inproceedings{damgard2010necessary,
  author = {Ivan Damgård and Jesper Buus Nielsen and Claudio Orlandi},
  title = {{On the Necessary and Sufficient Assumptions for UC Computation}},
  booktitle = {TCC},
  year = {2010},
  doi = {10.1007/978-3-642-11799-2\_8},
}
Figure