The computational hardness of factoring integers is the most established assumption on which cryptographic primitives are based. This work presents an efficient construction of pseudo-random functions whose security i...
详细信息
The computational hardness of factoring integers is the most established assumption on which cryptographic primitives are based. This work presents an efficient construction of pseudo-random functions whose security is based on the intractability of factoring. In particular, we are able to construct efficient length-preserving pseudo random functions, where each evaluation requires only a ( small) constant number of modular multiplications per output bit. This is substantially more efficient than any previous construction of pseudo random functions based on factoring and matches ( up to a constant factor) the efficiency of the best-known factoring-based pseudo-random bit generators.
Primality generation is the cornerstone of several essential cryptographic systems. The problem has been a subject of deep investigations, but there is still a substantial room for improvements. Typically, the algorit...
详细信息
Primality generation is the cornerstone of several essential cryptographic systems. The problem has been a subject of deep investigations, but there is still a substantial room for improvements. Typically, the algorithms used have two parts - trial divisions aimed at eliminating numbers with small prime factors and primality tests based on an easy-to-compute statement that is valid for primes and invalid for composites. In this paper, we will showcase a technique that will eliminate the first phase of the primality testing algorithms. The computational simulations show a reduction of the primality generation time by about 30 percent in the case of 1024-bit RSA key pairs. This can be particularly beneficial in the case of decentralized environments for shared RSA keys as the initial trial division part of the key generation algorithms can be avoided at no cost. This also significantly reduces the communication complexity. Another essential contribution of the paper is the introduction of a new one-way function that is computationally simpler than the existing ones used in public-key cryptography. This function can be used to create new random number generators, and it also could be potentially used for designing entirely new public-key encryption systems.
作者：
Yan, SYAston Univ
Sch Engn & Appl Sci Birmingham B4 7ET W Midlands England
The integer factorization problem (IFP), the finite field discrete logarithm problem (DLP) and the elliptic curve discrete logarithm problem (ECDLP) are essentially the only three mathematical problems that the practi...
详细信息
The integer factorization problem (IFP), the finite field discrete logarithm problem (DLP) and the elliptic curve discrete logarithm problem (ECDLP) are essentially the only three mathematical problems that the practical public-key cryptographic systems are based on. For example, the most famous RSA cryptosystem is based on IFP, the US government's Digital Signature Standard, DSS, is based on DLP, whereas the ECC (Elliptic Curve Cryptography) and Elliptic Curve Digital Signature Algorithm (ECDSA) are based on ECDLP. The security of such cryptographic systems relies on the computational intractability of these three mathematical problems. In this paper, we shall present a survey of various methods for solving the IFP/DLP and particularly the ECDLP problems. More specifically, we shall first discuss how the index calculus as well as quantum algorithms can be used to solve IFP/DLP. Then we shall show why the index calculus cannot be used to solve ECDLP. Finally, we shall introduce a new method, xedni calculus , due to Joseph Silverman, for attack ECDLP;some open problems and new research directions, will also be addressed.
A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ(2) where P is a prime sufficiently smaller than Q. The result is of interest to cryptog...
详细信息
A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ(2) where P is a prime sufficiently smaller than Q. The result is of interest to cryptographers, since integers with secret factorization of this form are being used in digital signatures. The algorithm makes use of what we call ''Jacobi signatures''. We believe these to be of independent interest.
We present rapidly converging series for the Khintchine constant and for general ''Khintchine means'' of continued. fractions, We show that each of these constants can be cast in terms of an efficient ...
详细信息
We present rapidly converging series for the Khintchine constant and for general ''Khintchine means'' of continued. fractions, We show that each of these constants can be cast in terms of an efficient free-parameter series, each series involving values of the Riemann zeta function, rationals, and logarithms of rationals. We provide an alternative, polylogarithm series for the Khintchine constant and indicate means to accelerate such series. We discuss properties of some explicit continued fractions, constructing specific fractions that have limiting geometric mean equal to the Khintchine constant. We report numerical evaluations of such special numbers and of various Khintchine means. In particular, we used an optimized series and a collection of fast algorithms to evaluate the Khintchine constant to more than 7000 decimal places.
This paper deals with two different asymptotically fast algorithms for the computation of ideal sums in quadratic orders. If the class number of the quadratic number field is equal to 1, these algorithms can be used t...
详细信息
This paper deals with two different asymptotically fast algorithms for the computation of ideal sums in quadratic orders. If the class number of the quadratic number field is equal to 1, these algorithms can be used to calculate the GCD in the quadratic order. We show that the calculation of an ideal sum in a fixed quadratic order can be done as fast as in Z up to a constant factor, i.e., in O(mu(n) log n), where n bounds the size of the operands and mu(n) denotes an upper bound for the multiplication time of n-bit integers. Using Schonhage-Strassen's asymptotically fast multiplication for n-bit integers, we achieve mu(n) = O(n log n log log n).
Given a multiplicative group of nonzero rational numbers and a positive integer m, we consider the problem of determining the density of the set of primes p for which the order of the reduction modulo p of the group i...
详细信息
Given a multiplicative group of nonzero rational numbers and a positive integer m, we consider the problem of determining the density of the set of primes p for which the order of the reduction modulo p of the group is divisible by m. In the case when the group is finitely generated the density is explicitly computed. Some examples of groups with infinite rank are considered.
Two integral structures on the Q-vector space of modular forms of weight two on X-0(N) are compared at primes p dividing N at most once. When p = 2 and N is divisible by a prime that is 3 mod 4, this comparison leads ...
详细信息
Two integral structures on the Q-vector space of modular forms of weight two on X-0(N) are compared at primes p dividing N at most once. When p = 2 and N is divisible by a prime that is 3 mod 4, this comparison leads to an algorithm for computing the space of weight one forms mod 2 on X-0(N/2). For p arbitrary and N > 4 prime to p, a way to compute the Hecke algebra of mod p modular forms of weight one on Gamma(1)(N) is presented, using forms of weight p, and, for p = 2, parabolic group cohomology with mod 2 coefficients. Appendix A is a letter of October 1987 from Mestre to Serre in which he reports on computations of weight one forms mod 2 of prime level. Appendix B, by Wiese, reports on an implementation for p = 2 in Magma, using Stein's modular symbols package, with which Mestre's computations are redone and slightly extended.
We give an effective algorithm to determine the endomorphism ring of a Drinfeld module, both over its field of definition and over a separable or algebraic closure thereof. Using previous results we deduce an effectiv...
详细信息
We give an effective algorithm to determine the endomorphism ring of a Drinfeld module, both over its field of definition and over a separable or algebraic closure thereof. Using previous results we deduce an effective description of the image of the adelic Galois representation associated to the Drinfeld module, up to commensurability. We also give an effective algorithm to decide whether two Drinfeld modules are isogenous, again both over their field of definition and over a separable or algebraic closure thereof. Questions of efficiency are left completely out of consideration. (c) 2021 Published by Elsevier Inc.
Based on the general strategy described by Borel and Serre and the Voronoi algorithm for computing unit groups of orders we present an algorithm for finding presentations of S-unit groups of orders. The algorithm is t...
详细信息
Based on the general strategy described by Borel and Serre and the Voronoi algorithm for computing unit groups of orders we present an algorithm for finding presentations of S-unit groups of orders. The algorithm is then used for some investigations concerning the congruence subgroup property.
暂无评论