The Relative Eigenvector Problem (REP) is a simple generalization of the well-known Eigenvector Problem. It was applied by Griess and Ryba in 2002 as the non-linear step in a method to compute finite simple subgroups of simple Lie groups of exceptional type. It has since been used in new algorithms to compute tensor decompositions, systems of imprimitivity, and semilinear tensor decompositions of irreducible modular representations of finite groups. Ryba, in 2022, showed that specific cases of this problem are efficiently solvable, but a more general treatment remained an open problem. In this paper, we investigate the complexity of REP and derive multiple results on it. First, we show that its decisional variant is NP-complete by reducing it from CNF-SAT. Our reduction is tight with the solution to the CNF-SAT instance being directly available from the solution to the Relative Eigenvector Problem. We then turn to investigating the tractability of solving the REP for different parameter regimes. We introducing a new model of the Relative Eigenvector Problem as an instance of the MinRank problem, a well-known NP-Hard problem occurring in computer algebra with notable applications in cryptography or real algebraic geometry. Upper bounds on the complexity of solving generic instances of the MinRank problem were obtained by Faugère, Safey El Din and Spaenlehauer in 2011 by analyzing the complexity of computing a Gröbner basis of a closely related determinantal ideal. We use these results to derive upper bounds for the REP problem. We further provide a wide range of parameter regimes for which REP can be solved in polynomial time.

Abstract In this paper, we analyze the hardness of the Matrix Code Equivalence () problem for matrix codes endowed with the rank metric, and provide the first algorithms for solving it. We do this by making a connection to another well-known equivalence problem from multivariate cryptography—the Isomorphism of Polynomials (). Under mild assumptions, we give tight reductions from to the homogenous version of the Quadratic Maps Linear Equivalence () problem, and vice versa. Furthermore, we present reductions to and from similar problems in the sum-rank metric, showing that is at the core of code equivalence problems. On the practical side, using birthday techniques known for , we present two algorithms: a probabilistic algorithm for running in time $$q^{\frac{2}{3}(n+m)}$$ q 2 3 ( n + m ) up to a polynomial factor, and a deterministic algorithm for with roots, running in time $$q^{\min \{m,n,k\}}$$ q min { m , n , k } up to a polynomial factor. Lastly, to confirm these findings, we solve randomly-generated instances of using these two algorithms.

Privacy-preserving techniques for processing sets of information have attracted the research community’s attention in recent years due to society’s increasing dependency on the availability of data at any time. One of the fundamental problems in set operations is known asPrivate Set Intersection(PSI). The problem requires two parties to compute the intersection between their sets while preserving correctness and privacy. Although several efficient two-party PSI protocols already exist, protocols for PSI in the multi-party setting (MPSI) currently scale poorly with a growing number of parties, even though this applies to many real-life scenarios. This paper fills this gap by proposing two multi-party protocols based on Bloom filters and threshold homomorphic PKEs, which are secure in the semi-honest model. The first protocol is a multi-party PSI, whereas the second provides a more subtle functionality -thresholdmulti-party PSI (T-MPSI) - which outputs items of the server that appear in at least some number of other private sets. The protocols are inspired by the Davidson-Cid protocol based on Bloom filters. We compare our MPSI protocol against Kolesnikovet al., which is among the fastest known MPSI protocols. Our MPSI protocol performs better than Kolesnikovet al.in terms of run time, given that the sets are small and there is a large number of parties. Our T-MPSI protocol performs better than other existing works: the computational and communication complexities are linear in the number of elements in the largest set given a fixed number of colluding parties. We conclude that our MPSI and T-MPSI protocols are practical solutions suitable for emerging use-case scenarios with many parties, where previous solutions did not scale well.

The best algorithms for the Learning Parity with Noise (LPN) problem require sub-exponential time and memory. This often makes memory, and not time, the limiting factor for practical attacks, which seem to be out of reach even for relatively small parameters. In this paper, we try to bring the state-of-the-art in solving LPN closer to the practical realm. We improve upon the existing algorithms by modifying the Coded-BKW algorithm to work under various memory constrains. We correct and expand previous analysis and experimentally verify our findings. As a result we were able to mount practical attacks on the largest parameters reported to date using only 239bits of memory.

This paper presents MQDSS, the first signature scheme with a security reduction based on the problem of solving a multivariate system of quadratic equations ( $$\mathcal {MQ}$$ problem). In order to construct this scheme we give a new security reduction for the Fiat-Shamir transform from a large class of 5-pass identification schemes and show that a previous attempt from the literature to obtain such a proof does not achieve the desired goal. We give concrete parameters for MQDSS and provide a detailed security analysis showing that the resulting instantiation MQDSS-31-64 achieves 128 bits of post-quantum security. Finally, we describe an optimized implementation of MQDSS-31-64 for recent Intel processors with full protection against timing attacks and report benchmarks of this implementation.

Staircase-Generator codes (St-Gen codes) have recently been introduced in the design of code-based public key schemes and in the design of steganographic matrix embedding schemes. In this paper we propose a method for random splitting of St-Gen Codes and use it to design a new coding based public key encryption scheme. The scheme uses the known list decoding method for St-Gen codes, but introduces a novelty in the creation of the public and private key. We modify the classical approach for hiding the structure of the generator matrix by introducing a technique for splitting it into random parts. This approach counters the weaknesses found in the previous constructions of public key schemes using St-Gen codes. Our initial software implementation shows that encryption using Random Split of St-Gen Codes compared to original St-Gen Codes is slower by a linear factor in the number of random splits of the St-Gen code, while the decryption complexity remains the same.

We introduce a new family of binary linear codes suitable for steganographic matrix embedding. The main characteristic of the codes is the staircase random block structure of the generator matrix. We propose an efficient list decoding algorithm for the codes that finds a close codeword to a given random word. We provide both theoretical analysis of the performance and stability of the decoding algorithm, as well as practical results. Used for matrix embedding, these codes achieve almost the upper theoretical bound of the embedding efficiency for covers in the range of 1000 – 1500 bits, which is at least an order of magnitude smaller than the values reported in related works.

In this paper we describe two methods for constructing Multivariate Quadratic Quasigroups (MQQ) in Galois fields of any characteristic and order. Our constructions extend the previously known constructions defined for operations over the prime field of characteristic 2. Application of these new constructions can reduce the public key size of the recently introduced family of public key schemes based on MQQs up to 58 times.