Authors:László Mérai Pages: 193 - 203 Abstract: Let p be a prime and let \(\mathbf {E}\) be an elliptic curve defined over the finite field \(\mathbb {F}_p\) of p elements. For a point \(G\in \mathbf {E}(\mathbb {F}_p)\) the elliptic curve congruential generator (with respect to the first coordinate) is a sequence \((x_n)\) defined by the relation \(x_n=x(W_n)=x(W_{n-1}\oplus G)=x(nG\oplus W_0)\) , \(n=1,2,\ldots \) , where \(\oplus \) denotes the group operation in \(\mathbf {E}\) and \(W_0\) is an initial point. In this paper, we show that if some consecutive elements of the sequence \((x_n)\) are given as integers, then one can compute in polynomial time an elliptic curve congruential generator (where the curve possibly defined over the rationals or over a residue ring) such that the generated sequence is identical to \((x_n)\) in the revealed segment. It turns out that in practice, all the secret parameters, and thus the whole sequence \((x_n)\) , can be computed from eight consecutive elements, even if the prime and the elliptic curve are private. PubDate: 2017-06-01 DOI: 10.1007/s00200-016-0303-x Issue No:Vol. 28, No. 3 (2017)

Authors:Alexander Bors Pages: 205 - 214 Abstract: Aiming at a better understanding of finite groups as finite dynamical systems, we show that by a version of Fitting’s Lemma for groups, each state space of an endomorphism of a finite group is a graph tensor product of a finite directed 1-tree whose cycle is a loop with a disjoint union of cycles, generalizing results of Hernández-Toledo on linear finite dynamical systems, and we fully characterize the possible forms of state spaces of nilpotent endomorphisms via their “ramification behavior”. Finally, as an application, we will count the isomorphism types of state spaces of endomorphisms of finite cyclic groups in general, extending results of Hernández-Toledo on primary cyclic groups of odd order. PubDate: 2017-06-01 DOI: 10.1007/s00200-016-0304-9 Issue No:Vol. 28, No. 3 (2017)

Authors:Dabin Zheng; Zhen Chen Pages: 215 - 223 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: 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: 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:Yogesh Kumar; P. R. Mishra; N. Rajesh Pillai; R. K. Sharma Pages: 257 - 279 Abstract: In this paper, we explore further the non-linearity and affine equivalence as proposed by Mishra et al. (Non-linearity and affine equivalence of permutations. 2014. http://eprint.iacr.org/2014/974.pdf). We propose an efficient algorithm in order to compute affine equivalent permutation(s) of a given permutation of length n, of complexity \(O(n^4)\) in worst case and \(O(n^2)\) in best case. Also in the affirmative in a special case \(n = p\) , prime, it is of complexity \(O(n^3)\) . We also propose an upper bound of non-linearity of permutation(s) whose length satisfies a special condition. Further, behaviour of non-linearity on direct sum and skew sum of permutation has been analysed. Also the distance of an affine permutation from the other affine permutations has also been studied. The cryptographic implication of this work is on permutation based stream ciphers like RC4 and its variants. In this paper, we have applied this study on RC4 cipher. The analysis shows that increasing the key size for RC4 does not mean that increase in the security or saturation after a limit but security may falls as key size increases. PubDate: 2017-06-01 DOI: 10.1007/s00200-016-0307-6 Issue No:Vol. 28, No. 3 (2017)

Authors:Deepa Sinha; Deepakshi Sharma 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: 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: 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: 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: 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:Jaehyun Ahn; Dongseok Ka Abstract: Recently, linear codes constructed from defining sets have been studied widely and they have many applications. For an odd prime p, let \(q=p^{m}\) for a positive integer m and \(\mathrm {Tr}_{m}\) the trace function from \(\mathbb {F}_{q}\) onto \(\mathbb {F}_{p}\) . In this paper, for a positive integer t, let \(D\subset \mathbb {F}^{t}_{q}\) and \(D=\{(x_{1},x_{2}) \in (\mathbb {F}_{q}^{*})^{2} : \mathrm {Tr}_{m}(x_{1}+x_{2})=0\}\) , we define a p-ary linear code \(\mathcal {C}_{D}\) by $$\begin{aligned} \mathcal {C}_{D}=\left\{ \mathbf {c}(a_{1},a_{2}) : (a_{1},a_{2})\in \mathbb {F}^{2}_{q}\right\} , \end{aligned}$$ where $$\begin{aligned} \mathbf {c}(a_{1},a_{2})=\left( \mathrm {Tr}_{m}\left( a_{1}x^{2}_{1}+a_{2}x^{2}_{2}\right) \right) _{(x_{1},x_{2})\in D}. \end{aligned}$$ We compute the weight enumerators of the punctured codes \(\mathcal {C}_{D}\) . PubDate: 2017-05-26 DOI: 10.1007/s00200-017-0329-8

Authors:Dongyoung Roh; I-Yeol Kim; Sang Geun Hahn Abstract: There are many variants of the computational Diffie–Hellman problem that are necessary to provide security of many cryptographic schemes. Two of them are the square Diffie–Hellman problem and the square root Diffie–Hellman problem. Recently, the first and third authors proved that these two problems are polynomial-time equivalent under a certain condition (Roh and Hahn in Des Codes Cryptogr 62(2):179–187, 2011). In this paper, we generalize this result. We introduce the l-th power Diffie–Hellman problem and the l-th root Diffie–Hellman problem and show that these two problems are polynomial-time equivalent for \(l = O (\log p)\) under a condition similar to that of Roh and Hahn (2011), where p is the order of the underlying group. PubDate: 2017-05-23 DOI: 10.1007/s00200-017-0321-3

Authors:Yuan Cao; Yonglin Cao; Li Dong Abstract: Let \({\mathbb {F}}_{3^m}\) be a finite field of cardinality \(3^m\) , \(R={\mathbb {F}}_{3^m}[u]/\langle u^4\rangle \) which is a finite chain ring, and n be a positive integer satisfying \(\mathrm{gcd}(3,n)=1\) . For any \(\delta ,\alpha \in {\mathbb {F}}_{3^m}^{\times }\) , an explicit representation for all distinct \((\delta +\alpha u^2)\) -constacyclic codes over R of length 3n is given, formulas for the number of all such codes and the number of codewords in each code are provided, respectively. Moreover, the dual code for each of these codes is determined explicitly. PubDate: 2017-05-23 DOI: 10.1007/s00200-017-0328-9

Authors:Fatmanur Gursoy; Elif Segah Oztas; Irfan Siap 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: “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: 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

Authors:Haode Yan Abstract: BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. Recently, several classes of BCH codes with length \(n=q^m-1\) and designed distances \(\delta =(q-1)q^{m-1}-1-q^{\lfloor (m-1)/2\rfloor }\) and \(\delta =(q-1)q^{m-1}-1-q^{\lfloor (m+1)/2\rfloor }\) were widely studied, where \(m\ge 4\) is an integer. In this paper, we consider the case \(m=3\) . The weight distribution of a class of primitive BCH codes with designed distance \(q^3-q^2-q-2\) is determined, which solves an open problem put forward in Ding et al. (Finite Fields Appl 45:237–263, 2017). PubDate: 2017-05-16 DOI: 10.1007/s00200-017-0320-4

Authors:Xiaoni Du; Yunqi Wan Abstract: Linear codes have been an interesting topic in both theory and practice for many years. In this paper, for an odd prime power q, we present a class of linear codes over finite fields \(F_q\) with quadratic forms via a general construction and then determine the explicit complete weight enumerators of these linear codes. Our construction covers some related ones via quadratic form functions and the linear codes may have applications in cryptography and secret sharing schemes. PubDate: 2017-05-15 DOI: 10.1007/s00200-017-0319-x