Spring School on Symmetric Cryptography

This is part one of a two-part blog post collaboratively written by Matthias and Ralph.

The Spring School on Symmetric Cryptography takes place at Beckmanns Hof just one minute south of Ruhr University Bochum.
The Spring school, which can be seen as a supplementary event for FSE 2016 next week, lies literally on the verge of the botanical garden of Bochum!

The Spring School's program covers lectures on the theory of "Boolean Functions" and "Statistical Models" in symmetric cryptography. Additionally there are exercises to gain a firm understanding thereof which were compiled by Anne Canteaut and Celine Blondeau.
The theoretical part is supplemented by the more practically oriented talks of the invited researchers Joan Daemen and Ventzi Nikov.


For the lecture on "Boolean Functions" Anne Canteaut preferred a sympathetic, old-fashioned presentation with chalk on black board in the lecture hall over an overhead presentation in the modern seminar room.

The topic ranged from Boolean functions and their algebraic normal form to the interpretation as Reed–Muller codes. Then the Walsh transform was introduced as a tool to analyze and approximate Boolean functions by linear ones.


In the lecture on "Statistical Models" Celine Blondeau (lecture notes here)
reminded us of basic probability distributions well known to statisticians and we explored some of their uses in cryptography. The discussion lead us from Binomial-, Poisson-, Normal- over Chi-Square- and Hypergeometric distributions to the study of Kullback-Leibler divergence and the applications for i.e. Linear attacks, Differential attacks and Impossible differential cryptanalysis. She also gave directions of ongoing work in that field.

The advantages of "Permutation Based Cryptography" were presented by Keccak (SHA-3) and Rijndael (AES) (co-)designer Joan Daemen.


The talk about "Threshold Implementations" by Ventzi Nikov covered techniques to decompose (non-linear) functions to separate the inputs from intermediate results and masking.
The key-values are masked by splitting up function inputs into separate shares such that knowledge of less than all shares does not allow to recover the value.

Matthias and Ralph will stay tuned for some S-Box theory and the statistical wrap-up on Saturday morning and the slides and recorded videos of this Spring School will soon be available at the official website.

Sixth Bar-Ilan University Winter School on Cryptography (Part 1)

This two-part blog post has been collaboratively written by Eduardo, Marie-Sarah, Matthias and Ralph.

Earlier this month, from 4-7 January, a few ECRYPT-NET fellows and about a hundred others attended the Bar-Ilan University winter school on cryptography. It took place in Ramat Gan, a suburb of Tel Aviv, at the Kfar Maccabiah hotel and conference centre (named after the Maccabiah, or Jewish Olympics, that take place there every four years). The school was intense, but well organized. It was split into two parts, verifiable computation and special encryption, and so will be our coverage of it.

Part 1: Verifiable Computation

Michael Walfish, Yael Tauman Kalai, and Eran Tromer guided us through methods for verifying the outsourced computation of functions. We particularly appreciated the crystal-clear overview of all sessions, given by Michael Walfish, that emphasized how the content of the talks fit together.

Let's set the scene for verifiable computation: a client (the verifier) wants to outsource the computation of a function f to a server (the prover) who has more computing resources. But how does the verifier know that the value returned by the prover is actually the result of applying the function f to the purported inputs? A malicious or a lazy server could indeed modify the process to gain some advantages as, for instance, reducing the cost of operating a system.

Verifiable computation of f(x) comprises the following two phases:

1. Program representation (or arithmetization): The verifier (or a party he trusts) expresses the function f as a set of arithmetic constraints over a field, in terms of the input x, output y, and intermediate variables z. Each of these x, y, and z may be vectors, e.g., x=(x₁,x₂,x₃). Typically, the format these constraints needs to have is that of degree-2 polynomials that equal 0 when they (and the function f) are satisfied.
2. Solving and proving: The server must prove to the client that the solution it returns, y, is correct. The landscape of proof protocols shows a trade-off between efficiency, expressiveness and additional properties like zero-knowledge or non-interactivity. The speaker himself recently wrote a survey which is a very nice introduction to the state of the art and these trade-offs.

Yael Kalai's talks took a more theoretical approach, guiding us through the evolution of Probabillistically Checkable Proofs (PCPs). She emphasized the importance of "good" security assumptions, where "good" requires at least, and according to her point of view, that the underlying assumptions can be efficiently falsified. These theoretical worries were well founded, as most of today's verifiable computation protocols rely on SNARKs (standing for Succint Non-interactive ARguments of Knowledge) which cannot be proved secure via black-box reductions from (efficiently) falsifiable assumptions. 

Yael's talks provided also very interesting and intuitive examples. To give one, suppose that Peggy and Victor are playing chess. After a number of moves, Peggy (the prover) wants to prove to Victor (the verifier) that she has a checkmate. If Victor fails to see it, it is for Peggy easier to convince him by continuing the game (an interactive proof) until he does, rather than to explain all the possible combinations of moves without moving any piece (a non-interactive proof). This intuition of the power of interaction extends to the rest of the proof systems. Finally, she even showed us how the subject fits in the quantum framework, introducing us to the notion of non-signalling adversaries.

Eran Tromer recovered the line of Michael Walfish and focused on the details of SNARKs and how they are actually constructed. Among others, he has been writing libsnark, a C++ library that is used a lot for verifiable computation systems relying on SNARKs. He also showed us a potential application for them, called Zerocash. Zerocash is a protocol that provides a privacy-preserving version of Bitcoin. In contrast to Bitcoin, where all the transactions are public in the block chain, Zerocash does not contain information about the payment’s origin, destination or amount. The correctness of the transaction is guaranteed via a zero-knowledge proof. More details can be found here.

Part 1.5: Excursion to Caesarea and Binyamina Winery

Sun starting to go down in Caesarea.

Tuesday afternoon, we made an excursion to the remains of Caesarea, a Roman city on the Mediterranean coast that was built by Herod over 2000 years ago. To say that it had a tumultuous history would be an understatement. Our tour included a walk through a "graveyard" of columns and capitals, the amphitheatre (whose first row is still intact), and the hippodrome.

Next, we took an informative tour of the Binyamina winery. We learned that grapes are crushed with a flexible rubber material to simulate the skin of feet. For red wine, the grapes are fermented (skin, seeds, and all) before being crushed. For white wine, seeds and skin are removed (by sedimentation) after pressing, then fermented. The tannin (bitter-tasting substances) in wine comes from the seeds, skin, and maybe the material of the barrel in which it is matured. Whether wine is aged or matured in an American oak (sweeter) or French oak (more tannins, adds more complex flavours) barrel affects the final product. Tannins prevent oxidation, so red wine (with more tannins) can be matured longer. Stopping fermentation early makes wine more sweet.

After learning how wine is made, we concluded the day by learning how it tastes (using our five senses!) and enjoying a generous dinner.

Stay tuned for the second and last part of the post!

School on Design and Security of Cryptographic Algorithms and Devices 2015

Between the 18th and the 23rd of October 2015 took place the fourth School on Design and Security of Cryptographic Algorithms and Devices. This year's location was Chia Laguna, Sardinia (Italy), and most importantly, this was also the first networking event for all the new Early Stage Researchers involved in the ECRYPT NET.

We were, anyway, not alone. Around ninety people attended the school, which had a programme  mostly focused on private-key cryptography, from different approaches (software implementation, provable security, side-channel attacks, lightweight ciphers and practical sessions). I would like to take advantage of this blog post to thank all of the speakers for their talks, as they were able to make them interesting and understandable for those of us coming from a predominantly public-key mindset. Personally, I enjoyed Christian Rechberger's talk 'Symmetric Cryptography with Few Multiplications', where he introduced his work on block ciphers designed with Multi-Party Computation, Fully Homomorphic Encryption and Succinct Non-Interactive Arguments of Knowledge. I think interdisciplinarity is one of the most positive and stimulating aspects of research, and it was nice to see people stepping forward to bring closer the private-key primitives and the public-key protocols communities.

Talks are always the main ingredient of a School, but not the only one. A lot of discussion took place during the meals and after the scheduled programme, which also included a gap on Wednesday afternoon to visit Cagliari or Is Zuddas. Some of us made the most out of our location and walked around the hotel or took a swim in the close beaches. 

On Thursday we had the ECRYPT NET kick-off meeting, where we, its members, got to know each other better.  I was delighted to verify that our group enjoys very diverse backgrounds and how our different, yet related projects join us together. We also learned about our future meetings, schools, workshops and responsibilities and even if this was slightly daunting for some of us, I got an incredible feeling of amazement. I hope that our upcoming posts will give you, at least in a smaller dose, this feeling!

Hit the road, ECRYPT fellows! Credit: Marie-Sarah

PS: As this is an European project, formed by world-wide citizens and nationalities, I think that a cultural share is also important to build a sense of community. So I hope you enjoy this excerpt of "Proverbios y Cantares", from Antonio Machado, that I feel it is a good first step on our new trip.

Caminante son tus huellas ..... The road you march, lonely wanderer
El camino, y nada más ..... It’s just your tracks, nothing much.
Caminante no hay camino ..... There is no road, lonely wanderer
Se hace camino al andar ..... The road is made as you march.
Al andar se hace camino ..... As you move on paths appear
Y al volver la vista atrás .... And upon glancing behind,
Se ve la senda que nunca ..... You contemplate lanes and byways
Se ha de volver a pisar ..... Where you shall never go back.
Caminante, no hay camino ..... There is no road, lonely wanderer
Sólo estelas en la mar ..... Just wakes at sea, only that.

from "Proverbios y cantares" in Campos de Castilla. 1912