Key Transparency cannot audit lookup permission

Summary

KEYTRANS can authenticate the result of a permitted search and help expose inconsistent log views; it does not standardise the application policy that admits or blocks the request before the transparency operation.
draft-ietf-keytrans-architecture-09 explicitly permits largely arbitrary application access control, including authentication, relationship rules and rate limits, while draft-ietf-keytrans-protocol-05 preserves a narrow right to continue required monitoring after search access is revoked.
Daniel Kade proposes a privacy-preserving lookup-policy receipt that records policy version, requester and relationship classes, operation, decision code, log epoch, exceptions and correction without exposing labels, contact graphs, credentials or complete search histories. It is editorial guidance, not a KEYTRANS or IETF requirement.

A transparent answer can begin with an invisible decision

Key Transparency addresses a real weakness in end-to-end encrypted communication. A messaging service that distributes users’ public keys can substitute a key it controls and place itself inside conversations that appear encrypted. A searchable, cryptographically protected history makes identity-to-key bindings verifiable. A user can inspect the key associated with a label, retain state and detect a view that diverges from the history seen by others.

That promise is intentionally bounded. The active KEYTRANS charter says the authentication service should reveal information about a person—including whether an identity is registered—only to clients authorised to ask. The architecture turns that privacy goal into a division of labour. The Key Transparency protocol authenticates stored mappings and the evolution of the data structure. The surrounding application decides who is authorised to run Search, Update or related operations.

The boundary is visible in the architecture’s simplest example. Alice may search for Alice and Bob and update Alice. A search for Fred and an update to Bob are blocked by the transport layer. The denied arrows stop before the transparency log produces a proof. A verifier of Alice’s successful SearchResponse can test the cryptographic statement it contains. The verifier receives no symmetrical object explaining the missing Fred response.

This is not a flaw in the protocol. A general-purpose transparency scheme cannot know whether a service defines “friend”, “colleague”, “same organisation”, “paid account”, “abuse suspect” or “rate-limited client”. The architecture therefore allows applications, with limited exceptions, to impose arbitrary access rules and leaves the rejection mechanism and possible explanation to them. The governance mistake would be to let a valid transparency proof imply that the gate was also transparent.

What the proof actually proves

The current protocol draft combines two data structures. A prefix tree maps a label-version search key to a commitment and permits efficient inclusion or non-inclusion proofs. A log tree records successive prefix-tree roots and permits consistency checking over time. SearchResponse carries a tree head, value and opening, binary-ladder material and a combined proof. Verification reconstructs the relevant roots and checks the requested lookup against retained state.

The architecture describes the resulting guarantee carefully. A user who correctly verifies a proof and performs the required monitoring gains assurance that the transparency-log operator executed the operation correctly and consistently with what other users would have seen for the same label at roughly the same time. If the operator presents a fork, incorrectly executes the operation or leaves a user on an impermissibly stale view, monitoring and freshness limits are meant to expose the problem under the stated deployment assumptions.

None of those calculations carries the application’s policy inputs. A prefix proof does not encode whether Alice and Bob were friends, whether Fred’s account had crossed a rate limit, whether an abuse exception was active, whether a corporate tenant allowed cross-department lookup, or which policy version the service used. Its precision is about a search key in a tree, not a person’s entitlement to submit that search.

The distinction resembles Certificate Transparency only at one layer. RFC 6962 and RFC 9162 use append-only Merkle structures to make certificate logging inspectable and inconsistent histories detectable. They do not make every relying party’s admission, trust or enforcement policy part of a log proof. KEYTRANS adds efficient private lookup and account-oriented monitoring, but it does not dissolve the same institutional boundary: authenticated evidence can be consumed under a separate policy.

Privacy requires denial, but denial still exercises power

Access control is not an inconvenience that should simply be removed. The KEYTRANS privacy model relies on it. A service may need to hide whether a label exists from strangers. A person who is no longer a contact may be prevented from learning whether an account has changed. An operator may pad the log to obscure its user population and update rate. A public, unrestricted directory would defeat these purposes even if every answer were cryptographically impeccable.

The application gate therefore protects legitimate interests. It also makes consequential decisions. If a rule is stale, the intended recipient’s new key may become unreachable to an authorised correspondent. If relationship state differs across devices, two people may receive different admission decisions without any fork in the log. If a rate limit silently changes, a high-risk client may be unable to verify a key during an incident. If an exception persists past its purpose, someone may keep learning that an account exists after the relationship ended.

The tree can remain globally consistent through all four failures. It can answer every request that reaches it perfectly. The discrepancy lies in which requests were allowed to become protocol operations. Calling the whole service “transparent” without naming this boundary risks giving the cryptographic layer credit for a decision it never observed.

RFC 6973 offers the right discipline for the other side of the problem. Making access decisions auditable must not create a second, more revealing search history. Identity, query target, relationship and time can combine into sensitive social and operational data. RFC 7258 keeps traffic characteristics and correlation within the threat model. A complete central record of who searched for whom would be an accountability system built from the very disclosure that access control was meant to prevent.

Revocation exposes the state machine

The clearest evidence that the gate is not a simple allow/deny bit is Contact Monitoring. A user who previously searched for a label may need to monitor that earlier observation so a malicious update cannot evade later detection. The architecture and protocol therefore require certain Monitor operations to remain available even if the user would no longer be permitted to repeat the Search or Update. The protocol mentions a commitment opening as one simple way to prove that earlier permission.

That sequence contains at least four states: permission to search, possession of a valid result, loss of permission for new searches, and continuing permission for bounded monitoring of the old result. “Access revoked” is too coarse. It might correctly end new discovery while incorrectly terminating the evidence duty created by an earlier accepted lookup. Conversely, continued monitoring must not become a route to learn post-revocation account content that the privacy model intends to conceal.

The Reasonable Monitoring Window adds time to this state machine. Distinguished entries supply common checkpoints, and clients must retain enough state and remain active long enough to detect misconduct under the deployment mode. Application policy has to preserve the required monitoring path across account deletion, device replacement, relationship change and rate-limit events. A search proof cannot tell an auditor whether that path remained available after the gate changed.

This is where policy versioning becomes operational rather than clerical. An authorisation rule at the time of Search creates a later monitoring obligation. If the service replaces the rule without retaining the transition, a denied Monitor request cannot be distinguished from an implementation fault, an intended privacy boundary or abuse controls. The policy epoch needs a durable join to the tree epoch without placing the underlying social relationship in a public record.

Third parties change who can see the seam

KEYTRANS supports several deployment modes, and the visibility of access decisions changes across them. In Third-Party Management, users send operations to the service operator. The operator enforces access control and forwards permitted operations to a manager. The manager generally learns plaintext labels and values, their modification history and traffic patterns such as lookup frequency. It does not automatically learn the application reason behind every admission or denial; rejected operations may never reach it.

In Third-Party Auditing, the auditor can learn the number, order and approximate timing of changes while labels and values remain masked by VRF outputs and commitments. That is useful separation, but the auditor’s cryptographic view does not include the population of requests stopped by application policy. A service could operate an honest log and an inconsistent gate. The auditor could truthfully approve the history it saw without having evidence about differential lookup admission.

RFC 9458 and RFC 9614 show why separation can still help. One role can know the client while another sees the request; partitioning can reduce what any participant learns. Yet non-collusion, timing, small anonymity sets and shared infrastructure matter. For KEYTRANS, routing all denials into a common audit service would recreate a correlation point. The objective is not maximal visibility. It is the minimum evidence that lets an independent reviewer test whether a policy was applied as declared.

Multi-service deployments add another boundary. The architecture requires consistent routing to the correct log and permits a controlling entity to act as an anonymising proxy, while cautioning against mirroring or combining other logs in ways that disrupt their access policies. A proxy can reduce exposure of the requester to another service. It can also become the actor that maps identity, destination and decision. Its policy version, retention and non-collusion assumptions belong in the control surface.

A lookup-policy receipt, not a search dossier

Daniel Kade’s proposal is a privacy-preserving lookup-policy receipt. It sits outside the cryptographic proof and does not pretend to extend the KEYTRANS wire format. It makes the admission decision testable while refusing to create a public map of who searched for whom.

The receipt begins with a policy identifier and immutable version. It records the operation class—Search, Update, initial Monitor or continuing Monitor—and a coarse requester class such as owner, current contact, former contact with a monitoring entitlement, same-tenant user or unauthenticated caller. It records a relationship class and decision code without storing the relationship members. The target can be represented by a rotating keyed local digest or broad label class that cannot be reused across services.

Next it binds the decision to a time band, service and relevant transparency-log configuration or tree epoch. It distinguishes allow, deny, rate limit, stale client state, required prior-monitor continuation and time-bounded exception. It identifies the rule that controlled the result, the authority that approved any exception and the exception’s expiry. A correction path says how a user can challenge a decision without being forced to disclose a contact graph to a public audience.

The receipt should not contain usernames, raw labels, public keys, credentials, message metadata, full IP addresses, exact contact relationships, durable cross-service identifiers or a complete personal history. Most oversight can operate on short-lived local counters and privacy-safe aggregates: decision-code distributions by policy version, synthetic pairs representing permitted and forbidden relationship classes, rates of Monitor continuation after Search revocation, expired exceptions and unexplained differences between equivalent test cases.

An independent test can create controlled accounts, establish and end a relationship, obtain a search proof, rotate a key, revoke new-search access and verify that the bounded Monitor path remains. The output is a policy conformance observation, not a copy of real users’ queries. Where incident investigation requires finer evidence, access should be purpose-bound, time-limited and logged under a separate authority.

Erasure reinforces the separation

The architecture also separates user data from cryptographic material for pruning and erasure. Values made permanently inaccessible by application policy may be deleted, while VRF outputs, commitments or other tree material may remain necessary to produce proofs for other versions. The protocol does not carry the application’s access policy into the log. That is a useful separation of concerns, but it means a surviving commitment is not a record of why access ended or whether deletion followed the right authority.

An access-policy receipt should therefore avoid claiming to prove erasure. It can record that a named policy transition authorised deletion, that an application data layer reported completion, and that the protocol layer retained only material required by its own algorithm. Actual deletion assurance, backups, replicas and legal duties require their own evidence. Cryptographic persistence and application deletion are connected states, not interchangeable verdicts.

What remains unproven

The architecture and protocol are current Working Group Internet-Drafts, not RFCs. Revision 09 of the architecture is intended to be Informational; protocol revision 05 remains work in progress. Their text and deployment assumptions can change. The approved charter establishes the group’s scope, not implementation or market adoption.

The frozen sources do not establish that a named service has deployed these drafts, that users have suffered improper lookup denial, that one access-control model is prevalent, or that a particular policy is lawful. They provide no denial-rate benchmark, incident frequency, performance result or evidence of discriminatory operation. This article’s receipt is a governance proposal, not an allegation and not a protocol requirement.

The narrower conclusion is enough. A KEYTRANS proof can show that a permitted lookup was answered correctly against authenticated state. It cannot audit the earlier choice that decided whether the lookup would exist. Privacy needs that choice. Accountability needs it to be bounded and testable. The solution is not to publish the social graph, but to stop pretending the tree root governs the gate.

A Key Transparency Proof Cannot Audit Who Was Allowed to Look

Summary

A transparent answer can begin with an invisible decision

What the proof actually proves

Privacy requires denial, but denial still exercises power

Revocation exposes the state machine

Third parties change who can see the seam

A lookup-policy receipt, not a search dossier

Erasure reinforces the separation

What remains unproven

Sources

Deeper Profile Context

Strategic Circle

Leadership Alliance

Strategic Circle Briefing

Leadership Alliance Briefing