All Issues

Volume 16, 2022

Volume 15, 2021

Volume 14, 2020

Volume 13, 2019

Volume 12, 2018

Volume 11, 2017

Volume 10, 2016

Volume 9, 2015

Volume 8, 2014

Volume 7, 2013

Volume 6, 2012

Volume 5, 2011

Volume 4, 2010

Volume 3, 2009

Volume 2, 2008

Volume 1, 2007

Advances in Mathematics of Communications

May 2021 , Volume 15 , Issue 2

Select all articles


Encryption scheme based on expanded Reed-Solomon codes
Karan Khathuria, Joachim Rosenthal and Violetta Weger
2021, 15(2): 207-218 doi: 10.3934/amc.2020053 +[Abstract](3674) +[HTML](1019) +[PDF](373.36KB)

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.

On the dimension of the subfield subcodes of 1-point Hermitian codes
Sabira El Khalfaoui and Gábor P. Nagy
2021, 15(2): 219-226 doi: 10.3934/amc.2020054 +[Abstract](2633) +[HTML](612) +[PDF](312.64KB)

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.

Construction of minimal linear codes from multi-variable functions
Jong Yoon Hyun, Boran Kim and Minwon Na
2021, 15(2): 227-240 doi: 10.3934/amc.2020055 +[Abstract](2266) +[HTML](638) +[PDF](391.33KB)

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.

Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations
Sugata Gangopadhyay, Constanza Riera and Pantelimon Stănică
2021, 15(2): 241-256 doi: 10.3934/amc.2020056 +[Abstract](2221) +[HTML](625) +[PDF](467.73KB)

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.

Verifying solutions to LWE with implications for concrete security
Palash Sarkar and Subhadip Singha
2021, 15(2): 257-266 doi: 10.3934/amc.2020057 +[Abstract](2096) +[HTML](611) +[PDF](355.45KB)

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.

On the existence of PD-sets: Algorithms arising from automorphism groups of codes
Nicola Pace and Angelo Sonnino
2021, 15(2): 267-277 doi: 10.3934/amc.2020065 +[Abstract](1998) +[HTML](640) +[PDF](384.21KB)

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.

Two classes of near-optimal codebooks with respect to the Welch bound
Gaojun Luo and Xiwang Cao
2021, 15(2): 279-289 doi: 10.3934/amc.2020066 +[Abstract](1857) +[HTML](609) +[PDF](378.41KB)

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.

An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $
Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi and Fang-Wei Fu
2021, 15(2): 291-309 doi: 10.3934/amc.2020067 +[Abstract](2583) +[HTML](581) +[PDF](453.4KB)

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.

Cryptographic properties of cyclic binary matrices
Akbar Mahmoodi Rishakani, Seyed Mojtaba Dehnavi, Mohmmadreza Mirzaee Shamsabad and Nasour Bagheri
2021, 15(2): 311-327 doi: 10.3934/amc.2020068 +[Abstract](2196) +[HTML](709) +[PDF](513.17KB)

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.

A note on generalization of bent boolean functions
Bimal Mandal and Aditi Kar Gangopadhyay
2021, 15(2): 329-346 doi: 10.3934/amc.2020069 +[Abstract](2108) +[HTML](551) +[PDF](429.61KB)

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.

Capacity-achieving private information retrieval scheme with a smaller sub-packetization
Wenqin Zhang, Zhengchun Zhou, Udaya Parampalli and Vladimir Sidorenko
2021, 15(2): 347-363 doi: 10.3934/amc.2020070 +[Abstract](2007) +[HTML](577) +[PDF](394.87KB)

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.

Secure and efficient multiparty private set intersection cardinality
Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu and Tanmay Choudhury
2021, 15(2): 365-386 doi: 10.3934/amc.2020071 +[Abstract](2904) +[HTML](819) +[PDF](818.16KB)

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.

2021 Impact Factor: 1.015
5 Year Impact Factor: 1.078
2021 CiteScore: 1.8




Email Alert

[Back to Top]