Optical character recognition now reads a handwritten note about as well as a person does, and cameras are becoming ordinary input devices for machines as well as for people. Hence a camera can serve as a channel between two machines with no network between them, i.e. an optical air gap. In our paper with Jintai Ding, published in the Proceedings of the Computer Vision Conference (CVC) 2026, we look at the old paper-pencil stencil cipher with a camera, rather than a person, reading the page, and use it as a layer of obfuscation over the Merkle–Hellman knapsack cryptosystem (MHKC).
MHKC rests on the subset-sum problem, which is NP-hard in general. A super-increasing sequence, where each number exceeds the sum of all before it, is easy to solve, and MHKC hides one behind a modular transformation to form a trapdoor. Its encryption is much faster than RSA. However, Shamir and Adleman broke it, because the modular transformation is linear and the secret key has a special structure, and variants using the Chinese Remainder Theorem fall the same way to lattice reduction with LLL. However, partitioning the plaintext, splitting the parts into geometric stencils and adding combinatorial entropy before encryption leaves the lattice attack with a matrix of letters rather than the message, as we will analyze.
The stencil
The matrix below hides a message in the cells marked in red. The rest of the matrix is pseudo-random filler that is not correlated with the message. A camera that knows where the stencils are zooms on each marked region in turn and reads the text; a reader who does not know sees only a page of letters. Nothing precludes treating the matrix as a byte stream instead, i.e. unwound row by row into a sequence of length rows × columns, in which case a stencil is a set of indices into that stream.
The scheme
Let S be the set of all stencil shapes, connected or not. S is public. Let M be the message and l = |M| its length. Let Rl be a random partition of a random number lmax ≥ l, i.e. a set of positive integers xi summing to lmax. Let SRl ⊂ S be a subset of shapes with a bijection g : Rl → SRl, such that the encrypted text of M fits in the chosen stencils. For example, the “RLD” stencil above is the set {(13, 12), (13, 13), (14, 13)}. The ciphertext is split among the stencils and permuted by σ until it cannot be told apart from the letters around it. The secret key is
{ S_Rl, g, Private_mhkc, σ },
and the underlying cipher is MHKC with the key pair {Publicmhkc, Privatemhkc}. The shared key is exchanged over a public channel with ECDH or RSA. By default the camera zooms left to right and top to bottom. If the zoom order is itself random, the decrypter re-permutes the text it reads in polynomial time, and the key need not carry σ.
Cryptanalysis
LLL is still applicable; the lattice here is two-dimensional, where even Gauss’s reduction runs in polynomial time. However, the attack only recovers the decrypted matrix, and the message sits in that matrix permuted among random letters. The question is therefore how likely an adversary is to pick out the right stencils after the lattice attack has succeeded. Choosing a partition of n = lmaxuniformly at random succeeds with probability P1 = 1/P(n), where P(n) is the partition function, and by Hardy and Ramanujan
P₁ ≈ 4n√3 / eπ√(2n/3).
With k = |Rl| stencils, the number of ways to choose the stencil set, and hence the number of maps g, is C(|S|, k), so P2 = 1/C(|S|, k). Assuming the two choices are independent, the probability of finding the stencils that hold the message is P = P1P2, and it can be made as small as we like by the choice of lmax, |S| and k, irrespective of the cipher underneath.
For example, a message of length 100 has P(100) = 190,569,292 partitions. With |S| = 40,000 and k = 20, i.e. 20 numbers xi summing to 100,
P = 1 / (190,569,292 · C(40000, 20)) ≈ 1.17 × 10−82,
i.e. about 272 bits. (The paper states this as 82-bit security, which is the base-10 exponent; log2(1/P) is 272.2.)
Complexity and extensions
A random partition of n is generated in O(n3/4) time by Fristedt’s algorithm and a random stencil set in O(n) by Vitter’s sequential sampling. Hence the scheme runs in O(n) in the worst case, assuming MHKC runs fast over many iterations. The matrix need not be specific to one message. Several messages may share one random matrix, or both sides may refer to an agreed ASCII matrix containing every message, in which case nothing is encrypted at all and the cost is that of exchanging the stencils. The main stencils may also partition the whole matrix into districts. This brings in the geometry of gerrymandering, which is NP-hard by reduction from the rectilinear minimum Steiner tree problem, and a message inside one district then needs further stencils to locate, which lowers P further.
Limits
The paper is marked preliminary, and the scheme has practical limits. Reading a 100-byte message by OCR takes 10 to 30 seconds, against 100 to 500 ms for a QR code, and OCR accuracy in normal lighting drops to about 90%. Reed–Solomon forward error correction before scattering into the stencils, as QR codes do, would compensate at about 33% overhead. The stencil coordinates assume near-perfect alignment, whereas a real camera introduces tilt and distortion; corner anchors with a homographic correction, again as in QR codes, would address this. The key is large: a 100-byte message needs a 250-byte key, a ratio of 2.5 : 1 against 0.32 : 1 for AES-256, and there is likely room to encode the partitions more compactly. Where stronger security is required, MHKC can be replaced by AES-256.
Beyond this, stencils in an n-dimensional hypercube of character cells, and a purely geometric public-key scheme built from public and private stencil shapes, are open. For example, a 9 × 9 grid has 706,152,947,468,301 partitions into equal-sized districts, which suggests room for a geometric scheme resistant to quantum attack.
Acknowledgment
We thank Sarang Vehale, a graduate student at the National Forensic Sciences University, Delhi, and the Indian Institute of Technology, Chennai, for the details of the practical limitations above.
The paper
G. Anantharaman and J. Ding, “A Camera Zoom-Based Paper-Pencil Cipher Encryption Scheme Atop Merkle–Hellman Knapsack Cryptosystem (Preliminary)”, in K. Arai and P. Lorenz (eds.), Proceedings of the Computer Vision Conference (CVC) 2026, Volume 3, Lecture Notes in Networks and Systems, vol. 1976, pp. 30–37, Springer, 2026. doi:10.1007/978-3-032-26217-2_3. A preprint is on the IACR ePrint archive as 2025/1481. The work was first presented at MathFest 2025.