soft skills, hard facts

Within the ECRYPT-NET program we have the chance to learn effective communication of scientific results. Although often regarded as "soft skills", thus indicating their lesser value compared to the classical "hard skills", these methods are versatile. Obtaining them means being able to apply the techniques to either written or oral presentations.

In particular at the School on Design for a secure Internet of Things our oral presentation training started with practical sessions. Classical topics like how to deal with stage fright and non-verbal communication such as body language were demonstrated and different ways to know and connect to the audience were addressed.

Among others, we spoke detailed about posture, use of voice, articulation on the one hand and style, amount of information per presentation slide as well as how to present in a lively way yet giving a memorable take-home message on the other hand.

Later this year, during the Cloud Summer School recently in Leuven we had the chance to actively participate the practical training session on academic writing to concisely yet accurately convey future research findings. Our trainer taught us how to chop-up long, unwieldy sentences into more easly digestible ones by reorganizing competing foci and effectively conveying the essence. Showing worked examples from our area and even some excerpts of our own texts definitely helped in understanding the concepts.

There, all of us ECRYPT-NET early stage researchers gave their (possibly first, big) presentation and we received feedback from the board and our individual supervisors. The combined, but especially the individual, feedback of good choices and less fortunate formulations were brought up.

As we'll have more and more tasks to work on as a group coming up in our career, developing an efficient work-flow for joint-documents is not to be considered wasted effort and time. Thus, soon we'll have the chance to obtain more soft-skills that can turn out to be useful in a dynamic setting.

I want to take the opportunity to organize a workshop as a follow-up event of the upcoming Passwords2016-conference for us ESRs. The plan is to have a day of sessions and meetings in Bochum on Thursday, 8.12.:

It'll be co-located with the 11th International Conference on Passwords, where you can listen to the Long Story of Password (Re-)use, learn Password Hardening techniques, debate whether new Password Management strategies based on Episodic Memories or Through Use of Mnemonics is revolutionary and find out about the Hopes and Fears of Mobile Device Security.

About 100 international participants from academia, companies, ... will come and follow the conference program, which is a mix

of classical talks and more practical "hackers sessions", showing attacks in the real-world setting.

Unfortunately there is no detailed program available yet, but soon for sure.

However, the registration is open now until 2016-11-30.

For those interested to join this event, try to save some € by obtaining the early bird offer (only until 2016-10-31).

Ruhr-University seen from Beckmanns Hof

All other fellows are warmly invited to come on Wednesday, 7.12 after the Passwords2016-talks for a first ECRYPT-NET get-together in Bochum and our program tailored to the upcoming writing project.

Thursday, 8.12 is the main day which we will start off by a workshop followed by project-oriented brainstorming and group discussions.

We'll have an expert training on collaborative creative writing and group

communication (in English), working in nice atmosphere close to Bochum's botanical gardens.

In short, in this workshop the focus lies on how to get things done, collaboratively. The technical aspect will be covered by a git repository with the projects' skeleton, that I set up here on a RUB-Server, where one can get a git account even as a RUB-external.

If you need a refresher, reread Ralph's blog post about git basics.

I am looking forward welcoming all of you here.

Supersingular isogeny Diffie-Hellman

Supersingular isogeny Diffie-Hellman (SIDH) is a relatively recent proposal for a post-quantum secure key-exchange method which I will briefly outline here.

Most post-quantum cryptography is based on lattices, codes, multivariate quadratics or hashes. See Gustavo's post for more.

A fifth category seems to slowly establish itself: Isogeny-based crypto.

These schemes are based on the difficulty of finding an isogeny between two supersingular elliptic curves. Isogenies are specific rational maps between elliptic curves which must also be a group homomorphism for the group of points on the curve.

The original proposal [Stolbunov et al., 2006] was to use the problem of finding isogenies between ordinary elliptic curves but this system was shown to be breakable with a quantum computer [Childs et al., 2010]. After that it was proposed to use supersingular elliptic curves instead [De Feo et al., 2011].

SIDH currently has significantly worse performance than lattice based key-exchange schemes but offers much smaller key-sizes. Compared to Frodo it is 15 times slower but the key size is only one twentieth. Compared to NewHope it is over 100 times slower at less than one third of the keysize. This can be relevant in scenarios like IOT where cryptographic computations require orders of magnitude less energy then actually transmitting data via the radio.

Although finding isogenies between curves is difficult, Vélu's formulas allow calculating an isogeny with a given finite subgroup as its kernel. All such isogenies are identical up to isomorphism.

Now, starting with a public curve \(E\) that is a system parameter we have both parties, Alice and Bob generate an isogeny for kernels \(\langle r_a \rangle, \langle r_b\rangle\) respectively. Let \(r_a, r_b\) be any generators of a subgroup for now. This gives us two isogenies
$$ \phi_a: E \rightarrow E_a\\
\phi_b: E \rightarrow E_b.$$
Now we  would like to exchange $E_a, E_b$ between the partners and somehow derive a common $E_{ab}$ using the kernels we have used. Unfortunately, $r_a$ does not even lie on $E_b$ so we have a problem.

The solution that was proposed by De Feo et al. is to use 4 more points $P_a, P_b, Q_a, Q_b$ on $E$ as public parameters, two for each party. This allows constructing
$$r_a = m_aP_a + n_aQ_a\\
r_b = m_bP_b + n_bQ_b$$ using random integers $m_a, n_a, m_b, n_b$ appropriate for the order.
Now, after calculating the isogenies $\phi_a, \phi_b$ the parties not only exchange the curves $E_a, E_b$ but also $\phi_a(P_b), \phi_a(Q_b)$ and $\phi_b(P_a), \phi_b(Q_a)$.
Looking at the example of Alice she can now calculate
$$m_a\phi_b(P_a)+n_a\phi_b(Q_a) = \phi_b(m_aP_a + n_aQ_a) = \phi_b(r_a)$$ and Bob can perform the analogous computation. Constructing another isogeny using this $\langle \phi_b(r_a) \rangle$ and $\langle \phi_a(r_b) \rangle$ respectively gives Alice and Bob two curves $E_{ba}, E_{ab}$ which are isomorphic and their j-invariant can be used as a common secret.

I will leave you with this wonderfully formula laden image from the De Feo et al. paper showing the protocol.

Quantum computation, algorithms and some walks.. pt.1

During the last meeting of the ECRYPT-NET project in Leuven, I gave an introduction to Quantum Algorithms. In the first part, I explained quantum computation, it is natural that we need to have a base. In this post, I will give more detailed explanation of it. First, we need to understand the concept of superposition in quantum physics. To achieve this, we are going to go back to the idea from Schrödinger, i.e., a cat that may be simultaneously both alive and dead. This phenomenon is called superposition in quantum physics and quantum computers take advantage of this. If you are interested about how physically implement a quantum processor you can see at [2].

Well, computers aren't made with cats inside. Computers use bits and registers to work. So, how is it possible to compute with a quantum computer? How is it possible to represent bits? How is it possible to take advantage of the superposition?

Quantum Notation

First, let's learn about the Dirac notation, that is commonly used in Quantum physics and in most of the literature about quantum computers.  Since Blogger doesn't allow me to create mathematical equations, I will get some help from physciense blog and pick some images from them:

 
The Dirac notation could be a little bit different. If you want to check about it, I selected some nice lecture notes in the following links: Lecture 1 and Lecture 2.

So, the bra-ket notation is just vectors and we are going to use this to represent our qubit, yes we call the bit of a quantum computer by this name. In classical computers we represent a bit with 0 and 1 but in quantum computers it is a little bit different. We can represent the states as follows:

As the image show to us, the qubit is 0,1 or a superposition of 0 and 1. However, if we measure, i.e., if we see the qubit we lose the superposition. In other words, our state collapses and we cannot take advantage of the superposition anymore. In the same way that in classical computers we have gates, the quantum computer also has gates. One very famous gate is the Hadamard gate. This gate has the property to put a qubit in the superposition state. We can see the action of this gate in the following image:

Quantum Algorithms

Now, we know what is a qubit and how we can operate with it. We can move for the next step and create some algorithms to solve problems. The most common and very well-known example came from Deutsch and Jozsa. It is known by Deutsch-Jozsa problem and consist of:

• Input:  f: {0,1}^n to {0,1} either constant or balanced
• Output:   0 iff the function f is constant
• Constraints: f is a black-box

In the classical computers we can represent this problem such as:

If we solve this problem with a quantum computer, we are going to make exactly 1 query. The function f will be implemented as a black-box in the quantum computer and it will be:

However, if we just use this implementation, it is not enough to solve the problem. In order to solve this, we are going to create a quantum circuit and use Hadamard gates. In fact, the Hadamard gates are going to help us to take advantage of the superposition. We are going to have this circuit:

Now, we have the circuit to determine if a function is constant or balanced. Nevertheless, how do  we compute this circuit? How does it work? In order to answer these questions, we work out the qubit after each gate. In the end we have the final measure. Suppose that we just have one qubit and we start it in state 0 and pass through it the first gate. We are going to have this:

 After this, we can see that we put our qubit in a superposition state. Now, we go to our function and call our black box. The result of it can be seen as:

The third step, we are going to use the interferences to "reconstruct" the qubit. In the last step, we are going to compute now the last gate and see what is "expected" when we measure:

In the end, we have that final state, i.e., if the function is constant "f(0)=1" then we are going to have the result as qubit in 0. However, if the function is balanced "f(1)=1" then we are going to have the qubit in 1. The algorithm can be generalized and it works for a system with "n"-qubits. It is possible to find more information in [1]. Also, you can check this class.

In my next blog entry, I will talk about  Shor's, Grover's algorithms and Random quantum walks. However, we just saw the begging of quantum algorithms. If you want more information about it, you can check the slides from my presentation in Leuven on my website.

[1] David Deutsch and Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A.

[2] Gambetta, Jay M., Jerry M. Chow, and Matthias Steffen. "Building logical qubits in a superconducting quantum computing system." arXiv preprint arXiv:1510.04375 (2015).