Concurrent Knowledge Extraction in the Public-Key Model

Andrew C. Yao, Moti Yung, Yunlei Zhao

TL;DR

This paper introduces and formalizes "Concurrent Knowledge Extraction" (CKE) in the public-key model, a crucial security notion for concurrent cryptographic protocols. They demonstrate that existing concurrent zero-knowledge protocols are vulnerable to man-in-the-middle attacks and present both generic and efficient constructions for CKE arguments in the public-key model.

What Problem Does This Paper Address?

In cryptography, "proof of knowledge" (POK) is a fundamental concept that allows a prover to convince a verifier that they possess a secret witness to a statement, without revealing the witness itself. Traditional POK security is analyzed in a "stand-alone" or sequential setting. However, modern cryptographic systems, especially those operating over the internet, often involve concurrent interactions where multiple instances of a protocol run simultaneously.

The challenge arises when these protocols use public-key cryptography, where parties have registered public keys. In such scenarios, adversaries can potentially coordinate across different concurrent sessions, leading to subtle security vulnerabilities. Specifically, existing concurrent zero-knowledge (CZK) protocols, even those with concurrent soundness, might fail to guarantee that a prover truly knows what they claim to know. This is because a malicious prover could potentially exploit the public-key infrastructure or manipulate interactions across sessions to appear knowledgeable without possessing the actual witness. This paper addresses this gap by formalizing and achieving "Concurrent Knowledge Extraction" (CKE) in the public-key model, ensuring that even in concurrent settings, a prover's claimed knowledge can be extracted.

Methods

The paper introduces and formalizes the notion of Concurrent Knowledge Extraction (CKE) in the public-key model. This new security notion aims to capture the idea that if a malicious prover can convince a verifier of a statement in a concurrent setting, then a knowledge extractor should be able to extract a witness for that statement. A key aspect of their formulation is Knowledge Extraction Independence (KEI), which ensures that the extracted witness is independent of the verifier's secret key.

They then present two main constructions:

  1. Generic CZK-CKE: This construction is based on standard hardness assumptions and uses a composition of existing cryptographic primitives, including a statistical Witness Indistinguishable (WI) argument and a trapdoor commitment scheme.
  2. Efficient CZK-CKE: This construction aims for better efficiency by employing a novel technique called complexity leveraging. This involves using a commitment scheme that relies on a slightly weaker hardness assumption (sub-exponentially secure) for a specific component, which helps to frustrate concurrent man-in-the-middle attacks. They also introduce the concept of double commitments to simplify the protocol structure and achieve CZK simulation without relying on strong WI.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Vulnerability of existing CZK protocols: The paper demonstrates concrete "man-in-the-middle" (MIM) attacks that exploit concurrent interactions in existing CZK protocols within the public-key model. This highlights that concurrent soundness alone is insufficient for verifier security in this setting.
  • Formalization of CKE: The introduction of Concurrent Knowledge Extraction (CKE) provides a precise definition for ensuring that a prover genuinely possesses knowledge even in concurrent public-key settings. The KEI property is crucial for this formalization.
  • Complexity Leveraging as a Tool Against MIM: The paper showcases a novel application of complexity leveraging not just for efficiency but specifically to thwart sophisticated concurrent MIM adversaries. This suggests a new paradigm for designing secure protocols in adversarial environments.
  • Necessity of Double Commitments: The efficient construction relies on double commitments to bypass the need for strong WI in CZK simulation, simplifying the protocol while maintaining security.

Key Results

  • The paper presents a generic construction for constant-round CZK-CKE arguments for NP in the BPK model, based on standard hardness assumptions.
  • They propose an efficient construction for constant-round CZK-CKE arguments for NP in the BPK model, which achieves better practical performance by employing complexity leveraging.
  • They prove that CKE is strictly stronger than concurrent soundness in the public-key model, meaning protocols that are concurrently sound do not necessarily satisfy CKE.
  • The paper provides concrete attacks demonstrating the vulnerability of protocols without double commitments (specifically, variants of [78, 21] and [78]) to concurrent knowledge extraction.

Limitations and Future Work

  • Complexity Leveraging: While the complexity leveraging in the efficient construction is minimal and only applies to a specific component (csk), it relies on a sub-exponential hardness assumption for that component. The authors note that this is a "novel paradigm" and suggest it could be applied in other scenarios.
  • Practical Instantiations: The paper discusses practical instantiations for specific number-theoretic languages (like DLP), but further work could explore broader applicability.
  • Further Exploration of Subtleties: The paper delves into the subtleties of achieving CKE without complexity leveraging, indicating that this remains an area for further research.
  • Generalization: The authors mention that their formulations and proofs can be extended to more general settings, such as adaptive language selection for each session, which could be a direction for future work.

Summary updated

BibTeX
@inproceedings{yao2009concurrent,
  author = {Andrew C. Yao and Moti Yung and Yunlei Zhao},
  title = {{Concurrent Knowledge Extraction in the Public-Key Model}},
  booktitle = {ICALP},
  year = {2009},
  url = {https://openreview.net/forum?id=S0fcwuv5La},
}
Figure