Cryptanalysis of an MOR cryptosystem based on a finite associative algebra基于有限结合代数的 MOR 公钥密码安全性分析

The Shor algorithm is effective for public-key cryptosystems based on an abelian group. At CRYPTO 2001, Paeng (2001) presented a MOR cryptosystem using a non-abelian group, which can be considered as a candidate scheme for post-quantum attack. This paper analyses the security of a MOR cryptosystem based on a finite associative algebra using a quantum algorithm. Specifically, let L be a finite associative algebra over a finite field F. Consider a homomorphism φ: Aut(L) → Aut(H)×Aut(I), where I is an ideal of L and H ? L/I. We compute dim Im(φ) and dim Ker(φ), and combine them by dim Aut(L) = dim Im(φ)+dim Ker(φ). We prove that Im(φ) = Stab_Comp(H,I)(μ + B²(H, I)) and Ker(φ) ? Z¹(H, I). Thus, we can obtain dim Im(φ), since the algorithm for the stabilizer is a standard algorithm among abelian hidden subgroup algorithms. In addition, Z¹(H, I) is equivalent to the solution space of the linear equation group over the Galois fields GF(p), and it is possible to obtain dim Ker(φ) by the enumeration theorem. Furthermore, we can obtain the dimension of the automorphism group Aut(L). When the map ? ∈ Aut(L), it is possible to effectively compute the cyclic group 〈?〉 and recover the private key a. Therefore, the MOR scheme is insecure when based on a finite associative algebra in quantum computation.     

On the real complexity of a complex DFT

We present a method to construct a theoretically fast algorithm for computing the discrete Fourier transform (DFT) of order N = 2 ⁿ . We show that the DFT of a complex vector of length N is performed with complexity of 3.76875N log₂ N real operations of addition, subtraction, and scalar multiplication.     

On Supersymmetric M-brane configurations with an R<Stack><Subscript>*</Subscript><Superscript>1,1</Superscript></Stack> /Z<Subscript>2</Subscript> submanifold

We obtain new examples of partly supersymmetric M-brane solutions defined on products of Ricci-flat manifolds, which contain a two-dimensional Lorentzian submanifold R _* ^1,1 /Z ₂ with one parallel spinor. The examples belong to the following configurations: M2, M5, M2 ∩M5 and M5 ∩M5. Among them, an M2 solution with N = 1/32 fractional number of preserved supersymmetries is presented.     

Design and analysis of two stream ciphers based on chaotic coupling and multiplexing techniques

In this paper, we design and implement two new stream ciphers based on Pseudo Chaotic Number Generators (PCNGs) which integrate discrete chaotic maps, namely, Piecewise Linear Chaotic Map (PWLCM), Skewtent and Logistic map. They are weakly coupled by a predefined matrix A for the first PCNG and they are coupled by a binary diffusion matrix D for the second one. Each PCNG includes a chaotic multiplexing technique that allows the enhancement of the robustness of the system. The structure is implemented with finite precision N = 32 bits in C language. Security performance of the proposed stream ciphers is analysed and several cryptanalytic and statistical tests are applied. Experimental results highlight robustness as well as efficiency in terms of computation time of these two stream ciphers.     

Generalized cryptanalysis of RSA with small public exponent针对公钥e小于等于N的0.5次幂的RSA算法的广义密码分析

In this paper, we demonstrate that there exist weak keys in the RSA public-key cryptosystem with the public exponent e = N^α ≤ N^0.5. In 1999, Boneh and Durfee showed that when α ≈ 1 and the private exponent d = N^β < N^0.292, the system is insecure. Moreover, their attack is still effective for 0.5 < α < 1.875. We propose a generalized cryptanalytic method to attack the RSA cryptosystem with α ≤ 0.5. For \(c = \left\lfloor {\frac{{1 - \alpha }}{\alpha }} \right\rfloor \) and e^γc ≡ d (mod e^c), when γ, β satisfy \(\gamma < 1 + \frac{1}{c} - \frac{1}{{2\alpha c}}and\beta < \alpha c + \frac{7}{6} - \alpha \gamma c - \frac{1}{3}\sqrt {6\alpha + 6\alpha c + 1 - 6\alpha \gamma c} \), we can perform cryptanalytic attacks based on the LLL algorithm. The basic idea is an application of Coppersmith’s techniques and we further adapt the technique of unravelled linearization, which leads to an optimized lattice. Our advantage is that we achieve new attacks on RSA with α ≤ 0.5 and consequently, there exist weak keys in RSA for most α.     

On s-uniform property of compressing sequences derived from primitive sequences modulo odd prime powers

Let Z/(p^e) be the integer residue ring modulo p^e with p an odd prime and e ≥ 2. We consider the suniform property of compressing sequences derived from primitive sequences over Z/(p^e). We give necessary and sufficient conditions for two compressing sequences to be s-uniform with α provided that the compressing map is of the form ?(x₀, x₁,...,x_e?1) = g(x_e?1) + η(x₀, x₁,..., x_e?2), where g(x_e?1) is a permutation polynomial over Z/(p) and η is an (e ? 1)-variable polynomial over Z/(p).     

A novel method for digital image steganography based on a new three-dimensional chaotic map

This paper, presents a novel chaos-based image steganography algorithm. Because of efficient property of chaos based security systems besides steganography applicability in providing secure communication, chaos based steganography algorithms served as a hot topic in recent researches. The proposed scheme possess novelties and advantageous such as: 1) Introducing a novel 3-dimensional chaotic map (LCA map) with strong chaotic characteristics and maximum Lyapunov exponent 20.58, which is used for generating three chaotic sequences, each of them represents the number of row, column, and colour component, respectively. 2) Utilizing random selection procedure for selecting subsequences with length of 2L, which L is the length of secret message 3) Specifying L pairs of triples host positions for embedding LSBs and MSBs of secret message by using three high level chaotic maps. 4) Entering some parameters dependent on elementary initial values, host image, and secret message features as a key point for adding additional layer of security alongside providing high sensitivity. 5) Providing high capacity for embedding secret message, which is equal to 50 % of whole image capacity (M?×?N?×?12). The proposed method could be applied in different criterion such as, confidential communication and data storing, protection of data alteration, and etc. Our experimental results guarantees that our scheme is not only robust against differential attacks, but also has promising results such as highly sensitive keys, Quality index, PSNR, MSE, and hiding capacity as shown in statistical security analysis.     

A plaintext-related image encryption algorithm based on chaos

A symmetric key image cryptosystem based on the piecewise linear map is presented in this paper. In this cryptosystem, the encryption process and the decryption process are exactly same. They both include the same operations of plaintext-related scrambling once, diffusion twice and matrix rotating of 180 degrees four times. The length of secret key in the system is 64d where d is a positive integer. The proposed system can fight against the chosen/known plaintext attacks due to the using of plaintext-related scrambling. The simulate results and comparison analysis show that the proposed system has many merits such as high encryption/decryption speed, large key space, strong key sensitivity, strong plaintext sensitivity, strong cipher-text sensitivity, good statistical properties of cipher images, and large cipher-text information entropy. So the proposed system can be applied to actual communications.     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

Guaranteed approach with the farthest of the runaways

Games of the family {Λ _N } _N?2 are formulated and studied with the application of generalized Isaacs’s approach. The game Λ _N is a simplest model of the counteraction of one persecutor P and coalition N of E ^N runaways for the case when the payoff is the distance up to the coalition of E ^N equal to the Euclidean distance between P and the farthest from the runaways; P is in command of the termination moment. Moreover, an approach within the limits of which in games with a smooth terminal payoff are generated strategies prescribing players’ motions in the directions of local gradients of the payoff is described. The approach is used for constructing pursuit strategies in games in which smooth approximations of the maximum of Euclidean distances up to the runaways are in place of payoffs. Pursuit strategies prescribing the motion in the direction of the farthest of the runaways are studied. A numerical simulation of the development of the games Λ₂ and Λ₃ is conducted in using different strategies by the players.     

New quantum codes from dual-containing cyclic codes over finite rings

Let \(R=\mathbb {F}_{2^{m}}+u\mathbb {F}_{2^{m}}+\cdots +u^{k}\mathbb {F}_{2^{m}}\), where \(\mathbb {F}_{2^{m}}\) is the finite field with \(2^{m}\) elements, m is a positive integer, and u is an indeterminate with \(u^{k+1}=0.\) In this paper, we propose the constructions of two new families of quantum codes obtained from dual-containing cyclic codes of odd length over R. A new Gray map over R is defined, and a sufficient and necessary condition for the existence of dual-containing cyclic codes over R is given. A new family of \(2^{m}\)-ary quantum codes is obtained via the Gray map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R. In particular, a new family of binary quantum codes is obtained via the Gray map, the trace map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R.     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

Propelinear codes related to some classes of optimal codes

A code is said to be propelinear if its automorphism group contains a subgroup that acts regularly on codewords. We show propelinearity of complements of cyclic codes C _1,i , (i, 2 ^m ? 1) = 1, of length n = 2 ^m ? 1, including the primitive two-error-correcting BCH code, to the Hamming code; the Preparata code to the Hamming code; the Goethals code to the Preparata code; and the Z₄-linear Preparata code to the Z₄-linear perfect code.     

Advanced methods for the estimation of an unknown projection from a map

This article presents three new methods (M5, M6, M7) for the estimation of an unknown map projection and its parameters. Such an analysis is beneficial and interesting for historic, old, or current maps without information about the map projection; it could improve their georeference. The location similarity approach takes into account the residuals on the corresponding features; the minimum is found using the non-linear least squares. For the shape similarity approach, the minimized objective function ? takes into account the spatial distribution of the features, together with the shapes of the meridians, parallels and other 0D-2D elements. Due to the non-convexity and discontinuity, its global minimum is determined using the global optimization, represented by the differential evolution. The constant values of projection φ _k , λ _k , φ ₁, λ ₀, and map constants R,ΔX,ΔY, α (in relation to which the methods are invariant) are estimated. All methods are compared and the results are presented for the synthetic data as well as for 8 early maps from the Map Collection of the Charles University and the David Rumsay Map Collection. The proposed algorithms have been implemented in the new version of the detectproj software.     

Fast computation of Gröbner basis of homogenous ideals of $$ \mathbb{F} $$[ x,y]

This paper provides a fast algorithm for Grobnerbases of homogenous ideals of F[x, y] over a finite field F. We show that only the 8-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary 5-polynomials that are processed. We also show that the computational complexity of our new algorithm is O（N^2）, where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.     

On finite groups with large degrees of irreducible character

Let G be a finite nontrivial group with an irreducible complex character χ of degree d = χ(1). According to the orthogonality relation, the sum of the squared degrees of irreducible characters of G is the order of G. N. Snyder proved that, if G = d(d + e), then the order of the group G is bounded in terms of e for e > 1. Y. Berkovich demonstrated that, in the case e = 1, the group G is Frobenius with the complement of order d. This paper studies a finite nontrivial group G with an irreducible complex character Θ such that G ≤ 2Θ(1)² and Θ(1) = pq where p and q are different primes. In this case, we have shown that G is a solvable group with an Abelian normal subgroup K of index pq. Using the classification of finite simple groups, we have established that the simple non-Abelian group, the order of which is divisible by the prime p and not greater than 2p ⁴ is isomorphic to one of the following groups: L ₂(q), L ₃(q), U ₃(q), S _z(8), A ₇, M ₁₁, and J ₁.     

The formula of the solution for some classes of initial boundary value problems for the hyperbolic equation with two independent variables

A new representation is proved of the solutions of initial boundary value problems for the equation of the form u _xx (x, t) + r(x)u _x (x, t) ? q(x)u(x, t) = u _tt (x, t) + μ(x)u _t (x, t) in the section (under boundary conditions of the 1st, 2nd, or 3rd type in any combination). This representation has the form of the Riemann integral dependent on the x and t over the given section.     

Observational constraints on a hyperbolic potential in brane-world inflation

We focus on the large field of a hyperbolic potential form, which is characterized by a parameter f, in the framework of the brane-world inflation in Randall-Sundrum-II model. From the observed form of the power spectrum P _R (k), the parameter f should be of order 0.1m _p to 0.001m _p , the brane tension must be in the range λ ~ (1?10)×10⁵⁷ GeV⁴, and the energy scale is around V₀ ^1/4 ~ 10¹⁵ GeV. We find that the inflationary parameters (n _s , r, and dn _s /d(ln k) depend only on the number of e-folds N. The compatibility of these parameters with the last Planck measurements is realized with large values of N.     

Novel steganographic method based on generalized <Emphasis Type="Italic">K</Emphasis>-distance <Emphasis Type="Italic">N</Emphasis>-dimensional pixel matching

In this paper, a steganographic scheme adopting the concept of the generalized K _d -distance N-dimensional pixel matching is proposed. The generalized pixel matching embeds a B-ary digit (B is a function of K and N) into a cover vector of length N, where the order-d Minkowski distance-measured embedding distortion is no larger than K. In contrast to other pixel matching-based schemes, a N-dimensional reference table is used. By choosing d, K, and N adaptively, an embedding strategy which is suitable for arbitrary relative capacity can be developed. Additionally, an optimization algorithm, namely successive iteration algorithm (SIA), is proposed to optimize the codeword assignment in the reference table. Benefited from the high dimensional embedding and the optimization algorithm, nearly maximal embedding efficiency is achieved. Compared with other content-free steganographic schemes, the proposed scheme provides better image quality and statistical security. Moreover, the proposed scheme performs comparable to state-of-the-art content-based approaches after combining with image models.     

The bounded core for games with restricted cooperation

A game with restricted (incomplete) cooperation is a triple (N, v, Ω), where N represents a finite set of players, Ω ? 2^N is a set of feasible coalitions such that N ∈ Ω, and v: Ω → R denotes a characteristic function. Unlike the classical TU games, the core of a game with restricted cooperation can be unbounded. Recently Grabisch and Sudhölter [9] proposed a new solution concept—the bounded core—that associates a game (N, v,Ω) with the union of all bounded faces of the core. The bounded core can be empty even if the core is nonempty. This paper gives two axiomatizations of the bounded core. The first axiomatization characterizes the bounded core for the class G^r of all games with restricted cooperation, whereas the second one for the subclass G_bc^r ? G^r of the games with nonempty bounded cores.