This paper presents a new explicit infinite family of 2-quasi-perfect $p$-ary Lee codes of length $\frac{q-1}{2}$ and dimension $\frac{q-1}{2}-2k$ for $q = p^k \ge 14$, $p\geq 5$ a prime. Our codes are derived from the generating set $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$ of the additive group of the finite field $\mathbb{F}_{q^2}$. Furthermore, we bridge between 2-quasi-perfect Lee codes constructed by Mesnager, Tang, and Qi and well-known abelian Ramanujan graphs, specifically Li's graphs and finite Euclidean graphs, providing a unified theoretical framework for these families.

Constructing explicit RIP matrices is an open problem in compressed sensing theory. In particular, it is quite challenging to construct explicit RIP matrices that break the square-root bottleneck. On the other hand, providing explicit 2-source extractors is a fundamental problem in theoretical computer science, cryptography and combinatorics. Nowadays, there are only a few known constructions for explicit 2-source extractors (with negligible errors) that break the half barrier for min-entropy. In this paper, we establish a new connection between RIP matrices breaking the square-root bottleneck and 2-source extractors breaking the half barrier for min-entropy. Here we focus on an RIP matrix (called the Paley ETF) and a 2-source extractor (called the Paley graph extractor), where both are defined from quadratic residues over the finite field of odd prime order$p\equiv 1$(mod 4). As a main result, we prove that if the Paley ETF breaks the square-root bottleneck, then the Paley graph extractor breaks the half barrier for min-entropy as well. Since it is widely believed that the Paley ETF breaks the square-root bottleneck, our result accordingly provides a new affirmative intuition on the conjecture for the Paley graph extractor by Benny Chor and Oded Goldreich.

Abstract Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p of what is computed from messages. We design a QR-PSM protocol for any symmetric function $$f: \{0,1\}^n \rightarrow \{0,1\}$$ f : { 0 , 1 } n → { 0 , 1 } of communication complexity $$O(n^2)$$ O ( n 2 ) . As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of $$O(n^2\log n)$$ O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields $$\mathbb {F}_p$$ F p in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p. We show that there is a prime $$p \le (1+o(1))N^22^{2N-2}$$ p ≤ ( 1 + o ( 1 ) ) N 2 2 2 N - 2 such that any length-N pattern of quadratic (non)residues appears modulo p (and hence it can be used for general QR-PSM protocols), which improves the Peralta’s known result (Mathematics of Computation 1992) by a constant factor $$(1+\sqrt{2})^2$$ ( 1 + 2 ) 2 .

Complex codebooks with small inner-product correlation have many applications such as in code-division multiple access communications and compressed sensing. It is desirable but difficult to construct optimal codebooks achieving the well-known Welch bound. In this paper, complex codebooks are investigated from a graph theoretic perspective. A connection between codebooks and Cayley sum graphs is established. Based on this, many infinite families of complex codebooks are explicitly constructed, which are asymptotically optimal with respect to the Welch bound. These constructions not only include some known constructions as special cases but also provide flexible new parameters.

Compressed sensing is a celebrated framework in signal processing and has many practical applications. One of the challenging problems in compressed sensing is to construct deterministic matrices having the restricted isometry property (RIP). So far, there are only a few publications providing deterministic RIP matrices beating the square-root bottleneck on the sparsity level. In this paper, we investigate RIP of certain matrices defined by higher power residues modulo primes. Moreover, we prove that the widely-believed generalized Paley graph conjecture implies that these matrices have RIP breaking the square-root bottleneck. Also the compression ratio realized by these RIP matrices is significantly larger than 2.