Kryptologia

wtorek: 12:00 - 13:30, sala 0174

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 non-recycled 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 SHA-1

Poprzednie referaty

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.
Inclusive Block Chain Protocol is a alternative structure consists of a directed acyclic graph of blocks to the chain that allows for operation at much higher rates. It is showed that with this system the advantage of highly connected miners is greatly reduced. On the negative side, attackers that attempt to maliciously reverse transactions can try to use the forgiving nature of the DAG structure to lower the costs of their attacks.


References:
[1] Lewenberg Y., Sompolinsky Y., Zohar A., Inclusive Block Chain Protocols. In: Böhme R., Okamoto T. (eds) Financial Cryptography and Data Security, 2015. Lecture Notes in Computer Science, vol 8975. Springer, Berlin, Heidelberg (pdf)

14.03.2017 14:15
Marcin Briański
Non-Interactive 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 x1, ..., xk to one or more workers. The workers return the result of the function evaluation, e.g., yi = F(xi), as well as a proof that the computation of F was carried out correctly on the given value xi. The verification of the proof should require substantially less computational effort than computing F(xi) from scratch.

We present a protocol that allows the worker to return a computationally sound, non-interactive proof that can be verified in O(m) time, where m is the bit-length of the output of F. The protocol requires a one-time pre-processing 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 xi or yi.

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 pre-computations 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 quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic

Until recently, all the algorithms for computing discrete logarithm had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In this talk we'll discuss a heuristic algorithm that provides quasi-polynomial 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 quasi-polynomial 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 modern-day 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 polynomial-time 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.


References:

[1] M. Hirvensalo, Quantum Computing (http://link.springer.com/book/10.1007/978-3-662-09636-9)
[2] F. Benatti, M. Fannes, R. Floreanini, D. Petritis, Quantum Information, Computation and Cryptography (http://link.springer.com/book/10.1007/978-3-642-11914-9)
[3] D. Deutsc, Lectures on Quantum Computation (http://www.daviddeutsch.org.uk/videos/)
[4] U. Vazirani, BerkeleyX's Lectures: Quantum Mechanics and Quantum Computation (https://www.edx.org/course/quantum-mechanics-quantum-computation-uc-berkeleyx-cs-191x)

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 protocols---OTR and Signal Protocol in particular---that 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 non-generic and hence will have to manipulate the particular bit-representation 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 Zero-knowledge Proofs of Knowledge

We present a simple zero-knowledge 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 Fiat-Shamir and Guillou-Quisquater 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 Diffie-Hellman key, protocols for proving the multiplicative relation of three commitments (as required in secure multi-party 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 Zero-knowledge Proofs of Knowledge, Progress in Cryptology – AFRICACRYPT 2009, Vol. 5580 LNCS, pp 272-286

 

 

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.


References:
[1] Paul C. Kocher, Timing Attacks on Implementations of Diffe-Hellman, RSA, DSS and Other Systems (http://www.cryptography.com/public/pdf/TimingAttacks.pdf)
[2] David Brumley, Dan Boneh, Remote Timing Attacks are Practical (https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf)
[3] Daniel J. Bernstein, Cache-timing attacks on AES (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf)

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 privacy-protecting 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 ad-hoc security analysis for the most part. We provide a formal definition of onion-routing 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. 169--187
14.01.2015
Konrad Witaszczyk
How to Re-initialize a Hash Chain
Hash Chains are used extensively in various cryptographic systems such as one-time 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 re-initialized. In this paper, we present a new kind of hash chain which we call a Re-initializable Hash Chain (RHC). A RHC has the property that if its links are exhausted, it can be securely re-initialized in a non-repudiable 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 Re-initialize Hash Chains, PDF
Vipul Goyal, How to Re-initialize 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 pre-formatted, 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 real-world 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 sub-exponential 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 sub-exponential time. The existence of such schemes has been open for a number of years. (2) We give an expected sub-exponential 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 discrete-log over elliptic curves implies the security of the Diffie-Hellman 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 Black-Box Fields and their Application to Cryptography, Proceeding CRYPTO'96 pp. 283--297
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 signer-ambiguous, 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 552-565
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 Diffie-Hellman 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 Diffie-Hellman assumption. Indeed, this cryptosystem in its most basic form is in fact insecure if the Decisional Diffie-Hellman 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 Diffie-Hellman assumption is true; we give strong evidence that the scheme is secure if the weaker, Computational Diffie-Hellman 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 non-standard discrete log and Diffie-Hellman problems
We examine several versions of the one-more-discrete-log and one-more-Diffie-Hellman 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 non-standard problems.  
References:
N. Koblitz, A. Menezes, Another look at non-standard discrete log and Diffie-Hellman problems, J. Math. Cryptology 2 (2008), pp. 311--326
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 Pseudo-Random Number Generator
 
References:
L. Blum, M. Blum, M. Shub, A Simple Unpredictable Pseudo-Random Number Generator, SIAM Journal on Computing 15(2) pp. 364--383
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
Zero-knowledge proofs
A zero-knowledge 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 zero-knowledge proofs) or computationally indistinguishable (computational zero-knowledge 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 691-72
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 low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent 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 non-constant 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/ssl-timing.pdf
Paul C. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, http://www.cryptography.com/public/pdf/TimingAttacks.pdf
Daniel J. Bernstein, Cache-timing 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 private-key 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.1-5.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 "pseudo-random generators", which give us values indistinguishable from truly random ones. In the talk we define pseudo-random 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 k-bit to k-bit 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 non-malleable and secure against chosen-ciphertext 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 "chosen-ciphertext" attacks, and reveal weaknesses of RSA and ElGamal encryption schemes. Then I describe Cramer-Shoup encryption, and prove that if the Decision Diffiee-Hellman Problem is hard, then Cramer-Shoup encryption is indistinguishability-secure from chosen-ciphertext attack.