SoP-CTR: A Lightweight Stream Cipher with Beyond-Birthday-Bound Security for IoT and Embedded Devices

Abstract

As systems migrate toward post-quantum readiness, symmetric keys are kept longer and protect larger data volumes, a regime in which keystream security beyond the birthday bound matters. The dominant block–cipher counter mode, AES-CTR (Advanced Encryption Standard, counter mode), caps keystream security at the birthday bound regardless of key length, and, to our knowledge, no lightweight stream cipher pairs provable beyond-birthday-bound security with a permutation standardised by the National Institute of Standards and Technology (NIST). We propose SoP-CTR, a stream cipher built from the NIST-standardised Ascon-p12 permutation via the Sum of Permutations (SoP) paradigm. The z-split SoP framework achieves single-key beyond-birthday-bound (BBB) security by XORing a split constant into the counter word, eliminating independent key derivation. We prove an explicit two-term pseudorandom-function (PRF) advantage bound Adv≤q3/2/2320+2pq/2256, valid for pairwise-distinct counters in [0,263). The online term is negligible throughout this 263-block range, and the offline term bounds adversarial key-search and is the binding constraint for post-quantum offline budgets. The SoP construction provably eliminates the birthday distinguisher that breaks a hypothetical single-call CTR-Ascon at q≈2160. We also give the first quantum analysis of this domain-separated single-key variant in the Q1 model, where construction queries are classical and the public permutation may be evaluated quantumly, obtaining an attack at 285.3 and an unconditional lower bound of 264.3, so the post-quantum figure is the best known attack cost of 285.3 rather than the generic 2128 Grover level. On a physical STM32F407 ARM Cortex-M4 (168 MHz), hardware cycle-counter measurements yield 61.44 cycles per byte (cpb) for the unrolled variant, about 4.6% faster than Ascon-128 keystream extraction (64.39 cpb), and 63.78 cpb for the memory-optimised rolled variant (3832 bytes Flash), while providing a strictly stronger BBB guarantee. An x86-64 AVX2 two-block variant achieves 2.57 cpb at 1 KiB.