WITNESS ENCRYPTION — An Independent Cryptographic Art Experiment on knowledge, secrecy and the conditions of computational disclosure. A ciphertext can have a mathematical address (an instance of a problem whose solution may qualify a reader for access).
Formally introduced in 2013. A sender encrypts a message under a public instance without needing a solution.A relation fixes what counts as evidence.
Enc(x,m) → ct /
The statement may circulate as openly as the ciphertext.
Anyone with a valid witness can use the scheme's decryption procedure to recover the message. The reader is still unknown
when the object appears. An eventual reader may be identified
The archive follows the gap between an instance and its solution through combinatorics, Boolean logic, secret sharing and threshold cryptography. Consider how the same visible object can disclose different things to observers who possess different evidence. A mathematical address is reproducible. The question of who will arrive at it remains open. proof and access as operations in a relation. Formally introduced in 2013. A sender encrypts a message under a public instance without needing a solution.A relation fixes what counts as evidence.
Enc(x,m) → ct /
The statement may circulate as openly as the ciphertext.
Anyone with a valid witness can use the scheme's decryption procedure to recover the message. The reader is still unknown
when the object appears. An eventual reader may be identified
only by what they can eventually do with it.
The message awaits a satisfying witness. / THE SECRET EXISTS / THE STATEMENT IS PUBLIC / THE WITNESS MAY ARRIVE LATER
Consult the index /gate and primary sources / papers WE
CONTRACT / CA
PENDING
THE PUBLIC INSTANCE / x — encryption to a public statement
Givenx IS PUBLIC / w UNKNOWN
INSTANCE defines the condition a witness must meet
even when any satisfying solution remains computationally inaccessible
to the observer who can examine and transmit the instance.

THE WITNESS / w — a mathematical object capable of satisfying a public relation
Evidence with formal validity / POLYNOMIAL-TIME CHECK



CheckSTATEMENT / WITNESS
Suppose x is a Boolean formula and w assigns values to its variables.
The same relation can verify each candidate assignment by testing
every clause against the proposed values in polynomial time.
Finding such an assignment may require much more work.An archived interface offers an independent visual experiment in relations. Visit the interactive archive


THE ARCHITECTURE OF CONDITIONAL SECRECY
coordinates the statement, the message and the witness.Its
definition distinguishes the act of encryption from knowledge of
a solution. In the original formulation, Garg, Gentry, Sahai and Waters ask whether the statement itself can play the role of an encryption
address. Here we examine the proposal as three linked questionsconcerning ciphertext, verificationand recipient selection
. Encryption is randomized. Even the person who creates the ciphertext may have no idea
whether their instance belongs to the language. For a false instance, the original security definition asks that efficient adversaries cannot distinguish the encryptions of two equal-length messages. Correctness describes the complementary case: given a valid witness to a true instance, the decryption algorithm recovers the message. There is a meaningfulgap between these demands. The baseline definitionmakes no corresponding promise for every true instance with a witness thathappens to be difficult to find. More expressive security notions require separate arguments. A claim about hard true instances, for example, cannot be read off from guarantees on false instances. Compare the original construction , which proposes candidate techniques based on approximate multilinear maps.
/ CONDITION.
One way to see the connection to indistinguishability obfuscation is to imagine a program that holds a message and returns it only whenits input passes verification.On a false instance,two programs with different embedded messages behave identically because neither ever releases anything. Subject to the formal conditions of the transformation,iO can hide the choice between equivalent programs. The thought experiment is technically revealingbecause it depends on the specificsecurity of iO and is far beyondan ordinary compiler optimization. A program can have identical behavior while carrying very different secrets.
CIPHERTEXT / ct
a question of secrecy INSTANCE / MESSAGE / ENCRYPTION
A ciphertext can be copied, transmitted and examined independently of the knowledge needed to recover its contents. One observer encounters a byte sequence that does not resolve into meaning. Another possesses a witness and can run the relevant decryption algorithm. The same object meets these two observers without changing its contents. In conventional encryption we might explain the difference by saying that the second observer holds a secret key. Here the syntax
refers to a relation whose instance is chosen by the sender. The qualification for decryption is specified before anyone presents the necessary evidence. There are several layers to the distinction. The ciphertext may reveal its intended statement or accompany a separatelypublished one. The baseline security game compares messages of the same length; it does not promise to conceal every property of the surrounding protocol. Copying a ciphertext need not copy its interpretation. Whether a particular recipient can read its contents depends on the relation checked by the construction. The object is visible as an artifact. Its recovery is a separate operation, governed by mathematical evidence that can arrive by a route unknown to the sender. The interface may make theartifact available to many readers at once while leaving the required witness entirely outside their possession. Enc(x,m) → ct.
RELATION / R(x,w)
Verification
A relation is a predicate over an instance and a proposed
witness.
The instancenames the
condition;
the
witness supplies evidence in a form the verifier can inspect. For an NP language, witnesses have length bounded by a polynomial in the instance size, and there is a polynomial-time procedure for checking whether a proposed witness is valid. The instance belongs to the language exactly when at least one such witness exists. This statement concerns checking. It leaves open how much effort a solver will need to find a witness. For some problems there are fast algorithmsfor finding the evidence; other problems have no known efficient general search procedure. Within witness encryption, the decryption procedure uses this asymmetry without simply treating the verification result as a secret bit. The evidence itself provides a structured input to the cryptographic construction. Two valid witnesses can differ while unlocking the same message. Conversely, a candidate that resembles a valid witness is insufficient if it fails even one required condition. Formal verification resolves the status of a particular submitted object. It does not establish whether some unsubmitted object might pass. R(x,w) = 1 /Dec(ct,w) → m. An accepted witness supplies the relation that determines the conditions of A relation is a predicate over an instance and a proposed
witness.
The instancenames the
condition;
the
access.
Verification requires a public rule and a candidate. Discovery asks where a satisfying candidate could come from.
full video
/ Compare candidate constructions here
BEYOND THE SECRET KEYfull video
/ Compare candidate constructions here
PUBLIC INPUT REMAINS VISIBLE
Iview conventional public-key encryption as a scheme that binds recovery to possession of the secret key corresponding to a chosen public key. Witness encryption begins with a description of what must be known. Hair and Sahai give a construction for NP in the classical generic cyclic group model. For SAT, a satisfying assignment allows decryption in polynomial time with small correctness error. For an unsatisfiable instance, their bound appliesto adversaries whose group operations are mediated by the model and whose number of queries is bounded. The proof does not transfer automatically to an implementation using a concrete group. The construction also advances the hardnessof approximating homogeneous MinRank under randomized reductions. Here low-rank witnesses provide a bridge from combinatorial decision
problems to structured linear algebra.
Hair and Sahaiuse the structure of that problem to separate the availability of a rank-one solution in the yes case
from the absence of sufficiently low-rank matrices in the no case. The choice of group model and the bounds on queries are part of what the result says. Both matter when comparing theory and implementation. Hair and Sahaiuse the structure of that problem to separate the availability of a rank-one solution in the yes case
A small combinatorial experiment
/ Start with a universe of distinct elements and a collection of subsets of that universe. A cover can be incomplete or redundant (giving multiple copies of one element).
A witness selects a subfamily whose members cover each element exactly once. Count the occurrences to check the assignment.


components.
/ SELECT A SUBFAMILY / COUNT COVERAGE / VERIFY EVERY ELEMENT / CHECK THE WITNESS
open experiment
GATE-1 / THE SATISFIABILITY GATE
GATE-1 is a computational threshold built from Boolean variables. A formula supplies the public statement and an assignment supplies the candidatewitness. In a conjunction, every clause must evaluate to true. This fixes the same testfor each observer, whether they arrive at a proposed assignment by argument, by chance or by exhaustive search.GATE-1 is designed to suggest a single opening, but the instance may have several witnesses. If two assignments both satisfy every clause, the verification relation accepts each one. An invalid submission reveals only that this candidate fails. It does not show the instance is unsatisfiable. To establish that stronger claim requires reasoning about every possible assignment, or using the structure of the formula to rule out a whole family of assignments at once. This difference betweenchecking a proposal and deciding whether any proposal can succeed is at the center of satisfiability as a computational problem. Here, the small size lets us inspect both questions directly.
For the demonstration, begin with
A STRING IN BASE64
/ a reversible representation, followed by
AN ASSIGNMENT
of Boolean values.
A STRING IN BASE64
/ a reversible representation, followed by
AN ASSIGNMENT
of Boolean values.
The visible statement stays fixed as one assignmentgives way to another. Theinterface does not require an account or recognize a solver. Interpretation becomes an operation on inputs. A proposed witness may fail on one or moreclauses, while any successful
candidate fulfils the same public condition.
full video
full video
GATE-1 (SAT)
Boolean formula,
input, output
variables, two
satisfying assignments
input, output
variables, two
satisfying assignments
GATE-1 / DECRYPTION EXPERIMENT
VGhlIGtleSBpcyBhIHdpdG5lc3Mu
THE UNSOLVED STATEMENT
THE UNSOLVED STATEMENT / Think of a problem being circulated to a distributed
audience. A first group approaches it through search, testing and rejecting candidates. Another
discovers a reformulation that simplifies the search space. What each observer can attempt depends partly on
the representations available to them and partly on theirresources.
THE UNSOLVED STATEMENT /
The ciphertext anchors a distinction between visibility and knowledge. It may be archived long before anyone can account for the relation on which its interpretation depends. A change in available algorithms can alter that situation. A theorem may rule out every proposed witness, or a singlecounterexample mayfinally establish that the relation holds. Discovery may occur away from the person who set the condition. From this perspective,the addressee appears retroactively: whoever acquires the required evidence can become a reader. This is a way of interpreting the construction. Its formal definition specifies the
correctness and security conditions, leaving that interpretation open.
/
The visible statement is also a commitment to a particular question. Once the ciphertext is constructed, progress on a different instance does not ordinarily help a reader, even if the two problems sound similar. Disclosure concerns this instance and a witness this relation will accept. A reader can examine the exact terms of recovery while remaining unable to realize them.
SILENT THRESHOLD / DISTRIBUTED DISCLOSURE



full piece
alongside the
Berkeley thesis / independent public setup
Silent threshold encryption asks how a group canreceive encrypted information before its members carry out a joint key-generationceremony.Participants generate public keys independently, with corresponding privatekeys.Anyone can aggregate a designated collection of public keys into a constant-sized encryption key. An encryptor can choose the required threshold for that message, expressing the access condition as a sufficiently large subset of the group. Secrecyrests onthe scheme'sprecise adversary model, including what happens when some of those participants are compromised. For decryption, authorized participants contribute information derived from their private keys and the ciphertext. The result can be recoveredfrom sufficient valid contributions. Choosing a threshold makes a tradeoff explicit: smaller thresholds can make recovery easier to arrange, while larger thresholds distribute authority more widely at a possible cost in availability. Silent setup concerns when and how public keys are created and combined. It does not guarantee that participants will be present when their decryption contributions are needed. This distinction separates a setup property from a condition on the live system. Guru Vamsi Policharla's 2026 Berkeley thesis explores special-purpose witness encryption through modular constructions. The idea is to build primitives for particular kinds of statement and compose the pieces where their assumptions and interfaces line up. The permitted language of a specialized component may be far narrower than all of NP. That restriction gives the designer room to exploit concrete algebraic structure, including bilinear pairings in parts of the research. Pairingsoperate on group elements with an algebraic compatibility that can make certain relationships expressible. Each gadget must still state what counts as an instance, how a witness is represented and what is meant by hiding a message. Components cannot be swapped without checking how those promises compose.A protocol also has decisions beyond the construction itself: how to select participants, where to publish their keys and how to handle a party that withholds a decryptioncontribution. The primitive addresses a precise portion of the design. The conceptual resemblance to witness encryption lies in the transfer from a named addressee to a specified condition. In this setting the evidence is collective, and the ability to recover a secret depends on contributions from an eligible part of the committee. The threshold defines the boundary through which a message can cross. For the formulation and efficiency details, see Policharla.



full piece
alongside the
batching study / only selected ciphertexts