ECC 2018 Program

November 19 2018 (Mon) (8 talks)

(Download all slides)

08:30 - 09:00 Registration
09:00 - 09:20 Opening Remarks
09:20 - 11:00 Isogeny-Based Cryptography (1) (Chair: Tsuyoshi Takagi)
09:20 - 10:10

David Jao(University of Waterloo/evolutionQ, Inc., Waterloo): Implementing Supersingular Isogeny Cryptography
Abstract:
Recent years have seen dramatic progress and improvements in the implementation of supersingular isogeny-based cryptosystems. In this talk we provide an overview of results obtained to date, and discuss the near-term viability of supersingular isogeny cryptography on constrained and embedded hardware platforms.

[Slide] [Video]
10:10 - 11:00

Travis Morrison(The Pennsylvania State University): Computing Isogenies and Endomorphism Rings of Supersingular Elliptic Curves

[Slide] [Video]
11:00 - 11:20 Coffee Break
11:20 - 12:40 Block Chain (Chair: Kazumasa Omote)
11:20 - 12:10

Eiichiro Fujisaki(JAIST): Ring Signatures for Blockchain
Abstract:
Traceable ring signatures were proposed in PKC 2007. Recently, it was implemented in one of blockchain-based cryptocurrencies. We review traceable ring signatures and discuss how it can be used in the blockchain technology.

[Slide] [Video]
12:10 - 12:40

Roger Wattenhofer(ETH Zurich): The Role of Cryptography in Distributed Systems
Abstract:
Distributed protocols often employ some form of cryptography, in particular digital signatures. In my talk I would like to shed some light on the role of cryptography in distributed systems. I will start out with some examples of distributed protocols with and without cryptography: consensus, byzantine agreement, blockchain. This brings us the interesting question to what degree cryptography is needed: What distributed problems can or cannot be solved without cryptography, and what is still unknown?

[Slide] [Video]
12:40 - 13:40 Lunch Break
13:40 - 15:20 Beyond ECC (Chair: Tanja Lange)
13:40 - 14:30

Pierrick Gaudry(LORIA): Point Counting on Hyperelliptic Curves of Genus 3 and Higher in Large Characteristic
Abstract:
In this joint work with Simon Abelard and Pierre-Jean Spaenlehauer, we study the complexity of counting points on hyperelliptic curves with the family of methods derived from Schoof's algorithm. Our focus is mostly on the polynomial systems of equations used to model the torsion subgroups and their specificities. Depending on the context (genus 3 or higher; complexity result or practical computation), we use different tools: resultants, Groebner basis or geometric resolution. Using the multi-homogeneous nature of the systems, we show that the main exponent in the complexity grows linearly with the genus, while the previous best algorithm with this respect had an exponent quadratic in the genus. In the particular case of genus 3, we use an ad-hoc approach to the resolution, and show that in the case of curves with explicit real multiplication, the complexity can be significantly reduced and practical experiments are feasible.

[Slide] [Video]
14:30 - 15:20

Divesh Aggarwal(National University of Singapore): A New Public Key Cryptosystem Based on Mersenne Numbers
Abstract:
In this work, we propose a new public-key cryptosystem whose security is based on the computational intractability of the following problem: Given a Mersenne number p = 2^n - 1, where n is a prime, a positive integer h, and two n-bit integers T, R, decide whether their exist n-bit integers F, G each of Hamming weight less than h such that T = F R + G modulo p.

[Slide] [Video]
15:20 - 15:40 Coffee Break
15:40 - 17:20 Fundamental (Computer algebra to Quantum Computer) (Chair: Akira Otsuka)
15:40 - 16:30

Nobuyuki Imoto(Osaka University): Quantum Information Processing --- Similarities and Differences with Classical Information Processing
Abstract:
Quantum information processing, which is rapidly attracting attention in recent years, started around 1985. The purpose is the same. Quantum computation is a mean to realize faster computation. Quantum cryptography is a mean to realize more secure communication. The means are, however, different. We use quantum parallelism in quantum computation, and unavoidable quantum back action in detecting eavesdropping and distilling secure keys in quantum cryptography. The ingredients we use in quantum information processing are different from classical information processing. We use superposition of states and entanglement (= quantum correlation) between different qubits. The main obstacles that are common to classical and quantum technologies are noise and loss. Classically, a number of methods have been established such as error correction codes, repeaters (discriminating and regeneration of bits), and classical encryption algorithms. We also have quantum version of these: error correction codes, quantum repeaters, and quantum key distribution. Something uncommon is decoherence. We need to maintain the superposition and/or entanglement under noise and loss. I will explain these and introduce our efforts to cope with these problems including recent results. Something that needs to be improved, I feel, is that there have been little interaction between classical information and quantum information communities. Since the two areas are closely related, we definitely need more cooperations.

[Slide] [Video]
16:30 - 17:20

Henri Cohen(Université de Bordeau): Point Counting on Quasi-Diagonal Hypersurfaces
Abstract:
A quasi-diagonal hypersurface has a projective equation of the type $\sum_{1\le i\le m}a_ix_i^m-b\prod_{1\le i\le m}x_i=0$. The goal of this talk is to give a number of methods for computing its number of points over a finite field ${\mathbb F}_q$ and to compare their speed. The conclusion is that the best method is to use the $p$-adic Gross--Koblitz formula.

[Slide] [Video]
19:00 - 21:00 Banquet


November 20 2018 (Tue) (3 talks)


09:00 - 09:50 ECC implementation (Chair: Ryuichi Sakai)
09:00 - 09:50

Bo-Yin Yang(Institute of Information Science, Academia Sinica, Taiwan): Lower-Level Verifications for Cryptographic Software Involving Elliptic Curves and Others
Abstract:
It is naturally important for Cryptographic Software to be correct. However, one problem is that much of cryptographic implementations have as their central parts complicated arithmetic routines written in hand-crafted assembly, which makes the task difficult. We detail a sequence of work which tries to make this process easier and semi-automated, and show its applications to Elliptic Curves and even post-quantum instances.

[Slide] [Video]
09:50 - 10:10 Coffee Break
10:10 - 11:30 Post-Quantum and Privacy-Enhancing Cryptography (Chair: Kwangjo Kim)
10:10 - 10:40

Tsuyoshi Takagi(University of Tokyo): Recent Developments in Post-Quantum Cryptography
Abstract:
The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this talk, we give an overview of recent developments on post-quantum cryptography. In particular, we explain about the computational problems used in multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.

[Slide] [Video]
10:40 - 11:30

Sherman Chow(Chinese University of Hong Kong): Privacy-Enhancing Signatures

[Slide] [Video]
11:45 - 20:00 Excursion, Dinner and Rump session at Nara Park


November 21 2018 (Wed) (4 talks)


08:50 - 10:30 Homomorphic Encryptions (Chair: Serge Vaudenay)
08:50 - 09:40

Yongsoo Song(Microsoft Research, Redmond): Design and Application of Approximate Homomorphic Encryption
Abstract:
Homomorphic Encryption (HE) is an ideal solution for secure storage and non-interactive for outsourced data, however, its huge time/space complexity is the main bottleneck of applying HE in practice. This talk presents recent researches on an HE scheme of Cheon et al. (Asiacrypt’17), its bootstrapping method (Eurocrypt’18), as well as some applications in machine learning (CCS’18). This scheme supports an approximate rounding (extraction of MSBs) operation which brings a significant improvement in both efficiency and versatility of homomorphic operations over the real/complex numbers.

[Slide] [Video]
09:40 - 10:30

Goichiro Hanaoka(AIST): Practical Two-level Homomorphic Encryption in Prime-order Bilinear Groups

[Slide] [Video]
10:30 - 10:50 Coffee Break
10:50 - 12:30 Isogeny-Based Cryptography (2) (Chair: Shinya Okumura)
10:50 - 11:40

Chloe Martindale(Technical University of Eindhoven): CSIDH: An Efficient Post-Quantum Commutative Group Action
Abstract:
We present CSIDH, an isogeny-based scheme suitable for non-interactive key exchange in a post-quantum setting. We will explain the scheme and some background on isogeny graphs of supersingular elliptic curves necessary to understand how the scheme works. The CSIDH construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has very short public keys. This is joint work with Wouter Castryck, Tanja Lange, Lorenz Panny, and Joost Renes.

[Slide] [Video]
11:40 - 12:30

Katsuyuki Takashima(Mitsubishi Electric Corp): One-Round Authenticated Group Key Exchange from Isogenies
Abstract:
We propose two one-round authenticated group-key exchange protocols from newly employed cryptographic invariant maps (CIMs): one is secure under the quantum random oracle model and the other resists against maximum exposure where a non-trivial combination of secret keys is revealed. The security of the former (resp. latter) is proved under the n-way decisional Diffie-Hellman (resp. n-way gap Diffie-Hellman) assumption on the CIMs in the quantum random (resp. random) oracle model.
We instantiate the proposed protocols on the hard homogeneous spaces with limitation where the number of the user group is two. In particular, the protocols instantiated by using the CSIDH, commutative supersingular isogeny Diffie-Hellman, key exchange are currently more realistic than the general n-party CIM-based ones due to its implementability. Our two-party one-round protocols are secure against quantum adversaries.
We also propose other authenticated key exchange and group key exchange protocols from the SIDH protocol. The proposal of our SIDH-based group key exchange is joint work with Satoshi Furukawa and Noboru Kunihiro, and the rest of this talk is joint work with Atsushi Fujioka, Shintaro Terada and Kazuki Yoneyama.

[Slide] [Video]