X
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
only by what they can eventually do with it.

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.
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


public input/ a problem,x, openly specified, 0/1,
Given
x 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





                   
candidate object/ finite data,NP, verify, input and proof,
Check
STATEMENT / 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 questions
concerning 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 / ctAn encrypted object held as data/ constructed under x, public, copyable, digital data /
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.

full video
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
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 KEYEncryption to a condition separates the sender's choice of a public instance from the eventual discovery of evidence [an assignment, a cover, a certified contribution]. The encryption address is fixed at the moment of construction.
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.    




EXACT COVER / THE MATHEMATICS OF SATISFACTION
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.





               
For example, the sets {1,2} and {3,4} cover four elements exactly once. An overlapping choice could include every element and still fail because some element was counted twice. The early candidate construction uses Exact Cover to connect a precise combinatorial constraint with the ability to combine cryptographic
 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.
The display first offers a code whose letters can be recovered by decoding the representation. Base64 changes the alphabet used to represent bytes and contributes no secrecy. The second step offers a public formula and waits for knowledge that satisfies it. Negation flips a Boolean value; disjunction accepts when at least one operand is true; the conjunction accepts only when every clause holds. The  expected disclosure occurs   when the relation accepts a witness. In a real witness-encryption scheme the witness drives adecryption computation. This browser exercise compares two forms of disclosure and illustrates the logic of   the latter  using  openly  availablecode.

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
GATE-1 (SAT)
Boolean formula,
input, output
variables,
two
satisfying assignments
GATE-1 / DECRYPTION EXPERIMENT
VGhlIGtleSBpcyBhIHdpdG5lc3Mu
An educational model of a witness relation. The browser verifies a Boolean formula.
THE UNSOLVED STATEMENT
The existence  of a  solution  and its availability toan observer describe  different  facts. An  encryptor  can select an instance without knowing whether it has a witness. The ciphertext is complete as data, yet a particular reader might be unable to perform recovery. A later discovery can change what that reader knows whileleaving the instance and ciphertext intact.The object appears to wait, but mathematical discovery has no schedule. Time alone supplies no evidence.THE UNSOLVED STATEMENT / AFTER ENCRYPTION / PUBLIC INSTANCE, UNKNOWN SOLVER, POSSIBLE WITNESS, DISCLOSURE ON NO PREDETERMINED SCHEDULE




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
independent keys / collective recovery

 


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.
BATCHED THRESHOLD / THE ENCRYPTED ORDERsubmission / ordering / disclosure

 


full piece
alongside the

batching study  / only selected ciphertexts
A transaction may be encrypted before it is placed in a public queue. Its  arrival  can be recorded while its contents remain unavailable to other observers. In a network where observers react to pending orders, early disclosure can affect what later gets executed and who captures the resulting value. The encryption layer changes which information is available at each step. A threshold committee can reveal messages after some point specified by the surrounding protocol, such as after an order is fixed or a  batch is selected.  Batched threshold encryption studies how to recover a  designatedgroup of ciphertexts collectively without incurring the full cost of an independent threshold operation for each item. A batch is itself a consequential object: it identifies the scope of a release. Decryption for that set should leave ciphertexts outside the authorizedbatch confidential under the applicable security definition. Some applications also require the rest of the system to agree on the membership of the batch before contributors act. Otherwise, an apparently minor disagreement about which ciphertexts were selected becomes a disagreement about what to disclose. A committee can delay or obstruct recovery bywithholding contributions, depending on the protocol and the number of parties involved. Encryption leaves these protocol decisions in view. It can limit some forms of front-running by concealing transaction details before ordering, but the privacy of payloads alone does not specify fairness, eliminate MEV, or stop strategies based on timing and other visible metadata. Network participants may still observe when and how frequently something is submitted. Thedesign question is therefore granular: what exactly becomes public, when, and under which assumptions about the contributors? The ciphertext may enter first. The authorization condition determines a later point of visibility. Distribution and recovery remain distinct phases, and a decision about one is not automatically a decision about the other. An order of bytes becomes an order of knowledge only after the chosen decryption condition is fulfilled. See the formal treatment in the 2026 thesis.
RESEARCH NOTES on this archive:An independent  cryptographic art experiment / original paper/ read alongside   later work on the relation between statement and witness. The statement can remain public at every stage.  Its contents remain conditional. Recovery depends on the evidence held by a particular reader at the moment of disclosure.