PaperlayerView exact revision on arXiv

Source-linked AI summary

DECO: Liberating Web Data Using Decentralized Oracles for TLS

Fan Zhang, Sai Krishna Deepak Maram, Harjasleen Malvai, Steven Goldfeder, Ari Juels

arXiv:1909.00938v6cs.CR

TL;DR

TLS protects private web data but does not let users prove its provenance to third parties, and existing solutions require undesirable trust or server changes. DECO uses a three-party handshake and privacy-preserving proofs to authenticate TLS data and statements about it without trusted hardware or server modifications. The implemented system supports three applications and reports practical proof and execution times, while its use raises site-specific legal and compliance questions.

  • Problem

    TLS does not let users prove to third parties that accessed data came from a particular website, restricting exportability and data portability.

  • Method

    DECO creates unforgeable commitments to TLS session data through a three-party handshake and supports selective opening and zero-knowledge statements.

  • Results

    DECO is implemented for modern TLS without trusted hardware or server-side modifications, with three applications and 3–13s zero-knowledge proof generation.

  • Takeaways & Limitations

    DECO makes private TLS data accessible to applications such as smart contracts while preserving authenticity and privacy assurances.

  • Takeaways & Limitations

    DECO’s compliance with a website’s terms of service remains site- and application-specific, and incorrect attestations can have legal and performance implications.

Abstract

from arXiv · show

Thanks to the widespread deployment of TLS, users can access private data over channels with end-to-end confidentiality and integrity. What they cannot do, however, is prove to third parties the {\em provenance} of such data, i.e., that it genuinely came from a particular website. Existing approaches either introduce undesirable trust assumptions or require server-side modifications. As a result, the value of users' private data is locked up in its point of origin. Users cannot export their data with preserved integrity to other applications without help and permission from the current data holder. We propose DECO (short for \underline{dec}entralized \underline{o}racle) to address the above problems. DECO allows users to prove that a piece of data accessed via TLS came from a particular website and optionally prove statements about such data in zero-knowledge, keeping the data itself secret. DECO is the first such system that works without trusted hardware or server-side modifications. DECO can liberate data from centralized web-service silos, making it accessible to a rich spectrum of applications. To demonstrate the power of DECO, we implement three applications that are hard to achieve without it: a private financial instrument using smart contracts, converting legacy credentials to anonymous credentials, and verifiable claims against price discrimination.

1 INTRODUCTION

DECO addresses TLS’s inability to prove web-data provenance to third parties without server cooperation or trusted hardware. It combines provenance proofs, privacy-preserving statements, and practical applications for exporting TLS-protected data.

  • TLS protects confidentiality and integrity but does not let users prove that accessed data came from a particular website.
  • Existing oracle schemes rely on deprecated TLS, trusted hardware, or server-side cooperation, limiting compatibility, trust, or user-controlled export.
  • 1.1 DECO: DECO is designed for standard TLS without per-website support, server cooperation, or trusted hardware, and supports applications including smart contracts and anonymous credentials.
  • 1.2 Technical challenges: DECO uses a three-party handshake to create an unforgeable commitment to TLS session data that the verifier can authenticate to the server.
  • 1.2 Technical challenges: DECO supports selective opening, allowing users to reveal or redact only substrings while proving statements about committed TLS data in zero-knowledge.
  • 1.3 Implementation and evaluation: 3–13s are required to generate zero-knowledge proofs for the demonstrated applications, while WAN online time is 2.85s for the handshake and 2.52s for query execution.

2 BACKGROUND

The paper builds on TLS, secure computation, and protocol choices suited to different operations. TLS establishes shared keys and protects records, while 2PC enables joint computation without revealing private inputs.

  • TLS uses a handshake to establish shared client-server keys, followed by a record protocol providing confidentiality and integrity with symmetric cryptography.
  • TLS records fragment application data, optionally compress it, apply a MAC, encrypt it, and later decrypt, verify, decompress, and reassemble it.
  • Secure multi-party computation lets parties jointly compute a function of private inputs while revealing no information beyond the output; 2PC is its two-party case.
  • Garbled circuits suit bitwise operations, while secret-sharing protocols suit arithmetic operations, so the paper uses different optimized techniques for each.

3 OVERVIEW

DECO formalizes decentralized oracles that let a prover show TLS data came from a particular website and prove statements about it while keeping private data and inputs secret. Its three-party protocol uses a server-transparent handshake, query execution, and proof generation, with selective opening and confidential parsing for efficient proofs.

  • 3.1 Problem statement: Decentralized oracles: DECO targets TLS data provenance without trusted hardware, server cooperation, or server-side modifications.The server continues running standard TLS, while the verifier receives provenance and statement assurances without controlling the web server.
  • 3.1 Problem statement: Decentralized oracles: The ideal oracle accepts a prover’s secret parameter and query template, retrieves the server response, and returns a statement evaluation and data source to the verifier.The query template combines the prover’s secret with verifier-specified public parameters, and the prover can prove the query was formed correctly without revealing the secret.
  • 3.2 Notation and definitions: DECO provides prover-integrity, verifier-integrity, and privacy: provenance cannot be forged, responses remain server-authentic, and the verifier learns only public information and the statement evaluation.These guarantees are defined for executions where either the prover or verifier may be corrupted.
  • 3.4 Overview of DECO: DECO’s three phases establish secret-shared session keys, execute a standard-TLS query with verifier assistance, and generate proofs after the prover commits to the query and response.The handshake is transparent to the server; the verifier reveals its key share only after commitment.
  • 3.4.3 Proof generation.: Selective opening reveals or redacts only chosen transcript substrings, while zero-knowledge two-stage parsing proves constraints on locally extracted substrings.For unique-key web API grammars, the two-stage approach yields more efficient proofs than generic techniques.

4 THE DECO PROTOCOL

DECO uses a transparent three-party TLS handshake and specialized 2PC protocols to secret-share session keys, privately execute queries, and support provenance proofs. Its security is formalized under discrete-log and random-oracle assumptions, while optimizations reduce key-derivation and query-processing costs.

  • Three-party handshake: The three-party handshake secret-shares TLS session keys between prover and verifier without requiring server changes.ECDHE shares are combined and processed through the TLS-PRF to derive secret-shared session keys.
  • Efficient key derivation: DECO converts elliptic-curve shares into field shares before TLS-PRF evaluation, reducing addition from over 900,000 to approximately 768 AND gates.The ECtF conversion enables field addition with approximately 3|p| AND gates for a 256-bit field.
  • Private query execution: Custom 2PC protocols construct TLS records for private queries while keeping the query hidden from the verifier.For CBC-HMAC, the parties compute the HMAC tag jointly and the prover encrypts the query locally; generic 2PC would be expensive for large queries.
  • Security: ProtDECO UC-securely realizes the oracle functionality against static malicious adversaries with abort under discrete-log and random-oracle assumptions.The security theorem assumes a hard discrete-log problem and treats the SHA-256 compression function as a random oracle.

5 PROOF GENERATION

DECO’s proof-generation layer provides selective opening and context integrity for TLS responses. It exploits record structure and grammar-aware parsing to reveal or redact useful substrings while preserving provenance and limiting zero-knowledge costs.

  • Selective opening: Selective opening lets the prover reveal one plaintext chunk or redact selected chunks without exposing the rest of the TLS record.Reveal mode proves a chosen chunk, while Redact mode proves the remaining plaintext is the committed record with selected chunks removed.
  • Selective opening: CBC-HMAC reduces verifiable decryption from up to 1027 AES invocations to 3 by exploiting MAC-then-encrypt structure.The proof checks the encrypted tag blocks and verifies the MAC over the revealed plaintext.
  • Cipher-suite trade-offs: CBC-HMAC supports record-level revealing and block-level redaction, whereas GCM supports efficient block-level revealing.Selective opening can also preprocess data before a later zero-knowledge proof by reducing its input length.
  • Context integrity: Context integrity verifies that a revealed substring appears at an allowed parse-tree position in a structured TLS response.The verifier specifies permissible paths, and CTX_G checks whether the substring is yielded by a corresponding subtree.
  • Context integrity: Two-stage parsing preprocesses the full response and proves context integrity on a usually smaller transformed response.The approach assumes a shared unambiguous grammar, with JSON and HTML given as examples.

6 APPLICATIONS

DECO supports three applications: confidential smart-contract financial instruments, anonymous proofs from legacy credentials, and privacy-preserving claims about price discrimination. The applications use commitments, zero-knowledge proofs, and selective disclosure to verify web data while concealing sensitive details.

  • Applications: The applications demonstrate DECO’s use for confidential financial instruments, anonymous credentials, and verifiable price-discrimination claims.These applications exercise DECO’s oracle-based capabilities across smart contracts, credential proofs, and consumer reporting.
  • Confidential financial instruments: DECO supports a confidential binary option in which Alice proves a stock-price outcome to an oracle without revealing the instrument’s details.The option is specified by an asset, threshold price, and settlement date; the oracle returns a signed statement after verification.
  • Confidential financial instruments: The binary-option protocol commits the asset, threshold, and settlement date, then proves that retrieved data matches those commitments and the winning condition.The proof checks the response’s asset, price, and date, while the oracle signs the contract identifier after successful verification.
  • Anonymous credentials: Age proof: DECO converts web-based legacy credentials into anonymous credentials without server-side support or trusted hardware.The paper demonstrates age-over-18 proofs from demographic credentials stored on a university website.
  • Privacy-preserving price discrimination: DECO enables buyers to prove that an advertised price exceeds a threshold while hiding sensitive information such as their name and address.The implementation uses AES-GCM and reveals only necessary order details and the request URL.

7 IMPLEMENTATION AND EVALUATION

The implementation integrates DECO’s handshake, query-execution, and zero-knowledge components with TLS and evaluates them across protocols and applications. Results show practical performance, with WAN online processing and application proofs taking seconds, while the most complex application requires substantially more time and memory.

  • Implementation: DECO’s implementation includes TLS 1.2 three-party handshake and 2PC query-execution protocols integrated with mbedTLS.The system comprises about 4700 lines of C++ and includes a TLS-PRF circuit with 779,213 AND complexity.
  • DECO protocols: 0.37 seconds completes the three-party handshake in LAN settings, while 2PC-HMAC takes 0.13 seconds per record.2PC-HMAC’s cost is independent of record size; 2PC-GCM depends on query length and is generally more expensive.
  • Proof generation: DECO uses efficient statement templates and two-stage parsing to achieve practical prover performance, with negligible verifier time.The binary option has the highest constraint and prover-time cost, and the most complex application uses 1.78GB of memory.
  • End-to-end performance: 13.77 seconds completes the binary-option protocol in LAN settings, increasing to 18.64 seconds in WAN settings.The LAN total includes 12.97 seconds for zero-knowledge proofs; WAN MPC protocols take 5.37 seconds.
  • Performance comparison: Town Crier completes a similar application in about 0.6 seconds, around 20x faster than DECO but with additional trust assumptions.The comparison frames DECO’s higher overhead as the cost of cryptographic-strength security assurances.

8 LEGAL AND COMPLIANCE ISSUES

DECO exports data with integrity proofs without explicit website approval, but users still depend on oracles and compliance remains site- and application-specific. The system also exposes oracle-access metadata and raises legal responsibilities for users and oracles.

  • Scope and responsibilities: DECO can export website data with integrity proofs without the website’s explicit approval or awareness.The paper connects this capability to legal and compliance considerations.
  • Oracle dependence: Users cannot unilaterally export data with integrity assurance because they rely on oracles as verifiers.Oracles learn which websites and data types users access and may deny transactions for appropriate-use reasons.
  • Legal responsibility: Users and oracles bear legal responsibility for accessed data, while violating site terms may create civil rather than criminal exposure.Compliance with a site’s terms of service is site- and application-specific.
  • Attestation risks: Incorrect or subverted data can create legal, performance, and compliance implications for attestations.The paper notes that complex multisite data dependencies make these issues relevant beyond DECO alone.

9 RELATED WORK

Related approaches prove application-layer or TLS-layer provenance, but often require application-specific key management, server modifications, or server cooperation. DECO instead enforces context integrity with a two-stage parsing scheme that reduces zero-knowledge input length.

  • Application-layer data provenance: Application-layer provenance schemes have poor modularity and reusability because they are application-specific and require application-layer key management.This also moves cryptographic keys outside the TLS layer.
  • Server-facilitated TLS-layer solutions: Server-facilitated TLS-layer solutions require modifying security-critical server code and benefit users only when administrators cooperate.These requirements create high adoption costs and limit availability.
  • DECO’s distinction: DECO enforces context-integrity proofs through a two-stage parsing scheme that greatly reduces the zero-knowledge proof’s input length.The scheme addresses a property identified as missing from prior approaches while improving efficiency.

10 CONCLUSION

DECO is a privacy-preserving decentralized oracle scheme for modern TLS that removes trusted hardware and server-side modifications. It proves provenance and fine-grained statements about session content, with a formal security definition, mitigations, implementation, and three example applications.

  • DECO supports modern TLS without trusted hardware or server-side modifications.
  • DECO lets users prove data provenance and fine-grained statements about TLS session content while preserving privacy.
  • The paper identifies context-integrity attacks, provides an efficient two-stage parsing mitigation, and formalizes decentralized oracles through an ideal functionality.
  • A functional implementation and three example applications demonstrate DECO’s practicality and its potential to make private data accessible beyond centralized web-service silos.

A.1 Formal specification

The appendix specifies DECO’s three-party handshake, selective-opening components, cryptographic record processing, and optimized 2PC query execution. These protocols establish shared TLS secrets, convert elliptic-curve shares, process authenticated records, and reduce GCM verification cost.

  • A.1 Formal specification: The formal specification defines a three-party handshake in which prover and verifier establish additive shares of an ECDHE secret with the server and derive TLS session keys using TLS-PRF.The protocol is described as a two-step process and is specified in Figure 6.
  • A.2 Selective opening (CBC-HMAC): Selective opening proves consistency while redacting a prefix or suffix, but redaction is meaningful only when the revealed portion contains no private user data.The suffix protocol uses a zero-knowledge proof and hides the redacted suffix from the verifier.
  • A.2 Selective opening (CBC-HMAC): ECtF converts additive shares of elliptic-curve points into additive shares of the resulting x-coordinate for later TLS-PRF evaluation.Its inputs are two shared elliptic-curve points, and its outputs sum to the x-coordinate of their elliptic-curve sum.
  • B.1 Preliminaries: GCM processing combines AES counter-mode encryption with authenticated tags computed from the nonce, ciphertext, additional data, and GHASH polynomial evaluation.The tag is defined using AES(k, IV), the padded associated-data and ciphertext polynomial, and h = AES(k, 0).
  • B.2 Query execution: The GCM post-handshake protocols use 2PC to verify tags and decrypt records, while preventing reuse of an initialization vector that could reveal the GHASH key.The protocols are specified in Figure 9 and use 2PC-AES for the required AES computations.
  • B.2 Query execution: GCM tag verification is challenging because it mixes arithmetic operations in F_2^128 with binary AES computation, while direct polynomial evaluation costs about 1,000 field multiplications per record.The mixed computation creates a substantial circuit-design and performance challenge.
  • B.2 Query execution: The optimized protocol removes polynomial evaluation from the 2PC circuit and reduces each record’s computation to one 2PC-AES invocation using only binary operations.This avoids the expensive large-field multiplication circuit.
  • B.2 Query execution: The protocol must ensure that the verifier never responds to the same IV twice, because combining responses can remove blinding and allow the prover to solve for the GHASH key.This restriction is tied to the security of the blinded linear-combination technique.

B.3 Proof Generation

DECO’s proof-generation protocols prove encrypted-block and record statements while reducing zero-knowledge work through selective disclosure and commitments. The TLS 1.3 adaptation uses key independence to decrypt handshake messages locally, while multi-round sessions add tag commitments and sequence-number checks.

  • To reveal an encrypted block, the prover proves both correct AES encryption and tag correctness, while naïve tag proofs require degree-512 GHASH evaluation and two AES encryptions.
  • Revealing AES(k, IV) and AES(k, 0) lets the verifier check the tag, reducing the proof cost to 3 AES and 1 SHA-2 in zero knowledge.
  • TLS 1.3 uses 2PC-HKDF to derive handshake and application keys, then reveals handshake keys so the prover can decrypt handshake messages locally.The optimized circuit uses roughly 30 SHA-256 invocations and approximately 70k AND gates; TLS 1.3 support is limited to GCM mode.
  • For query-bound responses, client-to-server keys can be revealed after the handshake, allowing the prover to query the server without further verifier interaction.
  • Multi-round sessions reuse 2PC tag verification and require an additional commitment to prevent the prover from abusing verification to forge tags.
  • For server responses, the prover commits to a tag before 2PC recomputes it; for client messages, the verifier enforces increasing sequence numbers.These checks prevent forged server tags and duplicate-sequence client messages.

C.4 An alternative DECO protocol: Proxy mode

Proxy mode improves DECO efficiency by having the verifier proxy the TLS session and reveal the verifier’s key share after the prover commits to its share. This removes intensive post-handshake cryptography but requires stronger network assumptions and tolerates a weaker adversary.

  • HMAC mode has runtime independent of record size, while GCM is efficient for small requests with preprocessing but can be expensive for large records.
  • In proxy mode, the verifier relays traffic between prover and server, records the session, and reveals its key share only after the prover commits to its own share.
  • The three-party handshake remains necessary because GCM is not committing: different keys can produce the same tag for a ciphertext while decrypting it differently.
  • Prover integrity requires the proxy to authenticate its connection to the server and prevent the prover from tampering with proxy-server traffic.
  • After the handshake, verifier authentication relies on network indicators such as current DNS records and protection against traffic injection.
  • Proxy mode trades security for efficiency: it avoids intensive post-handshake cryptography but withstands only a weaker network adversary.

D SECURITY PROOFS

The security proof shows that DECO securely realizes the ideal oracle functionality by constructing simulators whose hybrid executions are indistinguishable from the real protocol. Separate arguments establish prover integrity, verifier integrity, and privacy against malicious participants.

  • Simulation-based security: The proof constructs an ideal-world simulator for any real-world adversary and argues indistinguishability across a sequence of hybrid executions.The proof treats the real protocol as H1 and transforms it through simulations of ideal functionalities, parties, and checks.
  • Prover integrity: For malicious provers, DECO delivers a statement and server response only when the response corresponds to the prover’s queried server request.This establishes the prover-integrity guarantee in the ideal execution.
  • Hybrid arguments: Hybrid transitions remain indistinguishable because ideal-functionality simulations are perfect and sampled secrets are uniformly random.The proof specifically uses random prover or verifier secrets to replace protocol interactions without changing the adversary’s view.
  • Soundness of checks: The simulator’s added checks are justified because failed provenance, key-consistency, or authentication conditions would also make the real verifier abort except with negligible probability.The argument relies on discrete-log hardness, 2PC security, HMAC unforgeability, and CBC-HMAC receiver binding.
  • Verifier integrity and privacy: For malicious verifiers, the simulator forwards oracle inputs and supplies simulated handshakes, ciphertext records, and proof outputs while learning only record sizes.The construction uses random query and response strings and dummy HMAC computations to preserve the real execution’s observable behavior.

E APPLICATION DETAILS

The application details show how DECO selectively reveals authenticated web data while hiding sensitive fields, using redaction, parsing, and zero-knowledge proofs for concrete applications. Key-value grammars and unique-key parsing support reliable extraction of targeted fields from structured web responses.

  • Binary option: DECO redacts sensitive HTTP parameters while revealing the API endpoint and other necessary fields, with the private API key providing entropy against disclosure.The binary-option application applies this technique to preserve sensitive request parameters while proving access to the intended endpoint.
  • Age proof: The age-proof application parses 6-7 AES blocks containing a birth date and proves in zero knowledge that the student is above 18.Unique HTML tags surrounding the birth date provide a key-value grammar for identifying the relevant field.
  • Price discrimination: 24 AES blocks containing necessary order details and the request URL are revealed to prove that an advertised price exceeds a threshold while hiding name and address.The price-discrimination example uses AES-GCM for the TLS session and keeps unrelated sensitive invoice data hidden.
  • Grammar-based validation: The parsing framework models key-value grammars with context-free production rules, explicit delimiters, escaping, and an LL(1) parser for validating selectively opened pairs.The context function checks that the opened substring is a valid pair with the specified key and occurs as a pair in the full response.
  • Key-value parsing: For key-value grammars, Trans extracts a continuous substring whose scope can be determined correctly, reducing two-stage parsing to substring parsing.This relies on unique keys within the relevant grammar scope.
Loading 1909.00938v6…