Search

This paper presents two modifications for Loidreau's cryptosystem, a rank metric-based cryptosystem constructed by using Gabidulin codes in the McEliece setting. Recently a polynomial-time key recovery attack was proposed to break this cryptosystem in some cases. To prevent this attack, we propose the use of subcodes to disguise the secret codes in Modification I. In Modification II, we choose a random matrix of low column rank to mix with the secret matrix. Our analysis shows that these two modifications can both resist the existing structural attacks. Furthermore, these modifications have a much more compact representation of public keys compared to Classic McEliece, which has been selected into the fourth round of the NIST-PQC project. [ABSTRACT FROM AUTHOR]

Special Issue: "Computer Algebra and Application to Combinatorics, Coding Theory and Cryptography" ACA 2019, Montreal, Canada, July 16-20, 2019 This volume contains the refereed papers within the scope of the special session on Computer Algebra and Application to Combinatorics, Coding Theory and Cryptography, in the ACA 2019 conference held July 16-20, 2019 at Montreal, Canada. These 8 papers covered various topics in computer algebra with applications to combinatorics (e.g., projective planes, SAT problem), coding theory (e.g., error locator polynomials for BCH codes, optimal RS-like LRC codes, skew or repeated-root constacyclic codes), and cryptography (e.g., boomerang uniformity, Gröbner basis, Dickson polynomials, permutation polynomials). [Extracted from the article]

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. ). 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. [ABSTRACT FROM AUTHOR]

In this paper we show that the Z / p m Z -module structure of the ring E p (m) is isomorphic to a Z / p m Z -submodule of the matrix ring over Z / p m Z . Using this intrinsic structure of E p (m) , solving a linear system over E p (m) becomes computationally equivalent to solving a linear system over Z / p m Z . As an application we break the protocol based on the Diffie–Hellman decomposition problem and ElGamal decomposition problem over E p (m) . Our algorithm terminates in a provable running time of O (m 6) Z / p m Z -operations. [ABSTRACT FROM AUTHOR]

When a pairing e : G 1 × G 2 → G T , on an elliptic curve E defined over a finite field F q , is exploited for an identity-based protocol, there is often the need to hash binary strings into G 1 and G 2 . Traditionally, if E admits a twist E ~ of order d, then G 1 = E (F q) ∩ E [ r ] , where r is a prime integer, and G 2 = E ~ (F q k / d ) ∩ E ~ [ r ] , where k is the embedding degree of E w.r.t. r. The standard approach for hashing into G 2 is to map to a general point P ∈ E ~ (F q k / d ) and then multiply it by the cofactor c = # E ~ (F q k / d ) / r . Usually, the multiplication by c is computationally expensive. In order to speed up such a computation, two different methods—by Scott et al. (International conference on pairing-based cryptography. Springer, Berlin, pp 102–113, 2009) and by Fuentes-Castaneda et al. (International workshop on selected areas in cryptography)—have been proposed. In this paper we consider these two methods for BLS pairing-friendly curves having k ∈ { 12 , 24 , 30 , 42 , 48 } , providing efficiency comparisons. When k = 42 , 48 , the application of Fuentes et al. method requires expensive computations which were infeasible for the computational power at our disposal. For these cases, we propose hashing maps that we obtained following Fuentes et al. idea. [ABSTRACT FROM AUTHOR]

'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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we give and explain some illustrative examples of research topics where error-correcting codes overlap with cryptography. In some of these examples, error-correcting codes employed in the implementation of secure cryptographic protocols. In the others, the codes are used in attacks against cryptographic schemes. Throughout this paper, we show the interrelation between error-correcting codes and cryptography, as well as point out the common features and the differences between these two fields. [ABSTRACT FROM AUTHOR]

Recent research within the field of cryptography has suggested that S-boxes should be chosen to contain few fixed points, motivating analysis of the fixed points of permutations. This paper presents a novel mean of obtaining fixed points for all functions satisfying a property put forth by Carlitz. We determine particular results concerning the fixed points of rational functions. Such concepts allow the derivation of an algorithm which cyclically generates fixed points for all three classes of functions satisfying the Carlitz property, the most renowned of which are Rédei rational functions. Specifically, we present all fixed points for any given Rédei function in a single cycle, generated by a particular non-constant rational transformation. For the other two classes of functions, we present their fixed points in cycles consisting of smaller cycles of fixed points. Finally, we provide an explicit expression for the fixed points of all Rédei functions over F q . [ABSTRACT FROM AUTHOR]

Recently, Edwards curves have received a lot of attention in the cryptographic community due to their fast scalar multiplication algorithms. Then, many works on the application of these curves to pairing-based cryptography have been introduced. In this paper, we investigate refinements to Miller's algorithm that play a central role in paring computation. We first introduce a variant of Miller function that leads to a more efficient variant of Miller's algorithm on Edwards curves. Then, based on the new Miller function, we present a refinement to Miller's algorithm that significantly improves the performance in comparison with the original Miller's algorithm. Our analyses also show that the proposed refinement is approximately 25 % faster than Xu-Lin's refinements (CT-RSA, 2010). Last but not least, our approach is generic, hence the proposed algorithms allow to compute both Weil and Tate pairings on pairing-friendly Edwards curves of any embedding degree. [ABSTRACT FROM AUTHOR]

The efficient computation of the Tate pairing is crucial for various cryptographic applications. In the computation the Tate pairing, two types of costs should be considered: that of scalar multiplication and the evaluations of Miller's line functions for elliptic curves. In this paper we optimize the calculation of $$(f_{2j\pm 1}(Q),[2j\pm 1]P)$$ , $$(f_{3j}(Q),[3]P)$$ , $$(f_{3j\pm 1}(Q),[3j\pm 1]P)$$ given the points P and Q in an elliptic curve, to improve the efficiency of the Tate pairing, when using the representation of the scalar n in NAF, in signed ternary base, and in double-base chain. Finally we compare their computational costs. In the case of a double-base chain, a general comparison is not simple, so we consider a few examples. [ABSTRACT FROM AUTHOR]

Applying the Gram-Schmidt process (also called Gram-Schmidt orthogonalization) to a matrix M∈GL(n,R), set of n×n invertible matrices over the field of real numbers, with the usual inner product gives easily an orthogonal matrix. However, the orthogonality in the vector space Fqk, where Fq is a binary finite field, is quite tricky as there are non-zero vectors which are orthogonal to themselves. For this reason the computational variants of Gram-Schmidt orthogonalization can fail. This paper presents an algorithm for constructing random orthogonal matrices over binary finite fields. The approach is inspired from the Gram-Schmidt procedure. Since the inverse of orthogonal matrix is easy to compute, the orthogonal matrices are used to construct a proactive variant of Bloom's threshold secret sharing scheme. [ABSTRACT FROM AUTHOR]

Permutation polynomials have important applications in cryptography, coding theory, combinatorial designs, and other areas of mathematics and engineering. Finding new classes of permutation polynomials is therefore an interesting subject of study. In this paper, for an integer s satisfying s=qn-12+qr, we give six classes of permutation polynomials of the form (axqm-bx+δ)s+L(x) over Fqn, and for s satisfying s(pm-1)≡pm-1(modpn-1) or s(pk2m-1)≡pkm-1(modpn-1), we propose three classes of permutation polynomials of the form (aTrmn(x)+δ)s+L(x) over Fpn, respectively. [ABSTRACT FROM AUTHOR]

Modern lattice-based public-key cryptosystems require sampling from discrete Gaussian (normal) distributions. The paper surveys algorithms to implement such sampling efficiently, with particular focus on the case of constrained devices with small on-board storage and without access to large numbers of external random bits. We review lattice encryption schemes and signature schemes and their requirements for sampling from discrete Gaussians. Finally, we make some remarks on challenges and potential solutions for practical lattice-based cryptography. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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, Fp12 arithmetic, groups involved and their generators, system of coordinates). We focus on low level implementations, assuming that Fp additions have a significant cost compared to other Fp operations. However, our results are still valid if Fp additions can be neglected. We also explain why the best choice for the polynomials defining the tower field Fp12 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 Fp12 arithmetic (in a pairing context). [ABSTRACT FROM AUTHOR]

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 Ep(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. [ABSTRACT FROM AUTHOR]

In this paper, we consider the finite groups H(t,l,m)=⟨a,b,c|at=bl=cm=1,[a,b]=c,[a,c]=[b,c]=1⟩.\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\begin{aligned} H_{(t,l,m)}=\langle a,b,c | a^t=b^l=c^m=1, [a,b]=c, [a,c]=[b,c]=1\rangle . \end{aligned}$$\end{document}We obtain the generalized order-k Pell sequences and study their periods. We prove the period of the order-k Pell sequence divided the period of the generalized order-k Pell sequence in the Heisenberg group. Then, the generalized order-k Pell sequence in Heisenberg group are used to define new cyclic groups. As an application, these groups are used in encryption algorithms. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper we propose a tokenization algorithm of Reversible Hybrid type, as defined in PCI DSS guidelines for designing a tokenization solution, based on a block cipher with a secret key and (possibly public) additional input. We provide some formal proofs of security for it, which imply our algorithm satisfies the most significant security requirements described in PCI DSS tokenization guidelines. Finally, we give an instantiation with concrete cryptographic primitives and fixed length of the PAN, and we analyze its efficiency and security. [ABSTRACT FROM AUTHOR]

Recently, Kim et al. proposed a modified Dual-Ouroboros public-key encryption (PKE ) using Gabidulin codes to overcome the limitation of having decryption failure in the original Dual-Ouroboros using low rank parity check codes. This modified Dual-Ouroboros PKE using Gabidulin codes is proved to be IND–CPA secure, with very compact public key size of 738 bytes achieving 128-bit security level. However, they did not specify on their choice of the secret key S used in their PKE . In this paper, we analyze different possible choices for S in the modified Dual-Ouroboros PKE using Gabidulin codes. More specifically, we show that if S is invertible over F q m without any restriction, then the decryption algorithm will fail. Furthermore, we show that Kim et al.'s proposal of the modified Dual-Ouroboros PKE using Gabidulin codes has secret key S over F q for its decryption algorithm to be correct. Then, we proposed two attacks: key recovery attack and plaintext recovery attack on their PKE with S over F q . We are able to recover the secret key for all the proposed parameters within 235 seconds. Moreover, we show that the public key matrix in their proposal generates a subcode of Gabidulin code. As a consequence, we can apply the Frobenius weak attack on their proposal and recover the plaintext for all the proposed paramters within 0.614 second. Finally, we give a proposal for the modified Dual-Ouroboros PKE using Gabidulin codes such that it is correct and secure, by considering certain restrictions on S over F q m . [ABSTRACT FROM AUTHOR]

Are there other Boolean functions having two distinct Walsh coefficients except affine Boolean functions and maximal nonlinear (i.e. bent) Boolean functions? This paper proves that all Boolean functions with exactly two distinct Walsh coefficients are just the two known classes of affine and bent Boolean functions and the Boolean functions obtained by modifying the value of affine or bent Boolean functions at x = 0. [ABSTRACT FROM AUTHOR]

The r-th order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. By investigating the lower bound of the nonlinearity of the derivative of the function f, this paper tightens the lower bound of the second-order nonlinearity of a class of Boolean functions over $${F_{2^n}}$$ with high nonlinearity in the form f( x) = tr(λ x), where $${\lambda\in F_{2^r}^*, d=2^{2r}+2^{r}+1}$$ and n = 4 r. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper, several classes of Boolean functions with few Walsh transform values, including bent, semi-bent and five-valued functions, are obtained by adding the product of two or three linear functions to some known bent functions. Numerical results show that the proposed class contains cubic bent functions that are affinely inequivalent to all known quadratic ones. [ABSTRACT FROM AUTHOR]

In Sakumoto et al. (CRYPTO 2011, LNCS, vol 6841. Springer, Berlin, pp 706-723, ), presented a new multivariate identification scheme, whose security is based solely on the MQ-Problem of solving systems of quadratic equations over finite fields. In this paper we extend this scheme to a threshold ring identification and signature scheme. Our scheme is the first multivariate scheme of this type and generally one of the first multivariate signature schemes with special properties. Despite of the fact that we need more rounds to achieve given levels of security, the signatures are at least twice shorter than those obtained by other post-quantum (e.g. code based) constructions. Furthermore, our scheme offers provable security, which is quite a rare fact in multivariate cryptography. [ABSTRACT FROM AUTHOR]

Fair exchange protocols have been widely studied since their proposal, but are still not implemented on most e-commerce transactions available. For several types of digital items (e-goods), the current e-commerce business model fails to provide fairness to customers. The item validation problem is a critical step in fair exchange, and is yet to receive the proper attention from researchers. We believe these issues should be addressed in a comprehensive and integrated fashion before fair exchange protocols can be effectively deployed in the marketplace. In this work, we contextualize how the current model for buying and selling digital items fails, by overlooking the subtleties of the item validation problem, to provide guarantees of a successful transaction outcome to customers-thus being unfair by design. We also introduce the concept of Reversible Degradation, a method for enhancing buy-sell transactions concerning digital items that inherently includes the item validation step in the purchase protocol in order to tackle the discussed problems. In this paper we further explore the concept of reversible degradation (Piva and Dahab in Proceedings of international conference on security and cryptography (SECRYPT). SciTePress Digital Library, ) and propose a deliverable instantiation based on systematic error correction codes, suitable for multimedia content. We describe our technique in detail and provide methods for key generation, degradation and recovery, as well as a discussion about efficiency, security and flexibility. We also present and discuss experimental data, and exemplify how the technique can be useful for enabling item validation and dispute resolution in some application scenarios. [ABSTRACT FROM AUTHOR]

A foreword to "Applicable Algebra in Engineering, Communication & Computing" is presented.

In the past decades, linear codes with a few weights have been extensively studied for their applications in space communication, data storage and cryptography etc. We construct several classes of binary linear codes and determine their weight distributions. Most of these codes can be used in secret sharing schemes. [ABSTRACT FROM AUTHOR]

In recent years, various cryptographic protocols using infinite non-commutative groups, notably braid groups, have been proposed. Both experimental and theoretical evidence collected so far, however, makes it appear likely that braid groups are not a good choice for the platform. In this paper, we thus consider to use affine braid groups, a natural generalization of braid groups, as a platform. Like braid groups, affine braid groups have a very nice geometrical interpretation and have several properties that make them acceptable for cryptographic purposes. On the other hand, there are also essential differences between their structures; for example, unlike braid groups, affine braid groups have no Garside structure, which makes the conjugacy problem in these groups more difficult. We examine the feature that makes affine braid groups useful to cryptography and then conclude that this class of groups could provide a promising alternative platform for group-based cryptography. [ABSTRACT FROM AUTHOR]

Koblitz curves have been proposed to quickly generate random ideal classes and points on hyperelliptic and elliptic curves. To obtain a further speed-up a different way of generating these random elements has recently been proposed. In this paper we give an upper bound on the number of collisions for this alternative approach. For elliptic Koblitz curves we additionally use the same methods to derive a bound for a modified algorithm. These bounds are tight for cyclic subgroups of prime order, which is the case of most practical interest for cryptography. [ABSTRACT FROM AUTHOR]

In the RSA public-key cryptosystem the encryption function is a permutation on the residue class ring ℤ/Nℤ induced by some polynomial X ∈(ℤ/Nℤ) [X], where N is the product of two large primes. Variants of the RSA-scheme can be obtained, if this permutation is replaced by different types of rational permutations on ℤ/Nℤ. A more general approach is the use of arbitrary finite rings instead of residue class rings in cryptography. Since the message space is finite, in either case cryptanalysis can be effected by superenciphering. A serious weakness of those PKCs is the existence of a large number of fixedpoints. But even if there are only few fixedpoints in the message space, the elements of considerable small cyclelength are much inconvenient. Anyway an analysis of the minimal cyclelength, i.e. the minimum of cyclelengths of elements different from fixedpoints, is necessary. In this paper such an analysis will be carried out in the case of Rédei- and Dickson permutations on arbitrary finite rings. The results obtained provide a good basis to construct secure PKCs with best protection against superenciphering. Some of the problems and results in the special cases of finite fields and residue class rings have been stated earlier in the literature (see references). [ABSTRACT FROM AUTHOR]

Let γ be a generator of a cyclic group G of order n. The least index of a self-mapping f of G is the index of the largest subgroup U of G such that f (x) x - r is constant on each coset of U for some positive integer r. We determine the index of the univariate Diffie–Hellman mapping d (γ a) = γ a 2 , a = 0 , 1 , ... , n - 1 , and show that any mapping of small index coincides with d only on a small subset of G. Moreover, we prove similar results for the bivariate Diffie–Hellman mapping D (γ a , γ b) = γ ab , a , b = 0 , 1 , ... , n - 1 . In the special case that G is a subgroup of the multiplicative group of a finite field we present improvements. [ABSTRACT FROM AUTHOR]

Let $$g$$ be a function over $$\mathbb {F}_q$$ . If there exist a function $$f$$ and $$a\in \mathbb {F}_q^*$$ such that $$g(x)=f(x+a)-f(x)$$ , then we call $$g$$ a differential function and call $$f$$ a differential-inverse of $$g$$ . We present two criteria to decide whether a given $$g$$ is a differential function. The set of the degrees of all differential functions over $${\mathbb {F}}_q$$ is determined. Then we give a lower bound and an upper bound on the number of differential functions over $${\mathbb {F}}_q$$ . Besides, we show how to construct differential inverses of a given differential function. At last, some applications of our results are introduced. [ABSTRACT FROM AUTHOR]

Climent et al. (Appl Algebra Eng Commun Comput 22:91-108, ) identified the elements of the endomorphisms ring End $${(\mathbb{Z}_p \times \mathbb{Z}_{p^2})}$$ with elements in a set, E, of matrices of size 2 × 2, whose elements in the first row belong to $${\mathbb{Z}_{p}}$$ and the elements in the second row belong to $${\mathbb{Z}_{p^2}}$$. By taking advantage of matrix arithmetic, they proposed a key exchange protocol using polynomial functions over E defined by polynomials in $${\mathbb{Z}[X]}$$. In this note, we show that this protocol is insecure; it can be broken by solving a set of 10 consistent homogeneous linear equations in 8 unknowns over $${\mathbb{Z}_{p^2}}$$. [ABSTRACT FROM AUTHOR]

In 1994, Moss Sweedler's dog proposed a cryptosystem, known as Barkee's Cryptosystem, and the related cryptanalysis. Its explicit aim was to dispel the proposal of using the urban legend that "Gröbner bases are hard to compute", in order to devise a public key cryptography scheme. Therefore he claimed that "no scheme using Gröbner bases will ever work". Later, further variations of Barkee's Cryptosystem were proposed on the basis of another urban legend, related to the infiniteness (and consequent uncomputability) of non-commutative Gröbner bases; unfortunately Pritchard's algorithm for computing (finite) non-commutative Gröbner bases was already available at that time and was sufficient to crash the system proposed by Ackermann and Kreuzer. The proposal by Rai, where the private key is a principal ideal and the public key is a bunch of polynomials within this principal ideal, is surely immune to Pritchard's attack but not to Davenport's factorization algorithm. It was recently adapted specializing and extending Stickel's Diffie–Hellman protocols in the setting of Ore extension. We here propose a further generalization and show that such protocols can be broken simply via polynomial division and Buchberger reduction. [ABSTRACT FROM AUTHOR]

We study the relation among some security parameters for vectorial Boolean functions which prevent attacks on the related block cipher. We focus our study on a recently-introduced security criterion, called weak differential uniformity, which prevents the existence of an undetectable trapdoor based on imprimitive group action. We present some properties of functions with low weak differential uniformity, especially for the case of power functions and 4-bit S-Boxes. [ABSTRACT FROM AUTHOR]

We give the trace representation of a family of binary sequences derived from Euler quotients by determining the corresponding defining polynomials. The result extends an earlier result of Z. Chen on the trace of binary sequences derived from Fermat quotients modulo a prime. However, the case of composite modulus brings some interesting twists. Trace representation can help us producing the sequences efficiently and analyzing their cryptographic properties, such as linear complexity. [ABSTRACT FROM AUTHOR]

An extension of the primitive normal basis theorem and its strong version is proved. Namely, we show that for nearly all $$A = {\small \left( \begin{array}{cc} a&{}b \\ c&{}d \end{array} \right) } \in \mathrm{GL}_2(\mathbb {F}_{q})$$ , there exists some $$x\in \mathbb {F}_{q^m}$$ such that both $$x$$ and $$(-dx+b)/(cx-a)$$ are simultaneously primitive elements of $$\mathbb {F}_{q^m}$$ and produce a normal basis of $$\mathbb {F}_{q^m}$$ over $$\mathbb {F}_q$$ , granted that $$q$$ and $$m$$ are large enough. [ABSTRACT FROM AUTHOR]

We define a polynomial generating pairing (PGP) and propose a method to construct a family of pairing friendly curves from PGP. We show that a bilinear map over the family is directly determined by the coefficients of the PGP and the map is non-degenerate under a minor condition which is satisfied with cryptographic parameters. Finally, we provide a criterion for PGP to obtain an optimal pairing. [ABSTRACT FROM AUTHOR]

For binary sequences with period $$p^{n}$$ , where $$p$$ is an odd prime and 2 is a primitive root modulo $$p^{2}$$ , we present an algorithm which computes the minimum number $$k$$ so that the $$k$$ -error linear complexity is not greater than a given constant $$c$$ . An associated error sequence which gives the $$k$$ -error linear complexity is also obtained. [ABSTRACT FROM AUTHOR]

BEAR, LION and LIONESS are block ciphers presented by Biham and Anderson (), inspired by the famous Luby-Rackoff constructions of block ciphers from other cryptographic primitives (). The ciphers proposed by Biham and Anderson are based on one stream cipher and one hash function. Good properties of the primitives may ensure good properties of the block cipher. In particular, Biham and Anderson are able to prove that their ciphers are immune to any efficient known-plaintext key-recovery attack that can use as input only one plaintext-ciphertext pair. Our contribution is showing that these ciphers are actually immune to any efficient known-plaintext key-recovery attack that can use as input any number of plaintext-ciphertext pairs. We are able to get this improvement by using slightly different hypotheses on the primitives. We also discuss the attack by Morin (). [ABSTRACT FROM AUTHOR]

In secret sharing schemes a secret is distributed among a set of users $${\mathcal{P}}$$ in such a way that only some sets, the authorized sets, can recover it. The family Γ of authorized sets is called the access structure. To design new cryptographic protocols, we introduce in this work the concept of extension of an access structure: given a monotone family $${{\it \Gamma} \subset 2^\mathcal{P}}$$ and a larger set $${\mathcal{P}^{\prime} = \mathcal{P} \cup \tilde{\mathcal{P}}}$$, a monotone access structure $${{\it \Gamma}^{\prime}\subset 2^{\mathcal{P}^{\prime}}}$$ is an extension of Γ if the following two conditions are satisfied: (1) The set $${\mathcal{P}}$$ is a minimal subset of Γ′, i.e. $${\mathcal{P} \in {\it \Gamma}^{\prime}}$$ and $${\mathcal{P} - \{R_i\}\notin {\it \Gamma}^{\prime}}$$ for every $${R_i \in \mathcal{P}}$$, (2) A subset $${A \subset \mathcal{P}}$$ is in Γ if and only if the subset $${A \cup \tilde{\mathcal{P}}}$$ is in Γ′. As our first contribution, we give an explicit construction of an extension Γ′ of a vector space access structure Γ, and we prove that Γ′ is also a vector space access structure. Although the definition may seem a bit artificial at first, it is well motivated from a cryptographic point of view. Indeed, our second contribution is to show that the concept of extension of an access structure can be used to design encryption schemes with access structures that are chosen ad-hoc at the time of encryption. Specifically, we design and analyze a dynamic distributed encryption scheme and a ciphertext-policy attribute-based encryption scheme. In some cases, the new schemes enjoy better properties than existing ones. [ABSTRACT FROM AUTHOR]

Abstract  Perfect nonlinear functions are of importance in cryptography. By using Galois ring, relative trace and investigating the character values of corresponding relative difference sets, we present a construction of perfect nonlinear functions from $${\mathbb{Z}_4^{2m}}$$ to $${\mathbb{Z}_4^{m'}}$$ , where m′ is a divisor of 2m, and a construction of perfect nonlinear functions from $${\mathbb{Z}_{p^2}^{n}}$$ to $${\mathbb{Z}_{p^2}^m}$$ where 2m is possibly larger than the largest divisor of n. Meanwhile we prove that there exists a perfect nonlinear function from $${\mathbb{Z}_{2p}^2}$$ to $${\mathbb{Z}_{2p}}$$ if and only if p = 2, and there doesn’t exist a perfect nonlinear function from $${\mathbb{Z}_{2^kl}^{2n}}$$ to $${\mathbb{Z}_{2^kl}^m}$$ if m > n and l(l is odd) is self-conjugate modulo 2 k (k ≥ 1). [ABSTRACT FROM AUTHOR]

Abstract  We provide some guidelines for deriving new projective hash families of cryptographic interest. Our main building blocks are so called group action systems; we explore what properties of these mathematical primitives may lead to the construction of cryptographically useful projective hash families. We point out different directions towards new constructions, deviating from known proposals arising from Cramer and Shoup’s seminal work. [ABSTRACT FROM AUTHOR]

Cryptographic sequence generators are discussed in which a linear feedback shift register (LFSR) is clock controlled in a pseudorandom manner by another register. A model of clock-controlled sequences is proposed. The necessary and sufficient condition guaranteeing the maximal linear complexity and the maximal period of such sequences is given. Two kinds of improved models having better statistical properties are given. In order to study the security of this model, three types of algebraic attacking algorithms are proposed. If the length of the second LFSR in such a model is large, the model can resist our algebraic attacks. [ABSTRACT FROM AUTHOR]