An unbreakable cryptosystem

Arindam MitraarXiv 2004 · arXiv

Abstract

This paper explores a novel classical cryptosystem proposed by Arindam Mitra that aims to achieve "perfect secrecy" without the infrastructure requirements of Quantum Key Distribution (QKD). By leveraging a small initial shared secret to extract bits from a public stream of high-entropy random data, the system generates a continuous supply of secure keys. We examine the two-stage evolution of this protocol, from basic position-based extraction to a recursive expansion method designed to withstand authentication-based attacks.

Introduction

The quest for unbreakable encryption has traditionally led to two extremes: the mathematically perfect but practically cumbersome One-Time Pad (OTP) and the physically secure but expensive Quantum Key Distribution (QKD). The OTP requires a secret key as long as the message, which can never be reused—a logistical nightmare for modern communication. QKD solves the key distribution problem using quantum mechanics but necessitates specialized hardware. Mitra proposes a "middle way," a classical system that turns a small initial secret into an infinite supply of secure keys by "plucking" entropy from public randomness.

The Key Distribution Problem

Modern cryptography largely relies on computational security, where breaking a code is theoretically possible but practically infeasible for current hardware. However, the advent of quantum computing threatens these foundations. To achieve true "Shannon-level" security, a system must ensure that an eavesdropper gains zero information about the plaintext from the ciphertext.

System-I: Position-Based Extraction

The first iteration of the system relies on a shared secret bit-string $K$ between two parties, Alice and Bob. They categorize the positions of '1's and '0's in $K$ to create two position keys, $K^r$ and $K^p$. A third-party server broadcasts a public sequence of random bits, $S_i$.

Public random bit sequences (S_i) used as the entropy source.

Using their secret position keys, Alice and Bob extract specific bits from the public sequence. For example, if $K^r$ contains the positions {2, 3, 4, 6, 8, 12, 14}, they only record the bits at those indices from the public stream $S_i$ to form a new secret key $k_i^r$.

Extraction of secret keys (k_i^r) using a shared position key (K^r).

Because an eavesdropper does not know the positions $K^r$, they cannot distinguish the extracted bits from the rest of the public noise. This allows for the generation of multiple keys from a single broadcast.

System-II: Recursive Key Expansion

While System-I is secure for encryption, it faces a vulnerability if the extracted keys are ever revealed (e.g., used for authentication). If an attacker learns $k_i^r$, they can correlate it with the public $S_i$ to deduce the secret positions $K^r$.

System-II addresses this by making the process recursive. The first extracted key is used to encrypt a new, locally generated random bit-string $X_1$. This $X_1$ then becomes the position key for the next round of extraction. By constantly rotating the "map" used to extract entropy, the system prevents long-term correlation attacks, maintaining security even if individual session keys are compromised.

Security and Mathematical Foundation

The author demonstrates that the probability of an eavesdropper guessing the extracted key is $1/2^n$, where $n$ is the key length. This matches the security level of QKD. The system's strength lies in the fact that it does not reuse the bits of the secret key, but rather the positions—and in System-II, even those positions are updated continuously.

Conclusion and Limitations

Mitra's proposal offers a compelling classical alternative to quantum-based security. It allows multiple pairs of users to derive unique, secure keys from the same public broadcast, provided they start with different initial secrets. However, the system is a key expansion protocol; it still requires a secure method for the initial "bootstrap" exchange of the first secret $K$. Furthermore, its security is tethered to the quality of the public random source. If the source is compromised or predictable, the extracted keys lose their entropy. Future work involves refining local generation methods to reduce reliance on external communication channels.

Summary updated

BibTeX
@misc{mitra2004unbreakable,
  author = {Arindam Mitra},
  title = {{An unbreakable cryptosystem}},
  year = {2004},
  eprint = {cs/0412099},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0412099},
}
Figure