Fast Fully Homomorphic Evaluation of Neural Networks in the Cloud

In order for Fully Homomorphic Encryption (FHE) to be deployed in real-world applications, still today --- even if a theoretical solution has been around for almost 10 years --- it is required to increase the efficiency of used algorithms. As the interactions of parameters and components of nowadays lattice-based realizations of FHE are non-trivial, schemes once set up to meet a multitude of design constraints, often end up having high requirements. Too high for some "killer"-application as run-times may pose a prohibitive hurdle.

In this blog-post, I'd like to present a use-case where an Fully Homomorphic Encryption (FHE) scheme achieves unprecedentedly fast classification of encrypted data, and makes scale-invariant homomorphic evaluation of neural networks (NN) possible.

Are privacy-preserving services in the Cloud relevant?

At this point, I think, I can skip philosophizing about the ubiquitous utility of machine learning, as we can see its impact everyday all around us. On the other hand the quest for privacy-preserving application of machine learning algorithms to user data is becoming a central topic of discussions recently. It is expected that the General Data Protection Regulation (GDPR), a result of the call for European law (which could serve as paragon internationally) to protect its citizens, its economy, will push forward innovation in this direction too.

Simply put, users of Machine Learning as a Service (MLaaS) in the Cloud, want to only share & upload encrypted images as input to the companies' powerful, pre-trained cognitive models.

Clearly, encrypting content ensures data confidentiality, assuming the associated private key of the  public-key encryption scheme never leaves the user’s trusted device. (As a side note; recent news reports suggest that such an assumption for user controlled devices are not always guaranteed. The Cloud operating on FHE encrypted data on the other hand is not possibly vulnerable to leak private user data through the whole class of cache attacks, i.e. Meltdown and Spectre.)

Let's briefly look at the problem setting.

To overcome conflicting interests of confidentiality and utility of data in the Cloud-based scenario, Fully Homomorphic Encryption can help the user to receive a useful answer to their encrypted question in a privacy-preserving way. Hence, the cloud needs to support homomorphic computations on the FHE encrypted inputs and send back the still encrypted result of this delegated operation in a reasonable time. In principal, only the legitimate user can decrypt the output using their secret key. The cloud service cannot deduce information from the random looking inputs, intermediate or final results, but can still charge the user for providing the service, e.g. classifying an image in this example.

Let's briefly look at the task.

First step when approaching a solution of how to use FHE for NN is defining minimal requirements of the concrete task and knowing what can be considered practical FHE.
We want to showcase fast homomorphic evaluation of a pre-trained NN to classify a depicted shape without leaking privacy of the input data at an 80 [bit] security level, e.g. images of handwritten digits from the MNIST dataset.
The output, given in less than two seconds, shall be encrypted scores assigned to each possible output and the highest score, decrypted by the user, is the most probable label of the input image.

A depiction of how input is propagated in order to evaluate a discretized deep neural networks with an arbitrary depth $d$ of hidden layers to arrive at a classification. Each neuron performs operations $f_i$; a function linearly depending on values of the incoming wires and weights followed by a non-linear operations. The latter is typically referred to as ``activation''.

As deep neural networks with $d$ hidden layers give good results in practice, we target this type with a scale-invariant FHE scheme.

Let's look at the problem solution.

In an attempt to bringing forth FHE in practice, our C++ code builds on top of an existing Fast Fully Homomorphic Encryption Library over the Torus (TFHE) and introduces a new framework for homomorphic evaluation.

To increase the efficiency, which is an important step paving the way to practicality, the underlying FHE scheme needs to be parametrized once for a given network.
Secondly, a security analysis is another crucial step in vetting the algorithms, ensuring their use maturely resists state-of-the-art cryptanalysis and fulfills the targeted security level.

The main capability of our scheme is that when evaluating a single neuron, the output value can readily be used for the next operation as it is bootstrapped to ensure low error propagation.

Close-up on a single neuron.

We apply the activation function directly to the weighted sum of inputs according to the network's wires, i.e. computing $y = f(x) = sign( \langle x, w\rangle )$, with fixed weights for the neuron and sign as activation.

Scale-invariance means that privacy-preserving evaluation of deep neural networks do not longer pose a hurdle, as computations carried out by every neuron in the network is independent of the total number of neurons and layers and hence scales linearly.

With this approach, we can report the performance result of an experiment to classify 10000 encrypted images from the MNIST dataset with more than 96% accuracy on average taking less than 1.7 seconds, using the TFHE library as a starting point.

Running an experiment on a trained neural net with 784:100:10--topology deployed in the Cloud.

An uploaded encrypted test image is input to the homomorphic evaluation of our scheme that classifies a depicted shape (without leaking privacy of the input data). The evaluation of the neural network outputs the encrypted scores $S_i$ assigned to each digit $i$. The highest score, decrypted by the user, is the most probable label of their image.

I'd like to stress that the good performance of this scale-able approach is not limited to homomorphic evaluation of neural networks with one hidden layer, as depicted above, but can be applied to deep neural networks, that in practice could be composed of possibly a hundred hidden layers or an even broader class of cognitive models.

For a detailed, formal description I refer to the full version of the paper or you may try out the proof-of-concept implementation code, available online that shows how to obtain these research results, applying our generic framework to a trained NN and MNIST dataset inputs as a demonstration.

Let's look at directions for future work and open-questions.

Finally, mentioning limits on the functionality of our FHE scheme, and pointing out the applicability to other well-specified domains rounds off this treatment here.

To comfort a potential concern for the service providers that their users might be sending malicious requests, to evaluate private networks with our framework is not dealt with at the moment, although it is in principal possible.
They could either try to learn the company's intellectual property (the weights and the topology of the neural network itself), or try to derive sensitive information encoded therein (which could be a breach into the privacy of the training dataset).
In this latter case a statistical databases studied in the differential privacy literature can be used in the training phase.

An open question is how further performance gains can be achieved by refining the algorithms. Also listing all general cognitive models that are possible is interesting.

So long, stay tuned for faster solutions and more general demonstrations!

Differential privacy

These days one reads a lot about the right to privacy. But what is it and how does it differ between the real and the digital description of the world? Briefly, it is a person's right to have and more importantly maintain control over information about oneself, which is fundamental to human's freedom of self-determination. In the digital context one seemingly lost this right in favor of using free services, handy tools that satisfy people's urge to communicate with each other and stay in touch and up-to-date at all times. Since more and more people realize that behind such apps and web pages naturally there are business models, society increasingly demands to reclaim control over collected personal data, which has been provided, unsolicited or involuntarily, to online merchants or telephony service providers at the time of use, for example. On the other hand collecting user information in databases is crucial as corporations offering named services see it. In order to make good products, tailored recommendations, and especially in the age of big data and machine learning, precise predictions by evaluating various functions on the data.

Statistical database queries have been studied quite some time now, and in fact it turns out that often it is sufficient to allow query access only to a population's aggregate data, not individual records, to derive useful statistics and achieve desired functionality! A common approach is to merely allow aggregate queries (i.e. range, histogram, average, standard deviation, ...) and rather than returning exact answers about sensitive data fields to specify intervals or give imprecise, statistically noisy counts.

You might have asked yourself, don't cryptographic techniques that have been omnipresent in this blog such as FHE (Fully Homomorphic Encryption) or secure MPC (Multi-Party Computation) solve this problem? Wouldn't it be possible to encrypt the user data yet for the service provider to compute useful statistics on it?

Indeed, it could be realized with the general FHE, MPC toolkit, but currently it is inefficient to operate them at that scale in practice, such that statistics over huge quantities of data are useful to infer statements about a given database. Hence specific, more slender tools have been designed to overcome this gap. Whereas FHE avoids a trusted 3rd party to compute (i.e. arbitrary functions or sophisticated statistics) on users sensitive data, here typically one explicitly allows a trusted 3rd party to collect and aggregate data in a privacy-preserving fashion. Users might do so i.e. when installing an app and argue to have an advantage for themselves like good default settings, an overall performance gain; or it might be a requirement to share information in order to use the service for free in the first place.

Differential privacy (often abbreviated DP) is a framework for formalizing privacy in statistical databases. It can protect against so called de-anonymization techniques that try identifying an individual record by linking two separately released databases that have been stripped off (quasi-)identifiers and look innocuous. Especially apriori knowledge or known partial history can be leveraged to derive more information from a released "anonymized dataset" other than the purpose it was originally intended to serve.

Let's look at a mathematical definition that captures and formalizes the notion of privacy and which has been studied in cryptography in the past 10 years. Let $d,n$ be a positive integers and $f: X^n \rightarrow \mathbb {R} ^{d}$ some statistics on a database comprised of $n$ records.

An algorithm $\mathcal {A}: X^n \rightarrow \mathbb {R} ^{d}$ that computes $f$ is said to have the $(\epsilon, 0)$-differential private attribute or ($\mathcal {A}$ is $\epsilon$-DP, for short) if for all neighboring subsets of a given database $x_{1} \neq x_{2}$ and $x_{1} \sim x_{2} := x_{1} \sim_1 x_{2}$ (they differ in just 1 element), and all subsets $S \subseteq \mathbb {R} ^{d}:$

\begin{align}
\mathbb{P}[\mathcal{A}(x_{1})\in S]\leq e^{\epsilon } \cdot \mathbb{P}[\mathcal{A}(x_{2})\in S]
\end{align}

holds. Looking more closely at this definition $\forall x_{1}, x_{2} \in X^n, x_{1} \sim x_{2}:$

$$\mathbb{P}[{\mathcal{A}}(x_{1})\in S]
\leq e^{\epsilon } \mathbb{P}[{\mathcal{A}}(x_{2})\in S] \Leftrightarrow \frac{\mathbb{P}[{\mathcal{A}}(x_{1})\in S]}{\mathbb{P}[\mathcal{A}(x_{2})\in S]} \leq e^{\epsilon }\\ \Leftrightarrow \log \left(\frac{\mathbb P[\mathcal{A}(x_{1})\in S]}{\mathbb{P}[{\mathcal{A}}(x_{2})\in S]}\right) \leq {\epsilon}$$

we can identify the so called "privay loss" of an algorithm (or in this context often called mechanism) $\mathcal {A}$. In this setting $\epsilon$ can be called the privacy budget. In less exact terms it captures the following: By specifying the privacy budget, it is possible to control the level of privacy and make an algorithm respect this additional constraint by techniques introduced below.
For those familiar with the concept of max-divergence, the definition of privacy loss is in fact the definition of $$D_\infty( A(x_1) || A(x_2)) := \max_{S\subseteq {\textbf supp}(A(x_1))} \log \left(\frac{\mathbb P[\mathcal{A}(x_{1})\in S]}{\mathbb{P}[{\mathcal{A}}(x_{2})\in S]} \right).$$

Furthermore, the multiplicative factor $e^\epsilon$ can be -- using a common approximation for small $\epsilon<1$ -- viewed as $1+\epsilon$:

$$e^\epsilon = exp(\epsilon) = 1 + \epsilon + \epsilon^2 + \dots \approx 1 + \epsilon.$$

In less formal terms this definition says that a given result is approximately the same whether it is computed using the first or the second, neighboring database.

A more general definition, that adds flexibility -- but also makes the proofs less elegant and more technical -- is $(\epsilon, \delta)$ -differentially privacy, when

$$\mathbb P[{\mathcal {A}}(x_{1})\in S]\leq e^{\epsilon } \cdot \mathbb P[{\mathcal {A}}(x_{2})\in S] + \delta.$$

Interpreting the definition, the goal of DP is that the risk of violating one's privacy should not substantially increase as a result of either appearing in a statistical database or not. Thus an analyst should not be able to learn any information about a record (i.e. participating an online questionnaire) that couldn't have been learned if one had opted not to participate or answered the questions randomly by rolling a die or flipping a coin rather than answering truthfully.

To overcome the fundamental challenge -- the trade-off between utility of data or accuracy of returned answers and privacy of records -- the set goal is to learn as much as possible about a group's data while revealing as little as possible about any individual within the group. Transforming an algorithm into a DP-algorithm requires probabilistic tools. The sensitivity of a function of $f$ is a good measure of how much statistical noise is needed to mask an answer:$$\Delta f=\max_{x_1 \sim x_2} ||f(x_{1})-f(x_{2})||_{1} = \max_{x_1 \sim x_2} \sum_{i=1}^d |f(x_{1})_i-f(x_{2})_i|.$$Low sensitivity of a function, i.e. small change of output given two neighboring inputs, allows to add statistical noise to achieve privacy yet don't use utility. The Laplace mechanism, adds noise from the Laplace distribution $\mathcal L(\lambda)$, i.e. noise $\eta(x)\propto \exp(-|x|/\lambda)$ which has 0 mean and $\lambda$ standard deviation. Substituting Laplace noise with other probability distributions, such with a 0 mean Gaussian and $\lambda$ standard deviation would be possible, but influences proof details.

A typical construction now is, instead of computing $f(x)$ directly, to compute $\mathcal A(x) = f(x) + \eta(x)$ and obtain a $\epsilon = \frac{\Delta f}{\lambda} $-DP algorithm, since the noise of two neighboring databases doesn't exceed this $\epsilon$ even in the worst-case. In terms of composability, sequential respectively parallel composition leads to a sum of all occurring $\epsilon_i$ resp. maximum of all occurring $\epsilon_i$ differentially private steps within the composed mechanism. This allows to efficiently turn algorithms into DP-algorithm.

These basic construction, including detailed proofs, and much more were covered during the 7th BIU Winter School on Cryptography named "Differential Privacy: From Theory to Practice" featuring speakers, who defined and contributed already roughly 10 years ago to the field. Slides are already online and video recordings about to appear on the webpage.

Furthermore, relationships of DP to various, related scientific fields ranging from statistics to machine learning and finally game theory were explored.

Concluding, in wake of the growing awareness of privacy issues in the digital domain, together with stricter interpretation of legislation and finally the possibility to satisfy most interests by anonymized data anyways; several big players strive to provide differentially private collection of data. Some companies market themselves as quasi-pioneers in privacy topics for some reasons: It pays off to be perceived as the first one; they would be facing various problems in the near future anyways, if they don't respect these issues; and most importantly, they can continue their business model: creating value of user's data. The more information is queried from the database, the more statistical noise has to mask the correct answer in order to meet a predefined privacy budget bound. This total allowed, justifiable privacy leakage can be specified in the number of admissible queries or the answer accuracy.

Provable cryptography avoids the situation of mere obfuscation that can be undone by a clever enough attacker / strategy -- given the security assumption holds -- and provides bounds and thus a guideline on how to choose parameters to guarantee a desired level of privacy. Algorithms invest a given privacy budget at privacy-critical steps. With this in mind, differential privacy is an additional design paradigm for cryptographic algorithms and protocols to keep in mind.

I'd like to end this cryptologic point of view on achieving privacy goals on the internet, as I started; with a fundamental sociological question. One thought that remains standing out is: Shall we collect as much data in the first place? Is it really necessary to predict individuals as online merchants? Do we want this ubiquitous tracking? As with advanced technologies, who's long-term effects cannot be predicted, maybe also in aggregating big data and tracking the only winning move seems to be not to collect data in the first place.

Symmetric Key Ciphers for FHE

In recent years, small devices with limited storage and computing power have acquired more and more popularity. This phenomenon, together with the appearance of cloud services that offer extensive storage and high computing power, has made computation outsourcing a key application to study. This setting, where a user with limited resources stores data on a remote server and also asks this server to make some computation on his behalf, comes together with new challenges and concerns related to privacy and security.

A simple scenario

The user Alice encrypts her data under a homomorphic encryption scheme and sends the ciphertexts to the server (eg. cloud). Now the server computes some function (eg. mean value) on Alice's encrypted data and sends back an encryption of the result, which can be decrypted by Alice with the appropriate key. Despite its simplicity, this model still requires a lot of effort from the user. In fact, all the FHE schemes that we know of have very large keys and heavy encryption overhead. The most natural approach is then trying to free the user from the burden of complex homomorphic computations, by asking her to do only the key generation part, the symmetric encryption and the final decryption, while leaving all the rest to the powerful server.

A hybrid framework

The user Alice generates a secret key $sk^S$ for a symmetric encryption scheme, a pair $(pk^H, sk^H)$ for a homomorphic public key encryption scheme, and sends $pk^H$ to the server together with an encryption of $sk^S$ under $pk^H$. Then, Alice encrypts her data under the symmetric encryption scheme and sends the resulting ciphertexts to the server, which homomorphically evaluates the decryption circuit of the symmetric encryption scheme, thus obtaining ciphertexts under the homomorphic scheme. This last operation can be seen as a sort of bootstrapping (from one scheme to another one), but does not involve any circular security assumption. At this point, the server can homomorphically compute a certain function $f$ on the resulting ciphertexts and send back the result, encrypted under the homomorphic encryption scheme. Alice can finally recover the result thanks to her $sk^H$.

Despite numerous improvements in recent years FHE remains highly unpractical, and one of the main problems is limited homomorphic capacity. In fact, all the FHE schemes we know of contain a noise term that grows with homomorphic operations. The homomorphic capacity corresponds to the amount of computation that can be performed before having to ``refresh'' the ciphertext via the expensive operation of bootstrapping. It is thus of vital importance to manage the error growth during homomorphic operations.

State-of-the-art ciphers

AES is a natural benchmark for FHE implementations. The homomorphic evaluations of some lightweight block ciphers such as SIMON have been investigated by Lepoint and Naehrig as well. It turns out that there is much room for improvement in optimizing the multiplicative depth. In this direction, many dedicated symmetric key ciphers with low-noise ciphertexts have been proposed.

• In 2015, Albrecht et al presented a flexible block cipher LowMC, which is based on an SPN structure with $80,128$ and $256$-bit key variants. The design philosophy is to minimize the multiplicative complexity, which is more relevant in the multi-party computation context. It also has very low multiplicative depth compared with existing block ciphers.

  Later, Dinur et al mounted optimized interpolation attacks against some instances of LowMC. More precisely, some $80$-bit key instances could be broken $2^{23}$ times faster than exhaustive search and all instances that are claimed to provide $128$-bit security could be broken about $1000$ times faster than exhaustive search. These attacks show that the ciphers do not provide the expected security level. The cryptanalysis also led to a revised version of LowMC.
• Keyvrium was designed by Canteaut et al and is a stream cipher aiming at $128$-bit security. It is based on the lightweight stream cipher Trivium, which has $80$-bit security. Trivium and Keyvrium both achieve similar multiplicative depth compared to instances of LowMC. They have a smaller latency than LowMC, but have a slightly smaller throughput.
• The FLIP family stream ciphers proposed by Méaux et al have the lowest depth compared with previous ciphers. Several versions are provided including $80$-bit and $128$-bit security instantiations. The main design principal is to filter a constant key register with a time-varying public bit permutation, which allows for small and constant noise growth. However, FLIP has a much higher number of ANDs per encrypted bit than the above ciphers.

To sum up, blending symmetric ciphers and FHE is definitely an interesting idea that could prove fundamental for bringing homomorphic encryption in the real world.

The other fellows also made contributions to this blog post.

Requirements and security goals for the Cloud

This is a two-part blog post giving an overview on the requirements and security goals for the Internet of Things (IoT) and the Cloud.

But first ... I'd like to mention that soon the ECRYPT-NET Summer School on cryptography for the cloud in Leuven is coming up.
This blog post can be seen as an intro to cryptology in the cloud; so there are some topics we will for sure hear about at the event in depth. I'm looking forward to a good discourse during the scheduled talks and to the discussions afterwards.

Part I: Requirements and security goals for the Cloud

The cloud here is loosly defined as computing and storage resources out-sourced to servers located off-site that are on-demand accessible via Internet.

Overview of cloud computing services to be secured
(Image by Wikimedia user Sam Johnston)

The usage of cloud services should thus be viewed as a potential threat, because inherently critical data is released from personal control and uploaded and so immediately raising several security as well privacy issues.

Requirements and the according cryptologic counter-measures are defined for various use-cases (such as depicted in the image) and briefly explained. It is important to realize that this needs to be done without deliberately weakening (or "back-dooring") solutions, as is sometimes suggested. To ensure democratic use of the developed technologies it is vital to see that the difference of a "front door" and a "back door" is merely ones viewpoint. Intentionally implementing two entrances makes an attacker happy not the legitimate user.

Transparent services, meaning the use of the cloud as if it was on-site, should ideally be built upon a back-end with verifiable, clear, possibly standardized, cryptologic concepts and open code for public scrutiny.

To capture the real-world cloud settings one has to view it from different perspectives: First the one of a private entity (user), then that of an organization (such as a company) and lastly the global perspectives of, say, a government.

An interesting starting-point for threats we have to consider, is the Cloud Security Alliance's 2016 report for cloud security naming twelve critical issues ranked by severity of real-world impact.

Data breaches is followed directly by weak identity, credential and access management and insecure Application Programming Interfaces (APIs) in this report --- issues that can be addressed by assessing requirements and tailoring cryptographic solutions from the beginning and deploying state-of-the-art implementations instead of sticking to legacy code.


Roughly four categories of requirements for the usages of the cloud can be distinguished:

• Computations in the Cloud
• Sharing Data in the Cloud
• Information Retrieval from the Cloud
• Privacy Preservation in the Cloud

The approach to secure these areas are manifold. General speaking, while data minimization is a fundamental paradigm for efficient interaction with the cloud security-by-design --- considering best-practices from the beginning --- is enabled by encapsulation of scopes of methods.
The following, briefly explained, concepts tackle concrete use-cases for end-users, companies and e-Government tasks alike:

• Order-Preserving Encryption (OPE) allows efficient range queries but does it diminish security too much?
• Format-Preserving Encryption (FPE) offers in-place encryptions in legacy databases.
• Data De-Duplication (DDD) is enhancing servers' back-end performance.
• Secret Sharing Schemes (SSS) is solving back-up and availability issues by distributing encrypted parts of the whole.
• Malleable Signature Schemes (MSS) is providing flexible authentication for documents and derived data.
• Private Information Retrieval (PIR) privately accessing elements in a database.
• Provable Data Possession (PDP) ensures that the cloud is storing the (uncorrupted) files.
• Multi-Party Computation (MPC) allows secure cooperation across the Internet.
• Verifiable Computation (VC) builds trust in results of a delegated computation.

We can observe that the cryptology community is striving for efficient cryptographic primitives that serve as building-blocks for implementations. Naturally researchers base their constructions on well-established security assumptions and derive clear security proofs to offer i.e. long-term confidentiality. This is not at least important because of the emergence of future quantum computers with powerful quantum algorithms posing a threat and needs to be addressed today before the transition of current solutions to the cloud, where the constructions would be exposed and would possibly be vulnerable to a quantum attacker.

Let's hope this trend continues and ultimately leads to reliable, standardized primitives for real-world applications.


Stay tuned for Part II: Requirements and security goals for the IoT...

ArcticCrypt

From 17th to 22nd of July the northernmost crypto workshop ever organized took place in Longyearbyen, Svalbard at latitude 78.13N. There are only about 1300 kilometers missing until the north pole.

Nordenskiöld glacier

Three ECRYPT-NET fellows (Marie-Sarah, Matthias and Ralph) had the opportunity to join the fascinating event.

The talks had a good mixture between talks from invited speakers as well as talks from researchers that submitted a paper. The topics reached from symmetric cryptography to fully homomorphic encryption as well as digital signatures and side channel attacks. The full program can be found here: http://arcticcrypt.b.uib.no/program/.

One of the most interesting talks on Monday, was given by Eik List: POEx: A Beyond-Birthday-Bound-Secure On-Line Cipher. In his talk he presented POEx that reached beyond-birthday-bound security with one call to a tweakable blockcipher and a call to a 2n-bit universal hash function per message block.  He then showed a security proof and gave possible instantiations.

In the evening from Monday/Tuesday at midnight there were two fascinating talks during midnight sun. The first one was given by Ron Rivest on: Symmetric Encryption based on Keyrings and Error correction. The second talk was from Adi Shamir: How Can Drunk Cryptographers Locate Polar Bears.

Adi Shamir explaining how drunk cryptographers can locate polar bears.

On Tuesday, Joan Daemen gave his invited talk on: Generic security of full-state keyed duplex. In his talk he briefly explained sponge constructions and how they can be used for authenticated encryption. Afterwards, he explained how to achieve beyond-birthday-bound security using sponges. In the end, he showed a new core of sponges, the (full state) keyed duplex construction.

On Wednesday, there was a full day of sightseeing planned, where we went on a boat trip to the "ghost town" Pyramiden. We started our boat trip in Longyearbyen, where we saw some minke whale. The captain of the ship told us that he saw also a blue whale a few days earlier. After a while we approached the bird cliffs where many seagulls and puffins were nesting. Birds are very important for the eco system of svalbard, as they exchange life from the water to the main lands. From there we continued our journey to the nordenskiöld glacier, a huge glacier with blueish shining ice. After a whiskey with glacier ice, we continued to our final destination. The "ghost town" pyramiden was a russian settlement and coal-mining community was closed in 1998 and is since 2007 a tourist attraction.

Reindeer

Polar bear

Polar bear warning sign

On Thursday, Marie-Sarah presented her paper: Security of BLS and BGLS signatures in a multi-user setting that was related to her master's thesis at the University of Waterloo. Marie-Sarah was inspired to re-visit it after reading about how the tightness of security reductions for the Schnorr signature scheme played a role in the CFRG's selection of an elliptic-curve based signature scheme for standardization. The standard notion of existential unforgeability under chosen-message attacks is in the single-user setting, since the adversary is given one public key to target.
In the more realistic multi-user setting, the attacker gets all users' public keys and can choose which one to attack. In her paper, she first analysed the BLS (Boneh-Lynn-Shacham) signature scheme's security in a manner similar to what was done for Schnorr - is key-prefixing necessary to maintain unforgeability of signatures in a multi-user setting? Next, she analysed the multi-user security of the aggregate signature scheme BGLS (Boneh-Gentry-Lynn-Shacham). She proposed a security notion in a multi-user setting analogous to the multi-user setting for normal (non-aggregate) signatures, then analysed BGLS's security in this model.

On Friday, Gregor Leander was presenting Structural Attacks on Block Ciphers where he presented invariant subspace attacks. Furthermore, he introduced an improved technique called non-linear invariant attacks.

Matthias, Marie-Sarah and Ralph

The artist of this sign never saw a polar bear before in his life. Therfore, they told him to paint a big white dog.

Santa Clause mailbox