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!

Looking for fast OpenSource algorithms on lattices? Try fpLLL!

Dear ECRYPT-NET fellows and readers,
I have some news from CWI @ Science Park in Amsterdam where fplll-days-3, organized by Leo Ducas and Marc Stevens, are currently taking place!

Previously held at ENS Lyon, this is the third time already for such a combined effort to enhance the fplll OpenSource project. fplll has become a lively project with many suggestions that help to debug and feature requests for continuously improving the code-base in various directions.

As a brief history of fplll it can be noted that the first code was written by Damien Stehlé. It is now written by many active contributors (according to GitHub, the most active developers are: Martin Albrecht, Shi Bai, Damien Stehlé, Guillaume Bonnoron, Marc Stevens and Koen de Boer) and maintained by Martin Albrecht and Shi Bai.

What does fplll do?

What fplll does, depending on additionally specified parameters, is performing its implementation of the LLL algorithm using fast floating-point arithmetic under the hood. Other available lattice reduction algorithms are HKZ, BKZ reduction and variants. These algorithms can be applied on an input lattice represented by a matrix, given i.e. in a file as a set of row vectors, to obtain a reduced representation --- a versatile starting point of numerous applications. Furthermore, fplll allows to solve (arbitrarily adjustable approximate-) SVP and CVP instances, when used to find a shortest lattice vector relative to a user-chosen center.

To get started, one can not only use and compile the fplll C++ sources to run experiments, but the often dubbed 'user-friendlier variant' fpylll which provides Python access to the underlying, fast C++ functions. Finally, every mathematician's dear, Sage, (at least for anyone who isn't fully satisfied by pure Python) benefits from an improved fpylll as well, because importing the fpylll module seamlessly allows direct usage within Sage. Soon a new Sage version, SageMath 8.0, will be released, which ships the current fpylll module that accesses said, fast C++ routines.

The significance of lattice-based cryptography is repeatedly mentioned in paper's abstracts and has been explored in past ECRYPT-NET blog posts i.e. on 'What are lattices?' and 'Learning problems and cryptography: LPN, LWE and LWR'.

Significance for cryptanalysis

From a cryptanalysts point of view, the significance lies in the fact that most security models of lattice-based cryptography typically assume lattice reduction to be the most promising attack-vector against the underlying lattice-based primitive. Some security models are able to immediately (and provably) rule out certain classes of attacks and, for instance, a few others can be argued to be less promising than known formulations as lattice problems. Such arguing hence leads to fplll basically representing the SVP/CVP-oracle and it's performance is deemed as a lower bound for the practical performance of an attack. Typically attacks require many calls to such an oracle function, thus such an approach of taking the time of a single run as a lower bound is used to set parameters in experimental cryptosystems, when commonly a more conservative

lower bound including a security margin is chosen. Specifically, many proposed lattice-based crypto-schemes have been parametrized such that these best known-attacks are taken into account.

I suppose, I do not need to point out the numerous advantages of OpenSource software (over closed-source projects) but and its value to the research community the significance of having freely-available, fast lattice reduction routines is manifold.

To begin with, there is a discrepancy between what theory predicts and algorithmic performance in practice. Techniques described in the literature, summarized as BKZ2.0, leave a broad range of implementation choices. Different groups using different software and metrics where their approach is supreme, naturally lead to results that are hard to compare. If there was software that comes with meaningful defaults for many standard lattice tasks, is customizable, and extensible to individual lattice solutions, then there is hope that the community can agree on problem instances. Ideally, problem instances should cover deployed or model experimental cryptosystems such that they embody a meaningful benchmark for new designs.

Originally, fplll was trying to provide such algorithms with reasonable speed. Recently, developers broadened theirs goals and try to fill gaps of cryptanalytic research. Concretely, now fplll strives for speed from low level optimizations, and by implementing diverse techniques from the literature hence catching up with the state of the art. Additionally, it can be easily tweaked on a high algorithmic level with the Python layer fpylll, yet easily exploiting all the available optimized routines boosting the performance. One can argue that together with diverse lattice challanges this project helps to benchmark and compare various efforts to cryptanalyze cryptographic primitives used in cryptosystem's constructions.

A couple of Lattice Challenges have been proposed (SVP-, Ideal-, LWE- and Ring-Challenges) and it seems that researchers also test their code on these instances, which aids a comparison of approaches.

Having them conveniently accessible and high-level, fast lattice operations allows to quickly try out a new idea, or slightly different approach which saves time and hopefully makes researchers willing to share their tweaks and algorithmic tricks more often in the future.

The workshop

To come back to the start, the fplll-days are meant to be a hands-on, work-oriented workshop that enables direct discussions with core developers and with the goal to improve existing functions and the many algorithms involved. The general idea behind this meeting is to optimize often used routines, make it user-friendlier and accessible to cryptanalysts, for example.

By using code profiling tools, performance and memory usage bottlenecks can be spotted in a first overview, which allows to direct efforts where they might lead to significant speed-ups. After discussing know issues and useful features, this workshop tries to provide an implementation of numerically stable algorithmic variants to push the dimension LLL can handle (like Givens rotations while resorting only to machine floating point type), sophisticated pruning strategies to speed-up enumeration, and implementing sieving algorithms --- all as a promising new direction in finding short vectors faster.

It is exciting to join and shape such a project so let's hope for many interesting projects that got started and delegated here to be completed during this week and further interested researchers turning into active users joining the party and coming up with meaningful, reproducible research results. Remember that Newton "has seen further, by standing on the shoulders of giants" thus achieving progress, and so you too are encouraged to become active, using an already established framework!

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.

Inherent leakage-resiliency of LWE

Why we care about post-quantum cryptography should be clear by now (if it’s not, you’re in the right place anyway: you just need to take a step back and read this splendidly packaged blog post). A mathematical notion that is having much success in achieving it is the Learning With Errors (LWE) problem (guess what, we've also talked about that here). Thanks to some mathematical evidences, we are quite confident about its hardness so that many cryptographic primitives whose security is based on it have arisen. That said, let’s take a step further and imagine a future (not that far in time) when all those primitives are standardised and deployed at many levels, including hardware security. Our experience with classic algorithms teaches us that we shouldn't be too confident of the security of an implementation given the security of the scheme on paper, and post-quantum cryptography is no exception. In fact, side-channel attacks are known to be a great threat to cryptographic implementations. The question this blog post wishes to partially answer is: how can we secure our (future) post-quantum implementations?

Playing cops and robbers is a way, of course: applying common techniques (e.g. masking, randomisation, …) against known side-channel attacks is possible just by fixing the design of specific schemes. However, this approach has at least a couple of drawbacks:

1. a protection is not guaranteed to thwart future attacks (sometime new attacks are specifically designed to circumvent a countermeasure). More generally, a countermeasure doesn't protect against anything outside what it was designed to protect against;
2. usual countermeasures introduce overhead (in terms of whatever metric you prefer, e.g. area, time, ...). This results in a protected scheme to be less efficient than its unprotected version.

Leakage-resilient cryptography is a possible alternative: a cryptographic scheme is provably secure even in the case of some anticipated amount of leakage, by design. Usually such proofs only rely on a bounded amount of leakage that the scheme can tolerate. The main idea sounds like the following statement.

We build a cryptographic scheme which retains security even if a bounded amount of arbitrary information is leaked.

Full stop. There aren't many other assumptions: this fact gives leakage-resilient cryptography enough generality to capture many, if not all, side-channel attacks. In essence, we are assuming that the scheme is secure if leakage occurs, no matter how that is exploited by an attacker. This seems to address the first drawback of ad-hoc countermeasures, provided everything is implemented in the proper manner. Is there anything we can do about the second drawback?

If we keep thinking of securing a scheme, then answering to that question is really difficult. Indeed a countermeasure, even the most general and provable one, introduces some changes in the original design which necessarily result in a overhead, for the simple reason that they take into account a more powerful adversary, namely one who is able of measuring and exploiting leakage too. However, think of the case in which none of the anticipated amount of leakage actually occurs. Then we end up having a less efficient implementation, the protected one, which doesn't provide any additional security because, without leakage, the original scheme was secure anyway. Eventually, stop thinking of securing a scheme and start thinking of securing an assumption.

In their paper, Goldwasser, Kalai, Peikert and Vaikuntanathan show that LWE has the nice feature of being hard even in the presence of leakage. Does it sound like what we've just said? Essentially yes, but with a great difference: they're not building a leakage-resilient scheme, hence introducing some sort of overhead, but proving the leakage-resiliency of an assumption. This makes a big difference, because the former implies that the efficiency degrades to let leakage-resiliency grow, while the latter implies that security, not efficiency, degrades. In particular, their proof establishes a relation between the security level and the amount of leakage in such a way that we don't need to anticipate a maximum tolerable amount of it. The straightforward consequence is that a scheme based on LWE is secure independently on whether the leakage occurs or not, with the advantage that in the latter case we have not introduced any protection-related overhead in the design. As a result, they propose a symmetric-key encryption scheme being secure even in the presence of leakage (with some caveats): the novelty relies on the fact that you won't find any parameter describing an amount of leakage (usually called $\lambda$ in the literature of leakage-resilient cryptography).

We omit any technicality here as this would like to be a generic and accessible reading. For further details on how the authors achieved this result, we refer to their paper. Instead, it you prefer to have just a mathematical flavour without going into too many details, you may like this post from the Bristol cryptography group's blog. Stay tuned for more insights on post-quantum cryptography!

P.S.: the word "leakage" appears 19 times in this text. If you're tired of reading it, watch this.

Marco (Thanks to Simon and Matthias for some corrections!)

Post-Quantum Cryptography: Why? What is it?

Why Post-Quantum Cryptography?

When I wrote my first blog entry here ("Ola from Gustavo"), I gave a short description of what will happen when someone presents the first quantum computer, i.e., most of the actual cryptography (ECC, RSA) will be dead, see [1] for more details. One statement about quantum computers and cryptography is:
"Well, we don't have a quantum computer now and the expectation for one is around 15 years, why I should be worried now?"
I will give one good reason, imagine that you use some encryption (RSA, ECC or whatever) in your messages and someone starts storing these messages. Now, this agency/person/computer is not able to read your messages. However, in 15 years (around this) when a real quantum computer appears then, it will be possible to break the encryption and read everything about your past. For this reason, we need to be prepared against this threat now and we don't need to wait for the quantum computer to start to protect ourselves. For this protection, we have good guardians of the privacy that with the union of their powers started the research in Post-Quantum cryptography (PQC).

In the figure (see above), we can see that PQC divides into four big areas, i.e., Hash-based, Code-based, Multivariate-quadratic-equations-based and Lattice-based. There are other areas but these four became more important in the last 10 years. In the following, I will give a very brief explanation and examples of schemes of each area in PQC. There is a website about PQCrypto with initial recommendations and a list of publications in the area to access click here.

HASH-BASED Cryptography

In hash-based, we can see important signature schemes such as Lamport-Diffie OTS, Merkle's hash-tree, XMSS, SPHINCS and a lot of relevant work. I decided to talk about one of the newest works in the area, i.e., SPHINCS.
SPHINCS was presented in 2015 at EUROCRYPT under the title of "SPHINCS: practical stateless hash-based signatures". In order to understand better the idea behind this work, it is necessary to have a previous knowledge about hash signatures because they present two new ideas: replacement of the leaf OTS (One-time Signature) with a hash-based FTS (Few-time Signature) and Goldreich’s construction as a hyper-tree construction with h layers of trees of height 1. For more details about the implementation and construction of SPHINCS, it is possible to access here.
Also, if you have more interest in Hash-Based cryptography can be checked via pqcrypto hash-based and at this webpage of Andreas Hülsing.

CODE-BASED Cryptography

The classic name that appears in Code-based is McEliece’s hidden-Goppa-code public-key encryption system from 1978. However, there is new work in the area such as the work from Misoczki, Tillich, Sendrier, and Barreto using quasi-cyclic moderate-density-parity-check (QC-MDPC) codes for the McEliece encryption system. The principal contribution of this work for the area is the use of small key sizes.
Other relevant work, this time in the fast implementation area, came from Bernstein, Chou, and Schwabe under the name of "McBits: Fast constant-time code-based cryptography". The main contribution of this work is a constant-time in the implementation of code-based cryptography and they avoid time attacks.
The literature for code-based is very big and can be checked in this link.

MQ-BASED Cryptography

The Multivariate Cryptography schemes are based on the difficult to solve non-linear systems of equations over
finite fields. Finding a solution for these systems, in general, is considered a NP-complete/-hard problem. One of many
interesting examples is Patarin’s Hidden Fields , generalizing a proposal by Matsumoto and Imai (1988).
The original work from Paratin can be found at: Hidden Field Equations (HFE) andIsomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms.

If we want to see what happened recently in the MQ area, there is slides from the PQCrypto winter school are available online at PQCrypto . The slides from Jintai Ding gave a very nice overview of the state-of-art in the Multivariate
Public Key Cryptography (MPKC). In the slides, he gave an introduction MQ with a small example to understand
how MQ works. After that, the author gives the principal cryptosystems in MPKC.
The slides are available at this link and more material about MQ-based cryptography can be checked at PQCrypto project.

LATTICE-BASED Cryptography

The lattice area received a lot of attention in the past years, new cryptosystems, new attacks, and implementations. Everything is based on hard problems in lattices such as shortest-vector problem (SVP), Ideal Lattice, Closest-vector Problem (CVP) and others. There is a lattice challenge to show the shortest vector in a Lattice and the ideal Lattice given the dimension of it, more details about it can be checked at Lattice Challenge.

In the area of public-key cryptography, there are several schemes and mostly is based on SVP and Ideal lattices. That is the case for  the scheme described by Peikert and Stehlé et al.

Post-quantum Cryptography and ECRYPT-NET

One of the interests of the ECRYPT-NET project is in PQC and we have four fellowships working in this area. In Lattice-based, we have Marco Martinoli, Michele Minelli and Henry de Valence. In the quantum algorithms area I started work with this.

I started to read about all of the areas described before for two reasons. Firstly, I needed to understand the basic of each area to decide where I want to work. Secondly,  after all the reading I decided to work with quantum algorithms and attack each area using it. In the following months, I will start writing about quantum algorithms and the impact in the cryptography.


[1] Bernstein, Daniel J., Johannes Buchmann, and Erik Dahmen, eds. Post-quantum cryptography. Springer Science & Business Media, 2009.

Learning problems and cryptography: LPN, LWE and LWR

The beginning of a new year is always a perfect moment to make plans for the future: one can sit down, look at the past year and figure out what to do and where to go during the upcoming one. It is legitimate, then, to take a while and think of new directions in the field of cryptography too. One of such is certainly post-quantum cryptography, that is to say what we should do when quantum computers running Shor's algorithm will break all the cryptosystems based on integer factorisation problem and (elliptic curve) discrete logarithm problem. In the literature, different approaches can be found: Code-based cryptographic systems depend on the hardness of correcting a codeword following a random error-correcting code while the security of lattice-based cryptosystems is based on the hardness of finding the shortest vector of a given lattice and of several other problems, just to mention two widely known and studied branches of post-quantum cryptography. In fact, at the present moment no quantum algorithm is known to solve them significantly better than any classic one. But there is more: hidden behind, there is a vast class of problems known as learning problems.

Essentially, they are computational problems related to learning theory, whose main issue is what kind of functions can be learned efficiently from noisy, imperfect data. Although only in recent years the link between learning theory and cryptography has been deeply studied, it existed since the early '90s. These two subjects are in a sense complimentary since the ease of learning an information, which is desirable in learning theory, excludes the possibility of hiding it, a must in cryptography. Hard learning problems are then good candidates to base cryptographic schemes on and the fact that they are thought to be quantum-resistant makes them even more appealing.

Let us begin the 2016 with a brief description of three well known learning problems: LPN, LWE and LWR.

Learning Parity with Noise (LPN)

The decisional LPN problem asks to find a secret vector $\mathbf{s} \in \mathbb{Z}_2^n$ where $n\in\mathbb{N}$, given samples of the form $$ ( \mathbf{a},\langle \mathbf{a} , \mathbf{s} \rangle \oplus e) \in \mathbb{Z}_2^n\times\mathbb{Z}_2 $$ where $\mathbf{a}\xleftarrow{U}\mathbb{Z}_2^n$ is drawn uniformly at random and $e\leftarrow Ber_\tau$ is drawn from the Bernoulli distribution of parameter $\tau \in (0,1/2)$, i.e. $\mathbb{P}(e=1)=\tau$. Equivalently, LPN can be stated as the problem of solving a system of noisy linear equations with coefficients in $\mathbb{Z}_2$, or to decode the codeword $\mathbf{s}$ affected by error $e$ using the random code generated by $\mathbf{A}$, which is the matrix whose rows are different $\mathbf{a}$ from several samples. More formally, for $\tau\in(0,1/2)$ and $n\in\mathbb{N}$ the LPN$_{\tau,n}$ is $(q,t,\epsilon)$-hard if for every distinguisher $\mathcal{D}$ running in time $t$: $$ \Big\lvert \underset{\mathbf{s},\mathbf{A},e}{\mathbb{P}}(\mathcal{D}(\mathbf{A},\mathbf{s}\mathbf{A}\oplus \mathbf{e})=1) - \underset{\mathbf{r},\mathbf{A}}{\mathbb{P}}(\mathcal{D}(\mathbf{A},\mathbf{r})=1) \Big\rvert \leq \epsilon $$ where $\mathbf{s}\xleftarrow{U}\mathbb{Z}_2^n$ is the vector to be discovered, $q\in\mathbb{N}$ is the number of samples, $\mathbf{A}\xleftarrow{U}\mathbb{Z}_2^{n\times q}$, $\mathbf{r}\xleftarrow{U}\mathbb{Z}_2^q$ and $\mathbf{e}\leftarrow Ber_\tau^q$.

Another particularly elegant way of describing the problem is the following. Given a secret $\mathbf{s} \in \mathbb{Z}_2^n$ and $\tau \in (0,1/2)$, I denote by $\Pi_{\tau,n}(\mathbf{s})$ the distribution over $\mathbb{Z}_2^n\times\mathbb{Z}_2$ sampled choosing a vector $\mathbf{a}\xleftarrow{U} \mathbb{Z}_2^n$ and outputting $( \mathbf{a},\langle \mathbf{a} , \mathbf{s} \rangle \oplus e)$ with $e\leftarrow Ber_\tau$. Hence, the hardness of LPN$_{\tau,n}$ is equivalent to $\Pi_{\tau,n}(\mathbf{s})$ and the uniform distribution over $\mathbb{Z}_2^n\times\mathbb{Z}_2$ being indistinguishable.

As an example of usage of LPN to build cryptosystems, I describe the symmetric scheme LPN-C. Let $C : \mathbb{Z}_2^r \rightarrow \mathbb{Z}_2^n$ be an $[n, r, d]$ error-correcting code (i.e. of length $n$, dimension $r$ and minimal distance $d$) with correction capacity $t = \big\lfloor \frac{d-1}{2} \big\rfloor$. The code $C$ is assumed to be publicly known. Let $\mathbf{M}$ be a secret $k\times n$ matrix constituting the secret key of the cryptosystem. To encrypt a $r$-bit vector $\mathbf{x}\in\mathbb{Z}_2^r$, the sender draws $\mathbf{a}\xleftarrow{U}\mathbb{Z}_2^k$ and computes $$ \mathbf{y} = C(\mathbf{x}) \oplus \mathbf{a}\mathbf{M} \oplus \boldsymbol\nu $$ where $\boldsymbol\nu\leftarrow Ber_\tau^n$. The ciphertext is $(\mathbf{a},\mathbf{y})$. Thanks to the fact that the receiver knows $\mathbf{M}$ and that $\mathbf{a}$ is public, the decryption algorithm is just the XOR $\mathbf{y} \oplus \mathbf{a}\mathbf{M} = C(\mathbf{x}) \oplus \boldsymbol\nu$ followed by the decoding of $C(\mathbf{x}) \oplus \boldsymbol\nu$, which is always possible in the case $HW(\boldsymbol\nu)\leq t$, otherwise $\bot$ is returned. Since the noise vector $\boldsymbol\nu$ is drawn by the sender, a simple test on its Hamming weight can be done to avoid incorrect decoding.

Learning With Errors (LWE)

The Learning With Errors (LWE) problem is a machine learning problem and its hardness reduces from worst-case lattice problems. Essentially, LWE is a generalisation of LPN to larger moduli and different error distributions, i.e. the secret vector $\mathbf{s}$ and the random vector $\mathbf{a}$ live in $\mathbb{Z}_p^n$ for a certain prime $p$ and natural $n$, while the error is drawn from a generic distribution $\chi$, which is the Bernoulli one in standard LPN. In its simplest (search) formulation, LWE asks to recover a secret vector $\mathbf{s}\xleftarrow{U}\mathbb{Z}_q^n$ from a number of samples of the form (note the extreme similarity with the correspondent equation in LPN): $$ ( \mathbf{a},\langle \mathbf{a} , \mathbf{s} \rangle + e) \in \mathbb{Z}_q^n\times\mathbb{Z}_q $$ where $\mathbf{a}\xleftarrow{U}\mathbb{Z}_q^n$ is picked uniformly at random, $e\xleftarrow{\chi}\mathbb{Z}_q$ is chosen according a certain distribution $\chi$ and addition is performed modulo $q$.

Such description, however, does not allow the construction of schemes being efficient enough for practical purposes. For this reason, an interesting variant of LWE called Ring-LWE has been developed which significantly decreases the amount of storage needed and speeds up the computations. Informally speaking, vectors of bits in $\mathbb{Z}_q^n$ are seen as coefficients of polynomials in $R_q=\mathbb{Z}_q[x]/(f)$ where $f$ is a polynomial of degree $n$ in $\mathbb{Z}_q[x]$. Hence, one element of the ring $R_q$ can stand for $n$ elements of $\mathbb{Z}_q$, thus reducing public and private keys by a factor of $n$.

A basic public-key scheme based on Ring-LWE works as follows. Let $R=\mathbb{Z}[x]/(x^n+1)$ where $n$ is a power of two and $R_q=R/qR$. Both the secret key $s$ and the error $e$ are chosen according to an error distribution $\chi$, hence $s,e\xleftarrow{\chi}R$. The public key is $(a,b=a\cdot s + e)\in R_q^2$ where $a\xleftarrow{U}R_q$. An $n$-bit message $z\in\{0,1\}^n$ is then seen as an element of $R$ via the following transformation. \[ (z_1,\dots ,z_n) \mapsto \sum_{i=1}^n z_ix^{i-1} \] Then, three "small" random elements $r,e_1,e_2 \in R$ are chosen according to $\chi$ and are used to compute the ciphertext $(u,v)\in R_q^2$ as follows. \begin{align*} u &= a \cdot r + e_1 \pmod{q} \\ v &= b \cdot r + e_2 + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z \pmod{q} \end{align*} The decryption works as follows (the $\pmod{q}$ is implicit). \begin{align*} v - u\cdot s &= b \cdot r + e_2 + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z - a \cdot s \cdot r - e_1 \cdot s \\ &= a\cdot s \cdot r + e\cdot r + e_2 + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z - a \cdot r \cdot s - e_1 \cdot s \\ & = (e\cdot r + e_2 - e_1 \cdot s)+ \Big\lfloor \frac{q}{2} \Big\rceil \cdot z \\ & = E + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z \end{align*} For a suitable choice of the parameters, $E\in R$ is a polynomial whose coefficients have magnitude less than $q/4$ (this is the reason why $r,e_1,e_2 \in R$ were "small"), so that the bits of $z$ can be recovered by rounding each coefficient of $v - u \cdot s$ back to either $0$ or $\lfloor q/2 \rceil$.

Learning With Rounding (LWR)

Among these three, the Learning With Rounding (LWR) problem is the newest. With respect to LWE, instead of adding random noise to $\langle \mathbf{a} , \mathbf{s} \rangle\in\mathbb{Z}_q$, LWR consists in rounding such value to the nearest element in a subgroup $\mathbb{Z}_p$ of $\mathbb{Z}_q$, hence computing $\lfloor\langle \mathbf{a} , \mathbf{s} \rangle\rceil_p\in\mathbb{Z}_p$. The hardness guarantee follows from the fact that, with a careful choice of the parameters, the following holds with high probability. $$ \lfloor\langle \mathbf{a} , \mathbf{s}\rangle +e\rceil_p=\lfloor\langle \mathbf{a} , \mathbf{s}\rangle\rceil_p $$ LWR has the immediate huge advantage that sampling the error $e$ is no longer needed. Moreover, since the operation of rounding is deterministic, a layer of uncertainty is cut down.

LWR can be directly used to build a deterministic encryption scheme, which is a cryptosystem always producing the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Although this raises security flaws, in some situation is a desired feature (e.g. searchable databases). The parameters are $n$, $m$, $q$ and $p$. First of all, a matrix $\mathbf{A}\in\mathbb{Z}_q^{m\times n}$ statistically closed to uniform is chosen as public key while the secret key is a trapdoor function $T$. The existence of an algorithm $Invert$ that returns a secret $\mathbf{s}\in\mathbb{Z}_q^n$ given $\mathbf{A}$, $T$ and the LWE sample $\mathbf{c}=\mathbf{A}\mathbf{s} + \mathbf{e}\in\mathbb{Z}_q^m$ is assumed. Then, the encryption of an $n$-bits message $s\in\{0,1\}^n$ is just $\mathbf{c}=\lfloor\mathbf{A}\mathbf{s}\rceil_p$. The decryption algorithm takes as input the ciphertext $\mathbf{c}$ and the secret key $T$ and works in two steps:

1. $\mathbf{c}$ is transformed from a LWR sample to a LWE one by applying $\lfloor(q/p)\cdot \mathbf{c}\rceil\in\mathbb{Z}_q^m$. Indeed: \begin{align*} \lfloor(q/p)\cdot \mathbf{c}\rceil &= \lfloor (q/p)\lfloor \mathbf{A}\mathbf{s} \rceil_p\rceil \\ &= \lfloor (q/p)\lfloor (p/q)\mathbf{A}\mathbf{s} \rceil\rceil \\ &= \lfloor (q/p)((p/q)\mathbf{A}\mathbf{s} + \mathbf{e}')\rceil \\ &= \mathbf{A}\mathbf{s} + \mathbf{e} \end{align*}
2. the algorithm $Invert$ is applied to $\mathbf{A}$, $T$ and $\lfloor(q/p)\cdot \mathbf{c}\rceil$.

References

[Pie12] is a very broad survey on LPN problem and gives several cryptographic applications as well as security proofs. LWE was first introduced in [Reg05] and its ring variant can be found in [LPR10]. Finally, LWR was introduced in [BPR12] but an improved version, allowing the choice of a bigger class of parameters, is given in [AKPW13].

[AKPW13]

Joel Alwen, Stephan Krenn, Krzysztof Pietrzak, and DanielWichs. Learning with rounding, revisited. In Advances in Cryptology CRYPTO 2013, pages 57-74. Springer, 2013.

[BPR12]

Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In Advances in Cryptology EUROCRYPT 2012, pages 719- 737. Springer, 2012.

[LPR10]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Advances in Cryptology EUROCRYPT 2010, pages 1- 23. Springer, 2010.

[Pie12]

Krzysztof Pietrzak. Cryptography from learning parity with noise. In SOFSEM 2012: Theory and Practice of Computer Science, pages 99- 114. Springer, 2012.

[Reg05]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 84 -93. ACM, 2005.

Marco

Codes and Coding

Dear readers, hi fellows,
as my master's thesis was about Linear Codes and Applications in Cryptography I'd like to provide some content of it in a nutshell and to give some recommendations of software that I used in the course of writing it.

multiple scientific fields are involved (created using TikZ)

Modern cryptography covers among others the three areas privacy, authentication and integrity of messages. The aim of coding theory on the other hand described by one word is reliability - adding redundancy to messages in order to detect transmission errors. Both fields cover seemingly different areas in the field of digital information processing.

The motivation of my thesis was to showcase the combination of multiple scientific fields within coding theory and modern cryptography and to explore how they interact in the domain mentioned above and why they are a good choice.


In the center of attention stood the McEliece public-key cryptosystem, it's variation (Niederreiter's cryptosystem) and generalizations to other code classes after those code classes of interest were introduced and discussed.

The McEliece public-key cryptosystem was published in 1978, is based on disguising a special code as a general code and it is of interest back then and today because it seems to stand solid in the so-called post-quantum era, when a powerful quantum computer is available to attackers. More than 35 years ago the original code parameters: codeword length $n = 1024$, code dimension (or message bits) $k = 524$ and error-correcting capability $t = 50$ were proposed for the binary code underlying the McEliece public-key cryptosystem for $2^64$ bit security. To achieve the a reasonable security level today they have been adjusted to $n = 6960, k = 5413, t = 119$ because of attacks that were explored since then.

Given the number $t$ of erroneous positions and a general code $C$, the task of decoding $y = c + e$ is to find a codeword $c \in C$ of Hamming weight or number of non-zero entries: $w(y-c) = w(e) = t$. In the complexity theoretic literature the result is that this problem is NP-complete - there is no algorithm known that fulfills this task in polynomial time depending on the input size (length of $y$ respectively $c$).

The choice to use a Goppa codes as private key, which is multiplied by permutation matrices to obtain the public key looking as if it was a general code, was due to performance reasons when decoding messages thanks to Patterson's algorithm.

Interestingly many attacks are not applicable to the class of binary Goppa codes that McEliece's scheme was based on but on similar schemes and generalizations allowing other alphabets or other structures - binary Goppa codes were seemingly proposed with foresight.

In spite of some advantages and the - so far - quantum computer resistant attacks the biggest drawback of public-key cryptosystems based on codes are rather long public keys compared to other schemes. If one adds a security margin, under the assumption of a working quantum computer performing the general attack through the application of Grover's algorithm, the public key size is as big as 1 MB.


In the thesis I implemented the fast algorithm (by N. J. Patterson) for algebraically decoding binary Goppa codes in Sage and demonstrated the full functionality of the system in yet another chapter giving an example. Since I was writing it all up in $\LaTeX$, using sagetex even allowed the computation and insertion of the results into the $\verb!.tex!$ file one the fly when the document is being compiled!

My recommendation (to my fellows) for researching, analyzing, developing & testing of algorithms in a structured manner with the ability to create nice plots and documents rather easily is to give Sage or Spyder a try. Even though it might not be a necessity in your research to actually code something, playing around with these tools already available is instructive and worth a try.

Sage is available online or offline via installation and it is a good choice if you need access to i.e. number theory. Maybe the aforementioned Spyder is preferable if a somewhat more automated handling even closer to the programming language Python of the implemented primitive at hand is needed in your case.

Autumnal Bochum around Oct 31

As usual, a little plurivalent:
Happy Coding and Happy Halloween - because $Dec(25) = Oct(31)$, right?!

Workshop on Lattice Cryptography

It is the day after AsiaCrypt 2015 and there are two workshops being held in Auckland. The one which is most relevant for my research is that on Lattice Based Cryptography; which consists of four talks. One by Jung Hee Cheon on "Multilinear Maps and Their Cryptanalysis", one by Amit Sahai on "Obfuscation", one by Fre Vercauteren on "Weak Instances of RLWE" and one by Martin Albrecht on "Small Secret LWE".

---

Cheon first described a very naive version of multi-linear maps and then went on to show how this can be attacked by creating non-trivial encodings of zero, and then taking greatest common divisors. Then he went on to generalise this naive scheme to the CLT scheme (which is a bit like the DGHV FHE scheme). The naive attack does not apply to CLT as the dimension increased, meaning taking naive greatest common divisors would not work. Cheon then showed how to extend the naive attack to the CLT case by turning the gcd extraction into an eigenvalue extraction problem. This done by building quadratic forms which represent encodings of zero. The result is that for the CLT scheme one can break the equivalent of the DLP problem.

Cheon then went on to present the GGH scheme, which is a bit like the NTRU FHE scheme; except the instead of encrypting via c=[(m+r*p)/z] for an integer p, one encodes via c=[(m+r*g)/z] for a polynomial g which generates the ideal lattice <g>. Modifying the prior attack in this situation allows us to recover a basis of this ideal. But finding a short vector in this lattice can be hard. However, by utilizing encodings of zero one can actually solve the equivalent of the CDH problem.

Both attacks rely heavily on the presence of encodings of zero. So the attacks do not apply to situations in which one does not publish such encodings; i.e. applications such as indistinguishability Obfuscation (iO).

---

Amit Sahai then gave an introduction to iO; he motivated it via an analogy of an attacker who captures your brain and is able to read and tamper with every neuron, yet we still do not want the attacker to know what we are thinking about. This is the problem which obfuscation tries to solve in the computing realm. Martin pointed out that this would be a great way to produce malware!

Amit then put Multi-Party Computation within this analogy. He suggested we can think of MPC as protecting our brain against the tampering adversary, by dividing the brain up into portions. As long as one portion is kept out of the adversaries control we can use MPC to protect our thoughts. Obfuscation tries to do the same, without there needing to be an honest part of the brain.

Any program which is suitable for obfuscation must be unlearnable from query access to the program. Since otherwise the adversary could learn the program from the input/output behaviour. However, black-box obfuscation has been shown to be impossible; essentially because their are contrived programs which are unlearnable but for which one cannot produce an obfuscation, since any obfuscated program has an explicit attack against it.

This is why iO as a concept was presented; since it at least seems possible to achieve. The idea is that if you have two equivalent programs and we obfuscate one of them, then the adversary cannot tell which one we obfuscated. One way of thinking of this is as a psuedo-canonicalizer. The question is what useful can one do if we could create an obfuscator which satisfied the iO definition. Amit gave the application of building demo versions of software, without needing to re-engineer the software.

---

Fre Vercauteren then discussed a more in depth analysis of a paper from CRYPTO this year on Weak Instances of Ring-LWE. The CRYPTO paper gave instances where decision Ring-LWE was easy, but search appeared to be hard. However, Fre's talk showed that the search problem was in fact easy from the start, and thus the CRYPTO paper was less surprising than it at first seemed to be. As with all things on Ring-LWE the question arises as to how to choose the error distributions.

Fre spend the first part of his talk discussing the geometry of number fields, and in particular the Minkowski embedding. The Ring-LWE problem generates errors according to a discrete Gaussian distribution in the Minkowski embedding, Poly-LWE is to generate the errors according to a discrete Gaussian in the polynomial embedding.

Eisentrager et al discussed cases for which Poly-LWE was easy, these were then extended by Elias et al to special cases of decision Ring-LWE. They did this by mapping the special Ring-LWE instance to a special Poly-LWE instance.This is done by pulling back the problem from Ring-LWE to Poly-LWE via the matrix which defines the Minkowski embedding. The Poly-LWE attack requires that q is larger than f(1), and hence q will "kind of show up" in the coefficients of the defining polynomial f. So the fields being attacked, are very special indeed.


(This post originally appeared in the BristolCrypto blog)

"Olá" from Gustavo

Hello! I'd like to introduce myself. My name is Gustavo Souza Banegas and I'm one of the two ECRYPT-NET participants from Technische Universiteit Eindhoven. I'm from Florianópolis, Brazil, and I've just moved to Eindhoven, Netherlands. During the time in Brazil, I have completed my undergraduate and master's degree in Computer Science at Federal University of Santa Catarina (UFSC) in Laboratory of Computer Security. The focus of my work in Brazil was in computer security and cryptography.

It is single opportunity for me to work in the ECRYPT-NET. My contribution for the project will be in the post-quantum area. From the pqcrypto.org, we can have an explanation of the importance about post-quantum cryptography: "Imagine that it's fifteen years from now. Somebody announces that he's built a large quantum computer. RSA is dead. DSA is dead. Elliptic curves, hyperelliptic curves, class groups, whatever, dead, dead, dead." (Bernstein, 2009)

In the next three years, I hope to contribute for the fascinating area of post-quantum cryptography  by improving it. In order to accomplish, I will be under the supervision of Tanja Lange and Daniel Bernstein.

The summer school in Sardinia was amazing and it was a nice moment to meet with people involved in ECRYPT-NET. I am very happy to work with you guys. See you in Tenerife!