|
Theoretical Computer Science Faculty of Mathematics and Computer Science Jagiellonian University |
| Algorithmics Research Group |
|
| Cryptography Seminar |
| Tuesday: 16:15 - 18:00, room 117 |
|
"One change in number theory over the last twenty years is that it has become an applied subject. Perhaps one should say it has gone back to being an applied subject as it was more than two thousand years ago. Public key cryptography has changed the way we look at secrecy and codes."
ANDREW WILES In this seminar we study the basic ideas and computational methods of elliptic curve cryptography. It is mainly aimed at graduate students with a basic knowledge of abstract algebra and algorithmic number theory. |
| table edited by: Zbigniew Hajto |
| 10.06.2008, Tytus Bierwiaczonek |
Zero-knowledge protocols II |
| 03.06.2008, Tytus Bierwiaczonek |
Zero-knowledge protocols I |
| 27.05.2008, Marcin Krzywda |
Computation of the Mordell-Weil rank of an elliptic curve over Q |
| Let E be an elliptic curve over Q. By Mordell's theorem, E(Q) is a finitely generated abelian group. This means that E(Q) = E(Q)tors × Z^r. By Mazur's theorem, we know how E(Q)tors looks like. On the other hand, it is not known what values of rank r are possible for elliptic curves over Q. The "folklore" conjecture is that the rank can be arbitrary large. The current record is an example of elliptic curve with rank >= 28, found by Elkies in 2006. In his work Chahal presents an "algorithm" for computing r in a special case, when the elliptic curve is given by an equation y2 = x3+Ax, where A is an integer. We get a straight formula for the rank, but unfortunately the weak point of this method is that in order to compute r we need to solve some diophantine equations. | |
| references: | |
| 20.05.2008, Łukasz Stec |
Tame Transformation Cryptography I |
| Tame transformations of finite fields have great potential in cryptography. With a good implementation messages can be very quickly encrypted and decrypted, while using known methods to build a private key from a public key and decrypting using only the public key would require huge amounts of computing power. In this talk we show the principle of tame transformation cryptography, encryption, decryption, error detection and signatures, then we show the implementation by T.T.Moh called TTM that was proposed in his paper entitled " A Public Key System With Signature And Master Key Functions". | |
| 13.05.2008, Elżbieta Sowa |
Galois Theory - a practical guide II |
| 06.05.2008, Elżbieta Sowa |
Galois Theory - a practical guide I |
| Main topics: the structure of finite and algebraic extension of fields, Galois extensions and their automorphisms, question about roots of polynomial equations, differential fields and differential automorphisms, Picard-Vessiot extensions, comparison of the fundamental theorems in Classical Galois Theory and Differential Galois Theory. | |
| 29.04.2008, Rafał Zaręba |
Wireless Security |
| 15.04.2008, Michał Staromiejski |
Time complexity lower bound of generic algorithms for discrete logarithm problem |
| The discrete logarithm problem (DLP) in a cyclic group G with n elements is the following: given a generator g of G and an element a,compute the unique integer k, 0 <= k < n satisfying g^k = a. An algorithm solving DLP is generic if (roughly speaking) the only operations on group elements performed by the algorithm are the group operations (multiplication, inversion and identity). Several generic algorithms are known which solve DLP, but all of them have running time exponential in log(n). In 1997, Shoup has shown that this is not an accident generic algorithms cannot solve DLP asymptotically faster than Theta(sqr{p}), where p is the largest prime factor of n. We present Shoup's result along with some algorithm solving DLP. | |
| 08.04.2008, Jakub Kozik |
Determinant vs. Permanent - Mulmuley, Sohoni approach III |
| 01.04.2008, Jakub Kozik |
Determinant vs. Permanent - Mulmuley, Sohoni approach II |
| 18.03.2008, Jakub Kozik |
Determinant vs. Permanent - Mulmuley, Sohoni approach I |
| Ketan Mulmuley and Milind Sohoni developed geometric complexity theory to address various separation problems of complexity classes. The theory is based on algebraic geometry and representation theory. We present their approach on the example of the problem of representability of permanents by determinants. The problem is closely related to the Valiant's hypothesis saying that VP != VNP. The first part of the exposition concerned Valiant's complexity classes and their complete problems. |
|
| 11.03.2008, Michał Staromiejski |
AKS algorithm: a deterministic, polynomial time primality test II |
| 04.03.2008, Arkadiusz Pawlik |
Complexity of integer Gaussian Elimination and the Smith Normal Form |
| Although Smith normal form can be computed in polynomial time, algorithms based on Gaussian elimination may require exponential number of bit operations. I present matrices which may require computations on exponential length numbers, provided that we make appropriate assumptions on the order of elimination. We also discuss some approaches which lead to algorithms that do work in polynomial time: lattice basis reduction and modular techniques. | |
| 26.02.2008, Michał Staromiejski |
AKS algorithm: a deterministic, polynomial time primality test I |
| Until the year 2002, there was no known deterministic, polynomial time algorithm for testing primality with unconditionally proven time complexity, despite much research. In 2002, three Indian computer scientists: Manindra Agrawal, Neeraj Kayal and Nitin Saxena discovered such an algorithm. Our goal is to present in completely elementary way the AKS algorithm: we bound time complexity and show correctness of the algorithm using elementary combinatoric and algebraic methods. The first part of the presentation is devoted to bounding time complexity whereas during the second part we are going to show correctness. | |
| 22.01.2008, Łukasz Nowak |
Algorithms for integer factorization II |
| 15.01.2008, Łukasz Nowak |
Algorithms for integer factorization I |
| In this talk are presented Pollard's p-1 method and Lenstra's elliptic curves method for the integer factorization. | |
| 08.01.2008, Teresa Crespo (Universitat de Barcelona) |
Quadratic fields and cryptography |
| Diffie-Hellman key exchange protocol and RSA public-key cryptosystem are based on the computational difficulty in factoring integers. Some variants of these have been proposed which are based on computationally hard problems in algebraic Number Theory. In this talk, we survey the unit group and the ideal class group of number fields. We show explicit computations for these groups in the case of quadratic number fields. We present cryptosystems based on the unit group and ideal class group. Finally we discuss why imaginary quadratic fields appear to be more suitable for encryption systems based on class groups. | |
| 18.12.2007, Marcin Krzywda |
Factorizations |
| 11.12.2007, 04.12.2007, Rafał Laskowski |
RSA - generalisations |
| 27.11.2007, Michał Pękała |
RSA public-key cryptosystem |
| During the speech you could have: 1) learnt historical background of public key cryptography conception; 2) taken a closer look at RSA - an algorithm commonly used in public key cryptosystems; 3) followed and understood RSA correctness proof; 4) got familiar with some technical details, i.e. concerning prime numbers generation; 5) watched a working RSA encryption/decryption applet, as well. | |
| 20.11.2007, 13.11.2007, Monika Górecka & Bartłomiej Nowak |
Digital Signature Algorithms |
| 06.11.2007, Bartosz Walczak |
Fundamental theorem of finitely generated abelian groups via Smith normal form |
| 23.10.2007, 16.10.2007, 09.10.2007, Michał Staromiejski |
The Weil pairing and the computation of discrete logarithms on elliptic curves |