Concurrent Knowledge Extraction in Public-Key Models

Andrew Chi-Chih Yao, Moti Yung, Yunlei ZhaoJ. Cryptol 2016 · DOI · OpenReview

Abstract

This paper formalizes Concurrent Knowledge Extraction (CKE), a critical security property for cryptographic protocols operating in chaotic, concurrent network environments like the Internet. In the Bare Public-Key (BPK) model, traditional security measures often fail to prevent man-in-the-middle attacks where a malicious prover "malleates" a verifier's own public-key proofs. We provide new, constant-round protocols that are provably secure by ensuring that extracted knowledge is statistically independent of the verifier's secret information.

Introduction

In cryptography, a Zero-Knowledge Proof of Knowledge (ZKPOK) allows a prover to convince a verifier of their possession of a secret (a "witness") without revealing it. While well-understood in stand-alone settings, these proofs face significant challenges in concurrent environments where multiple sessions occur simultaneously. Specifically, in the Bare Public-Key (BPK) model, verifiers have registered public keys, creating a vulnerability: a malicious prover can act as a man-in-the-middle, intercepting a verifier’s proof of their secret key in one session and transforming it into a successful proof for a different statement in another session.

Formalizing Concurrent Knowledge Extraction (CKE)

The core challenge addressed is defining and achieving "knowledge extraction" when statements may be adaptively chosen based on the verifier's public keys. The authors introduce the concept of Knowledge Extraction Independence (KEI). For a proof to be valid, the witness extracted from a prover must be independent of the verifier's secret key. If the extracted witness depends on this secret, the prover has merely reflected the verifier's knowledge rather than demonstrating their own.

Proposed Protocol Structures

To achieve CKE, the paper proposes two primary protocol architectures: a generic version and a more efficient variant utilizing complexity leveraging.

Protocol diagrams for Generic and Efficient CZK-CKE constructions.

Generic CZK-CKE Protocol

This construction combines statistical Witness-Indistinguishable (WI) proofs with Strong WI. As shown in the protocol diagram, the prover is required to commit to their witness ($c_w = C(w)$) before the final proof stage, ensuring that their success is not a byproduct of session interleaving or malleability.

Efficient CZK-CKE Protocol

This variant introduces a double-commitment technique and novel complexity leveraging. By using two different security parameters, specific parts of the protocol are made "weak" enough for sub-exponential brute-force search during mathematical security proofs, while remaining secure against polynomial-time adversaries in practice. This prevents man-in-the-middle attacks by making it impossible to malleate messages without "knowing" the underlying values.

Key Results and Insights

The research establishes several foundational results:

  • Soundness vs. Extraction: The authors prove that "concurrent soundness" (inability to prove false statements) does not imply "concurrent knowledge extraction" (requirement that the prover knows the witness for a true statement). CKE is a strictly stronger property.
  • Constant-Round Efficiency: The proposed CZK-CKE protocols are the first to be provably secure while running in a fixed, small number of rounds (typically 6 to 9).
  • Practicality: The abstract protocols can be instantiated using standard number-theoretic problems like the Discrete Logarithm Problem (DLP), making them suitable for real-world systems.

Conclusion and Future Work

While providing a robust framework for CKE, the paper identifies several avenues for future research. Round-optimality remains an open question, as does the potential for non-black-box extraction techniques to offer different efficiency trade-offs. Additionally, extending these formulations to the "Bounded Player" model represents a promising direction for concurrent cryptography.

Summary updated

Abstract

Knowledge extraction is a fundamental notion, modeling machine possession of values (witnesses) in a computational complexity sense and enabling one to argue about the internal state of a party in a protocol without probing its internal secret state. However, when transactions are concurrent, say over the Internet, with players possessing public keys (as is common in cryptography), assuring that entities “know” what they claim to know, where adversaries may be well coordinated across different transactions, turns out to be much more subtle and in need of re-examination. In such settings, mixing the public-key structure as part of the language and statements is a natural adversarial strategy. Here, we investigate how to formally treat knowledge possession by parties interacting concurrently in the public-key model. More technically, we look into the relative power of the notion of “concurrent knowledge extraction” (CKE) for concurrent zero knowledge (CZK) in the bare public-key (BPK) model, where the language and statements being proved can be dynamically and adaptively chosen by the prover and may be possibly based on verifiers’ public keys. By concrete attacks against some existing natural protocols, we first show that concurrent soundness and normal arguments of knowledge do not guarantee concurrent verifier security in the public-key setting. Here, roughly speaking, concurrent verifier security says that the malicious concurrent prover should “know" all the witnesses to all the possibly public-key-related statements adaptively chosen and successfully proved in the concurrent sessions. These concrete attacks serve as a good motivation for understanding “possession of knowledge” for concurrent transactions with registered public keys, i.e., the subtleties of concurrent knowledge extraction in the public-key model. This motivates us to introduce and formalize the notion of CKE, along with clarifications of various subtleties. Two implementations are then presented for constant-round concurrently knowledge extractable concurrent zero-knowledge (CZK–CKE) argument for $$\mathcal {NP}$$ NP in the BPK model: One protocol is generic and based on standard polynomial-time assumptions, whereas the other protocol is computationally efficient and employs complexity leveraging in a novel way. Both protocols can be practically instantiated for some specific number-theoretic languages without going through general $$\mathcal {NP}$$ NP -reductions. Of independent interest are the discussions about the subtleties surrounding the fundamental structure of Feige–Shamir zero knowledge in the BPK model.
BibTeX
@article{yao2016concurrent,
  author = {Andrew Chi-Chih Yao and Moti Yung and Yunlei Zhao},
  title = {{Concurrent Knowledge Extraction in Public-Key Models}},
  journal = {J. Cryptol.},
  year = {2016},
  doi = {10.1007/s00145-014-9191-z},
}

Loading related content...

Figure