arXiv preprint ·
Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Sendrier's Support Splitting Algorithm (SSA) is the standard solver for the Permutation Equivalence Problem (PEP); its cost is dominated by a term that grows exponentially in the hull dimension. We study, mathematically, how much this cost can be lowered by replacing the standard inner product, on which the hull is defined, with an alternative bilinear form. Two structural results give a complete answer: only a narrow two-parameter family of bilinear forms produces a hull on which SSA can still operate, namely those whose matrix in the standard basis is a linear combination of the identity and the all-ones matrix; and even within this family the hull dimension drops by at most one (with the reduction achieved on every self-dual code whose length is coprime to the field characteristic). Together, these results give a tight upper bound: since SSA on a code with hull dimension $h$ has cost dominated by $q^h$, replacing the standard hull with $\mathrm{Hull}_M$ lowers this dominant term from $q^h$ to at best $q^{h-1}$, so no bilinear-form generalization of the inner product can reduce the SSA cost by more than a factor of $q$, the field size. Going beyond this requires invariants outside the bilinear framework. As an application, we verify that PEP-based SPECK admits the factor-$q$ cost reduction, while LEP-based LESS and PKP-based PERK lie outside our framework. A SageMath implementation of the bilinear-hull preprocessing confirms feasibility at SPECK's recommended length $n = 252$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Cryptography & Security
Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes
Polynomial-Time Minimax Prediction for Stationary Renewal Processes
Cyclotomic polynomials with trinomial irreducible factors over finite fields
Secrecy Sum-Rate Maximization for RSMA-Enabled Pinching-Antenna Systems
Spatial Token Interleaving and Two-Pass BP Decoding for Semantic Image Transmission
Get the few papers worth your time in Cryptography & Security every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.