Authors:Serhii Dyshko Pages: 295 - 309 Abstract: Abstract The minimal code length for which there exists an unextendable Hamming isometry of a linear code defined over a matrix module alphabet is found. An extension theorem for MDS codes over module alphabets is proved. An extension theorem for the case of MDS group codes is observed. PubDate: 2017-08-01 DOI: 10.1007/s00200-017-0324-0 Issue No:Vol. 28, No. 4 (2017)

Authors:Dabin Zheng; Zhen Chen Pages: 215 - 223 Abstract: Abstract This note presents two classes of permutation polynomials of the form \((x^{p^m}-x+\delta )^s+L(x)\) over the finite fields \({{\mathbb {F}}}_{p^{2m}}\) as a supplement of the recent works of Zha, Hu and Li, Helleseth and Tang. PubDate: 2017-06-01 DOI: 10.1007/s00200-016-0305-8 Issue No:Vol. 28, No. 3 (2017)

Authors:B. Panbehkar; H. Doostie Pages: 225 - 235 Abstract: Abstract For a finitely generated automatic semigroup \(S=\langle A\rangle \) we define a semigroup \(L_S\) of languages concerning the automatic structure of S, and study the automaticity of \(L_S\) . Also we investigate the natural question “when S is isomorphic to \(L_S\) ?”. Finally, we attempt to verify the equation \(L_S\cup L_T=L_{S\cup T}\) for two non-monoid semigroups \((S, *)\) and (T, o). PubDate: 2017-06-01 DOI: 10.1007/s00200-016-0306-7 Issue No:Vol. 28, No. 3 (2017)

Authors:Thierry Mefenza; Damien Vergnaud Pages: 237 - 255 Abstract: Abstract We prove lower bounds on the degree of polynomials interpolating the Naor–Reingold pseudo-random function over a finite field and over the group of points on an elliptic curve over a finite field. PubDate: 2017-06-01 DOI: 10.1007/s00200-016-0309-4 Issue No:Vol. 28, No. 3 (2017)

Authors:Bentolhoda Binaei; Amir Hashemi; Werner M. Seiler Abstract: Abstract In this paper, we study first the relationship between Pommaret bases and Hilbert series. Given a finite Pommaret basis, we derive new explicit formulas for the Hilbert series and for the degree of the ideal generated by it which exhibit more clearly the influence of each generator. Then we establish a new dimension depending Bézout bound for the degree and use it to obtain a dimension depending bound for the ideal membership problem. PubDate: 2017-09-15 DOI: 10.1007/s00200-017-0342-y

Authors:Dae-Woong Lee Abstract: Abstract In this paper, we study the digital Hopf groups and the digital Hopf functions between digital Hopf spaces with digital multiplications, and construct a near-ring structure on the set of all pointed digital homotopy classes of digital Hopf functions between pointed digital Hopf groups. We also investigate a near-ring homomorphism between near-rings based on the pointed digital Hopf groups to find a new method of how to give answers to the original problems or how to get a new information out of old ones more effectively. PubDate: 2017-09-14 DOI: 10.1007/s00200-017-0341-z

Authors:Omar Akchiche; Omar Khadir Abstract: Abstract We address the problem of factoring a large RSA modulus \(N=pq\) with p and q sharing a portion of bits in the middle. New polynomial time algorithms for computing the prime decomposition of N under certain conditions are presented. As an application, several attacks against RSA system using this class of moduli with low public exponent are described. Our results suggest that such integers are not appropriate for cryptographic purposes. PubDate: 2017-08-21 DOI: 10.1007/s00200-017-0340-0

Authors:J. D. Key; B. G. Rodrigues Abstract: Abstract It is shown how LCD codes with a particularly useful feature can be found from row spans over finite fields of adjacency matrices of graphs by considering these together with the codes from the associated reflexive graphs and complementary graphs. Application is made to some particular classes, including uniform subset graphs and strongly regular graphs where, if a p-ary code from a graph has this special LCD feature, the dimension can be found from the multiplicities modulo p of the eigenvalues of an adjacency matrix and, bounds on the minimum weight of the code and the dual code follow from the valency of the graph. PubDate: 2017-08-19 DOI: 10.1007/s00200-017-0339-6

Authors:Can Xiang; Xianfang Wang; Chunming Tang; Fangwei Fu Abstract: Abstract Linear codes have been an interesting topic in both theory and practice for many years. In this paper, two classes of linear codes over the finite field \({\mathrm {GF}}(p)\) are presented and their weight distributions are also determined, where p is an odd prime. Some of the linear codes obtained are optimal or almost optimal in the sense that their parameters meet certain bound on linear codes. PubDate: 2017-08-18 DOI: 10.1007/s00200-017-0338-7

Authors:Chunming Tang; Yanfeng Qi; Zhengchun Zhou; Cuiling Fan Abstract: Abstract In the literature, few n-variable rotation symmetric bent functions have been constructed. In this paper, we present two infinite classes of rotation symmetric bent functions on \({\mathbb {F}}_2^{n}\) of the two forms: \(f(x)=\sum _{i=0}^{m-1}x_ix_{i+m} + {\upgamma }(x_0+x_m,\ldots , x_{m-1}+x_{2m-1})\) , \(f_t(x)= \sum _{i=0}^{n-1}(x_ix_{i+t}x_{i+m} +x_{i}x_{i+t})+ \sum _{i=0}^{m-1}x_ix_{i+m}+ {\upgamma }(x_0+x_m,\ldots , x_{m-1}+x_{2m-1})\) , where \(n=2m\) , \({\upgamma }(X_0,X_1,\ldots , X_{m-1})\) is any rotation symmetric polynomial, and \(m/\textit{gcd}(m,t)\) is odd. The class (i) of rotation symmetric bent functions has algebraic degree ranging from 2 to m and the other class (ii) has algebraic degree ranging from 3 to m. Moreover, the two classes of rotation symmetric bent functions are disjoint. PubDate: 2017-08-18 DOI: 10.1007/s00200-017-0337-8

Authors:Yoshinori Aono; Manindra Agrawal; Takakazu Satoh; Osamu Watanabe Abstract: Abstract We investigate a method for finding small integer solutions of a univariate modular equation, that was introduced by Coppersmith (Proceedings of Eurocrypt 1996, LNCS, vol 1070, pp 155–165, 1996) and extended by May (New RSA vulnerabilities using lattice reduction methods, Ph.D. thesis, University of Paderborn, 2003). We will refer this method as the Coppersmith technique. This paper provides a way to analyze a general limitations of the lattice construction for the Coppersmith technique. Our analysis upper bounds the possible range of U that is asymptotically equal to the bound given by the original result of Coppersmith and May. This means that they have already given the best lattice construction. In addition, we investigate the optimality for the bivariate equation to solve the small inverse problem, which was inspired by Kunihiro’s (LNCS 7483:55–69, 2012) argument. In particular, we show the optimality for the Boneh–Durfee’s equation (Proceedings of Eurocrypt 1999, LNCS, vol 1592, pp 389–401, 1999) used for RSA cryptoanalysis, To show our results, we establish framework for the technique by following the relation of Howgrave-Graham (Proceedings of cryptography and coding, LNCS, vol 1355, pp 131–142, 1997), and then concretely define the conditions in which the technique succeed and fails. We then provide a way to analyze the range of U that satisfies these conditions. Technically, we show that the original result of Coppersmith achieves the optimal bound for U when constructing a lattice in the standard way. We then provide evidence which indicates that constructing a non-standard lattice is generally difficult. PubDate: 2017-08-09 DOI: 10.1007/s00200-017-0336-9

Authors:Deepa Sinha; Deepakshi Sharma Abstract: Abstract In this paper, we generalize the iterated local transitivity (ILT) model for online social networks for signed networks. Signed networks focus on the type of relations (friendship or enmity) between the vertices (members of online social networks). The ILT model for signed networks provide an insight into how networks react to the addition of clone vertex. In this model, at each time step t and for already existing vertex x, a new vertex (clone) \(x'\) is added which joins to x and neighbors of x. The sign of new edge \(yx', \ y \in N[x]\) neighborhood of x is defined by calculating the number of positive and negative neighbors of x. We also discuss properties such as balance and clusterability, sign-compatibility and C-sign-compatibility. PubDate: 2017-07-03 DOI: 10.1007/s00200-017-0333-z

Authors:Sylvain Duquesne; Nadia El Mrabet; Safia Haloui; Franck Rondepierre Abstract: Abstract Because pairings have many applications, many hardware and software pairing implementations can be found in the literature. However, the parameters generally used have been invalidated by the recent results on the discrete logarithm problem over pairing friendly elliptic curves (Kim and Barbulescu in CRYPTO 2016, volume 9814 of lecture notes in computer science, Springer, Berlin, pp 543–571, 2016). New parameters must be generated to insure enough security in pairing based protocols. More generally it could be useful to generate nice pairing parameters in many real-world applications (specific security level, resistance to specific attacks on a protocol, database of curves). The main purpose of this paper is to describe explicitly and exhaustively what should be done to generate the best possible parameters and to make the best choices depending on the implementation context (in terms of pairing algorithm, ways to build the tower field, \(\mathbb {F}_{p^{12}}\) arithmetic, groups involved and their generators, system of coordinates). We focus on low level implementations, assuming that \(\mathbb {F}_p\) additions have a significant cost compared to other \(\mathbb {F}_p\) operations. However, our results are still valid if \(\mathbb {F}_p\) additions can be neglected. We also explain why the best choice for the polynomials defining the tower field \(\mathbb {F}_{p^{12}}\) is only dependent on the value of the BN parameter u mod small integers (like 12 for instance) as a nice application of old elementary arithmetic results. This should allow a faster generation of this parameter. Moreover, we use this opportunity to give some new slight improvements on \(\mathbb {F}_{p^{12}}\) arithmetic (in a pairing context). PubDate: 2017-07-01 DOI: 10.1007/s00200-017-0334-y

Authors:Yang Zhang Abstract: Abstract An extension of Bergman’s ring (Israel J Math 18:257–277, 1974) was introduced by Climent et al. (Appl Algebra Eng Commun Comput 23:347–361, 2014). For this ring called \(E_p^{(m)}\) , they established that only a negligible fraction of elements are invertible, and then proposed a key exchange protocol based on this property. Shortly afterwards, they constructed another key agreement protocol for multicast over this ring (WIT Trans Inf Commun Technol 45:13–24, 2013). In this paper, we introduce a polynomial-time attack to these two protocols without using invertible elements. PubDate: 2017-06-14 DOI: 10.1007/s00200-017-0332-0

Authors:Mridul Nandi; Tapas Pandit Abstract: Abstract Predicate encryption (PE), a generalization of attribute-based encryption (ABE), is a versatile tool for providing access control over data. The underlying predicate for a PE is parametrized by an index, called system parameter or simply system-index. A system-index, in general, consists of component(s) from \(\mathbb {N}\) . Yamada et al. in PKC 2011 proposed a verifiability-based conversion from CPA to CCA-secure ABE. This conversion was generalized by Yamada et al. in PKC 2012 from ABE to PE. In the later conversion, the authors considered the system-index to be a single component. In practice, there are many schemes, e.g., functional encryption for general relations and hierarchical-inner product (HIP) encryption schemes of Okamoto-Takashima in CRYPTO 2010, CANS 2011 and EUROCRYPT 2012, where system-indices consist of more than a single component. Therefore, for these schemes, the conversion of Yamada et al. (in PKC, 2012) is out of scope. In this paper, we revisit the CPA to CCA conversion for PE and propose a new conversion based on verifiability. The proposed conversion works irrespective of the number of components in the system-indices. It generalizes the existing conversion of Yamada et al. (in PKC, 2011) from ABE to PE. The PE schemes which are realized by the conversion of Yamada et al. (2011) are also realized by our conversion. Therefore, the conversion of ours has more scope than the conversion proposed in 2012. We show that all the aforementioned CPA-secure schemes for general relations and HIP relation are easily converted to the corresponding CCA-secure schemes by our conversion. Further, we show a generic conversion from CPA to CCA-secure functional encryption for regular languages which captures the existing PE schemes for regular languages. PubDate: 2017-06-05 DOI: 10.1007/s00200-017-0330-2

Authors:Pierre-Louis Cayrel; Mohammed Meziani; Ousmane Ndiaye; Richard Lindner; Rosemberg Silva Abstract: Abstract In this paper we construct a pseudorandom number generator using only worst-case hardness assumptions for standard lattice problems. With a common technique, we can then build a stream cipher by combining the generated pseudorandom sequence with the plaintext. Moreover, as an option to gain efficiency both in terms of speed and memory, we suggest the use of ideal lattices in the construction. Currently, there is no known attack that could exploit this choice. Our implementation for Graphics Processing Units leverages from the parallelism inherent in lattice schemes and reaches performances comparable to the fastest known constructions that enjoy security proofs. PubDate: 2017-05-30 DOI: 10.1007/s00200-017-0323-1

Authors:Fatmanur Gursoy; Elif Segah Oztas; Irfan Siap Abstract: Abstract In this study we determine the structure of reversible DNA codes obtained from skew cyclic codes. We show that the generators of such DNA codes enjoy some special properties. We study the structural properties of such family of codes and we also illustrate our results with examples. PubDate: 2017-05-22 DOI: 10.1007/s00200-017-0325-z

Authors:Jacques Patarin Abstract: Abstract “Mirror Theory” is the theory that evaluates the number of solutions of affine systems of equalities \(({=})\) and non equalities ( \(\ne \) ) in finite groups. It is deeply related to the security and attacks of many generic cryptographic secret key schemes, for example random Feistel schemes (balanced or unbalanced), Misty schemes, Xor of two pseudo-random bijections to generate a pseudo-random function etc. In this paper we will assume that the groups are abelian. Most of time in cryptography the group is \(((\mathbb {Z}/2\mathbb {Z})^n, \oplus )\) and we will concentrate this paper on these cases. We will present here general definitions, some theorems, and many examples and computer simulations. PubDate: 2017-05-20 DOI: 10.1007/s00200-017-0326-y

Authors:Nuh Aydin; Nicholas Connolly; John Murphree Abstract: Abstract Explicit construction of linear codes with best possible parameters is one of the major problems in coding theory. Among all alphabets of interest, the binary alphabet is the most important one. In this work we use a comprehensive search strategy to find new binary linear codes in the well-known and intensively studied class of quasi-cyclic (QC) codes. We also introduce a generalization of an augmentation algorithm to obtain further new codes from those QC codes. Also applying the standard methods of obtaining new codes from existing codes, such as puncturing, extending and shortening, we have found a total of 62 new binary linear codes. PubDate: 2017-05-17 DOI: 10.1007/s00200-017-0327-x