Kryptologia
wtorek: 12:00  13:30, sala 0174
Seminarium poświęcone kryptologii
Seminarium poświęcone kryptologii
28.03.2017 14:15 Piotr Wójcik 
Quantum Authentication with Key Recycling 
We show that a family of quantum authentication protocols introduced in FOCS 2002 can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this family of protocols, i.e., there exists an adversarial strategy to obtain all nonrecycled bits. Previous works recycled less key and only gave partial security proofs, since they did not consider all possible distinguishers (environments) that may be used to distinguish the real setting from the ideal secure quantum channel and secret key resource. References: [1] Christopher Portmann, Quantum Authentication with Key Recycling (pdf) 
04.04.2017 14:15 Mateusz Jachna 
Secure Hash Algorithms family and the recently found collision for SHA1 
21.03.2017 14:15 Jan Szczepaniec 
Inclusive Block Chain Protocols 
Distributed cryptographic protocols such as Bitcoin and Ethereum use the block chain to synchronize a global log of events between nodes in their network. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly.

14.03.2017 14:15 Marcin Briański 
NonInteractive Verifiable Computing: Outsourcing Computation to Untrusted Workers 
The talk is based on the paper with the same title by Rosario Gennaro, Craig Gentry and Bryan Parno. Verifiable Computation enables a computationally weak client to "outsource" the computation of a function F on various inputs x_{1}, ..., x_{k} to one or more workers. The workers return the result of the function evaluation, e.g., y_{i} = F(x_{i}), as well as a proof that the computation of F was carried out correctly on the given value x_{i}. The verification of the proof should require substantially less computational effort than computing F(x_{i}) from scratch. We present a protocol that allows the worker to return a computationally sound, noninteractive proof that can be verified in O(m) time, where m is the bitlength of the output of F. The protocol requires a onetime preprocessing stage by the client which takes O(C) time, where C is the smallest Boolean circuit computing F. Our scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the values x_{i} or y_{i}. 
07.03.2017 14:15 Zygmunt Łenyk 
Speeding up modular multiplication using Montgomery and Barrett reduction 
In the talk we present Montgomery and Barrett reductions that are used to speed up modular computations. In both reductions some precomputations are made allowing for replacing subsequent expensive divisions by some fixed modulus with much cheaper operations involving a suitable power of 2. This is particularly useful when many modular divisions by the same modulus are performed (for example in finite field arithmetic or in RSA). 
28.02.2017 Michał Dyrek 
LLL algorithm and its applications in Number Theory and Cryptography 
The talk is devoted to the algorithm by A. Lenstra, H. Lenstra and L. Lovász dated 1982 allowing for approximation of Shortest Vector Problem in polynomial time. We will present the idea of the algorithm and highlight its applications such as factoring polynomials over Q, constructing polynomials with small coefficients and connections with attacks on RSA. 
24.01.2017 Kamil Sałaś 
Lower Bounds for Discrete Logarithms 
In the talk we will present the computational complexity of the discrete logarithm in the context of "generic algorithms", that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as unique binary string. For discrete logarithm, any generic algorithm must perform Ω(p^1/2) group operations, where p is the largest prime dividing the order of the group. 
17.01.2017 Grzegorz Bukowiec 
A quasipolynomial algorithm for discrete logarithm in finite fields of small characteristic 
Until recently, all the algorithms for computing discrete logarithm had a subexponential complexity of type L(1/3), similar to the factorization problem. In this talk we'll discuss a heuristic algorithm that provides quasipolynomial complexity for discrete logarithm in finite fields of small characteristic and that even for other cases still surpasses the Function Field Sieve method. References: [1] R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A quasipolynomial algorithm for discrete logarithm in finite fields of small characteristic (pdf) 
10.01.2017 Szymon Policht 
Faster operations on elliptic curves using Edwards curves 
Elliptic curve cryptography is a broad and commonly used section of modernday cryptography. Because of that, the speed of elliptic curve operations directly impacts the performance of many current systems. In this talk we'll show how to speed up those operations using Edwards curves. References: [1] Bernstein D.J., Lange T. (2007) Faster Addition and Doubling on Elliptic Curves. In: Kurosawa K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg (https://eprint.iacr.org/2007/286.pdf) 
03.01.2017 
(Cancelled) 
20.12.2016 12:00 Bartłomiej Puget 
An introduction to quantum computing and cryptography II 
13.12.2016 12:00 Krzysztof Kleiner 
An introduction to quantum computing and cryptography I 
In this talk we're going to discuss quantum informatics and its impact on the field of cryptography. We will introduce the basic concepts of quantum computing as well as cryptography based on Quantum Key Distribution scheme, one of the aspects of quantum informatics which already is being used in practice. Then we will present Shor's algorithm for polynomialtime factorization, responsible for the cryptosystems based on the hardness of factorization or discrete logarithm (in abelian groups) being no longer secure against an adversary with access to a quantum computer.

06.12.2016 Marek Rusinowski 
Security of instant messaging applications. 
Nowadays billions of people around the world are sharing sensitive information using instant messaging applications. We will look into the current state of IM security, the problems in this area and a few encryption protocolsOTR and Signal Protocol in particularthat provide security features desired by users. 
29.11.2016 Anna Kobak 
Breaking RSA vs Factoring in generic ring model 
In the talk we present results of Aggarwal and Maurer [1], who showed that a generic ring algorithm for breaking RSA with modulus $N$ can be converted into an algorithm for factoring $N$. The results imply that any attempt at breaking RSA without factoring $N$ will be nongeneric and hence will have to manipulate the particular bitrepresentation of the input modulo $N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.
References: [1] D. Aggarwal, U. Maurer, Breaking RSA Generically is Equivalent to Factoring, EUROCRYPT 2009 
22.11.2016 Aleksandra Nowak 
Lattice Cryptography and The Learning With Errors Problem 
15.11.2016 Piotr Kawałek 
Teoretyczne podstawy kryptoanalizy 
Celem referatu jest przedstawienie teoretycznych modeli ataków kryptoanalitycznych oraz tematów pokrewnych wraz z przykładami. 
08.11.2016 Patryk Gołębiowski 
Advanced Encryption Standard 
Advanced Encryption Standard (AES) is one of the most popular and widely adopted symmetric encryption scheme. In the talk we discuss how it works and why it is considered safe by the U.S. National Institute of Standards and Technology to use it for protecting classified information. 
25.10.2016 Marcin Briański 
Unifying Zeroknowledge Proofs of Knowledge 
We present a simple zeroknowledge proof of knowledge protocol of which many protocols in the literature are instantiations. These include Schnorr's protocol for proving knowledge of a discrete logarithm, the FiatShamir and GuillouQuisquater protocols for proving knowledge of a modular root, protocols for proving knowledge of representations (like Okamoto's protocol), protocols for proving equality of secret values, a protocol for proving the correctness of a DiffieHellman key, protocols for proving the multiplicative relation of three commitments (as required in secure multiparty computation), and protocols used in credential systems. This shows that a single simple treatment (and proof), at a high level of abstraction, can replace the individual previous treatments. Moreover, one can devise new instantiations of the protocol. [1] Ueli Maurer, Unifying Zeroknowledge Proofs of Knowledge, Progress in Cryptology – AFRICACRYPT 2009, Vol. 5580 LNCS, pp 272286

18.10.2016 Grzegorz Jurdzinski 
Timing attacks 
Cryptosystems like AES or RSA use algorithms which runtime depends on input data or using CPU cache. Basing on this fact an attacker can find secret keys by choosing inputs and carefully measuring time needed for computations. In this talk I will present such attacks and how to prevent them.

11.10.2016 Michał Zieliński 
SafeDeflate: compression without leaking secrets 
CRIME and BREACH attacks on TLS/SSL leverage the fact that compression ratio is not hidden by encryption to recover content of secrets. We introduce SafeDeflate—a modification of a standard Deflate algorithm which compression ratio does not leak information about secret tokens. The modification is compatible with existing Deflate and gzip decompressors. We introduce a model in which attacker can obtain ciphertexts of arbitrary compressed plaintext containing secret values. Then we prove that SafeDeflate is secure in this model. 
21.01.2015 Bartosz Badura 
A Formal Treatment of Onion Routing 
Anonymous channels are necessary for a multitude of privacyprotecting protocols. Onion routing is probably the best known way to achieve anonymity in practice. However, the cryptographic aspects of onion routing have not been sufficiently explored: no satisfactory definitions of security have been given, and existing constructions have only had adhoc security analysis for the most part. We provide a formal definition of onionrouting in the universally composable framework, and also discover a simpler definition (similar to CCA2 security for encryption) that implies security in the UC framework. We then exhibit an efficient and easy to implement construction of an onion routing scheme satisfying this definition. References: J. Camenisch, A. Lysyanskaya, A Formal Treatment of Onion Routing, Proc CRYPTO'05, pp. 169187 
14.01.2015 Konrad Witaszczyk 
How to Reinitialize a Hash Chain 
Hash Chains are used extensively in various cryptographic systems such as onetime passwords, server supported signatures, secure address resolution, certificate revocation, micropayments etc. However, currently they suffer from the limitation that they have a finite number of links which when exhausted requires the system to be reinitialized. In this paper, we present a new kind of hash chain which we call a Reinitializable Hash Chain (RHC). A RHC has the property that if its links are exhausted, it can be securely reinitialized in a nonrepudiable manner to result in another RHC. This process can be continued indefinitely to give rise to an infinite length hash chain, or more precisely, an infinite number of finite length hash chains tied together. Finally we illustrate how a conventional hash chain (CHC) may be profitable replaced with a RHC in cryptographic systems. References: Leslie Lamport, Password Authentication with Insecure Communication, PDF Yuanchao Zhao, Daoben Li, An Improved Elegant Method to Reinitialize Hash Chains, PDF Vipul Goyal, How to Reinitialize a Hash Chain, PDF 
07.01.2015 Paweł Zegartowski 
The Padding Oracle attacks: theoretical background with practical exemplification 
In many standards, such as. SSL/TLS, IPSEC, WTLS, messages are first preformatted, then encrypted in CBC mode with a block cipher. Decryption needs to check if the format is valid. Validity of the format is easily leaked from communication protocols in a chosen ciphertext attack since the receiver usually sends an acknowledgment or an error message.This is a side channel. Since year 2002 the padding oracle attacks are known to be a working example of Chosen Ciphertext Attack possible to perform on various realworld cryptosystems using padding in their vital areas of calculation. The lecture attempts to describe the nature of a padding oracle attack and to point drawbacks of cryptosystems that make them vulnerable for attack of this kind. Moreover the POODLE attack shall be presented as an example of practical application of padding oracle attack against the SSLv3 protocol possible to be used also against servers using newer security protocols (like TLS 1.x). References: Serge Vaudenay, Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS, EUROCRYPT 2002. Juliano Rizzo, Thai Duong, Practical Padding Oracle Attacks, USENIX WOOT 2010 Möller, Bodo; Duong, Thai; Kotowicz, Krzysztof, This POODLE Bites: Exploiting The SSL 3.0 Fallback, Google Security Advisory 2014 
17.12.2014 Łukasz Majcher 
Searching for Elements in Black Box Fields and Applications 
We introduce the notion of a black box field and discuss the problem of explicitly exposing field elements given in a black box form. We present several subexponential algorithms for this problem using a technique due to Maurer. These algorithms make use of elliptic curves over finite fields in a crucial way. We present three applications for our results: (1) We show that any algebraically homomorphic encryption scheme can be broken in expected subexponential time. The existence of such schemes has been open for a number of years. (2) We give an expected subexponential time reduction from the problem of finding roots of polynomials over finite fields with low straight line complexity (e.g. sparse polynomials) to the problem of testing whether such polynomials have a root in the field. (3) We show that the hardness of computing discretelog over elliptic curves implies the security of the DiffieHellman protocol over elliptic curves. Finally in the last section of the paper we prove the hardness of exposing black box field elements in a field of characteristic zero. References: Dan Boneh, Richard J. Lipton, Algorithms for BlackBox Fields and their Application to Cryptography, Proceeding CRYPTO'96 pp. 283297 
10.12.2014 Krzysztof Kulig 
How to Leak a Secret 
In this paper we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature.Unlike group signatures, ring signatures have no group managers, no setup procedures, no revocation procedures, and no coordination:any user can choose any set of possible signers that includes himself,and sign any message by using his secret key and the others' public keys,without getting their approval or assistance. Ring signatures provide an elegant way to leak authoritative secrets in an anonymous way, to sign casual email in a way which can only be verified by its intended recipient, and to solve other problems in multiparty computations. The main contribution of this paper is a new construction of such signatures which is unconditionally signerambiguous, provably secure in the random oracle model,and exceptionally efficient:adding each ring member increases the cost of signing or verifying by a single modular multiplication and a single symmetric encryption. References: Ronald L. Rivest, Adi Shamir, Yael Tauman, How to Leak a Secret, Advances in Cryptology — ASIACRYPT 2001 LNCS vol. 2248, 2001, pp 552565 
03.12.2014 Piotr Bejda 
Using hash functions as a hedge against chosen ciphertext attack 
The cryptosystem recently proposed by Cramer and Shoup is a practical public key cryptosystem that is secure against adaptive chosen ciphertext attack provided the Decisional DiffieHellman assumption is true. Although this is a reasonable intractability assumption, it would be preferable to base a security proof on a weaker assumption, such as the Computational DiffieHellman assumption. Indeed, this cryptosystem in its most basic form is in fact insecure if the Decisional DiffieHellman assumption is false. In this paper we present a practical hybrid scheme that is just as efficient as the scheme of of Cramer and Shoup; indeed, the scheme is slightly more efficient than the one originally presented by Cramer and Shoup; we prove that the scheme is secure if the Decisional DiffieHellman assumption is true; we give strong evidence that the scheme is secure if the weaker, Computational DiffieHellman assumption is true by providing a proof of security in the random oracle model. References: R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Advances in Cryptology  Crypto'98, pages 13–25, 1998 V. Shoup. Using hash functions as a hedge against chosen ciphertext attack, in Proc. Eurocrypt 2000 
26.11.2014 Pola Kyzioł 
Another look at nonstandard discrete log and DiffieHellman problems 
We examine several versions of the onemorediscretelog and onemoreDiffieHellman problems. In attempting to evaluate their intractability, we find conflicting evidence of the relative hardness of the different problems. Much of this evidence comes from natural families of groups associated with curves of genus 2, 3, 4, 5, and 6. This leads to questions about how to interpret reductionist security arguments that rely on these nonstandard problems. References: N. Koblitz, A. Menezes, Another look at nonstandard discrete log and DiffieHellman problems, J. Math. Cryptology 2 (2008), pp. 311326 
19.11.2014 Patryk Mikos 
A practical public key cryptosystem probably secure against adaptive chosen ciphertext attack 
A new public key cryptosystem is proposed and analyzed. The scheme is quite practical, and is provably secure against adaptive chosen ciphertext attack under standard intractability assumptions. There appears to be no previous cryptosystem in the literature that enjoys both of these properties simultaneously. 
12.11.2014 Kamil Sałaś 
Simple Unpredictable PseudoRandom Number Generator 
References: L. Blum, M. Blum, M. Shub, A Simple Unpredictable PseudoRandom Number Generator, SIAM Journal on Computing 15(2) pp. 364383 
29.10.2014 
Cancelled 
22.10.2014 Robert Obryk 
Electronic money 
15.10.2014 Michał Staromiejski 
On Shoup's lower bound technique for generic algorithms for discrete logarithm problem 
08.10.2014 Jakub Brzeski 
Continued Fractions: theory and applications 
In the talk we focus on the most important (and interesting) properties of the continued fractions together with examples of their applications. 
12.06.2014 Andrzej Głuszyński 
Factoring with General Number Field Sieve 
The number field sieve (NFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n is of the form L[1/3, (64/9)^{1/3}]. The principle of the NFS can be understood as an improvement to the simpler rational and quadratic sieve which base on searching for smooth numbers. NFS had some spectacular successes with integers in certain special forms, most notably the factorization of the 155 decimal digit ninth Fermat number F9 = 2^512 + 1. References: Peter Stevenhagen, The number field sieve. Algorithmic Number Theory, MSRI Publication Vol. 44, 2008 Carl Pomerance, The number field sieve, Proceedings of Symposis in Applied Mathematics, Vol. 48. 1994 
05.06.2014 Krzysztof Kleiner 
Zeroknowledge proofs 
A zeroknowledge proof is a protocol providing that one site can prove to the other that a certain statement is true without revealing any other information. We demand that if the prover knows the proof of the statement, it will be accepted, that otherwise it will get rejected with liberally high probability and that the distribution of the protocol transcript is the same (perfect zeroknowledge proofs) or computationally indistinguishable (computational zeroknowledge proofs) from the output of some probabilistic Turing Machine, which doesn't have access to any of the prover's private information. References: O. Goldreich, S. Micali, A. Wigderson, Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design, Journal of the Association for Computing Machinery: Vol 38, No 1, July 1991, pp 69172 
29.05.2014 Andrzej Dorobisz 
Breaking RSA may not be equivalent to factoring 
This talk is based on the paper by D. Boneh and R. Venkatesan. Abstract of the paper: We provide evidence that breaking lowexponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking lowexponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any weakness in the RSA system. 
22.05.2014 Jakub Brzeski 
Breaking RSA may be as difficult as factoring 
This talk is based on the paper of Daniel R. L. Brown, who shows that if factoring is hard, then straight line programs cannot efficiently solve the low public exponent RSA problem. More precisely, no efficient algorithm can take an RSA public key as input and then output a straight line program that efficiently solves the low public exponent RSA problem for the given public key  unless factoring is easy. References: Daniel R. L. Brown, Breaking RSA May Be As Difficult As Factoring, Cryptology ePrint Archive: Report 2005/380, http://eprint.iacr.org/2005/380 
15.05.2014 Michał Masłowski 
Timing attacks 
Fast implementations of AES and RSA use algorithms with nonconstant time that attackers can affect by choosing inputs or using CPU cache. This allows recovering secret keys in local or remote attacks. This talk presents these algorithms, resulting timing attacks and mitigation techniques. References: David Brumley, Dan Boneh, Remote timing attacks are practical, https://crypto.stanford.edu/~dabo/papers/ssltiming.pdf Paul C. Kocher, Timing attacks on implementations of DiffieHellman, RSA, DSS, and other systems, http://www.cryptography.com/public/pdf/TimingAttacks.pdf Daniel J. Bernstein, Cachetiming attacks on AES, http://cr.yp.to/papers.html#cachetiming 
08.05.2014 Kamil Sałaś 
Data Encryption Standard 
Short introduction to Data Encryption Standard. Detailed analysis of encryption function. Security: brute force and differential cryptanalysis. Overview of Triple DES. 
24.04.2014 Konrad Ozimek 
Block ciphers 
17.04.2014 Szymon Policht 
Stream ciphers 
Stream ciphers are one of the most important branches of privatekey cryptography. They offer strong security, combined with high speed and ease of implementation. In this talk, we define them and discuss ways to convert block ciphers to stream ones. Additionally, we introduce a powerful way of creating such ciphers  linear feedback shift registers. References: Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, chapter 6 Oded Goldreich, Foundations of Cryptography vol. 2  Basic Applications, sections 5.3.15.3.2 
10.04.2014 Anna Dymek 
Pseudorandom generators 
Many encryption techniques use "random variables", and proofs of their correctness are based on the low probability of guessing the value of that "random variables". For that we need random generators, or so called "pseudorandom generators", which give us values indistinguishable from truly random ones. In the talk we define pseudorandom generators, discuss their existence and describe their relations with other problems. References: O. Goldreich, Foundations of Cryptography vol. 1  Basic Techniques, chapter 3 
03.04.2014 Damian Królik 
OAEP+ 
27.03.2014 Michał Staromiejski 
Bezout theorem and associativity of addition on elliptic curves 
13.03.2014 Grzegorz Guśpiel 
Optimal Asymmetric Encryption Padding (OAEP) 
We discuss the encryption scheme OAEP, long considered to be the first one to achieve both good performance and provable security. The latter was not obtained, however, due to a mistake in the proof. We present the scheme and the flawed proof. abstract of the paper: Given an arbitrary kbit to kbit trapdoor permutation f and a hash function, we exhibit an encryption scheme for which (i) any string x of length slightly less than k bits can be encrypted as f(r_x), where r_x is a simple probabilistic encoding of x depending on the hash function; and (ii) the scheme can be proven semantically secure assuming the hash function is "ideal." Moreover, a slightly enhanced scheme is shown to have the property that the adversary can create ciphertexts only of strings for which she "knows" the corresponding plaintexts  such a scheme is not only semantically secure but also nonmalleable and secure against chosenciphertext attack. References: M. Bellare, P. Rogaway, Optimal Asymmetric Encryption  How to Encrypt with RSA, http://cseweb.ucsd.edu/~mihir/papers/oae.pdf 
06.03.2014 Wojciech Łopata 
Introduction to provable security 
We discuss several definitions of cryptosystem security as a resistance against "chosenciphertext" attacks, and reveal weaknesses of RSA and ElGamal encryption schemes. Then I describe CramerShoup encryption, and prove that if the Decision DiffieeHellman Problem is hard, then CramerShoup encryption is indistinguishabilitysecure from chosenciphertext attack. 