The Star Product of Uniformly Random Codes
Preprint
Abstract
We consider the problem of determining the expected dimension of the star product of two uniformly random linear codes that are not necessarily of the same dimension. We achieve this by establishing a correspondence between the star product and the evaluation of bilinear forms, which we use to provide a lower bound on the expected star product dimension. We show that asymptotically in both the field size q and the dimensions of the two codes, the expected dimension reaches its maximum. Lastly, we discuss some implications related to private information retrieval, secure distributed matrix multiplication, quantum error correction, and the potential for exploiting the results in cryptanalysis.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- The Schur product of evaluation codes and its application to CSS-T quantum codes and private information retrievalComputational and Applied Mathematics, 2026
- On the dimension and structure of the square of the dual of a Goppa codeDesigns, Codes and Cryptography, 2022
- Quantum Private Information Retrieval From Coded and Colluding ServersIEEE Journal on Selected Areas in Information Theory, 2020
- Private and Secure Distributed Matrix Multiplication With Flexible Communication LoadIEEE Transactions on Information Forensics and Security, 2020
- Secure Multiparty Computation and Secret Sharing2015
- Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codesDesigns, Codes and Cryptography, 2014
- Multiple-particle interference and quantum error correctionProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1996
- Good quantum error-correcting codes existPhysical Review A, 1996
- On the existence of error-correcting pairsJournal of Statistical Planning and Inference, 1996
- On decoding by error location and dependent sets of error positionsDiscrete Mathematics, 1992