Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

A Conjecture on Primes in Arithmetic Progressions and Geometric Intervals Barthel, Jim Jean-Pierre ; Müller, Volker in American Mathematical Monthly (2022), 129(10), 979-983 Dirichlet’s theorem on primes in arithmetic progressions states that for any positive integer q and any coprime integer a, there are infinitely many primes in the arithmetic progression a + nq (n ∈ N ... [more ▼] Dirichlet’s theorem on primes in arithmetic progressions states that for any positive integer q and any coprime integer a, there are infinitely many primes in the arithmetic progression a + nq (n ∈ N). Unfortunately, the theorem does not predict the gap between those primes. Several renowned open questions such as the size of Linnik’s constant try to say more about the distribution of such primes. This manuscript postulates a weak, but explicit, generalization of Linnik’s theorem, namely that each geometric interval [q^t, q^(t+1)] contains a prime from each coprime congruence class modulo q ∈ N≥2. Subsequently, it proves the conjecture theoretically for all sufficiently large t, as well as computationally for all sufficiently small q. Finally, the impact of this conjecture on a result of Pomerance related to Carmichael’s conjecture is outlined. [less ▲] Detailed reference viewed: 23 (0 UL)On the (M)iNTRU assumption in the integer case Barthel, Jim Jean-Pierre ; Müller, Volker ; Rosie, Razvan in Qiong, Huang; Yu, Yu (Eds.) Provable and Practical Security, 15th International Conference, ProvSec 2021, Guangzhou, November 5 – November 8, 2021, Proceedings (2021, November 02) In AsiaCrypt 2019, Genise, Gentry, Halevi, Li and Micciancio put forth two novel and intriguing computational hardness hypotheses: The inhomogeneous NTRU (iNTRU) assumption and its matrix version MiNTRU ... [more ▼] In AsiaCrypt 2019, Genise, Gentry, Halevi, Li and Micciancio put forth two novel and intriguing computational hardness hypotheses: The inhomogeneous NTRU (iNTRU) assumption and its matrix version MiNTRU. In this work, we break the integer case of the iNTRU assumption through elementary lattice reduction, and we describe how the attack might be generalized to polynomial rings and to the low dimensional MiNTRU assumption with small noise. [less ▲] Detailed reference viewed: 191 (14 UL)Twisted Edwards-Form Elliptic Curve Cryptography for 8-bit AVR-based Sensor Nodes ; Groszschädl, Johann ; Liu, Zhe et al in Chen, Kefei; Xie, Qi; Qiu, Weidong (Eds.) et al Proceedings of the first ACM Workshop on Asia Public-Key Cryptography (ASIAPKC 2013) (2013, May) Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress ... [more ▼] Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply with the severe resource constraints of 8-bit sensor nodes such as the MICAz and IRIS motes. Our ECC software uses Optimal Prime Fields (OPFs) as underlying algebraic structure and supports two different families of elliptic curves, namely Weierstraß-form and twisted Edwards-form curves. Due to the combination of efficient field arithmetic and fast group operations, we achieve an execution time of 5.8*10^6 clock cycles for a full 158-bit scalar multiplication on an 8-bit ATmega128 microcontroller, which is 2.78 times faster than the widely-used TinyECC library. Our implementation also shows that the energy cost of scalar multiplication on a MICAz (or IRIS) mote amounts to just 19 mJ when using a twisted Edwards curve over a 160-bit OPF. This result compares fairly well with the energy figures of two recently-presented hardware designs of ECC based on twisted Edwards curves. [less ▲] Detailed reference viewed: 380 (44 UL)A Short Note on Secret Sharing Using Elliptic Curves Müller, Volker in Proceedings of SECRYPT 2008 (2008) In this short note, we describe a variant of Shamir's (n, t)-threshold scheme based on elliptic curves. Moreover, we show how pairings of elliptic curves can be used to also provide verifiability for the ... [more ▼] In this short note, we describe a variant of Shamir's (n, t)-threshold scheme based on elliptic curves. Moreover, we show how pairings of elliptic curves can be used to also provide verifiability for the new elliptic curve based threshold scheme. [less ▲] Detailed reference viewed: 287 (5 UL)Finding the Eigenvalue in Elkies' Algorithm Müller, Volker ; in Experimental Mathematics (2001), 10(2), 275-285 One important part of Elkies' algorithm for computing the group order of an elliptic curve is the search for an eigenvalue of the Frobenius endomorphism. In this paper we compare two well known algorithms ... [more ▼] One important part of Elkies' algorithm for computing the group order of an elliptic curve is the search for an eigenvalue of the Frobenius endomorphism. In this paper we compare two well known algorithms with two new ideas based on the Babystep Giantstep method. Moreover we show how resultants can be used to speed up this search. Finally we present a fast probabilistic algorithm for checking whether a given rational function is congruent to an entry in a table of rational functions modulo some fixed polynomial. [less ▲] Detailed reference viewed: 130 (3 UL)Sekilas tentang Keamanan di Jaringan Komputer Müller, Volker in Sintesis - Makalah Universitas Kristen Indonesia (2001) Detailed reference viewed: 152 (8 UL)Efficient Point Multiplication for Elliptic Curves over Special Optimal Extension Fields Müller, Volker in Proceedings of Public-Key Cryptography and Computational Number Theory Conference (2000) I generalize an idea of Gallant, Lambert, Vanstone for fast multiplication of points on elliptic curves with efficient endomorphisms. I describe how this generalization improves point multiplication for ... [more ▼] I generalize an idea of Gallant, Lambert, Vanstone for fast multiplication of points on elliptic curves with efficient endomorphisms. I describe how this generalization improves point multiplication for elliptic curves defined over optimal extension fields. Finally we present practical results for the new algorithm compared to Gallant's algorithm. [less ▲] Detailed reference viewed: 129 (2 UL)Differential Fault Attacks on Elliptic Curve Cryptosystems Biehl, Ingrid ; ; Müller, Volker in Proceedings of Crypto 2000 (2000) In this paper we extend the ideas for differential fault attacks on the RSA cryptosystem to cryptosystems using elliptic curves. We present three different types of attacks that can be used to derive ... [more ▼] In this paper we extend the ideas for differential fault attacks on the RSA cryptosystem to cryptosystems using elliptic curves. We present three different types of attacks that can be used to derive information about the secret key if bit errors can be inserted into the elliptic curve computations done in a tamper-proof device. The effectiveness of the attacks was proven in a software simulation of the described ideas. [less ▲] Detailed reference viewed: 147 (1 UL)A Few Remarks on the Security of Internet Applications Müller, Volker in Proceedings of he First International Workshop on Information Integration and Web-based Applications & Services (1999) In this short publication, I present a few facts on the security of some current Internet applications. Since one strong focus of this conference was the usage of the Internet for electronic business ... [more ▼] In this short publication, I present a few facts on the security of some current Internet applications. Since one strong focus of this conference was the usage of the Internet for electronic business applications, I address two applications often used in electronic business: electronic mail (E-mail) and secure access of web pages using the SSL protocol. It should be noted that all the facts presented in the note are well-known to security experts and not new. It might however be helpful for the ordinary of electronic commerce to become more aware of some security-related problems of the Internet. [less ▲] Detailed reference viewed: 65 (1 UL)Computing Discrete Logarithms in Real Quadratic Congruence Function Fields of Large Genus Müller, Volker ; ; in Mathematics of Computation (1999), 68(226), 807-822 We present a sub-exponential algorithm for computing discrete logarithms in real quadratic congruence function fields of sufficiently large genus. We prove the correctness and the expected running time ... [more ▼] We present a sub-exponential algorithm for computing discrete logarithms in real quadratic congruence function fields of sufficiently large genus. We prove the correctness and the expected running time of the algorithm. The algorithm is a generalization of a similar algorithm for quadratic number fields. [less ▲] Detailed reference viewed: 114 (0 UL)Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two Müller, Volker in Journal of Cryptology (1998), 11(4), 219-234 The paper shows how Frobenius expansions can be used to speed up multiplication of points on elliptic curves that are defined over very small fields of characteristic two. The Frobenius expansion ... [more ▼] The paper shows how Frobenius expansions can be used to speed up multiplication of points on elliptic curves that are defined over very small fields of characteristic two. The Frobenius expansion algorithm is analyzed in theory and in practice. It can gain significant improvements in practical applications. These curves are therefore especially interesting for implementations of elliptic curve cryptosystems. [less ▲] Detailed reference viewed: 156 (2 UL)Discrete Logarithm Based Cryptosystems in Quadratic Function Fields of Characteristic 2 Müller, Volker ; ; in Designs, Codes and Cryptography (1998), 14(2), 159-178 We describe a public key cryptosystem which works in quadratic function fields of characteristic two. Formulas for arithmetic are explicitly given. The security of the system is based on the discrete ... [more ▼] We describe a public key cryptosystem which works in quadratic function fields of characteristic two. Formulas for arithmetic are explicitly given. The security of the system is based on the discrete logarithm problem in these fields. Therefore we also describe a Discrete Logarithm algorithm based on the ideas of Pohlig and Hellman, especially adopted to quadratic function fields of characteristic two. [less ▲] Detailed reference viewed: 73 (3 UL)A Public Key Cryptosystem based on Elliptic Curves over Z/nZ Equivalent to Factoring Biehl, Ingrid ; ; Müller, Volker in Advances in Cryptology - Eurocrypt '96 (1996) The paper describes a new cryptosystem for elliptic curves over the ring Z/nZ which is equivalent to the Rabin-Williams cryptosystem. We prove that breaking the new cryptosystem is equivalent to factoring ... [more ▼] The paper describes a new cryptosystem for elliptic curves over the ring Z/nZ which is equivalent to the Rabin-Williams cryptosystem. We prove that breaking the new cryptosystem is equivalent to factoring the modulus n. [less ▲] Detailed reference viewed: 73 (1 UL)On the Reduction of Composed Relations from the Number Field Sieve ; Müller, Volker in Proceedings of the 2nd Algorithmic Number Theory Symposium (ANTS II) (1996) A very important step in the number field sieve for computing discrete logarithms in finite fields is the combination of so called relations. These combinations are used in the final linear algebra ... [more ▼] A very important step in the number field sieve for computing discrete logarithms in finite fields is the combination of so called relations. These combinations are used in the final linear algebra step to find the discrete logarithm. From a practical point of view, it is highly desirable to find combinations with as few as possible non zero entries, since this property speeds up the linear algebra part. In this paper we present a new algorithm for computing combinations which shows significant improvements in practice to existing other algorithms. [less ▲] Detailed reference viewed: 239 (1 UL)Counting the Number of Points on Elliptic Curves over Finite Fields of Characteristic Greater than Three ; ; Müller, Volker et al in Proceedings of Algorithmic Number Theory Symposium I, Lecture Notes in Computer Science (1994) The paper describes the implementation of the Algorithm of Atkin and Elkies for computing the group order of elliptic curves over large prime fields. The focus of the paper lays on algorithmical aspects ... [more ▼] The paper describes the implementation of the Algorithm of Atkin and Elkies for computing the group order of elliptic curves over large prime fields. The focus of the paper lays on algorithmical aspects of the Atkin/Elkies algorithm. Practical data and running times are given. [less ▲] Detailed reference viewed: 115 (2 UL)Computing the number of points of elliptic curves over finite fields ; Müller, Volker in Computing the number of points of elliptic curves over finite fields (1991) In this paper we report on our implementation of a combination of the Babystep-Giantstep Algorithm and the Algorithm of Schoof for computing group orders of elliptic curves over finite fields. This paper ... [more ▼] In this paper we report on our implementation of a combination of the Babystep-Giantstep Algorithm and the Algorithm of Schoof for computing group orders of elliptic curves over finite fields. This paper is a summary of the results in my Master Thesis. [less ▲] Detailed reference viewed: 135 (4 UL)On basis vectors of lattices Barthel, Jim Jean-Pierre ; Müller, Volker E-print/Working paper (n.d.) Integer lattices enjoy increasing interest among mathematicians and cryptographers. However, there are still many elementary open questions, like finding specific vectors or particular bases of a given ... [more ▼] Integer lattices enjoy increasing interest among mathematicians and cryptographers. However, there are still many elementary open questions, like finding specific vectors or particular bases of a given lattice. Our study consists in exhibiting which integer vectors may be chosen as basis vectors of a chosen lattice. The compelling part of our development is that this condition is obtained through an unusual application of Dirichlet's Theorem on primes in arithmetic progressions and that it has a surprising consequence for vectors achieving the successive minima. [less ▲] Detailed reference viewed: 46 (3 UL)ON THE (NON-)EQUIVALENCE OF INTEGRAL BINARY QUADRATIC FORMS AND THEIR NEGATIVE FORMS Barthel, Jim Jean-Pierre ; Müller, Volker E-print/Working paper (n.d.) Integral binary quadratic forms have been extensively studied in order to compute the class number of real and complex quadratic ﬁelds. Many studies restricted the equivalence class of quadratic forms or ... [more ▼] Integral binary quadratic forms have been extensively studied in order to compute the class number of real and complex quadratic ﬁelds. Many studies restricted the equivalence class of quadratic forms or identiﬁed speciﬁc forms in order to compute the class number through enumeration of equivalence classes. One often used assumption is that a given form and its negative are equivalent or are synthetically identiﬁed. This document presents a concise Lagrangian approach to integral binary quadratic forms, outlines the equivalence classes in its broadest sense and uses it to develop a general condition when a given integral binary quadratic form and its negative are equivalent. Then, the existence of integral binary quadratic forms which are non-equivalent to their negatives is proven and an elementary algorithm to determine the (non-)equivalence of a given form and its negative is outlined. [less ▲] Detailed reference viewed: 94 (6 UL)A conjecture on primes in arithmetic progressions and geometric intervals Barthel, Jim Jean-Pierre ; Müller, Volker E-print/Working paper (n.d.) We conjecture that any interval of the form [q^t ,q^(t+1) ], where q≥ 2 and t≥1 denote positive integers, contains at least one prime from each coprime congruence class. We prove this conjecture first ... [more ▼] We conjecture that any interval of the form [q^t ,q^(t+1) ], where q≥ 2 and t≥1 denote positive integers, contains at least one prime from each coprime congruence class. We prove this conjecture first unconditionally for all 2≤q≤45000 and all t≥1 and second under ERH for almost all q≥2 and all t≥2. Furthermore, we outline heuristic arguments for the validity of the conjecture beyond the proven bounds and we compare it with related long-standing conjectures. Finally, we discuss some of its consequences. [less ▲] Detailed reference viewed: 53 (9 UL) |
||