Title: Constructive aspects of code-based cryptography

Designing efficient and secure code-based cryptographic primitives is a challenging task, since efficiency always comes at some cost in security. In public-key cryptography, the main target is to securely disguise the private code into the public code. These two codes are permutation equivalent in classical public-key cryptosystems, but permutation equivalence turns out to be secure only with Goppa codes.

Using families of codes other than Goppa codes would be advantageous from several standpoints, but stronger disguises than permutations are required. This talk will provide an up-to-date overview of construction techniques for code-based public-key cryptosystems, with focus on LDPC code-based and GRS code-based solutions.

Some possible extensions to digital signatures and private-key cryptosystems will also be discussed.

Title: Introduction to quantum algorithms

Title: Properties of symmetric primes with implications for primality testing for extremely large numbers

Investigation of previously unconsidered properties of twin primes leads to a natural extension -- symmetric primes in power of two intervals. Construction of this class of primes will be discussed and the relationship to strong pseudo-primes and Carmichael numbers. A novel, fast, strong probabilistic primality test based on these principles will be discussed with the implications for cryptography in a post quantum computing world.

Title: Post-quantum cryptography

In this talk we motivate the necessity for post-quantum cryptography. Then we describe the current approaches to come up with post-quantum schemes. In particular, we mention the hash-based, lattice-based, code-based, and multivariate approaches and compare them in regard to their maturity.

Title: A quantum algorithm for computing the unit group of an arbitrary degree number field

Computing the group of units in a field of algebraic numbers is one of the central tasks of computational algebraic number theory. It is believed to be hard classically, which is of interest for cryptography. In the quantum setting, efficient algorithms were previously known for fields of constant degree. We give a quantum algorithm that is polynomial in the degree of the field and the logarithm of its discriminant. This is achieved by combining three new results. The first is a classical algorithm for computing a basis for certain ideal lattices with doubly exponentially large generators. The second shows that a Gaussian weighted superposition of lattice points, with an appropriate encoding, can be used to provide a unique representation of a real-valued lattice. The third is an extension of the hidden subgroup problem to continuous groups and a quantum algorithm for solving the HSP over $\mathbb R^n$. Joint work with Kirsten Eisentraeger, Alexei Kitaev, and Fang Song.

Title: Mathematical problems arising in multivariate cryptography

Multivariate public key cryptosystems have public keys that are multivariate polynomial functions over a finite field. Thus the problem of solving systems of such equations is fundamental to understanding the security of such systems. Analysis of the operational degree of Grobner basis algorithms raises numerous difficult algebraic questions, many of which have remained open for 10 years. We review some of these problems, their importance and recent successes and failures in answering them.

Title: SPHINCS: practical stateless hash-based signatures

Hash-based signatures are currently the most confidence-inspiring replacement for the signature schemes used today. Their security is solely based on the security of the used hash function(s) and can be related to the same by means of standard-model security reductions. Today's hash-based signature schemes have performance close to that of RSA & Co and are currently subject to standardization. The only drawback of hash-based signature schemes in practice is that they are stateful, i.e., the secret key has to be updated after each signature. However, recent results show that this problem can actually be solved while maintaining practical performance and reliable security.

This talk will discuss the basics of hash-based signature schemes. It will cover one-time and many-time signature schemes, Lamports scheme, the Winternitz OTS, Merkle's scheme, and XMSS. Finally, it will be explained how to build practical stateless hash-based signature schemes, explaining the concept of few-time signature schemes and introducing SPHINCS.

Title: On efficient ZK proofs for ideal lattices

Progress in lattice-based cryptography has led to highly efficient instantiations for basic primitives such as encryption or signatures. However, complex primitives such as group signatures or anonymous credentials cannot be realized efficiently from lattices yet. This is partially due to the lack of efficient zero-knowledge proofs of knowledge for lattice based crypto systems. Namely, existing proof protocols only achieve a constant knowledge error, and thus many repetitions of the protocol are required to achieve practical security, resulting in too high computational and communication costs.

In this talk, we will first show how to overcome this constant knowledge error "barrier" for encryption schemes over ideal lattices if one is willing to accept a small soundness gap, achieving an inverse-polynomial knowledge error. We will then modify an existing commitment scheme such that it even supports zero-knowledge proofs with a negligible knowledge error.

Title: Sieving for shortest lattice vectors using fast search algorithms

Many lattice-based cryptographic primitives rely on the shortest vector problem (SVP) on lattices being hard. To assess the computational hardness of SVP and breaking these schemes, one commonly relies on the estimated time complexity of enumeration for solving SVP. In 2001 the breakthrough work of Ajtai et al. showed that SVP can actually be solved faster than with enumeration in high dimensions, using a technique called sieving. Although this technique may have seemed impractical at first, various improvements have since shown that sieving may be practical after all. In this talk we will look at the state-of-the-art in sieving, and how fast search algorithms threaten the dominance of enumeration as the best SVP solver.

Title: Hidden field knapsack problems

In this talk we provide a brief introduction to knapsack problems and we describe a polynomial variant of the Naccache-Stern knapsack cryptosystem (EUROCRYPT '97). The protocol is featured by a similar asymptotic information rate and improved security.

Title: On the existence of semi-regular sequences

Semi-regular sequences over F2 are sequences of homogeneous elements of the algebra B^(n) = F_2[X1,...,Xn]=(X1^2,...,Xn^2), which have as few relations between them as possible. They were introduced in order to assess the complexity of Grobner basis algorithms such as F4 F5 for the solution of polynomial equations. Despite the experimental evidence that semi-regular sequences are common, it was unknown whether there existed semi-regular sequences for all n, except in extremely trivial situations. We prove some results on the existence and non-existence of semi-regular sequences. In particular, we show that if an element of degree d in B^(n) is semiregular, then we must have n<=3d. Also, we show that if d = 2^t and n = 3d there exits a semi-regular element of degree d establishing that the bound is sharp for in finitely many n. Finally, we generalize the result of non-existence of semi-regular elements to the case of sequences of a fixed length m.

Title: Moving towards a quantum-safe cryptographic infrastructure

Impressive progress in developing the building blocks of a fault-tolerant scalable quantum computer indicates that the prospect of a large-scale quantum computer is a medium-term threat that needs to be addressed immediately by developing, deploying and standardizing the necessary solutions. I will highlight some of the recent advances in experimental quantum computing.

Theoretical and software tools for optimizing the utilization of the quantum bits that will be available will also play an important role in determining when quantum computers will be able to implement large quantum algorithms, and I will highlight some examples of these tools.

Title: Bounding HFE with SRA

The Hidden Field Equation cryptosystem (HFE) is a public key encryption scheme whose security relies on the hardness of solving a system of polynomial equations over the finite field $\mathbb{F}_2$. This scheme and its generalizations have attracted a lot of attention by the cryptographic community. Experimental results have shown that HFE polynomial systems are much easier to solve than generic systems, and in fact the parameters proposed in the original HFE cryptosystem can be broken in practice using Groebner basis algorithms. Several theoretical explanations have been provided for this property, but all of them have so far relied on some plausible conjectures or heuristic assumptions.

In this paper, we provide a rigorous bound on the complexity of solving a general class of polynomial systems including HFE systems. Our proof connects the polynomials constructed by Groebner basis algorithms to the partial computation results of the Successive Resultants Algorithm (SRA), a recently introduced algorithm for finding roots of polynomials over finite fields. We believe that our approach could have further applications on similar systems that were recently introduced in connection to the elliptic curve discrete logarithm problem over small characteristic fields.

Title: The simple matrix encryption scheme

Cryptographic techniques are an essential tool to guarantee the security of communication in modern society. Today, the security of nearly all of the cryptographic schemes used in practice is based on number theoretic problems such as factoring large integers and solving discrete logarithms. The best known schemes in this area are RSA, DSA and ECC. However, schemes like these will become insecure as soon as large enough quantum computers arrive. The reason for this is Shors algorithm, which solves number theoretic problems such as integer factorization and discrete logarithms in polynomial time on a quantum computer. Therefore, one needs alternatives to those classical public key schemes which are based on mathematical problems not affected by quantum computer attacks. Besides lattice, code and hash based cryptosystems, multivariate cryptography is one of the main candidates for this. Multivariate schemes are very fast and require only modest computational resources, which makes them attractive for the use on low cost devices like smart cards and RFID chips. However, while there exist many practical multivariate signature schemes (UOV, HFEv- Rainbow), the number of efficient and secure multivariate encryption schemes is somewhat limited. At PQCrypto 2013, Tao et al. proposed a new kind of multivariate encryption scheme, called the Simple Matrix (or ABC) encryption scheme, which resists all known attacks against multivariate schemes. Furthermore, since the decryption process involves only the solution of linear systems, the scheme is very efficient. On the downside, decryption errors occur with non-negligible probability and the key sizes of the scheme are relatively large. In this talk we give an overview on the original Simple Matrix scheme and improved variants of the scheme proposed later.

Title: SVP in 2^n time using discrete Gaussian sampling

We give a 2^{n+o(n)}-time algorithm for the shortest vector problem on lattices. The previous best-known algorithm of Micciancio and Voulgaris runs in time 2^{2n+o(n)}. The algorithm is based on an elementary yet powerful observation that by properly combining samples from a Gaussian distribution on the lattice, we can produce samples from a *narrower* Gaussian distribution on the lattice. Our primary technical tool is a method that allows us to use black-box access to some distribution on a finite set to relatively efficiently output the "squared distribution" (i.e. the distribution that assigns to each element i a probability proportional to the square of its probability in the original distribution). Time permitting, we will also show how to find somewhat short vectors in time roughly 2^{n/2}.

Title: Attacking binary elliptic curves on a quantum computer: on quantum arithmetic and space-time trade-offs

Implementing finite field arithmetic on a quantum computer is a non-trivial matter. The issue is that the requirement for any computation to be reversible makes it difficult, if not prohibitive, to apply many classical methods for fast arithmetic as they either lead to large space overheads or are not input-oblivious. Here ``large'' is considered to be anything that scales superlinear in the bit-size of the inputs which is motivated by the slow scaling of the underlying quantum hardware. In this talk, we focus on the binary case where suitable choice of basis leads to efficient circuits for field multiplication. Furthermore, the Itoh-Tsujii method can be adapted to the quantum case, leading to efficient circuits for inversion. We then discuss various representations of binary elliptic curves and the resulting cost in the quantum circuit model when implementing Shor's quantum algorithm to find dlogs in the group generated by an elliptic-curve point. Based on joint work with Rainer Steinwandt (Florida Atlantic): arxiv:1306.1161

Title: Best known attacks on code-based cryptosystems: state of the art and perspectives

One of the keys to understand the security of code-based public key encryption or digital signature is the security reduction. It tells us that an adversary must be able (computationally) either to decode in a generic linear code or to unveil (part of) the hidden structure of the code. This hidden structure, the trapdoor, gives access to a low cost decoder, and should be available to the legitimate user only. We review here what are the best attacks on the message (decoding) and the best attacks on the public key (dintiguisher or, best, key recovery). The ultimate purpose is to understand what is the good practice to design secure code-based cryptosystems.

Title: NTRU and Lattice-Based Cryptography: Past, Present, and Future

In this talk I will present a brief historical survey of the mathematical theory of lattices and their use in cryptography. This will include a discussion of fundamental lattice problems (SVP and CVP), lattice reduction, the GGH and NTRU lattice-based public key cryptosystems, and recent work on the use of rejection sampling to create lattice-based digital signature schemes that are secure against transcript attacks.

Title: Authenticated Key Exchange from Ring Learning with Errors

We present a protocol for authenticated key exchange (AKE) using techniques similar to the HMQV protocol. The security of our protocol is based on the hardness of the ring learning with errors (rLWE) problem. Our system does not rely on other cryptographic primitives. In particular, it does not require cryptographic signatures, greatly simplifying the protocol and resting the security solely on the underlying rLWE instances. Our security proof uses a version of the Bellare-Rogaway model, with enhancements to capture weak Perfect Forward Secrecy.

Title: MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems

Multivariate polynomial (MP) problem is the basis of security for potentially post-quantum cryptosystems. The hardness of solving MP problem depends on a number of parameters, most importantly the number of variables and the degree of the polynomials, as well as the number of equations, the size of the base field etc. When the degree is two, we investigate the relation among these parameters and the hardness of solving MP problem, in order to construct hard instances of MP problem. These instances are used to create a challenge, which may be helpful in determining appropriate parameters for multivariate public key cryptosystems, and stimulate furthermore the research in solving MP problem.

Title: Multivariate Cryptosystems and Their Security: Current Estimates

Multivariate or Multivariate Quadratic Public-Key Cryptosystems (sometimes MPKC or MQPKC) dates back to the early 1980's and form one of the 4 main branches of post-quantum public-key cryptography.

MPKC as an area probably has an undeserved bad reputation because many designs are published and then broken, with the last well-known case being SFLASH (C*-, or C-star-minus) broken in 2008, one decade after its introduction. Still, several MPKCs have been around for more than a decade with no obvious problems. We review the main security concerns for MPKCs and give some updated security estimates together with parameters.