American Institute of Mathematical Sciences

We present a code-based public-key cryptosystem, in which we use Reed-Solomon codes over an extension field as secret codes and disguise it by considering its shortened expanded code over the base field. Considering shortened expanded codes provides a safeguard against distinguisher attacks based on the Schur product. Moreover, without using a cyclic or a quasi-cyclic structure we obtain a key size reduction of nearly \begin{document}$ 45 \% $\end{document} compared to the classic {McE}liece cryptosystem proposed by Bernstein et al.

Subfield subcodes of algebraic-geometric codes are good candidates for the use in post-quantum cryptosystems, provided their true parameters such as dimension and minimum distance can be determined. In this paper we present new values of the true dimension of subfield subcodes of \begin{document}$ 1 $\end{document}–point Hermitian codes, including the case when the subfield is not binary.

In this paper, we define a linear code by using multi-variable functions, and construct three classes of minimal linear codes with few-weight from multi-variable functions.

In this paper, we investigate the Gowers \begin{document}$ U_2 $\end{document} norm for generalized Boolean functions, and \begin{document}$ \mathbb{Z} $\end{document}-bent functions. The Gowers \begin{document}$ U_2 $\end{document} norm of a function is a measure of its resistance to affine approximation. Although nonlinearity serves the same purpose for the classical Boolean functions, it does not extend easily to generalized Boolean functions. We first provide a framework for employing the Gowers \begin{document}$ U_2 $\end{document} norm in the context of generalized Boolean functions with cryptographic significance, in particular, we give a recurrence rule for the Gowers \begin{document}$ U_2 $\end{document} norms, and an evaluation of the Gowers \begin{document}$ U_2 $\end{document} norm of functions that are affine over spreads. We also give an introduction to \begin{document}$ \mathbb{Z} $\end{document}-bent functions, as proposed by Dobbertin and Leander [8], to provide a recursive framework to study bent functions. In the second part of the paper, we concentrate on \begin{document}$ \mathbb{Z} $\end{document}-bent functions and their \begin{document}$ U_2 $\end{document} norms. As a consequence of one of our results, we give an alternate proof to a known theorem of Dobbertin and Leander, and also find necessary and sufficient conditions for a function obtained by gluing \begin{document}$ \mathbb{Z} $\end{document}-bent functions to be bent, in terms of the Gowers \begin{document}$ U_2 $\end{document} norms of its components.

A key step in Regev's (2009) reduction of the Discrete Gaussian Sampling (DGS) problem to that of solving the Learning With Errors (LWE) problem is a statistical test required for verifying possible solutions to the LWE problem. We derive a lower bound on the success probability leading to an upper bound on the tightness gap of the reduction. The success probability depends on the rejection threshold \begin{document}$ t $\end{document} of the statistical test. Using a particular value of \begin{document}$ t $\end{document}, Regev showed that asymptotically, the success probability of the test is exponentially close to one for all values of the LWE error \begin{document}$ \alpha\in(0,1) $\end{document}. From the concrete analysis point of view, the value of the rejection threshold used by Regev is sub-optimal. It leads to considering the lattice dimension to be as high as 400000 to obtain somewhat meaningful tightness gap. We show that by using a different value of the rejection threshold and considering \begin{document}$ \alpha $\end{document} to be at most \begin{document}$ 1/\sqrt{n} $\end{document} results in the success probability going to 1 for small values of the lattice dimension. Consequently, our work shows that it may be required to modify values of parameters used in an asymptotic analysis to obtain much improved and meaningful concrete security.

This paper deals with the problem of determining whether a PD-set exists for a given linear code \begin{document}$ \mathcal C $\end{document} and information set \begin{document}$ I $\end{document}. A computational approach is proposed and illustrated with two exceptional codes with automorphism groups isomorphic to the sporadic simple groups \begin{document}$ \mathrm{M}_{12} $\end{document} and \begin{document}$ \mathrm{M}_{22} $\end{document}, respectively. In both cases, the existence of a PD–set is proven. In general, the algorithm works well whenever the code \begin{document}$ \mathcal C $\end{document} has a very large automorphism group.

An \begin{document}$ (N,K) $\end{document} codebook \begin{document}$ {\mathcal C} $\end{document} is a collection of \begin{document}$ N $\end{document} unit norm vectors in a \begin{document}$ K $\end{document}-dimensional vectors space. In applications of codebooks such as CDMA, those vectors in a codebook should have a small maximum magnitude of inner products between any pair of distinct code vectors. In this paper, we propose two constructions of codebooks based on \begin{document}$ p $\end{document}-ary linear codes and on a hybrid character sum of a special kind of functions, respectively. With these constructions, two classes of codebooks asymptotically meeting the Welch bound are presented.

In this paper, we give an explicit representation and enumeration for negacyclic codes of length \begin{document}$ 2^kn $\end{document} over the local non-principal ideal ring \begin{document}$ R = \mathbb{Z}_4+u\mathbb{Z}_4 $\end{document} \begin{document}$ (u^2 = 0) $\end{document}, where \begin{document}$ k, n $\end{document} are arbitrary positive integers and \begin{document}$ n $\end{document} is odd. In particular, we present all distinct negacyclic codes of length \begin{document}$ 2^k $\end{document} over \begin{document}$ R $\end{document} precisely. Moreover, we provide an exact mass formula for the number of negacyclic codes of length \begin{document}$ 2^kn $\end{document} over \begin{document}$ R $\end{document} and correct several mistakes in some literatures.

Many modern symmetric ciphers apply MDS or almost MDS matrices as diffusion layers. The performance of a diffusion layer depends on its diffusion property measured by branch number and implementation cost which is usually measured by the number of XORs required. As the implementation cost of MDS matrices of large dimensions is high, some symmetric ciphers use binary matrices as diffusion layers to trade-off efficiency versus diffusion property. In the current paper, we investigate cyclic binary matrices (CBMs for short), mathematically. Based upon this theorical study, we provide efficient matrices with provable lower bound on branch number and minimal number of fixed-points. We consider the product of sparse CBMs to construct efficiently implementable matrices with the desired cryptographic properties.

Suppose that \begin{document}$ \mu_p $\end{document} is a probability measure defined on the input space of Boolean functions. We consider a generalization of Walsh–Hadamard transform on Boolean functions to \begin{document}$ \mu_p $\end{document}-Walsh–Hadamard transforms. In this paper, first, we derive the properties of \begin{document}$ \mu_p $\end{document}-Walsh–Hadamard transformation for some classes of Boolean functions and specify a class of nonsingular affine transformations that preserve the \begin{document}$ \mu_p $\end{document}-bent property. We further derive the results on \begin{document}$ \mu_p $\end{document}-Walsh–Hadamard transform of concatenation of Boolean functions and provide some secondary constructions of \begin{document}$ \mu_p $\end{document}-bent functions. Finally, we discuss the \begin{document}$ \mu_p $\end{document}-bentness for Maiorana–McFarland class of bent functions.

Private information retrieval (PIR) allows a user to retrieve one out of \begin{document}$ M $\end{document} messages from \begin{document}$ N $\end{document} servers without revealing the identity of the desired message. Every message consists of \begin{document}$ L $\end{document} symbols (packets) from an additive group and the length \begin{document}$ L $\end{document} is called the sub-packetization. A PIR scheme with download cost (DC) \begin{document}$ D/L $\end{document} is implemented by querying \begin{document}$ D $\end{document} sums of the symbols to servers. We assume that each uncoded server can store up to \begin{document}$ tLM/N $\end{document} symbols, \begin{document}$ t\in\{1,2,\cdots,N\} $\end{document}. The minimum DC of storage constrained PIR was determined by Attia et al. in 2018 to be \begin{document}$ DC_{min} = 1+1/t+1/t^{2}+\cdots+1/t^{M-1} $\end{document}. The capacity of storage constrained PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired symbols that can be privately retrieved per bit of downloaded symbols. Tandon et al. designed a capacity-achieving PIR scheme with sub-packetization \begin{document}$ L' = {N\choose t}t^{M} $\end{document} of each message. In this paper, we design a PIR scheme with \begin{document}$ t $\end{document} times smaller sub-packetization \begin{document}$ L'/t $\end{document} and with the minimum DC for any parameters \begin{document}$ N, M, t $\end{document}. We also prove that \begin{document}$ t^{M-1} $\end{document} is a factor of sub-packetization \begin{document}$ L $\end{document} for any capacity-achieving PIR scheme from storage constrained servers.

In the field of privacy preserving protocols, Private Set Intersection (PSI) plays an important role. In most of the cases, PSI allows two parties to securely determine the intersection of their private input sets, and no other information. In this paper, employing a Bloom filter, we propose a Multiparty Private Set Intersection Cardinality (MPSI-CA), where the number of participants in PSI is not limited to two. The security of our scheme is achieved in the standard model under the Decisional Diffie-Hellman (DDH) assumption against semi-honest adversaries. Our scheme is flexible in the sense that set size of one participant is independent from that of the others. We consider the number of modular exponentiations in order to determine computational complexity. In our construction, communication and computation overheads of each participant is \begin{document}$ O(v_{\sf max}k) $\end{document} except that the complexity of the designated party is \begin{document}$ O(v_1) $\end{document}, where \begin{document}$ v_{\sf max} $\end{document} is the maximum set size, \begin{document}$ v_1 $\end{document} denotes the set size of the designated party and \begin{document}$ k $\end{document} is a security parameter. Particularly, our MSPI-CA is the first that incurs linear complexity in terms of set size, namely \begin{document}$ O(nv_{\sf max}k) $\end{document}, where \begin{document}$ n $\end{document} is the number of participants. Further, we extend our MPSI-CA to MPSI retaining all the security attributes and other properties. As far as we are aware of, there is no other MPSI so far where individual computational cost of each participant is independent of the number of participants. Unlike MPSI-CA, our MPSI does not require any kind of broadcast channel as it uses star network topology in the sense that a designated party communicates with everyone else.