Can a Yin Yang puzzle become a cryptographic key?

So, what is a Yin Yang puzzle in the first place? It is a grid that we fill with black and white cells. All black cells must connect to each other, all white cells must also connect to each other, and no 2 by 2 square can have only one color. Some cells are given as clues. The remaining cells are the puzzle that we need to solve.

I have thought about using this puzzle as a cryptographic key since my first paper. For example, we could share the incomplete puzzle with everyone and keep its complete solution private. It feels like a natural public and private pair. But that feeling is only the beginning. A public object and a private object do not automatically give us public key encryption.

This blog post turns the idea into something we can actually try. It includes a working text encryption and decryption system, and it also keeps the security claim honest. Standard cryptography protects the text in the current experiment. The puzzle solution acts as a committed private witness that must be present during decryption. The puzzle is not the encryption trapdoor yet.

What are we actually trying to build?

A recipient first runs KeyGen. The result must contain a public package and a private package. A sender uses only the public package to create an encrypted message. The recipient uses the private package to recover the text. Someone who sees the public package and every encrypted message should not learn the text.

Modern public key encryption is often described through a key encapsulation mechanism. Encaps creates a shared secret and a public encapsulation value. Decaps recovers the same shared secret with the private key. A key derivation function turns that secret into a content key. Authenticated encryption then protects the message and detects changes.

The puzzle introduces a second relation. The public clues define an instance. The hidden solution is a witness for that instance. Decryption can verify the witness before it accepts the private agreement key. This creates a useful binding between puzzle knowledge and key use, even though standard agreement still supplies confidentiality.

One puzzle, but three different packages

It is tempting to call the puzzle a public key and the solution a private key. That description hides the rest of the protocol. The sender also needs agreement material. The ciphertext needs an ephemeral key, a nonce, an authentication tag, and a reference to the exact public package that was used.

The public package in this experiment contains the board dimensions, public clues, a puzzle identifier, a salted commitment to the solution, and an agreement public key. The private package contains the complete solution, the commitment salt, and the matching agreement private key. The cipher envelope contains only message specific public material.

The 20 by 20 material we already have

The demonstration uses a 20 by 20 Yin Yang board. This is not a claim that 20 by 20 means 400 bits of security. It is material that we already possess: a valid solution, a public clue mask, and the two rules that let the recipient validate the private witness.

Every public clue is encoded in a fixed row order. Unknown cells use a separate symbol. The dimensions and clue strings are serialized with one canonical format. SHA 256 hashes this encoding to produce the puzzle identifier. The identifier becomes part of key derivation and part of the commitment. A different clue, dimension, or encoding therefore describes a different public instance.

How the browser experiment works

The live system below first tries X25519 through the Web Cryptography API. If the browser does not support it, the system uses elliptic curve Diffie Hellman with P 256. Both paths derive 256 shared bits. HKDF with SHA 256 uses the puzzle identifier as salt and a protocol label as context. AES 256 GCM encrypts the UTF 8 text with a new 96 bit nonce.

The complete public package is serialized and hashed. That fingerprint becomes authenticated data for AES GCM. The ciphertext is therefore tied to the puzzle, commitment, protocol version, and recipient agreement key. Changing any of those fields causes decryption to reject the envelope.

Generating key material…

What happens when we create a key?

KeyGen starts from a valid complete board. A clue mask creates the public puzzle. The system serializes that puzzle and computes its SHA 256 identifier. It then generates 128 random salt bits and computes a domain separated commitment over the salt, puzzle identifier, and complete solution.

The commitment has two jobs. First, it binds one private solution to one public package. Second, the random salt prevents the same solution from producing the same visible digest in different key records. The salt stays in the private package because public verification is not needed in this first design.

KeyGen also creates the recipient agreement pair. The public half joins the public puzzle. The private half joins the hidden solution. This pairing means that puzzle knowledge alone cannot decrypt current messages. It also means that stealing only the agreement private key is not accepted by this implementation unless the attacker also supplies the committed solution.

What does the sender do?

For every message, the sender creates a new ephemeral agreement pair. The ephemeral private key and recipient public key produce a shared secret. The ephemeral public key goes into the cipher envelope. The sender then runs HKDF and deletes the ephemeral private material when the operation ends.

AES GCM receives the derived content key, a random nonce, the plaintext, and the public package fingerprint. Its output contains ciphertext and a 128 bit authentication tag. The tag covers both the encrypted text and the public fingerprint. This prevents an attacker from moving a ciphertext to another puzzle package without detection.

What does the recipient check?

Decapsulation begins with rejection checks. The private board must match every public clue. Both colors must form one connected region. No solid 2 by 2 block can exist. The salted solution commitment must match. The public coordinates inside the agreement private key must also match the public agreement key.

Only after these checks does the system combine the recipient private key with the sender ephemeral public key. It derives the same AES key, recomputes the authenticated public fingerprint, and asks AES GCM to open the envelope. A wrong solution, wrong key, changed nonce, changed public package, or changed ciphertext causes failure.

When eight boards are really one board

A square Yin Yang board can be rotated or reflected in eight spatial forms. The colors can also be inverted when a protocol treats black and white as interchangeable. A key registry should not assign a new identity to every drawing of the same mathematical object.

The safe method is canonicalization before hashing. Generate every allowed form, serialize each form with the same rules, and choose the smallest encoding. The protocol then hashes that canonical encoding. The choice of allowed forms must be part of the protocol version because changing it changes key identity.

Why is a commitment not encryption?

The solution commitment hides the direct representation of the witness and binds the private package to the public package. It does not encrypt the solution. It also does not replace a proof of knowledge. A future protocol that needs public verification should use a reviewed proof system instead of revealing the salt and solution.

The visualization shows the avalanche behavior of SHA 256. One changed witness cell alters many digest bits. This is useful for binding. It says nothing about the effort needed to recover a valid solution from public clues. Hash behavior and puzzle hardness are different claims.

Why is board width not a security level?

An n by n board contains n squared cells, but those cells are not independent secret bits. Public clues remove choices. Connectivity and 2 by 2 constraints remove many more choices. Symmetry merges equivalent boards. A solver uses all of this structure.

A cryptographic parameter must predict attack work for instances drawn from a defined generator. We would need a large public challenge set, the exact generator, clue distributions, solution multiplicity, memory cost, parallel attack cost, and results from independent solvers. A single difficult instance is not a security level.

Who are we protecting the message from?

The current system separates two failures. If an attacker solves the puzzle, the witness loses its value, but the attacker still lacks the private agreement key. If an attacker steals the agreement private key without the solution, this implementation rejects the package. If both private parts are stolen, confidentiality is lost.

Other attacks matter too. A malicious sender can submit malformed ephemeral keys. A parser can disagree about canonical JSON. A nonce can repeat after a random number failure. An implementation can leak key material through logs or browser extensions. Protocol review must include these engineering failures, not only the mathematical puzzle.

NP completeness still does not give us a trapdoor

Yin Yang decision problems are NP complete. That result describes worst case problem families. Public key encryption needs more. KeyGen must create instances that are hard on average for attackers but easy for the trapdoor owner. The public distribution must not reveal which instances contain a trapdoor.

We do not have that native construction today. The complete solution is a witness, but it does not provide a public operation that only the witness can invert. This is why the working system keeps standard key agreement in charge of confidentiality. The puzzle receives a real role without receiving an unsupported security claim.

Where could this idea go next?

One practical next version could replace classical agreement with ML KEM from FIPS 203. The public puzzle can remain connected to the KEM key. A proof of knowledge could also let the recipient prove that a valid solution exists without exposing it. In that design, the puzzle would help with authentication and a standard post quantum method would protect the message.

The native trapdoor question is a different and much harder idea. We would need a generator with hidden structure, a public distribution that hides that structure, an efficient inverse for the owner, and strong evidence against structural attacks. I want to explore that question, but it should not protect real user data until independent cryptographers have tried to break it.

What would a real product need?

A production design would use a reviewed KEM and AEAD construction, stable binary encodings, explicit protocol versions, algorithm identifiers, key expiration, revocation, rotation, secure random generation, hardware backed private storage, constant time validation where secret data affects control flow, and test vectors shared between implementations.

It would also need misuse tests. Repeated nonces, truncated packages, unknown fields, duplicate fields, enormous boards, malformed points, wrong puzzle dimensions, invalid UTF 8, old protocol versions, and corrupted commitments must all fail in a defined way. The browser experiment is useful because these questions become visible. It is not a release candidate.

Where did the agent help?

The cryptographic direction, puzzle key idea, symmetry idea, and research questions came from the researcher. GPT 5.6 soul high was used to explore the protocol, implement the interactive system faster, test failure cases, and help turn the idea into this blog post.

There is also something interesting about using agents this way. They can shorten the distance between an idea and a working experiment. The researcher gets more chances to test a thought, notice a weakness, and then revise the direction. The human still decides which question matters and which claim is responsible.

Why not? That is really why I am doing this. We already have a beautiful puzzle, a public object, a private solution, and many open questions. We can now encrypt and decrypt text, connect the ciphertext to a public Yin Yang puzzle, and require the private solution during decryption. We can also see the exact missing piece: a native puzzle trapdoor with a security argument that other cryptographers can test. Maybe this does not become a new cryptographic system. Maybe it leads to a different use of puzzle knowledge. But the only good way to learn that is to build the idea carefully, ask where it fails, and then keep going.