💻 computer science

New Ideas on a New Old Type of Cipher:The Mixed-Radix One-Time Pad

This paper formalizes and generalizes the one-time pad to non-uniform bases as the Mixed-Radix One-Time Pad (MR-OTP), proving it achieves Shannon perfect secrecy, recovering classical variants as special cases, and demonstrating that secret bases cannot reduce the required key entropy while proposing a secure session protocol.

Original authors: Fabio F. G. Buono

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fabio F. G. Buono

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: A Better Way to Pack a Suitcase

Imagine you have a suitcase (a message) you want to send to a friend, but you want to make sure no one else can open it. The gold standard for this is the One-Time Pad (OTP). Think of the OTP as a magical lock where you need a key that is exactly the same size as your suitcase. If the key is truly random and used only once, the lock is unbreakable.

However, the traditional OTP usually forces you to pack everything into a standard "binary" suitcase (using only 0s and 1s). If you are sending a letter, you have to convert every letter into a long string of 0s and 1s, which can be inefficient.

This paper introduces a new version called the Mixed-Radix One-Time Pad (MR-OTP). Instead of forcing everything into a binary suitcase, it lets you build a custom suitcase where every compartment can be a different size.

How It Works: The Custom Suitcase

Imagine you are packing a suitcase with three different items:

A letter (26 possibilities: A–Z).
A traffic light color (3 possibilities: Red, Yellow, Green).
A coin flip (2 possibilities: Heads, Tails).

In the old binary system, you would have to convert all of these into a long, messy string of 0s and 1s.
In the MR-OTP, you create a "mixed-radix" system. You have three slots in your suitcase:

Slot 1: Holds 26 options.
Slot 2: Holds 3 options.
Slot 3: Holds 2 options.

To lock it, you don't just use a single key. You use a key for each slot:

A random number between 0–25 for the letter.
A random number between 0–2 for the light.
A random number between 0–1 for the coin.

You add your secret message to these random numbers (like mixing ingredients in a bowl) to create the "ciphertext" (the locked suitcase). To unlock it, your friend subtracts the same random numbers. Because the math is done in the specific "base" of each slot (mod 26, mod 3, mod 2), the message comes out perfectly.

The Big Discovery: Does This Make the Key Shorter?

The author asks a very tempting question: "If we keep the sizes of the slots (the bases) secret, can we use a shorter key?"

Imagine you tell your friend, "I'm using a suitcase with a 26-slot, a 3-slot, and a 2-slot," but you don't tell them which slot is which. Maybe you swap them around? The hope was that this secret arrangement might let you get away with a smaller key.

The paper proves this is impossible.
The author shows that for the lock to be mathematically unbreakable (perfect secrecy), the random numbers (the key) must still cover every single possibility in every slot.

The Analogy: Imagine trying to hide a specific card in a deck. If you shuffle the deck (the message) and then deal a random card (the key) to cover it, the card you deal must be able to be any card in the deck. If you try to use a smaller deck of keys, the math breaks, and the secret leaks.
The Result: Even if you hide the "rules" of the suitcase (the bases), the key still needs to be just as long and random as the message itself. You cannot cheat the laws of information theory to get a shorter key.

The Real Benefit: Efficiency, Not Magic

So, if the key isn't shorter, why use this new system? The paper argues it's about efficiency and adaptability, not magic.

Natural Packing: If you are sending DNA data (4 letters: A, C, T, G), you don't need to force it into binary (0s and 1s). You can just use a "base-4" slot. It fits the data naturally, like putting a round peg in a round hole instead of a square one.
Key Rolling: The paper suggests a protocol where Alice and Bob share a giant "roll" of keys. For the first message, they use a specific set of bases (e.g., for text). For the next message, they unroll a new section of the key that defines a different set of bases (e.g., for numbers).
- Crucial Rule: They never reuse the same part of the key roll. This keeps the security perfect while allowing them to switch formats on the fly.

What This Means (and Doesn't Mean)

What it IS: A formal, mathematically proven way to use the One-Time Pad on data that isn't just binary. It confirms that the old binary OTP is just a special case of this new, more flexible system.
What it IS NOT: It is not a way to break the rule that "Key Length must be at least Message Length." It does not offer a "free lunch" where you can use a tiny key to lock a huge message.
The Open Question: The paper admits that while the math is perfect, there is a practical question left unanswered: If an attacker doesn't know the "bases" (the sizes of the slots), is it hard enough for them to guess the right combination to crack the code? The paper leaves this as a mystery for future research.

Summary

The Mixed-Radix One-Time Pad is like upgrading from a rigid, single-size shipping container to a set of modular, custom-sized crates. It allows you to pack different types of data more naturally and switch formats easily. However, the paper firmly states that security still costs the same: you still need a key as long and random as the message itself. You gain flexibility, but you don't gain a shortcut to perfect secrecy.

Technical Summary: The Mixed-Radix One-Time Pad (MR-OTP)

Problem Statement
The paper addresses the representation and encryption of data using non-uniform bases (mixed-radix numeral systems). While a 2012 preprint introduced a cipher based on decomposing integers via decreasing divisors, it remained an undeveloped sketch with awkward analytical constraints. The core problem is to formalize this concept into a rigorous cryptographic primitive that generalizes the classical One-Time Pad (OTP) to mixed bases, while determining whether the use of secret bases can reduce the information-theoretic key requirements for perfect secrecy.

Methodology
The author formalizes the underlying mixed-radix representation and defines the Mixed-Radix One-Time Pad (MR-OTP).

Representation: A message $M$ is treated as a tuple of digits $(m_1, \dots, m_L)$ within a digit space defined by a sequence of bases $B = (b_1, \dots, b_L)$ , where each $b_i \ge 2$ . The message corresponds to an integer via positional weights derived from the product of subsequent bases.
Encryption: The cipher operates digit-wise. Given a key $K = (k_1, \dots, k_L)$ drawn uniformly at random from the key space, encryption is performed as $c_i = (m_i + k_i) \mod b_i$ .
Decryption: The inverse operation is $m_i = (c_i - k_i) \mod b_i$ .
Analysis: The paper employs Shannon's definition of perfect secrecy, utilizing Bayes' rule to analyze the conditional probability of messages given ciphertexts. It also examines the entropy of the key space when bases are treated as secret versus when they are fixed.

Key Contributions

Formalization of MR-OTP: The paper defines the MR-OTP as the natural extension of the OTP to mixed-radix systems, replacing bitwise XOR with digit-wise addition modulo $b_i$ .
Proof of Perfect Secrecy and Correctness:
- Correctness: Proven by showing the encryption map is a bijection on the finite cyclic group $\mathbb{Z}_{b_i}$ for each position.
- Perfect Secrecy: Proven by demonstrating that for a uniformly random key, the probability of a ciphertext $c$ given a message $m$ is independent of $m$ . Consequently, the posterior probability of the message given the ciphertext equals the prior probability.
Generalization of Classical OTPs: The paper establishes that the classical binary OTP is the specific case where all $b_i = 2$ , and fixed-base variants recover OTPs over arbitrary alphabets (e.g., base 26 for Latin text).
Resolution of the "Short Key" Conjecture: The paper investigates the hypothesis that treating the bases $B$ $B$ as part of the secret key could allow the additive pad $k$ $k$ to be shorter than the message while maintaining perfect secrecy. It proves this is false.
- Reasoning: Perfect secrecy requires the additive pad $k$ to be uniformly distributed over the full set $\{0, \dots, b_i-1\}$ for every position. If the pad is shortened (i.e., does not cover the full entropy of the message space), the conditional probability $P[C|M]$ becomes dependent on $M$ , breaking perfect secrecy. The entropy of the secret bases $H(B)$ adds to the total key entropy but cannot substitute for the entropy required in the additive pad.
Key-Rolling Session Protocol: A practical protocol is proposed where a shared initial key is partitioned into disjoint segments. Each session uses a fresh segment for the additive pad and a fresh segment to define the bases for the next session. This preserves perfect secrecy while allowing the bases to adapt to the structure of the data (e.g., matching base 26 for text) for encoding efficiency, without reducing the total key material consumed.

Results

Theoretical Bounds: The MR-OTP satisfies Shannon's bound $|K| \ge |M|$ . The key space and message space coincide ( $K = D_B = M$ ), ensuring no key material is wasted.
Entropy Accounting: The total key entropy required is $H(K) = H(B) + H(k|B)$ . Since $H(k|B) \ge H(M)$ is required for perfect secrecy, the inclusion of secret bases strictly increases the total key entropy requirement rather than reducing it.
Overhead: In the proposed session protocol, the overhead of transmitting the bases is negligible when the average base size is large relative to the bits required to represent the base itself. In the degenerate case of binary bases ( $b_i=2$ ), the overhead equals the pad length, offering no representational gain over standard binary OTP.

Significance and Claims
The paper claims to provide a "clean generalization" of the OTP that connects algebraic group theory (OTP over finite abelian groups) with numeral systems. Its primary significance lies in:

Clarification: It rigorously formalizes a previously sketchy concept, removing the "side constraints" of the original 2012 sketch.
Debunking a Misconception: It explicitly refutes the idea that secret bases can lower the information-theoretic key requirement for perfect secrecy, clarifying that any such reduction would violate the uniformity hypothesis essential to Shannon's proof.
Practical Utility: It positions the mixed-radix structure not as a method for key compression, but as a tool for encoding efficiency and adaptivity. By matching bases to the source alphabet (e.g., DNA or text), the system avoids artificial binary conversion and padding, making the OTP more efficient in representation while maintaining strict information-theoretic security.

The paper concludes by identifying open problems regarding the average-case hardness of recovering secret bases and the optimal selection of bases for structured sources, noting that the security of the base selection itself remains a computational rather than information-theoretic question.