Monday, May 16, 2016

EuroCrypt 2016 - a post about two talks

This post is about two interesting talks I attended at Eurocrypt 2016 in Vienna.

A well-structured talk has been given by Shota Yamada from the AIST (Japan), who presented two adaptive-secure Identity-Based Encryption schemes, both constructions being based on lattices. Identity-Based Encryption generalizes the public-key encryption paradigm by addressing the problem of simplifying the public-keys; it does this by storing some unique information about owner's identity: for instance, an email addresses or a phone number (referred to as identities).

In his paper, Yamada presents two adaptive-secure IBE constructions from lattices (we omit the details of construction). They follow the usual way of setting-up IBEs based on lattices. The secret-key corresponding to an identity ID of length $k$ is generated as $(A|H(ID)) \vec{e} = \vec{u}$ $mod$ $q$, where H maps the ID to a matrix of size $n \times m'$ and $A$ is $n \times m$. A ciphertext w.r.t. an ID includes $s^T(A|H(ID)) + (x_1^T|x_2^T)$. The novel part of Yamada's work is a technique allowing for improvement in the direction of reducing the size of the (master) public-key, based on which the function $H$ is computed. In a lattice based construction, one way to define it is: $H(ID) = B_0 + \sum_{i\in[1,k]\land ID_i=1} B_i$. The new idea uses the gadget matrix $G^{-1}$ and samples $2l = 2 \sqrt{k}$ matrices instead of $2k$; it also sets up $H(ID) = B_0 + \sum_{(i,j) \in S(ID)} B_{1,i} \cdot G^{-1}(B_{2,j})$, where $S$ is an injective map between IDs and $2^{[l] \times [l]}$. As a slide remark, one can further reduce the number of matrices from $O(k^{1/2})$ to $O(k^{1/d})$. In terms of efficiency, the size of the public parameters are $\tilde{O}(n^2 \cdot k^{1/d})$, therefore reducing the dimension of the master public key and allowing for faster encryption relative to an identity, while the size of the secret-key and ciphertexts have the same order of magnitude as the recent IBEs obtained from lattices.

Another noticeable presentation has been delivered by Igors Stepanovs (UCSD) about his joint work with Brent Waters and Mihir Bellare. The problem they tackled was the existence of differing-inputs obfuscation (diO). This work is related to the one of Garg, Gentry, Halevi and Wichs, who showed (Crypto 2014 paper) that the existence of "special purpose" obfuscation implies a negative result for the existence of diO.

In short, diO is a relaxation of indistinguishability obfuscation: while $iO$ asks that two obfuscated programs to be indistinguishable and produce the same results when evaluated at all inputs, the diO allows for inputs for which the two circuits are not equivalent (differing inputs), but it requires that it is computationally hard to find such inputs. The result of their work states that assuming sub-exponentially secure OWF, then we sub-exponentially secure diO for DTMs does not exist. A similar negative result for diO holds even if we assume that sub-exponentially secure iO exist.

These were just two interesting results, sampled from the set of "public-key" related talks, presented at EuroCrypt 2016.

Friday, May 13, 2016


I am writing this post on the plane, while coming back to Paris from Vienna, where I attended EUROCRYPT with a nice group of colleagues from ENS Paris. It was my first conference and really a magnificent experience: I am really glad I had the opportunity to spend some days attending interesting crypto talks, meeting new people, discussing possible new ideas and visiting such a beautiful city.

As I said, we had the opportunity to listen to many interesting talks, some of which were given by PhD students. In particular I would like to cite three talks, which were given by my labmates Romain Gay, Pierrick Méaux and Adrian Thillard. Pierrick talked about stream ciphers for FHE and how to get fully homomorphic encryption closer to practical efficiency (link). Adrian presented a joint work with other labmates of ours about randomness complexity and the d-probing model (link). And last, Romain presented a joint work with Hoeteck Wee (that I am privileged to have as one of my supervisors),  Dennis Hofheinz and Eike Kiltz about "tightly CCA-secure encryption without pairings" (link) which won the best paper award! The awarding ceremony took place during the cocktail organized for the participants at Vienna's town hall, where we were hosted by the mayor in the impressive Feestsaal of the Rathaus palace.

It was also a particularly special conference for me and my colleagues Florian and Rafael because it came just after being notified that the paper we wrote together with (and under the supervision of) Hoeteck has been accepted to CRYPTO 2016. The paper is about a new technique to achieve circuit privacy for fully homomorphic encryption and it is available here.
The satisfaction of publishing a paper (which for me is the first) is something really amazing and it surely rewards all of us for all the work we put in writing it! As icing on the cake, my advisor suggested that I should give a mini-talk at EUROCRYPT's rump session: even if it was short and given during an informal event such as a rump session, I really enjoyed myself. I would also like to thank all my labmates that were sitting in the first rows of the hall to cheer and clap! :)

Another really enjoyable moment was the official dinner, that was organized at Weingut Fuhrgassl-Huber, just outside of the city, where we had delicious pork meat, fried vegetables, wine and desserts, plus music and the opportunity to get together and meet new people.

In the end I would like to congratulate and sincerely thank all the organizers, the program chairs, the session chairs, and everyone who made EUROCRYPT 2016 possible and so nice. Great job!
Next year, EUROCRYPT will be in Paris and I am already looking forward to it. Safe travel home to everyone and see you soon!

And here is a nice picture of a part of the ENS team enjoying a delicious pizza at an Italian restaurant.

On the left: Michele Minelli, Geoffroy Couteau, Florian Bourse, Aurelien Dupin, Romain Gay, Pierrick Meaux

On the right: Jeremy Chotard, Pierre-Alain Dupont, Remi Geraud, Dahmun Goudarzi, Rafael Del Pino, Adrian Thillard

Monday, May 9, 2016

Grias eich in Wien!

Grias eich in Wien!

I'm glad to see many of my ECRYPT-NET fellows in Vienna, the city I finished my Master's program in, these days. Apart from EUROCRYPT, this working week actually already started on Sunday with "A Workshop About Cryptographic Standards" where questions like "How can we establish confidence in cryptographic standards?" were dealt with

The conference will be followed by a workshop about cryptographic protocols for small devices" on Friday.

So, let's dive into one of the 3 main annual crypto conferences of the IACR, where researchers present their recent results in both theoretical and applied cryptography... and stay tuned for posts, comments about our experiences at these events!

Until then, maybe you use the chance to explore Vienna after the numerous talks. Inspired as in Marie-Sarah's blog-post, here are a few phrases presented in the locally spoken "Austrian German" dialect in ascending difficulty and descending relevance for the daily life in the city. For help with the correct pronunciation feel free to approach us - Ralph and me - the two Austrian ECRYPT-NET fellows.

English German Austrian (aka proper German)
Hi, Hello Hi, Hallo Grias di, Servus
Good night Gute Nacht Guade Nocht
Goodbye Auf Wiedersehen Pfiad di
How's it going? Wie geht's? Oida?
What's up? What's happening? Was geht? Oida!
Yes Ja Jo
No Nein Na
Please Bitte Bitt sche
Thank you Danke Daung sche
1 one eins oans
2 two zwei zwoa
3 three drei drei
4 four vier vier
5 five fünf fünf
6 six sechs seggs
7 seven sieben siebm
8 eight acht ocht
9 nine neun nei
10 ten zehn zehn
You're welcome Bitte schön, gerne Setz di her scheid da a Brot owa, nimm da a G'söchts
Sorry Entschuldigung Tuat ma lad
Sorry, I do not understand you Wie Bitte? Wos is?
What is your name? Wie heißen Sie? (formal)
Wie heißt du? (informal)
Wie haßt'n du? (informal)
My name is... Ich heiße... I bin da/die ...
Where are you from? Von wo sind Sie? (formal)
Von wo bist du? Wo kommst du her? (informal)
Wo kimmstn du her? (informal)
I am from... Ich bin aus... I bin aus...
You look beautiful Du siehst hübsch aus. Schnitzerl!
Do you speak English? Sprechen Sie Englisch? (formal)
Sprichst du Englisch? (informal)
Red'st du Englisch?
Where is (the bathroom)?
(the train station)?
Wo ist (die Toilette)?
(die Zugstation)?
Wo isn's Heisl?
(da Baunhof)
Let's go! Los geht's! Geh mas on!
Cool! Cool! Leiwand!
Bon appétit! Mahlzeit! Mohlzeit!
A schnitzel and a beer, please Ein Schnitzel und ein Bier, bitte S'ansa Menü, bitte.
Cheers! Prost! (Zum Wohl!) Zaum, zaum, zaum, zaum: Prooost!
Check, please Zahlen bitte (Die Rechnung bitte) Zohln/Zoin, bitt schen!
How is the weather tomorrow? Könnten Sie mir bitte Ihre Kenntnis der Wettervorhersage mitteilen? Wie wird'n s'Weda?
Leave me alone. Seriously! Lassen Sie mich in Ruhe. Hau' ab! Loss mi ång'lahnt. Wüst a Gnackwatschn?
How to order a traditional (midnight-) snack: Hotdog & beer, fast. Einen Käsekrainerhotdog, ein Endstück Brot und eine Dose Ottakringer (16.Bezirk) Bier bitte. Zeitnah - wenn Sie so gnädig wären! A Eitrige im Präserl, an Buggl und an 16er-Blech. Oba Jennifer!

Good luck! ... und pfiat eich!