To see the other types of publications on this topic, follow the link: Discrete logarithm problem (DLP).
Dissertations / Theses on the topic 'Discrete logarithm problem (DLP)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 35 dissertations / theses for your research on the topic 'Discrete logarithm problem (DLP).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
McCulloch, Catherine Margaret. "Discrete logarithm problem over finite prime fields." Thesis, Queensland University of Technology, 1998. https://eprints.qut.edu.au/36976/1/36976_McCulloch_1988.pdf.
Full textAbstract:
Difficulty in solving the discrete logarithm problem has led to its use in key exchange, public key cryptography and digital signatures. To measure the security of these algorithms, it is necessary to evaluate the methods currently available for attack. Although the applications of the discrete logarithm problem can be implemented in a variety of different groups, only implementations over multiplicative integers modulo a large prime p are considered. The object of this work is to review the current methods of solving the discrete logarithm
problem - key exhaustion, Shanks' baby-step giant-step algorithm, Pollard's rho algorithm, the Silver Pohlig Hellman algorithm, index calculus methods and the general number field sieve. The resulting document contains all relevant mathematics, theorems and algorithms. As only
one workstation is used, the problem will not be solved for large primes, but an indication of the relative strengths and weaknesses of each algorithm will be gained. Both the theoretical and practical issues were considered when comparing the attacks available.
The algorithms were implemented using the computer algebra system "Magma", which was developed at the University of Sydney. Magma was chosen as it is a flexible package that is not restricted to group theory. The source code is included in Appendix B.
The simplest methods to implement are key exhaustion, which relies on testing all possibilities,
and the first improvement on this method - Shank's baby-step giant-step algorithm. Both methods are infeasible when the prime number is large. Pollard's rho algorithm, again impractical for large p, has the same expected running time as Shank's baby-step giant-step algorithm, but the storage requirements are negligible. The Silver Pohlig Hellman algorithm which is again impractical for a large p unless p-1 has small factors is also covered.
Index calculus methods offer improvements in the time involved to attack the system, once the prime number becomes too large for the earlier methods. Unlike the previous algorithms, the index calculus methods are not generic, they can only be used for particular groups, one of which is the field GF(p ), considered here. The methods involve two parts, a costly precomputation
stage that needs to be performed only once for each prime, and the calculation of the individual
logarithm. Three methods are investigated - the first by McCurley, the second by Coppersmith, Odlyzko and Schroeppel, and the third by LaMacchia and Odlyzko. By attacking with these methods, primes with fewer than 200 bits are insecure and primes with less than 512 bits should be avoided. By adapting the general number field sieve to solve logarithms, the running time of the attack in some instances can be further improved. Unlike the index calculus methods, the time required for the precomputation and that required for the evaluation of the individual logarithm, are similar. This perhaps reduces the usefulness of the algorithm in the case where the same attack is to be implemented a number of times to determine several different logarithms. If the same prime is to be used for a number of attacks, it may be quicker to use an index calculus method as the precomputation is performed once and then the logarithms can be quickly
calculated.
2
Al, Aswad Haetham. "The Discrete Logarithm Problem in Finite Fields with Extensions." Electronic Thesis or Diss., Université de Lorraine, 2024. http://www.theses.fr/2024LORR0192.
Full textAbstract:
Cette thèse étudie le problème du logarithme discret dans les corps finis, l'un des deux problèmes de théorie des nombres aux fondations de la cryptographie à clef publique utilisée de nos jours. En particulier, nous proposons plusieurs algorithmes pour la résolution de ce problème dans le cas des corps finis non premiers, c'est-à-dire de la forme F_{p}^n avec p la caractéristique et n le degré d'extension tel que n > 1. Ces algorithmes mobilisent un large ensemble de techniques et d'outils provenant de la théorie des nombres algorithmiques, et s'inscrivent dans une recherche de pointe de longue date : le crible par corps de nombre (NFS), squelette sur lequel se basent tous ces algorithmes ayant déjà plus d'une trentaine d'années. Les contributions de cette thèse se déclinent en trois volets. Le premier volet examine l'étape finale de NFS - et de ses variantes - lorsqu'il est appliqué à des corps finis avec n composé. En exploitant des sous-corps d'un corps de nombres, NFS construit un réseau dans lequel tous les éléments partagent une propriété commune. Une réduction de réseaux par LLL ou BKZ permet de retrouver un élément de petite norme L2 qui entraîne une petite norme algébrique. La contributation apportée à cette étape consiste à considérer certains sous-réseaux bien choisis qui permettent de chercher des éléments d'un degré inférieur au coût d'une norme L2 légèrement plus grande. Ce compromis fournit des éléments avec des normes algébriques plus petites pour diverses familles de corps de nombres. De plus, nous démontrons de nouvelles complexité asymptotique pour cette étape de NFS apportées par l'utilisation de certains algorithmes de réduction de réseaux (BKZ au lieu de LLL). Ce travail est publié en collaboration avec Cécile Pierrot dans le journal Designs, Codes and Cryptography. Le second volet modifie la structure de l'algorithme NFS tout entier. Nous élargissons le concept de Factoring Factory, initialement introduit pour la factorisation et les corps premiers uniquement. Nous y explorons la stratégie pour attaquer simultanément plusieurs corps finis de taille comparable mais de même n. Une phase de prétraitement dépendant uniquement de la taille et de n permet un calcul efficace des logarithmes discrets dans une certaine proportion de corps finis. Dans le cadre de plusieurs corps cibles, cette méthode offre de nouvelles complexités asymptotiques record pour NFS et la plupart de ses variantes. Cet article est publié en collaboration avec Cécile PIERROT et Emmanuel Thomé dans le journal IACR Communications in Cryptology. Enfin, le troisième volet se concentre sur une variante prometteuse de NFS, la variante dite Tower. Nous proposons d'accélerer l'algorithme TNFS avec des automorphismes Galoisiens. Les deux étapes les plus coûteuses de TNFS sont la collecte des relations et l'algèbre linéaire. Il est connu qu'un tel automorphisme d'ordre k---lié au corps fini cible---permet une accélération d'ordre k de la collecte de relations. Faisant suite à un premier résultat extérieur de 2021, qui permettait d'accélérer l'étape d'algèbre linéaire également, lorsque k = 2, nous étudions ici le résultat pour des ordres supérieurs, à savoir 6 et 12. Nous obtenons une nouvelle construction et atteint des facteurs d'accélérations pour cette lourde étape de l'ordre de 36 (pour k = 6) et 144 (pour k = 12). Ce travail donne lieu à un article en cours rédaction<br>This thesis studies the discrete logarithm problem in finite fields, one of the two number-theoretic problems at the foundation of public-key cryptography used today. In particular, we propose several algorithms for solving this problem in the case of non-prime finite fields, i.e. of the form F_{p}^n with p the characteristic and n the degree of extension such that n > 1. These algorithms mobilize a wide range of techniques and tools drawn from algorithmic number theory, and are part of a long-standing cutting-edge research project research: the number field sieve (NFS), the backbone on which all these algorithms are based. The contributions of this thesis are divided into three parts. The first examines the final stage of NFS - and its variants - when applied to finite fields with compoosite n. By exploiting sufields of a number field, NFS builts a lattice in which all elements share a common property. A lattice reduction by LLL or BKZ leads to an element of small norm L2 which leads to a small algebraic norm. The contribution made at this stage is to consider certain well-chosen sub-lattices that allow us to search for elements of smaller degree at the cost of a slightly larger L2 norm. This compromise provides elements with smaller algebraic norms for various families of number fields. In addition, we demonstrate new asymptotic complexities for this NFS step brought by the use of certain lattice reduction algorithms (BKZ instead of LLL). This work is published in collaboration with Cécile Pierrot in the journal Designs, Codes and Cryptography. The second part modifies the structure of the entire NFS algorithm. We extend the Factoring Factory concept, originally introduced for factoring and prime fields only. We explore the strategy for simultaneously attacking several finite fields of comparable size but of the same extension degree n. A pre-processing phase dependent only on approximate size and n enables efficient computation of discrete logarithms in a certain proportion of finite fields. In the context of multiple target finite fields, this method offers new record asymptotic complexities for NFS and most of its variants. This article is published in collaboration with Cécile PIERROT and Emmanuel Thomé in the journal IACR Communications in Cryptology. Finally, the third section focuses on a promising NFS variant, the so-called Tower variant. We propose to accelerate the TNFS algorithm with Galois automorphisms. The two most costly steps in TNFS are the relation collection and the linear algebra steps. It is known that such an automorphism of order k---linked to the target finite field---allows k-order acceleration of the relation collection. Following on from a first external result in 2021, which accelerated the linear algebra step too but only when k = 2, we study the result for higher orders, namely 6 and 12. We obtain a new construction and achieve acceleration factors for this heavy step of the order of 36 (for k = 6) and 144 (for k = 12). This is the subject of an article currently being written
3
Zumbrägel, Jens. "The Discrete Logarithm Problem in Finite Fields of Small Characteristic." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-219176.
Full textAbstract:
Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around<br>Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt
4
Falk, Jenny. "On Pollard's rho method for solving the elliptic curve discrete logarithm problem." Thesis, Linnéuniversitetet, Institutionen för matematik (MA), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-85516.
Full textAbstract:
Cryptosystems based on elliptic curves are in wide-spread use, they are considered secure because of the difficulty to solve the elliptic curve discrete logarithm problem. Pollard's rho method is regarded as the best method for attacking the logarithm problem to date, yet it is still not efficient enough to break an elliptic curve cryptosystem. This is because its time complexity is O(√n) and for uses in cryptography the value of n will be very large. The objective of this thesis is to see if there are ways to improve Pollard's rho method. To do this, we study some modifications of the original functions used in the method. We also investigate some different functions proposed by other researchers to see if we can find a version that will improve the performance. From the experiments conducted on these modifications and functions, we can conclude that we get an improvement in the performance for some of them.
5
Garefalakis, Theodoulos. "On the discrete logarithm problem in the finite fields and on elliptic curves." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0030/NQ53692.pdf.
Full text
6
Hitchcock, Yvonne Roslyn. "Elliptic curve cryptography for lightweight applications." Thesis, Queensland University of Technology, 2003. https://eprints.qut.edu.au/15838/1/Yvonne_Hitchcock_Thesis.pdf.
Full textAbstract:
Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980's. They provide public key cryptosystems based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) , which is so called because of its similarity to the discrete logarithm problem (DLP) over the integers modulo a large prime. One benefit of elliptic curve cryptosystems (ECCs) is that they can use a much shorter key length than other public key cryptosystems to provide an equivalent level of security. For example, 160 bit ECCs are believed to provide about the same level of security as 1024 bit RSA. Also, the level of security provided by an ECC increases faster with key size than for integer based discrete logarithm (dl) or RSA cryptosystems. ECCs can also provide a faster implementation than RSA or dl systems, and use less bandwidth and power. These issues can be crucial in lightweight applications such as smart cards. In the last few years, ECCs have been included or proposed for inclusion in internationally recognized standards. Thus elliptic curve cryptography is set to become an integral part of lightweight applications in the immediate future. This thesis presents an analysis of several important issues for ECCs on lightweight devices. It begins with an introduction to elliptic curves and the algorithms required to implement an ECC. It then gives an analysis of the speed, code size and memory usage of various possible implementation options. Enough details are presented to enable an implementer to choose for implementation those algorithms which give the greatest speed whilst conforming to the code size and ram restrictions of a particular lightweight device. Recommendations are made for new functions to be included on coprocessors for lightweight devices to support ECC implementations Another issue of concern for implementers is the side-channel attacks that have recently been proposed. They obtain information about the cryptosystem by measuring side-channel information such as power consumption and processing time and the information is then used to break implementations that have not incorporated appropriate defences. A new method of defence to protect an implementation from the simple power analysis (spa) method of attack is presented in this thesis. It requires 44% fewer additions and 11% more doublings than the commonly recommended defence of performing a point addition in every loop of the binary scalar multiplication algorithm. The algorithm forms a contribution to the current range of possible spa defences which has a good speed but low memory usage. Another topic of paramount importance to ECCs for lightweight applications is whether the security of fixed curves is equivalent to that of random curves. Because of the inability of lightweight devices to generate secure random curves, fixed curves are used in such devices. These curves provide the additional advantage of requiring less bandwidth, code size and processing time. However, it is intuitively obvious that a large precomputation to aid in the breaking of the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve which would be unavailable for a random curve. Therefore, it would appear that fixed curves are less secure than random curves, but quantifying the loss of security is much more difficult. The thesis performs an examination of fixed curve security taking this observation into account, and includes a definition of equivalent security and an analysis of a variation of Pollard's rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. A lower bound on the expected time to solve such ECDLPs using this method is presented, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. It is concluded that adding a total of 11 bits to the size of a fixed curve provides an equivalent level of security compared to random curves. The final part of the thesis deals with proofs of security of key exchange protocols in the Canetti-Krawczyk proof model. This model has been used since it offers the advantage of a modular proof with reusable components. Firstly a password-based authentication mechanism and its security proof are discussed, followed by an analysis of the use of the authentication mechanism in key exchange protocols. The Canetti-Krawczyk model is then used to examine secure tripartite (three party) key exchange protocols. Tripartite key exchange protocols are particularly suited to ECCs because of the availability of bilinear mappings on elliptic curves, which allow more efficient tripartite key exchange protocols.
7
Hitchcock, Yvonne Roslyn. "Elliptic Curve Cryptography for Lightweight Applications." Queensland University of Technology, 2003. http://eprints.qut.edu.au/15838/.
Full textAbstract:
Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980's. They provide public key cryptosystems based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) , which is so called because of its similarity to the discrete logarithm problem (DLP) over the integers modulo a large prime. One benefit of elliptic curve cryptosystems (ECCs) is that they can use a much shorter key length than other public key cryptosystems to provide an equivalent level of security. For example, 160 bit ECCs are believed to provide about the same level of security as 1024 bit RSA. Also, the level of security provided by an ECC increases faster with key size than for integer based discrete logarithm (dl) or RSA cryptosystems. ECCs can also provide a faster implementation than RSA or dl systems, and use less bandwidth and power. These issues can be crucial in lightweight applications such as smart cards. In the last few years, ECCs have been included or proposed for inclusion in internationally recognized standards. Thus elliptic curve cryptography is set to become an integral part of lightweight applications in the immediate future. This thesis presents an analysis of several important issues for ECCs on lightweight devices. It begins with an introduction to elliptic curves and the algorithms required to implement an ECC. It then gives an analysis of the speed, code size and memory usage of various possible implementation options. Enough details are presented to enable an implementer to choose for implementation those algorithms which give the greatest speed whilst conforming to the code size and ram restrictions of a particular lightweight device. Recommendations are made for new functions to be included on coprocessors for lightweight devices to support ECC implementations Another issue of concern for implementers is the side-channel attacks that have recently been proposed. They obtain information about the cryptosystem by measuring side-channel information such as power consumption and processing time and the information is then used to break implementations that have not incorporated appropriate defences. A new method of defence to protect an implementation from the simple power analysis (spa) method of attack is presented in this thesis. It requires 44% fewer additions and 11% more doublings than the commonly recommended defence of performing a point addition in every loop of the binary scalar multiplication algorithm. The algorithm forms a contribution to the current range of possible spa defences which has a good speed but low memory usage. Another topic of paramount importance to ECCs for lightweight applications is whether the security of fixed curves is equivalent to that of random curves. Because of the inability of lightweight devices to generate secure random curves, fixed curves are used in such devices. These curves provide the additional advantage of requiring less bandwidth, code size and processing time. However, it is intuitively obvious that a large precomputation to aid in the breaking of the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve which would be unavailable for a random curve. Therefore, it would appear that fixed curves are less secure than random curves, but quantifying the loss of security is much more difficult. The thesis performs an examination of fixed curve security taking this observation into account, and includes a definition of equivalent security and an analysis of a variation of Pollard's rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. A lower bound on the expected time to solve such ECDLPs using this method is presented, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. It is concluded that adding a total of 11 bits to the size of a fixed curve provides an equivalent level of security compared to random curves. The final part of the thesis deals with proofs of security of key exchange protocols in the Canetti-Krawczyk proof model. This model has been used since it offers the advantage of a modular proof with reusable components. Firstly a password-based authentication mechanism and its security proof are discussed, followed by an analysis of the use of the authentication mechanism in key exchange protocols. The Canetti-Krawczyk model is then used to examine secure tripartite (three party) key exchange protocols. Tripartite key exchange protocols are particularly suited to ECCs because of the availability of bilinear mappings on elliptic curves, which allow more efficient tripartite key exchange protocols.
8
Zumbrägel, Jens [Verfasser], Stefan E. [Gutachter] Schmidt, Gathen Joachim von [Gutachter] Zur, and Elisa [Gutachter] Gorla. "The Discrete Logarithm Problem in Finite Fields of Small Characteristic / Jens Zumbrägel ; Gutachter: Stefan E. Schmidt, Joachim von zur Gathen, Elisa Gorla." Dresden : Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://d-nb.info/1128036649/34.
Full text
9
Zumbrägel, Jens Verfasser], Stefan E. [Gutachter] [Schmidt, Gathen Joachim von [Gutachter] Zur, and Elisa [Gutachter] Gorla. "The Discrete Logarithm Problem in Finite Fields of Small Characteristic / Jens Zumbrägel ; Gutachter: Stefan E. Schmidt, Joachim von zur Gathen, Elisa Gorla." Dresden : Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://d-nb.info/1128036649/34.
Full text
10
Tvaroh, Tomáš. "Analýza útoků na asymetrické kryptosystémy." Master's thesis, Vysoká škola ekonomická v Praze, 2011. http://www.nusl.cz/ntk/nusl-81959.
Full textAbstract:
This thesis analyzes various attacks on underlying computational problem of asymmetric cryptosystems. First part introduces two of the most used problems asymmetric cryptography is based on, which are integer factorization and computation of discrete logarithm. Algorithms for solving these problems are described and for each of them there is a discussion about when the use of this particular algorithm is appropriate and when it isn't. In the next part computational problems are related to algorithms RSA and ECC and it is shown, how solving the underlying problem enables us to crack the cypher. As a part of this thesis an application was developed that measures the efficiency of described attacks and by providing easy-to-understand enumeration of algorithm's steps it can be used to demonstrate how the attack works. Based on the results of performed analysis, most secure asymmetric cryptosystem is selected along with some recommendations regarding key pair generation.
11
Lopez, Samuel. "MODERN CRYPTOGRAPHY." CSUSB ScholarWorks, 2018. https://scholarworks.lib.csusb.edu/etd/729.
Full textAbstract:
We live in an age where we willingly provide our social security number, credit card information, home address and countless other sensitive information over the Internet. Whether you are buying a phone case from Amazon, sending in an on-line job application, or logging into your on-line bank account, you trust that the sensitive data you enter is secure. As our technology and computing power become more sophisticated, so do the tools used by potential hackers to our information. In this paper, the underlying mathematics within ciphers will be looked at to understand the security of modern ciphers.
An extremely important algorithm in today's practice is the Advanced Encryption Standard (AES), which is used by our very own National Security Agency (NSA) for data up to TOP SECRET. Another frequently used cipher is the RSA cryptosystem. Its security is based on the concept of prime factorization, and the fact that it is a hard problem to prime factorize huge numbers, numbers on the scale of 2^{2048} or larger. Cryptanalysis, the study of breaking ciphers, will also be studied in this paper. Understanding effective attacks leads to understanding the construction of these very secure ciphers.
12
Taufer, Daniele. "Elliptic Loops." Doctoral thesis, Università degli studi di Trento, 2020. http://hdl.handle.net/11572/265846.
Full textAbstract:
Given an elliptic curve E over Fp and an integer e ≥ 1, we define a new object, called “elliptic loop”, as the set of plane projective points over Z/p^e Z lying over E, endowed with an operation inherited by the curve addition. This object is proved to be a power-associative abelian algebraic loop. Its substructures are investigated by means of other algebraic cubics defined over the same ring, which we named “shadow curve” and “layers”. When E has trace 1, a distinctive behavior is detected and employed for producing an isomorphism attack to the discrete logarithm on this family of curves. Stronger properties are derived for small values of e, which lead to an explicit description of the infinity part and to characterizing the geometry of rational |E|-torsion points.<br>Data una curva ellittica E su Fp ed un intero e ≥ 1, definiamo un nuovo oggetto, chiamato "loop ellittico", come l'insieme dei punti nel piano proiettivo su Z/p^e Z che stanno sopra ad E, dotato di una operazione ereditata dalla somma di punti sulla curva. Questo oggetto si prova essere un loop algebrico con associatività delle potenze. Le sue sotto-strutture sono investigate utilizzando altre cubiche definite sullo stesso anello, che abbiamo chiamato "curva ombra" e "strati". Quando E ha traccia 1, un comportamento speciale viene notato e sfruttato per produrre un attacco di isomorfismo al problema del logaritmo discreto su questa famiglia di curve. Migliori proprietà vengono trovate per bassi valori di e, che portano ad una descrizione esplicita della parte all'infinito e alla caratterizzazione della geometria dei punti razionali di |E|-torsione.
13
Alexander, Nicholas Charles. "Algebraic Tori in Cryptography." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1154.
Full textAbstract:
Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues. The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03]. They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem. This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP<sup>+</sup>05] that require even less bandwidth. In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented. Finally, we list some open research problems.
14
Colledan, Andrea. "On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16112/.
Full textAbstract:
Quantum computing has opened the way to new algorithms that can efficiently solve problems that have always been deemed intractable. However, since quantum algorithms are hard to design, the necessity to find a generalization of these problems arises. Such necessity is satisfied by the hidden subgroup problem (HSP), an abstract problem of group theory which successfully generalizes a large number of intractable problems. The HSP plays a significant role in quantum complexity theory, as efficient algorithms that solve it can be employed to efficiently solve other valuable problems, such as integer factorization, discrete logarithms, graph isomorphism and many others.
In this thesis we give a computational definition of the HSP. We then prove the reducibility of some of the aforementioned problems to the HSP. Lastly, we introduce some essential notions of quantum computing and we present two quantum algorithms that efficiently solve the HSP on Abelian groups.
15
Wilcox, Nicholas. "A Computational Introduction to Elliptic and Hyperelliptic Curve Cryptography." Oberlin College Honors Theses / OhioLINK, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1528649455201473.
Full text
16
Pönisch, Jens. "Kryptoggraphie mit elliptischen Kurven." Universitätsbibliothek Chemnitz, 2014. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-156488.
Full text
17
Kouchaki, Barzi Behnaz. "Points of High Order on Elliptic Curves : ECDSA." Thesis, Linnéuniversitetet, Institutionen för matematik (MA), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-58449.
Full textAbstract:
This master thesis is about Elliptic Curve Digital Signature Algorithm or ECDSA and two of the known attacks on this security system. The purpose of this thesis is to find points that are likely to be points of high order on an elliptic curve. If we have a point P of high order and if Q = mP, then we have a large set of possible values of m. Therefore it is hard to solve the Elliptic Curve Discrete Logarithm Problem or ECDLP. We have investigated on the time of finding the solution of ECDLP for a certain amount of elliptic curves based on the order of the point which is used to create the digital signatures by those elliptic curves. Method: Algebraic Structure of elliptic curves over finite fields and Discrete logarithms. This has been done by two types of attacks namely Baby Step, Giant Step and Pollard’s Rho and all of the programming parts has been done by means of Mathematica. Conclusion: We have come into a conclusion of having the probable good points which are the points of high order on elliptic curves through the mentioned attacks in which solving the ECDLP is harder if these points have been used in generating the digital signature. These probable good points can be estimated by means of a function we have come up with. The input of this function is the order of the point and the output is the time of finding the answer of ECDLP.
18
Kříž, Jiří. "Softwarová podpora výuky kryptosystémů založených na problému diskrétního logaritmu." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2009. http://www.nusl.cz/ntk/nusl-218163.
Full textAbstract:
Current needs of human communication came to status, when most of transferred messages are considered as private and transition over non-secured communication lines in open form is not possible. That originated a lot of different methods for securing of messages and transfers in ciphered form. Two mainstreams were established, symmetric cryptography and asymmetric cryptography. Second of mentioned groups is based on usage of two information – keys, when one of then is broadly known and is public and second, well protected and private. Using a public key it is possible to establish a cryptogram of message, but for deciphering it is necessary to know private key. Asymmetric methods are based on mathematical problems, for which there is not an effective computing algorithm. This thesis are focused for asymmetric cryptosystems based on discrete logarithm problem, where ciphering of message using public key is very easy and quick, but deciphering without knowledge of private key is extremely time consuming process. Work describes a mathematical base of discrete logarithm problem, its’ properties and methods developed for solving of this problem. Descriptions of particular cryptosystems are given, i.e. ElGamal cryptosystem, Diffie-Hellman protocol and DSA. Second part of thesis is focused for web application developed as study support of discrete logarithm problem and of cryptosystems using this problem. It describes functional and graphical interface, work with it and options given to user working with application. Mentions also lessons for user which should help with understanding of described problems and practicing.
19
Taufer, Daniele. "Elliptic Loops." Doctoral thesis, Università degli studi di Trento, 2020. http://hdl.handle.net/11572/265846.
Full textAbstract:
Given an elliptic curve E over Fp and an integer e ≥ 1, we define a new object, called “elliptic loop”, as the set of plane projective points over Z/p^e Z lying over E, endowed with an operation inherited by the curve addition. This object is proved to be a power-associative abelian algebraic loop. Its substructures are investigated by means of other algebraic cubics defined over the same ring, which we named “shadow curve” and “layers”. When E has trace 1, a distinctive behavior is detected and employed for producing an isomorphism attack to the discrete logarithm on this family of curves. Stronger properties are derived for small values of e, which lead to an explicit description of the infinity part and to characterizing the geometry of rational |E|-torsion points.<br>Data una curva ellittica E su Fp ed un intero e ≥ 1, definiamo un nuovo oggetto, chiamato "loop ellittico", come l'insieme dei punti nel piano proiettivo su Z/p^e Z che stanno sopra ad E, dotato di una operazione ereditata dalla somma di punti sulla curva. Questo oggetto si prova essere un loop algebrico con associatività delle potenze. Le sue sotto-strutture sono investigate utilizzando altre cubiche definite sullo stesso anello, che abbiamo chiamato "curva ombra" e "strati". Quando E ha traccia 1, un comportamento speciale viene notato e sfruttato per produrre un attacco di isomorfismo al problema del logaritmo discreto su questa famiglia di curve. Migliori proprietà vengono trovate per bassi valori di e, che portano ad una descrizione esplicita della parte all'infinito e alla caratterizzazione della geometria dei punti razionali di |E|-torsione.
20
Abu-Mahfouz, Adnan Mohammed. "Elliptic curve cryptosystem over optimal extension fields for computationally constrained devices." Diss., University of Pretoria, 2004. http://hdl.handle.net/2263/25330.
Full textAbstract:
Data security will play a central role in the design of future IT systems. The PC has been a major driver of the digital economy. Recently, there has been a shift towards IT applications realized as embedded systems, because they have proved to be good solutions for many applications, especially those which require data processing in real time. Examples include security for wireless phones, wireless computing, pay-TV, and copy protection schemes for audio/video consumer products and digital cinemas. Most of these embedded applications will be wireless, which makes the communication channel vulnerable. The implementation of cryptographic systems presents several requirements and challenges. For example, the performance of algorithms is often crucial, and guaranteeing security is a formidable challenge. One needs encryption algorithms to run at the transmission rates of the communication links at speeds that are achieved through custom hardware devices. Public-key cryptosystems such as RSA, DSA and DSS have traditionally been used to accomplish secure communication via insecure channels. Elliptic curves are the basis for a relatively new class of public-key schemes. It is predicted that elliptic curve cryptosystems (ECCs) will replace many existing schemes in the near future. The main reason for the attractiveness of ECC is the fact that significantly smaller parameters can be used in ECC than in other competitive system, but with equivalent levels of security. The benefits of having smaller key size include faster computations, and reduction in processing power, storage space and bandwidth. This makes ECC ideal for constrained environments where resources such as power, processing time and memory are limited. The implementation of ECC requires several choices, such as the type of the underlying finite field, algorithms for implementing the finite field arithmetic, the type of the elliptic curve, algorithms for implementing the elliptic curve group operation, and elliptic curve protocols. Many of these selections may have a major impact on overall performance. In this dissertation a finite field from a special class called the Optimal Extension Field (OEF) is chosen as the underlying finite field of implementing ECC. OEFs utilize the fast integer arithmetic available on modern microcontrollers to produce very efficient results without resorting to multiprecision operations or arithmetic using polynomials of large degree. This dissertation discusses the theoretical and implementation issues associated with the development of this finite field in a low end embedded system. It also presents various improvement techniques for OEF arithmetic. The main objectives of this dissertation are to --Implement the functions required to perform the finite field arithmetic operations. -- Implement the functions required to generate an elliptic curve and to embed data on that elliptic curve. -- Implement the functions required to perform the elliptic curve group operation. All of these functions constitute a library that could be used to implement any elliptic curve cryptosystem. In this dissertation this library is implemented in an 8-bit AVR Atmel microcontroller.<br>Dissertation (MEng (Computer Engineering))--University of Pretoria, 2006.<br>Electrical, Electronic and Computer Engineering<br>unrestricted
21
Vivek, Srinivas V. "On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem." Thesis, 2010. https://etd.iisc.ac.in/handle/2005/1996.
Full textAbstract:
There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields.
The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy
x3 y2z (mod p), x3 ≠ y2z, 1≤ x, y, z < pα ,
where α is a given real number ⅓ < α ≤ ½. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC.
This thesis is concerned with the CSC problem. Recently, the parametrization x y2z (mod p) and y υ3z (mod p) of CSC was introduced. We give a deterministic polynomial-time (O(ln3p) bit-operations) algorithm to determine, for a given υ, a nontrivial solution to CSC, if one exists. Previously it took Õ(pα) time to do this. We relate the CSC problem to the gap problem of fractional part sequences. We also show in the α = ½ case that for a certain class of primes the CSC problem can be solved deterministically Õ(p⅓) time compared to the previous best of Õ(p½). It is empirically observed that about one out of three primes are covered by this class, up to 109
22
Vivek, Srinivas V. "On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem." Thesis, 2010. http://etd.iisc.ernet.in/handle/2005/1996.
Full textAbstract:
There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields.
The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy
x3 y2z (mod p), x3 ≠ y2z, 1≤ x, y, z < pα ,
where α is a given real number ⅓ < α ≤ ½. The CSC problem is to find an efficient algorithm to obtain a nontrivial solution to CSC.
This thesis is concerned with the CSC problem. Recently, the parametrization x y2z (mod p) and y υ3z (mod p) of CSC was introduced. We give a deterministic polynomial-time (O(ln3p) bit-operations) algorithm to determine, for a given υ, a nontrivial solution to CSC, if one exists. Previously it took Õ(pα) time to do this. We relate the CSC problem to the gap problem of fractional part sequences. We also show in the α = ½ case that for a certain class of primes the CSC problem can be solved deterministically Õ(p⅓) time compared to the previous best of Õ(p½). It is empirically observed that about one out of three primes are covered by this class, up to 109
23
Lin, Kuei-Nuan. "The discrete logarithm problem on an elliptic curve." 1999. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0021-1804200714504002.
Full text
24
Kuei-Nuan, Lin, and 林桂暖. "The discrete logarithm problem on an elliptic curve." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/72594273947630879727.
Full textAbstract:
碩士<br>國立臺灣師範大學<br>數學研究所<br>88<br>In this master thesis, we talk about the discrete logarithm on an elliptic curve, and this is a reorganization of M-O-V's, Semaev's, and Voloch's papers.
Let E be an elliptic curve over a finite field F and char(F)=p,
the discrete logarithm problem on an elliptic curve is to compute an integer m such that Q=[m]P, where P and Q are rational points on E. If P has order n, we consider two cases:
(1)gcd(n,p)=1
(2)gcd(n,p) is not 1
Finally, we can use the Chinese remainder theorem to compute m
25
Sun, Yu-Rou, and 孫羽柔. "Index Calculus for the Elliptic Curves Discrete Logarithm Problem." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/35217207133936047005.
Full textAbstract:
碩士<br>國立交通大學<br>資訊科學與工程研究所<br>105<br>The security of elliptic curve cryptosystems is based on the hardness of the elliptic curve discrete logarithm problem(ECDLP). The most promising algorithm for ECDLP in binary fields is the index calculus method using Semaev’s summation polynomials and Weil Descent to create a polynomial system that is subsequently solved with Gröbner basis method. In this thesis we use SageMath to implement this type of index calculus method, discuss the algorithm in details and record the results.
26
Zumbrägel, Jens. "The Discrete Logarithm Problem in Finite Fields of Small Characteristic." Doctoral thesis, 2015. https://tud.qucosa.de/id/qucosa%3A30172.
Full textAbstract:
Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced.
This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems.
While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time.
Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around.<br>Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren.
Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben.
Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann.
Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.
27
Khalil, Antoine. "Application of sieve methods to factorization and the discrete logarithm problem." Thesis, 2002. http://spectrum.library.concordia.ca/1820/1/MQ72887.pdf.
Full textAbstract:
Factoring large numbers and computing discrete logarithms are presumed to be hard problems. No polynomial time solution for those problem has yet been found. Those problems have many significant applications, particularly in cryptography. Several cryptosystems base their security on their supposed difficulty. In this thesis we present some of the algorithms to solve these two problems. We mainly explore sieving as a tool for that purpose. Among other material we describe the Quadratic Sieve and the Number Field Sieve as they apply to factoring. We finally sketch how the Number Field Sieve can be applied to compute discrete logarithms.
28
Chu-Cheng, LI, and 李居政. "An ID-Based Cryptosystem Based on Discrete Logarithm and Factorization Problem." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/34313190390174073271.
Full textAbstract:
碩士<br>國立臺灣科技大學<br>電子工程系<br>87<br>This thesis proposed an ID-Based cryptosystem based on discrete logarithm and factorization problem. As compared to the public key cryptosystem, every user can send encrypted messages to the others without asking their public key. Sender can use the receiver's identity code, such as full name, E-mail address or else, as their public key to encrypt the message. The advantages of utilizing ID-based cryptosystem are that the system did not need to keep a public key file and the interactive communication of public key requesting.
This thesis was inspired by Tsujii and Itoh's ID-based cryptosystem. Our ID-based cryptosystem improved the restriction of the number of participants, which is the fatal drawback in their scheme, and could resist the chosen-public-key attack pointed by Sun and Hwang. Our scheme, moreover, did not need any tamper-free device or random numbers, which are the assumptions of most of previous researches. With sample modular exponential arithmetic, our scheme could be easily implemented in practice.
Besides, in the last section, we proposed an improved scheme of Wu-Wu's scheme (1997), which is a cryptosystem for broadcasting messages in computer networks. In this thesis, we dramatically reduce the storage and computation requirement without losing any consideration of security of Wu-Wu's scheme.
29
Vollmer, Ulrich. "Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields." Phd thesis, 2004. http://tuprints.ulb.tu-darmstadt.de/494/1/thesis.pdf.
Full textAbstract:
The purpose of this thesis is to study the complexity of the discrete logarithm problem (DLP) and related problems in quadratic orders. The significance of these problems stems in large part from their application in quadratic number field cryptography (QNFC). QNFC was proposed by Buchmann and Williams [Buchmann/Williams, 1988], [Buchmann/Williams, 1990], and relies on the fact that the DLP in quadratic orders is hard. The question whether QNFC is secure at all, and the choice of cryptographically secure key-sizes, if it is, requires the study of the difficulty of the DLP. This thesis takes a rigorous theoretical approach to this question. In the case of the probabilistic algorithms the analysis relies on the well-established Generalized Riemann Hypothesis (GRH). Starting point for the proposed deterministic algorithms were the works of Shanks [Shanks, 1971], [Shanks, 1972] and the variant of Shanks' idea for general groups suggested by Terr [Terr, 2000]. We give a detailed analysis of the run-time of our algorithms and indicate apart from the square root of the regulator at which (minimzed) power the logarithm of the discriminant enters the run-time bound. Starting point for the proposed probabilistic algorithms were the work of Hafner and McCurley [Hafner/McCurley, 1989] for negative discriminants and of Buchmann [Buchmann, 1990] for positive ones. The heart of the presented approach lies in the restriction of the computations to essential data (in particular partial instead of full relation lattice and sparse bases) and the use of fast sub-algorithms. One of these sub-algorithms is a newly developed algorithm for the computation of the Hermite Normal Form (HNF) of an integer matrix in cubic time. In summary we obtain the currently fastest deterministic and probabilistic algorithms for the problems at hand, and gives a rigorous analysis of their properties. Thus we establish an upper bound for the complexity of the DLP.
30
Gupta, Indivar. "Study of some cryptographic protocols based on discrete logarithm problem and pairing." Thesis, 2009. http://localhost:8080/xmlui/handle/12345678/4849.
Full text
31
Biswal, Biswa Bhusan, and Sukanta Kumar Mangal. "A Novel Blind Signature Scheme Based On Discrete Logarithm Problem With Un-traceability." Thesis, 2012. http://ethesis.nitrkl.ac.in/3481/1/Thesis_-_108CS040%2C108CS032.pdf.
Full textAbstract:
Blind Signatures are a special type of digital signatures which possess two special properties of blindness and untraceability, which are important for today’s real world applications that require authentication , integrity , security , anonymity and privacy.
David Chaum[2] was the first to propose the concept of blind signatures. The scheme's security was based on the difficulty of solving the factoring problem [3, 4]. Two properties that are important for a blind signature scheme in order to be used in various modern applications are blindness and untraceability[2, 5, 6] . Blindness means that the signer is not able to know the contents of the message while signing it, which is achieved by disguising (or blinding) the message through various methods. Untraceability refers to preventing the signer from linking the blinded message it signs to a later unblinded version that it may be called upon to verify.
Blind signatures based on discrete logarithm problem are still an area with much scope for research. We aim to propose a novel blind signature scheme with untraceability , based on the discrete logarithm problem .
32
Panda, Suryakanta. "Time Stamped Proxy Blind Signature Scheme With Proxy Revocation Based on Discrete Logarithm Problem." Thesis, 2013. http://ethesis.nitrkl.ac.in/5057/1/211CS1273.pdf.
Full textAbstract:
Proxy blind signature combines both the properties of blind signature and proxy signature. In a proxy blind signature scheme, the proxy signer is allowed to generate a blind signature on behalf of the original signer. It is a protocol played by three parties in which a user obtains a proxy signer’s signature for a desired message and the proxy signer learns nothing about the message. During the verification of a proxy blind signature scheme, the verifier cannot get whether signing is within the delegation period or after delegation period. In this thesis a time stamped proxy blind signature scheme with proxy revocation is proposed which records the time stamp during the proxy signing phase and satisfies all the security properties of proxy blind signature i.e distinguishability, nonrepudiation, unforgeability, verifiability, identifiability, unlinkability, prevention of misuse. In a proxy revocation scheme, the original signer can terminate the delegation power of a proxy signer before the completion of delegation period. Proxy blind signature has wide applications in real life scenarios, such as, e-cash, e-voting and e-commerece applications.
33
Vollmer, Ulrich [Verfasser]. "Rigorously analyzed algorithms for the discrete logarithm problem in quadratic number fields / von Ulrich Vollmer." 2004. http://d-nb.info/972690441/34.
Full text
34
TebbieTung, Iu-Chui, and 董蕘翠. "Finding the secret key in Bitcoin: A review on mathematical approaches to Elliptic Curve Discrete Logarithm Problem." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/bkwnf4.
Full textAbstract:
碩士<br>國立成功大學<br>數學系應用數學碩博士班<br>107<br>With the popular usage of Bitcoin, safety in making payments or transactions becomes a topic of concern. In brief, the security chiefly relies on the easiness of finding the secret key/ private key in Bitcoin. To a large extent, this depends on how easy it is to resolve an Elliptic Curve Discrete Logarithm Problem (ECDLP). With that in mind, the main focus of this paper is to review any mathematical approaches and their variants that can theoretically tackle an ECDLP in Bitcoin. The objective is to discuss the security of Bitcoin by studying methods of uncovering the private key.
On the other hand, the existence of non-mathematical approaches provides an alternative to figure out the private key faster. Notably, they work only in the presence of implementation vulnerabilities. Even so, in consideration of the influence that non-mathematical approaches may bring about, this paper also includes an outline of some of the frequently mentioned ones.
Last but not least, results indicated that using Bitcoin for payments or transactions appears to be secure at this stage, but the development of quantum computers may alter the situation in the future. By taking this into account, this paper ends up with a comment on the impact of quantum computers on Bitcoin.
35
Wang, Shyi-Chung, and 王錫中. "A Study of the Security of Mambo et al.'s Proxy Signature Scheme Based on the Discrete Logarithm Problem." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/68950790391982784919.
Full textAbstract:
碩士<br>逢甲大學<br>資訊工程所<br>92<br>Abstract
In this paper, we proposed two attacked (Type I & Type II) on the proxy signature scheme presented by Mambo, Usuda and Okamot in 1995. The attacker can forge the key pair of proxy signature in unknown the original private key, and disguise as proxy to sign document. The forgery signed document can pass the verification step and however he/she not be discovered. The skills of attacks are some mathematical computations based on Chinese Remainder Theorem to conduct the unauthorized key pair of proxy signature.
Type I, the forger only gets the public key v of original signer from public channel. By the Chinese Remainder Theorem computation, the counterfeiter can forge the key pair of proxy signature. Type II, inner member, proxy signer, play as an attacker, using his secret key σ of authorized proxy signature to forge key pair of proxy signature .
At last, we presented the analysis about the two type attacks and a simple countermeasure is further introduced to avoid this imperfection of Mambo et al.’s proxy signature scheme.
Keywords: Chinese Remainder Theorem, Discrete Logarithm Problem, Cryptography, Digital Signature, Proxy Signature Scheme.