Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus
Cryptology Seminar
Wednesday: 14:15 - 15:45, room 0086
Seminarium poświęcone kryptologii.
table edited by: Michał Staromiejski
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.  
  • 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.  
  • 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).  
  • 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.  
  • 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.  
  • 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.  
  • 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.  
  • 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.  
    Kamil Sałaś
    Simple Unpredictable Pseudo-Random Number Generator
  • 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,
    Robert Obryk
    Electronic money
    Michał Staromiejski
    On Shoup's lower bound technique for generic algorithms for discrete logarithm problem
    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.  
    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.  
  • 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.  
  • 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.  
    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.  
  • Daniel R. L. Brown, Breaking RSA May Be As Difficult As Factoring, Cryptology ePrint Archive: Report 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.  
  • David Brumley, Dan Boneh, Remote timing attacks are practical,
  • Paul C. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems,
  • Daniel J. Bernstein, Cache-timing attacks on AES,
  • 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.  
    Konrad Ozimek
    Block ciphers
    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.  
  • 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.  
  • O. Goldreich, Foundations of Cryptography vol. 1 - Basic Techniques, chapter 3
  • 03.04.2014,
    Damian Królik
    Michał Staromiejski
    Bezout theorem and associativity of addition on elliptic curves
    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.  
  • M. Bellare, P. Rogaway, Optimal Asymmetric Encryption - How to Encrypt with RSA,
  • 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.  
      webmaster: email = a@b, a=www-tcs,