Eurocrypt 2016: All Complete Functionalities are Reversible

In the multi-party computation (MPC) track at Eurocrypt 2016 in Vienna, Austria, Dakshita Khurana rather heroically gave two consecutive, very well-presented talks, the second of which explaining that All Complete Functionalities are Reversible. This second talk is the focus of this blog post.

In the context of MPC, a functionality is an algorithm which performs some operation using two or more parties' inputs while guaranteeing certain requisite security properties. The functionalities covered by this paper are secure function computations (SFEs), in which the parties want to compute some function on their combined inputs in a secure manner.

In the case of functionalities with two parties, $P_A$ and $P_B$, we usually consider one party as the sender and the other as the receiver. For decades, an open question in the field of MPC was, Given a two-party functionality $\mathcal{F}$ in which $P_A$ acts as the sender and $P_B$ as the receiver, is it possible to turn this into a secure scheme in which instead $P_A$ acts as the receiver and $P_B$ as the sender? This reverse functionality is denoted by $\textsf{reverse}(\mathcal{F})$. Intuitively, we think of a functionality allowing this reversal as containing 'enough symmetry' to perform the functionality of $\mathcal{F}$ regardless of which party performs which role.

It was shown by Wolf and Wullschleger that oblivious transfer (OT) can be reversed. OT is a process by which $P_A$ receives one of (at least) two values private to $P_B$ without $P_B$ finding out which $P_A$ chose.

A functionality $\mathcal{F}$ is called complete if both $\mathcal{F}$ and $\textsf{reverse}(\mathcal{F})$ are able to realise OT functionality. In light of Wolf and Wullschleger's result, a natural question to ask is then, Exactly which complete 2PC functionalities can be reversed? This new result shows that they all can be.

The main technical challenge that the authors overcome is that of creating commitments in both directions. This accomplishment is essentially what allows this symmetry property to go through and achieve the result.

As one would hope for in papers on cryptography, this result has practical as well as theoretical appeal: if one party possesses some physical property requiring that it perform a particular role in the functionality (e.g. a computationally 'weak' device), it is essential that this property suffice to compute securely even if roles are reversed. In this way, this paper serves as a good example of how cryptography theory and practice can and should go hand in hand. Like a couple dancing a Viennese waltz?

Eurocrypt 2016: Message Authentication Codes

Of the many sessions of EuroCrypt 2016, one of the most interesting was on Message Authentication  Codes (MACs). Chaired by Peter Gazi, the session was somewhat different from many provable security sessions in that it focused on better understanding the security of two schemes already in existence (and use).  In each case, the MAC in question is constructed through a mode-of-operation on top of an ideal primitive. This seems to be part of a trend at the moment: a number of recent papers on modes-of-operation papers have been written to tighten the security bounds of known schemes[1].

First up, Stefano Tessaro presented joint work with Mihir Bellare and Dan Bernstein [2] on the security of the MAC function used in the Ed25519 deterministic signature scheme, which they term AMAC (for Augmented MAC). AMAC can be thought of as a simplified version of using HMAC with an MD-based hash function, in which we replace the outer keying with a public output transformation.
The work first generalises AMAC to describe an "Augmented Cascade" by allowing any output transformation. This surfaces a new characterisation for the compression function: a PRF-under-Out-Leakage, where Out is the output transformation in question. That is, the primitive should be secure even when the adversary is given the evaluation of Out on it's inputs (this basically corresponds to length-extension attacks).  Directly targeting multi-user security of the overall scheme (rather than relying on a hybrid argument), they provide a reduction from the from the multi-user augmented cascade to the multi-user PRF-under-Out-leakage security of the compression function.
The work then demonstrates that (in the ideal model) this bound is small, and in doing so deduces the security of the cascade, which directly implies security of AMAC.  It was observed that bound was better than one would have by simply calculating single-user security and applying a hybrid argument.


The second talk of the session was by Atul Luykx, who spoke about PMAC (Parallelizable MAC) and its security bounds [3], based on work with Bart Preneel, Alan Szepieniec and Kan Yasuda. Atul focussed on what a security bound actually means, and why in the concrete world (where we expect in instantiate our schemes by setting real-world parameters) we should be careful about needlessly loose security proofs.  For example, he showed how, if one wishes to have reasonable level of confidence that an adversary cannot create a forgery yet use a small block cipher, birthday bound security can end up as low as a single-digit number of queries.
With this in mind, we looked at the security landscape for first EMAC (encrypted CBC MAC) and then PMAC through a graph of number of queries against maximum query length, with the various security bounds drawn in.  With generic attacks taking out large sectors of each graph, it was still clear that the attacks and bounds did not meet, and the paper focusses on whether these proofs can be modified to be independent of query length. The paper explains how this length-dependence is heavily dependent on the type of masking used internally, and this leads to the main conclusions. The most relevant of these for the real world is that using a Gray code to generate the masks leads to a length-dependent attack.


[1] See for example these papers from FSE.
[2] https://eprint.iacr.org/2016/142.pdf
[3] https://eprint.iacr.org/2016/185.pdf

Eurocrypt 2016: Hacker Ethics on the Rise

Following Phil Rogaway at Asiacrypt, Bart Preneel gave the IACR distinguished lecture on the future of cryptography. He went from outlining the Snowden leaks to proposing concrete ideas for how information technology should be used. It was refreshing to see a perspective that offers some optimism in these times.

Most of the Snowden leaks are already more than two years old, so I will not cover them in detail. However, it is important to repeat that they are less about breaking cryptography (and if so, more about breaking protocols than primitives) and more about breaking software and coercing companies.

Observing that privacy is a fundamental requirement of a free and democratic society, Bart expressed his disappointment over that the fact that most cryptography in use serves corporate interests rather than users' privacy. The largest deployment of cryptography for privacy is WhatsApp, which is of course dwarfed by the deployment in finance and access control.

A key point of the talk was the move of the focus from communication security to computation security. The real-world protocols of secure channels are far from being perfect, but there is continuous improvement, which promises to solve the problem eventually. However, the state of affairs is more critical for the software implementations. While attacks on TLS itself are relatively involved, software bugs tend to be more readily exploitable and require continuous patching, which in turns opens another attack vector. Current mitigations such as firewalls and anti-virus software seems to offer a weak line of defense at best and yet another attack vector at worst.

Moving away a bit from technological details, Bart compared the architecture of IT systems to politics. Just as democracies avoid a single point of control (and thus a single point of failure), IT systems should do the same. He advocated to move away from big data because big data leads to big breaches. In this light, privacy by design (a core of the new EU data protection law) requires data being stored decentrally. Cryptographic protocols such as MPC and FHE offer the capabilities of using decentralized data without any single point of failure.

Another important point of the talk was the observation that transparency is essential. Without open software and hardware it is impossible to assess the security of a system independently. Together with a call for more privacy, this sounds very much like the hacker ethics of keeping private data private and making data of public interest public.

Finally, Bart replied to Phil's point that cryptographers engage too much in crypto for crypto instead of real problem, saying that it is hard to predict which technology will be valuable in the future and quoting Einstein: "If we knew what it was we were doing, it would not be called research, would it?" Essentially, Bart called for the entirety of the cryptography "stack" to be continuously looked at, from the assumptions to the implementations, and for not avoiding hard problems.

He concluded by quoting Kant: "Optimism is a moral duty."

Some Reductions Will Always Be Lossy

One of the last sessions at yesterday’s Eurocrypt was an excellent talk by Tibor Jager, who presented his paper On The Impossibility of Tight Cryptographic Reductions, which is joint work with Christoph Bader, Yong Li and Sven Schäge.

Recall that we often prove the security of a public key primitive by constructing an algorithm, called a reduction, that is able to violate some complexity assumption $A$ (like CDH or DDH) if it has access to an adversary that breaks the primitive. So if $A$ is true, then such an adversary cannot exist.

In the setting where there are $n$ users, it is often the case that the probability of the reduction breaking $A$ is $\frac{1}{n}$ times the probability that the adversary breaks the primitive. This is what we mean when we say that the reduction is not “tight”: it is essentially $n$ times easier for an adversary to break the primitive than for the reduction to violate $A$. If $n$ is very large, then we must choose very large parameters to be sure that the primitive is unbreakable with these parameters (assuming $A$ is true). So tight reductions are highly desirable in practice.

The paper presented yesterday shows that there are many public key primitives for which no tight reductions can exist. We will illustrate this here with the example of an encryption scheme, but the result easily generalises to other primitives.

Consider the following multi-user security game $G$ for an encryption scheme: the adversary is given $n$ public keys $pk_1, \dots, pk_n$, outputs an index $i$ between 1 and $n$, receives the secret keys $sk_j$ for $j \in \{1, \dots, n\} \setminus \{ i \}$, and wins the game if it outputs a valid secret key for $pk_i$.

This looks like an odd game and it corresponds to a very weak notion of security, but showing that no tight reduction exists for $G$ implies that no tight reduction exists for a more natural game: $n$-key IND-CPA where the adversary can adaptively corrupt up to $n-1$ secret keys and query its test oracle using a single uncorrupted key.

We will suppose that a reduction from $G$ to an assumption $A$ exists, and use the reduction itself to violate $A$ directly, without accessing an adversary against $G$. Instead, our meta-reduction will simulate an ideal adversary against $G$ and violate $A$ using the reduction's output from interacting with the simulated adversary. To do the simulation, we essentially replay the reduction $n$ times, supplying a different index $i$ each time and storing the secret keys returned by the reduction, provided that they are actually valid for the public keys. Then it is trivial to “win” $G$ by simply outputting one of these stored secret keys, so our meta-reduction behaves like a very powerful adversary against $G$.

One of two things can happen: either the reduction answers honestly for exactly one index $i$, in which case our rewinding strategy won’t work but the reduction isn’t tight; or our meta-reduction perfectly simulates an ideal adversary, so we violate $A$. So either the reduction isn’t tight, or $A$ is false.

Many of the technical details are omitted here, but it’s worth pointing out one of the conditions that is necessary for this argument to go through. Simply forwarding valid secret keys provided by the reduction doesn’t quite simulate an ideal adversary, since these secret keys could be “non-uniform” in some way. So there must be an efficient algorithm that takes a public key $pk$ and a valid secret key $sk$ and uniformly samples from all the valid secret keys for $pk$. The easiest way to achieve this is if there is exactly one valid secret key for each public key: the “resampling” algorithm just returns its input.

I find this result very neat. It represents the intersection of theoretical work and practical concerns; often the two are very different things.

Eurocrypt 2016: Sanitization of FHE Ciphertexts

This year's Eurocrypt kicked off earlier in sunny Vienna. In today's last session, Léo Ducas talked about how to do your laundry homomorphically (and efficiently), which is joint work with Damien Stehlé.

Recall the aims of Fully Homomorphic Encryption: Alice has some data on which she wishes to compute some circuit $C$. However, she doesn't necessarily want to perform the computation herself, so she wants to outsource it. FHE allows her to outsource computations safely, by which we mean we want to preserve data privacy.

In this setting, Alice sends over her ciphertexts $c_i$ along with a circuit $C$. Bob then computes $c = Evaluate_{pk}(C, c_i)$ and sends $c$ back. In their work, the authors add the requirement that both parties preserve privacy - Alice's data is confidential, but so is Bob's circuit. As a motivation, imagine Bob to be a fiscal optimization consultant. The aim of this work is to efficiently obtain circuit privacy from existing FHE; in particular, we do not want the distribution of a ciphertext to depend on the circuit which led to it via homomorphic evaluation. This is assuming Alice to be honest-but-curious, meaning that we assume that the public key $pk$ and the ciphertexts are honestly formed. The authors combine previous techniques of bootstrapping and re-randomization to obtain a sanitization process.

The current method for doing the above is the so-called "flooding" of a ciphertext [Gentry09]. The drawback of this technique is the requirement of aggressive LWE assumptions (sub-exponential approximate factors) and bad asymptotic parameters.

In this work, the authors instead propose the soak-then-spin technique, which consists of bootstrapping several times and injecting some entropy in between each bootstrapping step. This allows for more lenient LWE hardness assumptions and smaller parameters. The downside is the repetitive bootstrapping operations, although the cost of such an operation has decreased with recent work [AP14][DM15].

They define WASH and SANITIZE algorithms and show them to be message preserving. This means that applying the algorithm then decrypting, or decrypting without applying the algorithm leads to the same result. Moreover, if two ciphertexts decrypt to the same plaintext, then the statistical distance between the sanitize (or wash) of the two ciphertexts is exponentially negligible. In terms of practical results, in HELib, they require around 3 bootstrapping operations.

If you haven't had time to read this post and/or see the talk, here is Léo's TL;DR:

• Put the ciphertext in water
• Wash it
• Rinse it
• Repeat three times!

References:

[AP14] J. Alperin-Sheriff and C. Peikert. Faster bootstrapping with polynomial error. In Proc. of CRYPTO, volume 8616 of LNCS, pages 297–314. Springer, 2014.

[DM15] L. Ducas and D. Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In Proc. of EUROCRYPT, volume 9056 of LNCS, pages 617–640. Springer, 2015.

[Gentry09] C. Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. Manuscript available at http://crypto.stanford.edu/ craig.

Side channel research in 2015: overview, statistics, and lots of new ideas!

This is the second time that we have produced a research review (thanks to everyone who commented on last year's effort!). Our review covers the many varied contributions to side channel research in the year 2015, and features five research themes:

• Efficiently extracting all information from leakage traces
• Furthering our understanding of fundamental statistical methods in the context of leakage attacks
• Efficient key rank computation and enumeration
• Attacking commodity devices
• Lightweight ciphers

I want to give credit to the effort made by my colleagues (RAs and PhD students) who read and reread last year's published papers and helped me put together a (reasonably) comprehensive review of the main themes of last year's research results. Without them this would not have been possible. 

For what it matters, we have also updated citation counts and other quantitative information about papers (if you think that we missed something, then please let us know). 

You can find the review on the SILENT website.

Study group: Crytography with One-Way Communication

The study group this week was on the paper "Cryptography withOne-Way Communication" by Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

In this paper the authors start the study of secure computation over noisy channel in the one-way setting, where only one party speaks. Different types of discrete noisy channels are considered and relationships  among them are studied (see the picture below).

It turns out that in the one-way setting the Binary Erasure Channel (BEC) and the Binary Symmetric Channel (BSC), that are equivalent in the interactive setting, are qualitatively very different. In particular, it is proved that a BEC cannot be constructed given a BSC; moreover while the erasure probability  of a BEC can be arbitrarily manipulated, i.e. can be both increased and reduced, the probability of  correct transmission of a BSC can only be diminished.

It is well known that in the interactive setting, oblivious transfer (OT) can be realized in an unconditionally secure way from almost any discrete memoryless noisy channel (DMC). This is no longer true in the one-way setting. For example,  we can see what happens if we try to realize a ROT channel (where the sender inputs two bit-strings $m_0$ and $m_1$, and the receiver obtains either $m_0$ or $m_1$, both with probability 1/2) from a BEC non-interactively. For realizing a ROT channel, the sender encodes $m_0$ and $m_1$ into some bits, say x=$(x_1, \dots, x_k)$, and send them over a BEC; the receiver obtains some of  these bits,  say y=$(y_1, \dots, y_{k'})$, depending on the  noise of the channel,  and from y they  should be  able to recover only one input string.  Security of the receiver is guaranteed by the fact that the  output string only depends on the  randomness of the channel and not on the sender's choice. On the other hand security of the sender  implies that it is impossible for them to obtain both  $m_0$ and $m_1$  just using the received bits y. However using the fact in a BEC each bit is independently erased, the authors prove that this  happens with large enough probability, i.e. a receiver could be able to extract both $m_0$ and $m_1$. Roughly speaking, security of the sender permits to break security of the receiver.

This result is generalized to any Generalized Erasure Channel (GEC) and BSC, and also to the case of computational security.

However, ROT channel can be realized using other type of discrete channels, for example the perfect bursty channel. It is a special GEC where all the erased bits are contiguous (see the paper for more details).

In the second part of the paper the authors consider one-way secure computation protocols over noisy channels for deterministic and randomized functionalities. More in particular, they prove that both the BEC and BSC are sufficient for securely realizing any deterministic functionality in the one way setting. Roughly, they first notice that ZK suffices for realizing any deterministic functionality in the malicious setting, and then that is possible to realize ZK from GEC and BSC by just sending over the channel multiple independent instances of ZK-PCPs to amplify the soundness.

In  case of randomized functionalities neither the BEC nor BSC can be used.

It is however possible to realize any randomized functionalities from bursty channels (BC), using the reduction from BC to ROT and then using results from [IPS08] or [IKO+11]. While the result on deterministic functionalities permits to obtain the first (highly inefficient) truly non-interactive solution to the ZK problem, this latter result on randomized functionalities  offers a solution (again non-efficient)  to the problem of certification of cryptographic keys in the one-way setting.