Recent zbMATH articles in MSC 94Bhttps://zbmath.org/atom/cc/94B2021-03-30T15:24:00+00:00WerkzeugOn perfect poset codes.https://zbmath.org/1455.942232021-03-30T15:24:00+00:00"Panek, Luciano"https://zbmath.org/authors/?q=ai:panek.luciano"Pinheiro, Jerry Anderson"https://zbmath.org/authors/?q=ai:pinheiro.jerry-anderson"Alves, Marcelo Muniz"https://zbmath.org/authors/?q=ai:alves.marcelo-muniz-silva"Firer, Marcelo"https://zbmath.org/authors/?q=ai:firer.marceloSummary: We consider on \( \mathbb{F}_q^n \) metrics determined by posets and classify the parameters of 1-perfect poset codes in such metrics. We show that a code with same parameters of a 1-perfect poset code is not necessarily perfect, however, we give necessary and sufficient conditions for this to be true. Furthermore, we characterize the unique way up to a labeling on the poset, considering some conditions, to extend an \( r \)-perfect poset code over \( \mathbb{F}_q^n \) to an \( r \)-perfect poset code over \( \mathbb{F}_q^{n+m} \).On classification of toric surface codes of dimension seven.https://zbmath.org/1455.140552021-03-30T15:24:00+00:00"Hussain, Naveed"https://zbmath.org/authors/?q=ai:hussain.naveed"Luo, Xue"https://zbmath.org/authors/?q=ai:luo.xue"Yau, Stephen S.-T."https://zbmath.org/authors/?q=ai:yau.stephen-shing-toung"Zhang, Mingyi"https://zbmath.org/authors/?q=ai:zhang.mingyi"Zuo, Huaiqing"https://zbmath.org/authors/?q=ai:zuo.huaiqingFollowing previous work on the classification of low-dimensional toric surface codes by \textit{S. S. T. Yau} and \textit{H. Zuo} [Appl. Algebra Eng. Commun. Comput. 20, No. 2, 175--185 (2009; Zbl 1174.94029)] and \textit{X. Luo} et al. [Finite Fields Appl. 33, 90--102 (2015; Zbl 1394.14017)] the main results of the paper under review extend the classification, up to monomial equivalence, of toric surface codes of dimension less than or equal to \(7\), with the monomial equivalence of some pairs of toric codes in this range still undetermined.
Reviewer: Felipe Zaldívar (Ciudad de México)QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field.https://zbmath.org/1455.942222021-03-30T15:24:00+00:00"Amirzade, Farzane"https://zbmath.org/authors/?q=ai:amirzade.farzane"Sadeghi, Mohammad-Reza"https://zbmath.org/authors/?q=ai:sadeghi.mohammad-reza"Panario, Daniel"https://zbmath.org/authors/?q=ai:panario.danielSummary: Trapping sets significantly influence the performance of low-density parity-check codes. An \((a, b)\) elementary trapping set (ETS) causes high decoding failure rate and exert a strong influence on the error floor of the code, where \( a \) and \( b\) denote the size and the number of unsatisfied check-nodes in the ETS, respectively. The smallest size of an ETS in \((3, n) \)-regular LDPC codes with girth 6 is 4. In this paper, we provide sufficient conditions to construct fully connected \( (3, n) \)-regular algebraic-based QC-LDPC codes with girth 6 whose Tanner graphs are free of \( (a, b)\) ETSs with \( a\leq 5 \) and \( b\leq 2 \). We apply these sufficient conditions to the exponent matrix of a new algebraic-based QC-LDPC code with girth at least 6. As a result, we obtain the maximum size of a submatrix of the exponent matrix which satisfies the sufficient conditions and yields a Tanner graph free of those ETSs with small size. Some algebraic-based QC-LDPC code constructions with girth 6 in the literature are special cases of our construction. Our experimental results show that removing ETSs with small size contribute to have better performance curves in the error floor region.On the non-existence of short vectors in random module lattices.https://zbmath.org/1455.941862021-03-30T15:24:00+00:00"Nguyen, Ngoc Khanh"https://zbmath.org/authors/?q=ai:nguyen.ngoc-khanhSummary: Recently [\textit{V. Lyubashevsky} and \textit{G. Seiler}, Lect. Notes Comput. Sci. 10820, 204--224 (2018; Zbl 1423.94087)] showed that small polynomials in the cyclotomic ring \(\mathbb{Z}_q [X]/(X^n+1)\), where \(n\) is a power of two, are invertible under special congruence conditions on prime modulus \(q\). This result has been used to prove certain security properties of lattice-based constructions against unbounded adversaries. Unfortunately, due to the special conditions, working over the corresponding cyclotomic ring does not allow for efficient use of the number theoretic transform (NTT) algorithm for fast multiplication of polynomials and hence, the schemes become less practical.
In this paper, we present how to overcome this limitation by analysing zeroes in the Chinese remainder (or NTT) representation of small polynomials. As a result, we provide upper bounds on the probabilities related to the (non)-existence of a short vector in a random module lattice with no assumptions on the prime modulus. We apply our results, along with the generic framework by \textit{E. Kiltz} et al. [ibid. 10822, 552--586 (2018; Zbl 1415.94448)], to a number of lattice-based Fiat-Shamir signatures so they can both enjoy tight security in the quantum random oracle model and support fast multiplication algorithms (at the cost of slightly larger public keys and signatures), such as the Bai-Galbraith signature scheme [\textit{S. Bai} and \textit{S. D. Galbraith}, ibid. 8366, 28--47 (2014; Zbl 1295.94011)], Dilithium-QROM [Kiltz et al., loc. cit.] and qTESLA (\textit{E. Alkim} et al. [ibid. 10346, 143--162 (2017; Zbl 1437.94047)]). Our techniques can also be applied to prove that recent commitment schemes by \textit{C. Baum} et al. [ibid. 11035, 368--385 (2018; Zbl 06957563)] are statistically binding with no additional assumptions on \(q\).
For the entire collection see [Zbl 1428.94009].Bounds on \(m_r(2,29)\).https://zbmath.org/1455.510032021-03-30T15:24:00+00:00"Daskalov, Rumen"https://zbmath.org/authors/?q=ai:daskalov.rumen-nikolov"Metodieva, Elena"https://zbmath.org/authors/?q=ai:metodieva.elenaSummary: An \((n,r)\)-arc is a set of \(n\) points of a projective plane such that some \(r\), but no \(r + 1\) of them, are collinear. The maximum size of an \((n,r)\)-arc in PG(2, q) is denoted by \(m_r(2, q)\). In this paper thirteen new \((n,r)\)-arc in PG(2,29) and a table with the best known lower and upper bounds on \(m_r(2,29)\) are presented. The results are obtained by non-exhaustive local computer search.Interactive non-malleable codes.https://zbmath.org/1455.941532021-03-30T15:24:00+00:00"Fleischhacker, Nils"https://zbmath.org/authors/?q=ai:fleischhacker.nils"Goyal, Vipul"https://zbmath.org/authors/?q=ai:goyal.vipul"Jain, Abhishek"https://zbmath.org/authors/?q=ai:jain.abhishek"Paskin-Cherniavsky, Anat"https://zbmath.org/authors/?q=ai:paskin-cherniavsky.anat"Radune, Slava"https://zbmath.org/authors/?q=ai:radune.slavaSummary: Non-malleable codes (NMC) introduced by \textit{S. Dziembowski} et al. [``Non-malleable codes'', in: Innovations in computer science -- ICS 2010, Tsinghua University, Beijing, China, January 7--9, 2011. Proceedings. Beijing: Tsinghua University Press. 434--452 (2010)] allow one to encode ``passive'' data in such a manner that when a codeword is tampered, the original data either remains completely intact or is essentially destroyed.
In this work, we initiate the study of interactive non-malleable codes (INMCs) that allow for encoding ``active communication'' rather than passive data. An INMC allows two parties to engage in an interactive protocol such that an adversary who is able to tamper with the protocol messages either leaves the original transcript intact (i.e., the parties are able to reconstruct the original transcript) or the transcript is completely destroyed and replaced with an unrelated one.
We formalize a tampering model for interactive protocols and put forward the notion of INMCs. Since constructing INMCs for general adversaries is impossible (as in the case of non-malleable codes), we construct INMCs for several specific classes of tampering functions. These include bounded state, split state, and fragmented sliding window tampering functions. We also obtain lower bounds for threshold tampering functions via a connection to interactive coding. All of our results are unconditional.
For the entire collection see [Zbl 1428.94014].Nonassociative algebraic structures in cryptography and coding.https://zbmath.org/1455.942272021-03-30T15:24:00+00:00"Markov, V. T."https://zbmath.org/authors/?q=ai:markov.viktor-t"Mikhalev, A. V."https://zbmath.org/authors/?q=ai:mikhalev.aleksandr-v"Nechaev, A. A."https://zbmath.org/authors/?q=ai:nechaev.alexandr-aFrom the text: In this review, we consider applications of nonassociative algebraic structures for the construction of linearly optimal codes and cryptosystems.
In the Introduction, the main concepts and statements necessary for further presentation are given.
Section 2 describes the construction of two families of linearly optimal \([n, n-3, 3]_q\)-codes for \(n = 2q\) and \(n = 2q - 2\) using quasigroup rings. To construct \([2q, 2q - 3, 3]_q\)-codes, we use the representation of Reed-Solomon codes as ideals of the group ring \(\mathbb F_{p^n}G\), where \(G\) is a \(p\)-elementary Abelian group of order \(p^n\). We define the commutator quasigroups and present linearly optimal codes that are constructed with the help of commutator quasigroups for the dihedral group \(D_n\).
In Sec. 3, we construct a cryptoscheme over a graded ring with a multiplicative basis. This generalizes the construction of a cryptosystem over a group ring. In this case, the ambiguity of the choice of grading and multiplicative basis extends the set of suitable algebraic structures for encryption.
In Sec. 4, a protocol of a common secret key generation and a cryptoscheme are constructed, where
all calculations are performed in the Moufang loop.
In Sec. 5, we introduce the notion of a groupoid with permutational degrees (CP-groupoid), and we
describe the protocol for generating a shared secret key, similar to the Diffie-Hellman algorithm, based on CP-groupoids, as well as some constructions of CP-groupoids.
Reviewer: Olaf Ninnemann (Uffing am Staffelsee)Constraint satisfaction through GBP-guided deliberate bit flipping.https://zbmath.org/1455.940902021-03-30T15:24:00+00:00"Bahrami, Mohsen"https://zbmath.org/authors/?q=ai:bahrami.mohsen"Vasić, Bane"https://zbmath.org/authors/?q=ai:vasic.bane-vSummary: In this paper, we consider the problem of transmitting binary messages over data-dependent two-dimensional channels. We propose a deliberate bit flipping coding scheme that removes channel harmful configurations prior to transmission. In this method, user messages are encoded with an error correction code, and therefore the number of bit flips should be kept small not to overburden the decoder. We formulate the problem of minimizing the number of bit flips as a binary constraint satisfaction problem, and devise a generalized belief propagation guided method to find approximate solutions. Applied to a data-dependent binary channel with the set of 2-D isolated bit configurations as its harmful configurations, we evaluated the performance of our proposed method in terms of uncorrectable bit-error rate.
For the entire collection see [Zbl 1428.68013].Constacyclic codes over local rings of order \(16\).https://zbmath.org/1455.942252021-03-30T15:24:00+00:00"Dougherty, Steven T."https://zbmath.org/authors/?q=ai:dougherty.steven-t"Saltürk, Esengül"https://zbmath.org/authors/?q=ai:salturk.esengulSummary: In this work, we study constacyclic codes of odd length over finite commutative local Frobenius non-chain rings of order 16. We give the structure of \(\lambda_i\)-constacyclic codes over each local Frobenius non-chain ring via cyclic codes over these rings where \(\lambda_i\) acts as a weight preserving unit in the corresponding ring. We also obtain binary optimal codes which are images of these constacyclic codes under a gray map.
For the entire collection see [Zbl 1415.16001].Quantum codes obtained from some constacyclic codes over a family of finite rings \(F_p+uF_p+vF_p\).https://zbmath.org/1455.810172021-03-30T15:24:00+00:00"Dertli, Abdullah"https://zbmath.org/authors/?q=ai:dertli.abdullah"Cengellenmis, Yasemin"https://zbmath.org/authors/?q=ai:cengellenmis.yaseminSummary: In this paper, we study the quantum codes over \(\mathbb F_p\), \(p\) is an odd prime, obtained from some constacyclic codes over the finite ring \(\mathbb F_p+u\mathbb F_p+v\mathbb F_p\), where \(u^2=u\), \(v^2=v\), \(uv=vu=0\). A constacyclic code over the finite ring \(\mathbb F_p+u\mathbb F_p+v\mathbb F_p\) is decomposed into three codes over \(\mathbb F_p\) in order to determine the parameters of the corresponding quantum codes. Finally, we have constructed some examples of quantum error-correcting codes.Low-weight superimposed codes and related combinatorial structures: bounds and applications.https://zbmath.org/1455.940932021-03-30T15:24:00+00:00"Gargano, Luisa"https://zbmath.org/authors/?q=ai:gargano.luisa"Rescigno, Adele Anna"https://zbmath.org/authors/?q=ai:rescigno.adele-anna"Vaccaro, Ugo"https://zbmath.org/authors/?q=ai:vaccaro.ugoSummary: A \((k, n)\)-superimposed code is a well known and widely used combinatorial structure that can be represented by a \(t \times n\) binary matrix such that for any \(k\) columns of the matrix and for any column \(\mathfrak{c}\) chosen among these \(k\) columns, there exists a row in correspondence of which column \(\mathfrak{c}\) has an entry equal to 1 and the remaining \(k - 1\) columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing \((k, n)\)-superimposed codes with a small number \(t\) of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1's in each column of the matrix is constant, and equal to an input parameter \(w\). Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors, generalized superimposed codes, and \(z\)-error correcting superimposed codes.On skew cyclic codes over a finite ring.https://zbmath.org/1455.942282021-03-30T15:24:00+00:00"Mohammadi, Rasul"https://zbmath.org/authors/?q=ai:mohammadi.rasul"Rahimi, Saeed"https://zbmath.org/authors/?q=ai:rahimi.saeed-k"Mousavi, Hamed"https://zbmath.org/authors/?q=ai:mousavi.hamedSummary: In this paper, we classify the skew cyclic codes over \(\mathbb{F}_p + v\mathbb{F}_p + v^2\mathbb{F}_p\), where \(p\) is a prime number and \(v^3 = v\). Each skew cyclic code is a \(\mathbb{F}_p + v\mathbb{F}_p + v^2\mathbb{F}_p\)-submodule of the \(\mathbb{F}_p + v\mathbb{F}_p + v^2\mathbb{F}_p\)\([x; \theta]\), where \(v^3 = v\) and \(\theta(v) = -v\). Also, we give an explicit forms for the generator of these codes. Moreover, an algorithm of encoding and decoding for these codes is presented.Arcs in finite projective spaces.https://zbmath.org/1455.510022021-03-30T15:24:00+00:00"Ball, Simeon"https://zbmath.org/authors/?q=ai:ball.simeon"Lavrauw, Michel"https://zbmath.org/authors/?q=ai:lavrauw.michelAn arc \(\mathcal{K}\) in a \((k-1)\)-dimensional projective space is a set of points such that any \(k\) of them span the whole space and an arc in a projective plane is called a \emph{planar arc}. An arc is called \emph{complete} if it is maximal with respect to the set-theoretical inclusion.
The study of arcs dates back to the 1950s and the 1960s when Beniamino Segre published his fundamental works on finite geometry. Arcs have interesting links with other areas of mathematics too: from a coding theory point of view, they correspond to MDS codes, i.e. codes attaining the Singleton bound.
In this excellent survey paper, the authors focus on large arcs in finite projective spaces. In particular, known old results and more recent theorems are unified and simplified. For instance, a general form of Segre's lemma of tangents yields a short proof of the MDS conjecture over prime fields.
Reviewer: Daniele Bartoli (Perugia)Computation of minimum Hamming weight for linear codes.https://zbmath.org/1455.942242021-03-30T15:24:00+00:00"Rostami, Esmaeil"https://zbmath.org/authors/?q=ai:rostami.esmaeil"Nekooei, Reza"https://zbmath.org/authors/?q=ai:nekooei.rezaSummary: In this paper, we consider the minimum Hamming weight for linear codes over special finite quasi-Frobenius rings. Furthermore, we obtain minimal free \(R\)-submodules of a finite quasi-Frobenius ring \(R\) which contain a linear code and derive the relation between their minimum Hamming weights. Finally, we suggest an algorithm that computes this weight using the Gröbner basis and we show that under certain conditions a linear code takes the maximum of minimum Hamming weight.Cryptanalysis of a system based on twisted Reed-Solomon codes.https://zbmath.org/1455.941772021-03-30T15:24:00+00:00"Lavauzelle, Julien"https://zbmath.org/authors/?q=ai:lavauzelle.julien"Renner, Julian"https://zbmath.org/authors/?q=ai:renner.julianSummary: Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed-Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic key-recovery methods. In this paper, an efficient key-recovery attack on the TRS variant that was used in the McEliece cryptosystem is presented. The algorithm exploits a new approach based on recovering the structure of a well-chosen subfield subcode of the public code. It is proved that the attack always succeeds and breaks the system for all practical parameters in \(O(n^4)\) field operations. A software implementation of the algorithm retrieves a valid private key from the public key within a few minutes, for parameters claiming a security level of 128 bits. The success of the attack also indicates that, contrary to common beliefs, subfield subcodes of the public code need to be precisely analyzed when proposing a McEliece-type code-based cryptosystem. Finally, the paper discusses an attempt to repair the scheme and a modification of the attack aiming at Gabidulin-Paramonov-Tretjakov cryptosystems based on twisted Gabidulin codes.Solving LPN using covering codes.https://zbmath.org/1455.941612021-03-30T15:24:00+00:00"Guo, Qian"https://zbmath.org/authors/?q=ai:guo.qian"Johansson, Thomas"https://zbmath.org/authors/?q=ai:johansson.thomas"Löndahl, Carl"https://zbmath.org/authors/?q=ai:londahl.carlSummary: We present a new algorithm for solving the LPN problem. The algorithm has a similar form as some previous methods, but includes a new key step that makes use of approximations of random words to a nearest codeword in a linear code. It outperforms previous methods for many parameter choices. In particular, we can now solve the \((512,\frac{1}{8})\) LPN instance with complexity less than \(2^{80}\) operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes.https://zbmath.org/1455.941472021-03-30T15:24:00+00:00"Dachman-Soled, Dana"https://zbmath.org/authors/?q=ai:dachman-soled.dana"Kulkarni, Mukul"https://zbmath.org/authors/?q=ai:kulkarni.mukul"Shahverdi, Aria"https://zbmath.org/authors/?q=ai:shahverdi.ariaSummary: \textit{D. Dachman-Soled} et al. [TCC 2015, Lect. Notes Comput. Sci. 9014, 427--450 (2015; Zbl 1359.94585)] proposed a notion called locally decodable and updatable non-malleable codes, which provide the security guarantees of a non-malleable code while allowing for efficient random access. They also considered such codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. The locality of their construction was \({\Omega}(\log n)\).
We prove that super-constant locality is inherent by showing tight upper and lower bounds. We show that a locally decodable and updatable non-malleable code with block size \(\chi \in \text{poly}(\lambda)\) requires locality \(\delta(n) \in \omega(1)\), where \(n = \text{poly}(\lambda)\) is the message length and \({\lambda}\) is security parameter. Furthermore, we present a construction of a locally decodable and updatable non-malleable code with block size \(\chi \in \Omega(\lambda^{1 / \mu})\) (for constant \(0 < \mu < 1)\) with locality \(\delta(n)\), for any \(\delta(n) \in \omega(1)\), and \(n = \text{poly}(\lambda)\).Isotropic constant dimension subspace codes.https://zbmath.org/1455.942262021-03-30T15:24:00+00:00"Bardestani, Fatemeh"https://zbmath.org/authors/?q=ai:bardestani.fatemeh"Adhami, S. Roghayeh"https://zbmath.org/authors/?q=ai:adhami.s-roghayehSummary: In network code setting, a constant dimension subspace code is a set of \(k\)-dimensional subspaces of \(\mathbb{F}^n_q\). If \(\mathbb{F}^n_q\) is a nondegenerate symplectic vector space with bilinear form \(f\), an isotropic subspace \(\mathcal{U}\) of \(\mathbb{F}^n_q\) is a subspace for which \(\mathcal{U} \subset \mathcal{U}^\bot\). We introduce isotropic subspace codes simply as a set of isotropic subspaces and show how the property of being isotropic is used in decoding process, then we demonstrate the structure of an isotropic spread code.