Syntactic separation of Skolem functions in local systems implies computational indistinguishability with Omega(n) or Omega(2^n) derivation lower bounds, presented as an abstract obstruction governing Natural Proofs, Type Omitting Theorem, and AC^0 barriers.
From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The Mixed-Radix One-Time Pad (MR-OTP) extends the classical OTP to heterogeneous alphabets while preserving perfect secrecy. We provide a practical, bias-free method to convert raw binary entropy from a QKD source into uniform mixed-radix keys by identifying Horner's method and its inverse as the natural mapping between binary integers and mixed-radix tuples. We show that naive modular reduction induces bias and prove that rejection sampling restores uniformity with optimal expected cost. We establish end-to-end information-theoretic security for single and multi-session pipelines, quantify efficiency gains, present a batched extractor, and give unconditional and conditional results on the Base Recovery Problem.
fields
cs.LO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Syntactic Separation Implies Computational Indistinguishability: An Abstract Obstruction Theorem
Syntactic separation of Skolem functions in local systems implies computational indistinguishability with Omega(n) or Omega(2^n) derivation lower bounds, presented as an abstract obstruction governing Natural Proofs, Type Omitting Theorem, and AC^0 barriers.