Graph coloring scheme builds lightweight symmetric cipher for short messages

Researchers at Vellore Institute of Technology have built a symmetric encryption scheme that turns the coloring of complete n-partite graphs into a working keystream generator, and they have been unusually blunt about what it can and cannot protect. The framework, described in Frontiers in Computer Science, derives its key from partition sizes and multi-character color labels, encrypts text with modular addition over a 127-symbol alphabet, and delivers meaningful confidentiality only against a ciphertext-only adversary when the message length does not exceed the keystream period. The authors position it as a graph-structured, session-bound, repeated-key additive cipher rather than a rival to standardized primitives such as AES or ChaCha20.

The construction begins with a complete n-partite graph, a graph whose vertices are divided into n disjoint partitions with edges running only between vertices in different partitions. Because vertices within one partition are mutually non-adjacent, they can share a color, and in a complete n-partite graph no two partitions can share a color, so the chromatic number equals exactly n. In the scheme, each partition carries a distinct color label written as a character string, such as Red, Blue or Yellow. Those labels are converted to their ASCII values, and a secret scalar weight is associated with each partition. The number of partitions and the partition sizes are public structural parameters recoverable from the transmitted graph, while the color labels constitute the shared secret exchanged between sender and receiver.

Key generation works by extending every color label cyclically to a common length m, defined as the length of the longest label, before summing the contributions of all partitions. This max-aligned padding makes the keystream period exactly m by construction rather than by approximation. The authors note that if each label cycled independently, the natural period would be the least common multiple of the label lengths, which is generally longer; they deliberately chose the shorter, exactly characterized period and flagged an LCM-based formulation as future work. Plaintext characters are mapped to their seven-bit ASCII values, which already lie in the range 0 to 126, so the reduction modulo 127 is injective and lossless. Encryption is then a symbol-wise modular addition of plaintext and keystream, and decryption is the corresponding modular subtraction. The scheme does not support extended ASCII, Unicode or arbitrary binary data, because the modulo-127 mapping would collapse those larger alphabets irreversibly.

The threat model distinguishes four adversary categories, and the security claims are made separately for each. Against a ciphertext-only adversary observing only ciphertext, recovery of the keystream for short messages requires an exhaustive search bounded above by 127 to the power m candidate keystreams. Once the message greatly exceeds the period, an adversary who suspects periodicity can apply Index of Coincidence or Kasiski-style analysis to estimate m and then run frequency analysis over the 127-symbol alphabet to recover individual keystream elements. Against a known-plaintext adversary, the picture is stark: exactly m plaintext-ciphertext pairs reveal the entire key sequence directly, a limitation the authors trace to every repeated-key additive stream cipher. Under chosen-plaintext access, a single query of length m recovers the key. The scheme also offers no integrity or authenticity guarantees against active network adversaries unless it is augmented with a message authentication code or digital signature, preferably in an encrypt-then-MAC construction.

The experimental work grounds these claims with measured numbers. Encryption and decryption times scale linearly with message length, with linear regression fits across message lengths from 100 to 2,000,000 characters yielding R-squared values of 0.998 for encryption and 0.997 for decryption. At a fixed message length of 100,000 characters, varying the partition count from 2 to 50 kept key-generation time under 0.2 milliseconds, confirming that the partition count contributes negligibly to runtime. Peak memory, profiled with Python’s tracemalloc, grew from 17.7 kilobytes at 1,000 characters to 16.1 megabytes at 1,000,000 characters, roughly 16.5 bytes per plaintext character. Empirical ciphertext entropy rose with the partition count, reaching 6.88 bits per symbol at n = 8 against a theoretical maximum of about 6.99 bits for the 127-symbol alphabet, with uniformity at 98.4 percent.

The attack-oriented experiments are the most revealing. Exhaustive search over the full parameter space completed in well under three minutes even for a period of 4 on a single unoptimized CPU core, and 31 to 56 percent of all candidate keystreams produced printable-ASCII decryptions of a length-m ciphertext, so brute force returns a large set of equally plausible candidates rather than a unique key. Extrapolating from a measured throughput of 1.58 million keys per second at m = 4, the authors estimated exhaustive search times for larger periods: about 5.8 hours at m = 5, 30.7 days at m = 6, 10.7 years at m = 7 and 1,358 years at m = 8. They stress these are single-core, unoptimized Python baselines that dedicated hardware would shrink substantially, and that the bounds should not be read as security comparable to ciphers with keyspaces of 2 to the 128 or larger.

Correlation analysis exposed the scheme’s principal statistical weakness. Under natural-language plaintext, adjacent-symbol correlation ranged from -0.325 to 0.113, closely tracking correlation already present in the plaintext itself, because the additive construction provides no diffusion and carries plaintext correlation through unchanged. When the experiment was repeated with uncorrelated pseudo-random plaintext, lag-1 correlation fell to within the null range of roughly plus or minus 0.014, confirming that component is plaintext-inherited. Correlation at lag equal to the keystream period, however, remained above the null bound in every tested configuration, from 0.043 to 0.511, regardless of plaintext content. That lag-m signature is precisely the statistical regularity exploited by Kasiski and Index-of-Coincidence period detection, and the authors identify keystream periodicity, not local ciphertext structure, as the scheme’s main vulnerability.

Further measurements quantified what the graph structure does and does not add. Index-of-Coincidence period detection succeeded on 94.2 percent of trials for a period of 4 with messages ten times the period, and 99.9 percent at fifty times the period, while detection dropped to 18.7 percent for a period of 16 at ten times and 14.2 percent for a period of 32 at twenty times. Under key perturbation, changing a single character in one color label altered 87 to 94 percent of ciphertext symbols, while incrementing a partition size changed all of them. Flipping a single plaintext bit changed only the corresponding ciphertext symbol, with a roughly 50 percent bit-change rate within that symbol and zero change elsewhere, confirming confusion without diffusion. NIST SP800-22 tests, run with seven-bit packing, showed the Frequency-Within-Block test statistically indistinguishable from a true-random baseline under the session-bound operating mode, with the Monobit deviation reduced by roughly 17 to 245 orders of magnitude compared with sustained single-key reuse.

The authors also benchmarked the scheme against reference implementations of ChaCha20, ASCON-128, SPECK-64/128, SIMON-64/128 and PRESENT-80, each used in counter mode, within the same Python process. Their scheme encrypted 10,000 characters in 1.54 milliseconds, faster in that same-language comparison than all five baselines, though ChaCha20’s compiled C backend reached 286 megabytes per second against 6.19 megabytes per second for the graph scheme. The authors are careful to frame this as a computational-overhead comparison under identical software conditions, not evidence of security equivalence: the keyspace of 127 to the power m, typically far below 2 to the 80 to 2 to the 128, the absence of diffusion and the lack of built-in authentication place the scheme well outside the security class of all five comparators.

The practical prescription follows directly from the mathematics. The authors recommend restricting messages to at most m symbols per session, renegotiating graph parameters for each session to ensure a fresh keystream, and incorporating a nonce or session identifier into the key derivation so that distinct sessions use distinct keys. Application scenarios, from smart homes and wireless sensor networks to healthcare data and financial technology, are presented as conceptual prospects requiring integration testing, protocol analysis and domain-specific security assessment before any deployment. The conclusion lists the open problems plainly: the effective keyspace accounting for parameter collisions has not been tightly characterized, the scheme provides confidentiality only, repeated-key extension introduces known-plaintext vulnerability for messages longer than the key period, and no formal security reduction to a standard hardness assumption has been established. What the paper delivers is a formally grounded generalization of earlier bipartite and tripartite graph-based encryption to arbitrary n, with a clear-eyed account of where a repeated-key additive cipher fits in the modern cryptographic landscape.

Subject of Research: A graph-coloring-based symmetric encryption scheme for lightweight, session-bound protection of short messages

Article Title: Secure symmetric encryption using coloring of multipartite graphs

Article References: Gomathi, D., & Nagarajan, S. (2026). Secure symmetric encryption using coloring of multipartite graphs. Frontiers in Computer Science, 8, Article 1918269. https://doi.org/10.3389/fcomp.2026.1918269

Image Credits: AI Generated

DOI: 10.3389/fcomp.2026.1918269

Keywords: symmetric encryption, graph coloring, multipartite graphs, lightweight cryptography, repeated-key additive cipher, keystream period, ciphertext-only attack, known-plaintext attack, Index of Coincidence, Internet of Things security, modular arithmetic, session-bound encryption