Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources

In this week's study group Gaven presented a paper that will be appearing at Crypto later in the year, titled "Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources" [BFM14]. In a nutshell, this work says that if indistinguishability obfuscation exists, then a notion of security called UCE1 security cannot be achieved.

Background

To understand what this result means, we have to go back over twenty years to the introduction of the random oracle model [BR93], a useful tool for making heuristic arguments about security. In the random oracle model algorithms have access to a truly random function (the random oracle), which plays the role a hash function will fulfil in the implemented scheme. Security is then proved with respect to this random oracle, the idea being that if the hash function "behaves like a random oracle" then the scheme will be secure in practice.

The main benefits of the random oracle model are its power and its conceptual simplicity. However it isn't without its drawbacks, the main one being that once the random oracle is instantiated with a hash function the original proof no longer applies. It has been shown [CGH98] that there exist schemes secure in the random oracle model that become insecure under any instantiation of the oracle. It could be argued that this construction (and other examples following it) is unnatural and that actual schemes with proofs in the random oracle remain unbroken, but the whole debate is really played out by now, so I'm not going to go into it.

An attempt to address these issues is the notion of Universal Computational Extractors (UCEs) [BHK13]. UCEs seek to formalise what it means to "behave like a random oracle". Schemes can then be proved secure based on the existence of a UCE rather than a random oracle, the difference being that the necessary properties of the instantiating hash are now explicit so that a scheme instantiated with a suitable hash is provably secure.

Behaving like a random oracle

The obvious definition of behaving like a random oracle would be the following game, when the adversary is given the hash key and access to either the real hash or a random oracle, and must determine which function he is interacting with.

This is clearly unsatisfiable as the adversary can query a point x to get response y, then use the hash key to evaluate for himself the hash at point x and check if the resulting value is y. To prevent this trivial win, the adversary is split into a source S and a distinguisher D, with only S having access to the function and only D having the hash key.

The source can aid the distinguisher in his task by providing leakage L. If this leakage is unrestricted then the adversary can use the same attack as before, so for the definition to be useful some restriction must be put on S's output. The restriction is that the source must be unpredictable, which roughly says that given the leakage L it is hard to identify any of the queries the source S made. If no distinguisher can tell real from random with the help of any unpredictable source, then the hash is UCE1 secure. With a UCE1-secure hash in hand, a whole bunch of primitives become achievable in the standard model. Unfortunately, the result of [BFM14] shows that a UCE1-secure hash cannot exist.

Indistinguishability obfuscation

An obfuscator is an algorithm that takes in a program and outputs an indecipherable mess of a program with the same functionality, the idea being that you can give this new program to someone and they can't work out anything about its functionality beyond what interacting with the original program in a blackbox way would reveal. It turns out this is impossible [BGI+01], but achieving a weaker notion called indistinguishability obfuscation might be possible. An indistinguishability obfuscator is an algorithm that obfuscates a circuit in such a way that the obfuscations of any two functionally equivalent circuits are indistinguishable, that is, given the obfuscation of either circuit 0 or circuit 1 an adversary can't tell which he was given. Such an obfuscator was constructed last year [GGH+13] using multilinear maps. Using an indistinguishability obfuscator, [BFM14] give an attack that breaks UCE1 security of any hash.

The attack

The source behaves as follows. First it queries its oracle at a randomly chosen point x and receives a response y. It then constructs a circuit that takes as input a hash key, evaluates H under that hash key at point x, and then outputs true if the result is y and false otherwise. The source runs the indistinguishability obfuscator on this circuit, and outputs the obfuscated circuit as its leakage L. The distinguisher D is given the hash key and the obfuscated circuit, and evaluates the circuit with the hash key as input. If the source was interacting with the real hash then the result will be true, otherwise it will almost certainly be false. Such a source and distinguisher can thus tell the real hash from a random oracle.

To break UCE1 security the source must be unpredictable, which can be shown through a standard game hopping argument. It is assumed that the output length of the hash is at least twice the key length, but this assumption is just to give high-level intuition and can be removed at the expense of simplicity. The first game is the unpredictability game where a predictor is given the leakage from S and to win must output a point in the set of queries S made. We move to a game that terminates if there exists a hash key such that the leaked obfuscated circuit evaluates to true. The probability that this bad event occurs can be bounded using the assumption to show that it is negligible, so the first two games are indistinguishable. Finally we move to a game where the source leaks an obfuscation of a circuit that always outputs false. Since the bad event of the previous game means it terminates whenever a hash key exists under which the circuit would evaluate to true, if the game does not terminate then the circuit must evaluate to false, and so in the last two games the circuit in each always outputs false. Indistinguishability obfuscation says that the obfuscation of the always false circuit in the second game and the obfuscation of the always false circuit in the last game are indistinguishable, so the games themselves are indistinguishable. In this final game S leaks no information about x, which is chosen at random, so the predictor has no information about x and hence the source is unpredictable.

Next steps

With UCE1 security unattainable but the UCE framework still a desirable tool, various modifications to the definition have been suggested, including moving from computational to statistical definitions and to split sources. Very recently it was shown [BM14] that a stronger form of unpredictability might be the answer, as it is shown that this notion is sufficient to achieve results in correlated-input secure hash functions, universal hardcore functions and PKE, and crucially a construction meeting this notion is given.

Bibliography

• [BFM14] Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources - Christina Brzuska and Pooya Farshim and Arno Mittelbach - https://eprint.iacr.org/2014/099
• [BGI+01] On the (Im)possibility of Obfuscating Programs - Boaz Barak and Oded Goldreich and Rusell Impagliazzo and Steven Rudich and Amit Sahai and Salil Vadhan and Ke Yang - http://www.iacr.org/archive/crypto2001/21390001.pdf
• [BHK13] Instantiating Random Oracles via UCEs - Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi - http://eprint.iacr.org/2013/424
• [BM14] Using Indistinguishability Obfuscation via UCEs - Christina Brzuska and Arno Mittelbach - http://eprint.iacr.org/2014/381
• [BR93] Random Oracles are Practical: A Paradigm for Designing Efficient Protocols - Mihir Bellare and Phillip Rogaway - http://cseweb.ucsd.edu/~mihir/papers/ro.pdf
• [CGH98] The Random Oracle Methodology, Revisited - Ran Canetti and Oded Goldreich and Shai Halevi - http://eprint.iacr.org/1998/011
• [GGH+13] Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits - Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters - http://eprint.iacr.org/2013/451

For Proper Garbling, Don't Go in Circles!

At Eurocrypt, Daniel Wichs presented a paper entitled "Garbled RAM Revisited" by Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, and himself. Their main contribution is to fix a security flaw in a similar paper at last year's Eurocrypt.

The main goal of the two papers is to achieve the equivalent of Yao's garbled circuits for RAM programs. This is desirable because compiling RAM programs to circuits, while possible, can come at a huge cost. As an example, a Google search formulated as a circuit would have to access the whole Internet.

In this context, garbled RAM computation is modeled as a way of outsourcing storage. During a setup phase, a client sends a garbled database to a server. Later, it garbles a small input and a program, which is then evaluated by the server and possible changes the database. This can happen many times. For efficiency, the running time should be proportionate the running time of the RAM programs, and for security, the server should only learn the program output and not even the access pattern of the memory.

An intermediate scheme provides weak security in the sense that the database content and the access pattern are revealed. ORAM then allows to compile such a scheme to a fully secure one.

For the construction, think of the following model for RAM computation: The memory is an array of bits, and the execution proceeds in steps. Every step takes as input the local state and a bit from the memory and outputs the location of the input bit for the next step. The initial and final state correspond to the input and output of the computation, respectively.

It is straightforward to garble the step circuit, the input, and the output. However, garbling the memory bits proves to be harder because the locations of the bits are not static. The previous paper solves this by using a PRF for encoding the bits in the memory and having every step circuit output two encryptions of the possible encoding and the respective garbled label for the next step. However, this introduces a circularity because every step circuit has to include the PRF key and the key to decrypt the output of the previous step.

The authors present two fixes for this. The first one uses IBE and is more efficient with polylogarithmic overhead for circuit creation and computation. The second only uses one-way functions but has overhead N^epsilon for an epsilon > 0.

The first solution requires only public keys in the step circuits and stores bits as secret keys derived from a master key. To allow writing to the memory, a further trick is necessary to avoid another circularity. The ID of the secret keys has to include the time when the location in question was written to at the last time, and the secret is derived in way such that the step circuits can derive the keys for future steps but cannot decrypt for previous steps. Hierarchical IBE can be used for this, but it is not necessary.

Non-Interactive Secure Computation Based on Cut-and-Choose

A talk by Arash Afshar (joint work with Payman Mohassel, Benny Pinkas and Ben Riva).

Arash explains how to do non-interactive, maliciously secure two-party computation, with efficiency comparable to the most efficient secure two-party computation protocols. In the context of the talk non-interactivity means that only two messages are sent in the entire protocol. One from Alice to Bob and then one from Bob to Alice. A motivation for looking into non-interactively is first of all the fact that latency in communication networks gives unavoidable increase in execution time so we want to limit the amount of rounds, but also the fact that with non-interactivity we can do asynchronous execution of secure computation.

The approach that Arash and his co-authors use to achieve non-interactive secure computation (NISC) is cut-and-choose of garbled circuits. This is an approach which has received much work both in its theoretical, but also in its practical aspects, in the recent years. Unfortunately cut-and-choose is inherently an interactive paradigm as it requires one party to sent a bunch of candidate values (in this case garbled circuits), then the other party randomly selects a subset of these candidates for verification, which means that the sending party sends all the information and randomness used in constructing these candidates to the receiving party. If all the candidates selected for verification were correctly constructed the receiving party knows that with large probability a lot of the remaining candidates are correctly constructed. Arash and his co-authors overcome this interactivity problem by embedding the choice of check and evaluation candidates into some non-interactive oblivious transfers (OT).

Unfortunately, when doing cut-and-choose of garbled circuits some issues arise, such as the problem with selective failure and input consistency. In general both of these can be handled with off the shelf constructions. However, these are not in general non-interactive. Still, for the selective failure problem a non-interactive solution exist which is called committing OT. This is also the solution Arash and his co-authors use in their protocol. For the problem of input consistency they introduce a new gadget which is an equality prover that gives the receiving party a proof that the sending party has given the same input to each of the garbled circuits.

To make their construction more competitive Arash and his co-authors also implement a non-interactive version of a recent optimization, making it possible to successfully execute the entire protocol even though only one correct evaluation circuit remains after cut-and-choose. In general it is needed that a majority of correct circuits remain for evaluation. In this optimization if the sending party constructs a circuit incorrectly which is evaluated, then the sending party's input is leaked making it possible for the party evaluating the circuits to compute the output in plain. Arash explains that they achieve this by changing the input keys to trapdoor ElGamal commitments such that knowing both a 0 and a 1 key on a given output wire leaks a trapdoor to the commitments on the input keys, making it possible for the evaluator to learn the input of the sending party.

Finally, Arash and his co-authors also introduce the first implementation of any NICS protocol. Their implementation runs on a common laptop through a Linux VM and uses the AES-NI instruction extension for the garbling, but only runs a single thread and uses disc IO to simulate communication between the parties. Assuming decent security parameters their implementation runs oblivious AES in 6.4 seconds. From their implementation they see that the time spent on garbling and cheating recovery is very small and that the bottlenecks are the exponentiations needed for the commitments and the communication (which in this case is IO).

Probable or Nonce-sense? Reconsidering Generic Composition

One of the most interesting talks at EuroCrypt 2014 was on ways of combining encryption and authentication algorithms to form a secure authenticated encryption scheme. I hope that (with the help of some Douglas Adams quotes) I can interest you too...

In the beginning the Universe was created. This has made a lot of people very angry and been widely regarded as a bad move.

The Guide

 The story behind this paper begins at AsiaCrypt 2000, where Bellare and Namprempre presented their seminal paper on Generic Composition [BN], studying mechanisms for turning secure MAC and encryption functions into a secure Authenticated Encryption (AE) scheme. The well known “result” of this is is that combining a MAC with an encryption scheme through Encrypt-then-MAC (EtM) is secure, but Encrypt-then-MAC (EtM) or MAC-and-Encrypt (MaE) are not. Unfortunately, this is not quite what the paper says, and leads to one of the most prevalent misunderstandings in symmetric cryptography...

That quite definitely is the answer. I think the problem, to be quite honest with you, is that you've never actually known what the question is.

Deep Thought

[BN] was written at a time when most symmetric schemes were formalised within the probabilistic encryption paradigm. This means that encryption schemes have access to their own internal coins, and output a ciphertext such that the message is recoverable from just the key and the ciphertext. A ciphertext is secure if an adversary cannot distinguish the encryption of a message from the (appropriately long) encryption of 0-bits.

Nowadays, it is standard to abstract away the generation of randomness through a third input parameter (an IV or nonce), which is transmitted unencrypted. Then, a message should be recoverable by combining the key, ciphertext and the IV or nonce. Following the paper, we refer to an IV-based encryption scheme as an 'ivE', and a nonce-based encryption scheme as 'nE', and similarly define 'nAE' as a nonce-based authenticated encryption scheme. Moreover, modern schemes are expected to handle Associated Data (AD) - data that should be authenticated but not encrypted. Overall, this provides a very different model in which to prove security, because, for example, an adversary may read or modify the randomness supplied to the encryption or decryption algorithms

It is within the first of these models that the original results were proven, but since most security results are now given in the latter model, they are no longer directly applicable.

Don't Panic!

The Guide

In this work (henceforth [NRS]), co-authored with Chanathip Namprempre and Phil Rogaway, Tom Shrimpton seeks to reevaluate the security of Generic Composition, answering the questions that many people thought [BN] had already answered.  Specifically, the paper aims to answer the questions "How can you combine an ivE with a secure MAC to form nAE?" and "How can you combine nE with a secure MAC to form nAE?".

With two more inputs (IV and AD) to consider than [BN] took, the first observation is that there are significantly more than three reasonable ways to combine a MAC and an ivE or nE scheme.

Firstly, the authors cover 160 reasonable methods for combining 2 MAC calls, one ivE call and a single concatenation involving a MAC output. Whilst many of these are nonsensical or trivially insecure, the paper produces a portfolio of 8 secure MAC+ivE→nAE methods (one of which is the SIV construction [SIV]), as well as four for which optimal security (or insecurity) could not be proven.

Similarly, the authors exhaust across 20 reasonable methods for combining a MAC call with one nE call to form an nAE scheme, and as before several of these can be trivially discounted. This leads to 3 schemes being proven secure, with the security of one left open.

So, which of these should I use? Well, the short answer is: it depends! Some of the schemes allow tag truncation, parallelizable encryption or parallelizable decryption. For the complete list, we refer the reader to the paper [NRS], where diagrams of each construction is provided.

It is a mistake to think you can solve any major problems just with potatoes.

The Guide

The paper proves some generic composition mechanisms are secure under hypothesis which are much more like the real world. Indeed, several of these form schemes that can be readily implemented from the sort of cryptographic primitives that one may already have access to. However, as with all provable security results, if the hypothesis are not met then the result does not hold. This means that, if you want an nAE scheme to inherit provable security from [NRS], not only must the encryption and MAC primitives be combined in one of the verified mechanisms, but the primitives must also have the properties this paper requires of them. For example, the encryption scheme must satisfy all the normal requirements (such as correctness), but also an additional requirement of 'tidyness', which we can think of as the opposite of correctness. Whilst correctness requires that if E_k(N,M)=C then D_K(N,C)=M, tidyness requires that D_k(N,C)=M implies E_k(N,M)=C.

So, how does this relate to potatoes? Well, there are two things one can take away from this paper. The first is that there are significantly more ways of combining schemes securely, other than EtM, and this is a very useful result. However, arguably the most important message to take away from the paper is that there is no such thing as a generic composition. At the end of the day, a generic composition result is only useful if you use primitives satisfying all the required properties. Potatoes are great, but they're no use if you want a cheese omelette.

So long and thanks for all the fish

The Dolphins

 

---

[BN]:
Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm
Mihir Bellare and Chanathip Namprempre
AsiaCrypt 2000
https://eprint.iacr.org/2000/025
 

[NRS]
Reconsidering Generic Composition
Chanathip Namprempre, Phillip Rogaway and Thomas Shrimpton
EuroCrypt 2014
http://eprint.iacr.org/2014/206

[SIV]
Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem
Phillip Rogaway and Thomas Shrimpton
EuroCrypt 2006
https://eprint.iacr.org/2006/221

Efficient non-malleable codes and key derivations against poly size tampering circuits

A talk by Pratyay Mukherjee about a joint work with Sebastian Faust, Daniele Venturi and Daniel Wichs

Pratyay's talk was in two parts, the first part being about the construction of non-malleable codes and the second on an application of these codes.

Part 1: A non-malleable code (NMC) is a code which consists of two randomized methods, encoding and decoding. It has the property that if a codeword is tampered with then the decoding algorithm will either reconstruct the message that was encoded or output a completely unrelated message. This is an interesting primitive which finds applications in tamper resilient cryptography.

However, since there is no secret key nothing prevents an adversary from doing a man-in-the-middle attack by decoding a codeword, flip a bit, and then reencode the modified message. This obviously makes it seem impossible to succeeded in constructing a NMC for unrestricted tampering functions, but Pratyay and his co authors overcome this impossibility result by only considering a restricted class of functions. In particular they are able to show that for any fixed polynomial p there exist an efficient NMC for any family of functions which can be computed by a circuit with size less than 2^p=P, assuming a common reference string (CRS).

More specifically by fixing P they give a specific construction for a family of efficient codes, parameterized by a CRS, which are non-malleable with high probability. The construction consists of two encodings: an inner encoding and an outer encoding. The outer encoding uses a t-wise independent hash function h. More specifically let C_i be the encoding that is output by the inner encoding, then the outer encoding is C_o=C_i || h (C_i). For the inner encoding they use a leakage resilient code, specifically Partyay uses the code with the encoding function computing c_i= r || h'(r) xor s for any r and input s where h' is again some limited independent hash function.

For the second part of the talk Pratyay introduced a new primitive called non-malleable key-derivation function and also proposed a efficient construction that is secure against poly sized circuits. In fact their construction is information theoretically secure and achieves optimal rate. A usage of this primitive is for example to construct a tamper resilient stream cipher.

A group therapy session with one person talking

The first invited talk of Eurocrypt 2014 was by Jeff Hoffstein on "A mathematical history of NTRU and some related cryptosystems". This history spans about 20 years and includes both successes and disasters, and the title of this blog post was how Jeff introduced his own talk.

It all started in '94, with a lecture by Goldfeld that Jeff attended, which was about a one way function from number theory due to Damgard in '88. This one way function was based on claw-free permutations, and Jeff noted that it was related to certain L-series and he began wondering what you could achieve with such constructions. Could you achieve Public Key Encryption or maybe just Key Exchange? He still does not know the answer to this day, but such open questions eventually led to the NTRU cryptosystem.

He began thinking about restricted polynomials mod q and how to prove the knowledge of a polynomial without revealing the polynomial itself. Linear algebra shot down most of his initial ideas, but eventually he began thinking about 'short' polynomials, whose coefficients are all bounded. With these 'short' polynomials, the problem that relates to breaking the schemes turns into the Closest Vector Problem. At this point lattice basis reduction comes into play, and at the time it was believed that LLL was deadly for most applications that include lattices in some form or shape.

The next step was to compactify the ring structure, because "it seemed like the right thing to do". Instead of just taking polynomials mod q, you also take them mod X^N-1 and you get the ring structure of NTRU. Now the multiplying of polynomials corresponds to a convolution, which in turn naturally corresponds to the Fourier transform. And based on the idea that 'short times short equals short', Jeff and some co-authors turned the idea of 'proof of knowledge of a short polynomial' into a digital signature scheme. However, it leaked information, like many of the subsequent lattice schemes, which was not improved until Vadim Lyubashevsky showed in 2009 how to fix the leakage issue in general using rejection sampling.

But now we get to NTRU. The next required observation was that for most polynomials f you can find an inverse in your ring and that if you compute g/f for short polynomials g and f the result 'looks random'. With this in hand, everything was ready to create NTRU. Jeff united with Jill Pipher and Joe Silverman and they began thinking about quantifying the security and how to select parameters. They understood the combinatorial approach to break the scheme pretty well and Odlyzko pointed out the Meet-In-The-Middle approach to break the scheme, but the big issue was the lattice attack. Lattice basis reduction algorithms like LLL and BKZ performed well in practice, but there was not a clear understanding of why.

At the rump session of Crypto '96, Jeff presented their ideas for the NTRU scheme as he would have at any mathematical conference: he showed the audience what he had so far, hoping for some advice or input on the security implications and how to improve the scheme or select parameters. However, he found that some cryptographers were irritated because they had not done their security analysis properly themselves and why would they present these unfinished ideas?

At Eurocrypt '97 Don Coppersmith and Adi Shamir presented their lattice attack on NTRU, which appears to be the only time that the cryptanalysis of a cryptosystem was published before the cryptosystem itself. They claimed that LLL would easily solve the associated lattice problems for any remotely practical parameters. They also added the important observation that any other short vectors in the NTRU lattice would allow an adversary to decrypt, so he would not have to obtain the exact short polynomial f. As a result of this attack, NTRU was rejected from Crypto '97, because why would you accept a broken scheme?

However, Jeff was not deterred by this attack. In fact, he was convinced that the success of LLL was an artifact as a result of the low lattice dimensions. Since NTRU had the efficient ring structure, this lattice dimension could be increased at a relative low cost to the key size. So Jeff and his co-authors began testing various parameters against the NTL implementation of BKZ by Victor Shoup to see what could be broken and what could not. During this testing phase there were a number of papers published on NTRU that either sped up the basis reduction or attacked some other aspect of the scheme like the possibility of decryption errors. Eventually they put out some challenges in '97/'98 and to the best of Jeff's knowledge only the warm-up challenge was ever solved.

This is when their problems began: they attempted to construct a signature scheme. As mentioned before, all these signature schemes had the same issue: they leaked information in some way that allowed an attacker to obtain the secret key with enough signatures. The first scheme, NSS, was broken due to an attack by Gentry and Szydlo that uses reversal polynomials and a powerful way to obtain the secret polynomial f from the resulting data. Fortunately, the crypto community was very forgiving (NOT). The next attempt at a signature scheme based on NTRU was broken by Nguyen and Regev in '06 and the final attempt which added perturbations was broken by Nguyen and Ducas in '12. However, these schemes could be fixed by using the rejection sampling ideas of Lyubashevsky.

In the meantime Gentry, Peikert and Vaikuntanathan introduced Gaussian sampling and after some improvements to this notion Stehlé and Steinfeld showed that slightly modifying NTRU allows you to prove its security based on the Learning With Errors problem. Also around this time Gentry introduced the first fully homomorphic encryption scheme based on ideal lattices and it turns out that NTRU is itself a somewhat homomorphic scheme due to its ring structure and can be used to construct FHE schemes as well. So even though NTRU has had its fair share of problems in the past, there is currently an explosion of interesting research in related areas. Jeff ended his presentation saying that he could talk about this for hours, but that he would not.

Finally, when asked by session chair Phong Nguyen whether he would think if NTRU would be accepted at Eurocrypt today if it had not existed yet, Jeff responded: probably not.

How to Hide What You're Looking at

Elaine Shi's talk at the MPC workshop in Aarhus covered her ORAM scheme and its usage in the context of garbled circuits.

The general motivation for ORAM is the fact that access patterns can leakage information. For example, imagine a genome database in the cloud. Even when the actual sequences are encrypted, the accessed position might leak the intention of the query because diseases are linked to certain positions in the genome.

Informally, oblivious random access machines are algorithms that allow memory-restricted clients to access the memory on a server without leaking the access pattern. It is known that this incurs at least an overhead logarithmic in the size of the server memory.

After a line of works that all involve some form of reshuffling, the scheme proposed by Shi et al. in 2011 was the first to avoid this. Moreover, it is conceptually easy and can be explained by about two dozen lines of pseudocode. The core idea is to organize the memory as a tree of buckets. Every block is assigned a random leaf node, which is stored on the client in a first step.  Reading is done by looking for the block in all buckets on the path to the assigned leaf node; a block is inserted by assigning it a new random leaf node and writing it to the root bucket. To distribute the blocks over the tree in their respective paths, a data-oblivious so-called eviction is run, which takes different forms in the different variants.

It is easy to prove that the resulting scheme is oblivious because the information given to the server is just the random path of a block, which is used only once. However, there is a chance that a bucket overflows, in which case there is no secure recovery. The neglibility of this event is much harder to prove.

The described construction requires the client to store the random paths of all blocks, which uses a lot of memory. However, it is possible to outsource this to server. Done recursively, this approach reduces the memorage usage on the client size to constant.

With O(log N) block size, the original recursive scheme incurs an overhead of O(log^3 N), which can be reduced to O(log^2 N) if the block size is chosen differently for the position maps

A newer variant dubbed Path ORAM uses logarithmic client memory to store a so-called stash where a whole path of buckets is loaded to for every access. After reading from and writing to the stash, the blocks are written back to a new random path as deeply as possible. Some blocks may remain in the stash. This approach allows a constant bucket size. Together with the recursion explained above, this results in a scheme that has the same overhead as the lower bound but with non-constant client memory and negligible failure probablity.

ORAM is useful in the context of MPC because it facilitates a significant speedup of certain computations. Basic MPC only allows to compute circuits. However, some computations are less efficient when implemented as a circuit instead of a RAM program. For example, accessing an array at one position has constant complexity in a RAM program, but an MPC circuit hiding the position has to access to whole array.

Elaine Shi presented a new compiler that compiles C code to a garbled circuit protocol using ORAM techniques. For the sake of efficiency, it does not allow to branch on secret values but it allows to use data structures such as arrays in an oblivious way. The goals of this compiler are usability for non-experts and efficiency improvements through static analysis. The latter is done by minimizing the use of ORAM and running computations on public and local data locally.

Branching on secret values would require that, for every step of the computation, the instruction is fetched from RAM and all possible instructions are executed in a way such that only the desired instruction takes effect. This includes further accesses to the RAM, which makes this approach quite expensive. Excluding branching does not rule out certain conditional constructs that involve executing both branches and then selecting the desired result according to a secret bit.

Being less oblivious also allows optimizations such as avoiding ORAM techniques for memory accesses that do not depend on secret data or using several ORAM instances for different data structures. For example, Dijkstra's shortest-path algorithm requires an array to store the weights of the edges and a priority queue during the execution.

One can conclude that the simplicity of binary tree ORAM makes it a useful tool to avoid the shortcomings of circuits in multiparty computation.

Practical and Theoretical MPC in Aarhus

Last week I was in Aarhus, Denmark for the workshop on the Theory and Practice of MPC. It was a really great week with all the MPC people, thanks largely to the excellent programme covering a wide range of areas (and of course the rump session featuring Marcel's Eurovision-worthy MPC song). In this post I'll briefly describe two of the talks that captured my attention the most: a practical talk by Benny Pinkas on Private Set Intersection, and a theoretical result presented by Yuval Ishai on a promising new approach to obtaining actively secure MPC protocols.

Private Set Intersection (Benny Pinkas)

The problem of private set intersection (PSI) is simple: two parties each hold a set of items, and one or both of them wish to learn the intersection of the sets without revealing anything else. Benny spent most of the talk giving an overview of pretty much every possible method of doing PSI, including a couple of new or improved techniques, and then presented timings for implementations of all the protocols, running on the same platform in the same conditions. This kind of rigour is (sadly) rarely found in applied MPC papers and it was really cool to see this being done.

The simplest PSI protocol is based on DDH and apparently dates back to the 80s. Both parties simply hash their items and raise them to the power of a secret exponent. Then they do a Diffie-Hellman-style exchange and compute the hashes raised to the product of the two exponents, which allows them to determine any matches. This very simple method needs 2N exponentiations for N items, but can be made pretty efficient using ECC and still performs surprisingly well.

Benny went on to describe a method based on oblivious polynomial evaluation, a generic circuit-based approach using oblivious shuffling and sorting networks, and a recent, efficient construction from CCS last year that uses a bloom filter and OT. Noting that with OT extensions, the OT primitive is now much more efficient than public key techniques, so they redesigned the bloom filter protocol to allow for OT extensions and finally gave a new method based solely on OT and hashing. This new method was the fastest, computing an intersection of 2^18 items in just 14s, with 76MB of communication. However if communication is a bottleneck then the classic DDH approach still wins, with only 26MB.

Active security in MPC (Yuval Ishai)

Traditional approaches to getting active security in MPC take a passively secure protocol and modify it in some way to ensure that the adversary will always follow the protocol and cannot cheat, often using zero knowledge proofs or cut-and-choose, which are fairly expensive tools. One notable exception to this is the IPS compiler, which is a general technique for building an actively secure protocol from several passive protocols with only constant overhead, but is still too expensive for practical usage right now.

Yuval presented a new method of obtaining active security, based on the idea of creating tamper-resistant circuits that are secure against arbitrary additive manipulation of wire values. He described a clever solution that encodes inputs in a way that additive attacks can be detected, based on similar encodings to MACs used in the BDOZ and SPDZ MPC protocols. These encodings contain a random verification value, which grows quadratically with every multiplication in the circuit; to avoid this growth, they have a special gadget after every gate that ensures the output degree does not increase.

The talk was theoretical, and it will probably take some work to make these circuit conversion techniques truly practical, but this would have exciting implications for the efficiency of actively secure protocols, such as:

• Active security by simply running a passive secure protocol (e.g. GMW) over the modified, additively secure circuit
• Actively secure MPC using untrusted preprocessing (generated from a passive protocol)

Invest or not invest? That is the question, for a Networked Control Systems security operator…

In this week’s study group Theodoros S. presented a paper on securing interdependent and identical Networked Control Systems (NCS) (http://www.sciencedirect.com/science/article/pii/S0005109812004682).

The very nature of those systems that can manage the operational part within Critical Infrastructure Systems (CIS), along with the use of commercial off-the-shelf devices, such as sensors and actuators, which often bear software and hardware vulnerabilities, renders them an attractive cyber-attack target.

The authors of the paper identify two types of risks in such systems; the risks associated with the technology of the utilised devices, resulting in a probability of reliability failure, and the risks that result from the vulnerabilities of the shared network on which plants and controllers are being attached, resulting in a probability of security failure. They utilise a probabilistic failure model to model the packet loss in both the sensor and control communication channel of the NCS. In their model they introduce the idea of security interdependencies as the result of an individual’s security decision on the other players, which in its turn affects the probability of security failure. The overall failure probability constitutes a sum of reliability failure and security failure.

In order to analyze the emerging security interdependencies among the NCS operators the authors introduce a game theory model that offers optimal solutions to the operators based on the aforementioned probabilistic failure model. They form their model as a two-stage non-cooperative game. In the first stage the operators, mentioned as players, have to select their security status, modeled as a binary choice between investing in security or not, while in the second stage they have to decide upon the optimal control inputs for their respective plants. Each player’s goal is to minimize the average long-term cost, which encompasses the cost of security and the cost of operating the plant.

Considering that V is the set of player security choices V := { V¹, … ,V^m} and U is the set of player control inputs U := {U¹,… U^m}, where m is the number of the operators/players they model each plant as a discrete-time stochastic linear system:

xⁱ_t+1 = Axⁱ_t + vⁱ_tBuⁱ_t + wⁱ_t

yⁱ_t = γⁱ_tCxⁱ_t + υⁱ_t

where xⁱ_t denotes the system’s state,  uⁱ_t is the control input, yⁱ_t stands for the measured output, and wⁱ_t and υⁱ_t represent the process and the sensor noise respectively. The vⁱ_t and γⁱ_t variables represent tha packet loss in the control and sensor communication channel respectivelly, and depend on V in the way that each player’s packet loss (failure) depends upon both his own security decision and the other players’ choises. Thus Both vⁱ_t and γⁱ_t incorporate the probability of failure due to the player’s own decision (reliability failure) and the probability of failure due to every players’ decision (security failure).

The total cost is calculated as a sum of the security cost and the control cost. The security cost, computed in stage 1 of the game, depends solely on the security choice of the player and it’s not affected by the other players’ choices. On the other hand, the control cost is given by the average Linear Quadratic Gaussian (LQG) cost and depends on both V and U. The objective of each player is to minimize his total cost, thus the Hash Equilibria of the game are described as the strategies (U and V) that give the minimum security cost while in parallel preserve security.

The authors distinguish two cases depending on how the player perceives security. In the first case the player’s objective is to minimize his own individual security cost, whilst in the second case the player, mentioned as social planner, aims at minimizing the aggregate cost of all players. By applying their model on two cases, a two-player and a m-player game, they conclude that the players tend to under-invest when playing for their own individual benefit compared to when they play as social planners. For higher values of security costs they tend not to invest in security when they follow the “individual interest” strategy, while for the same values they choose to invest when they follow the “social planner” approach.

All in all, this paper presents a thorough mathematical analysis of the problem of security investments when interdependencies affect the system. The authors have successfully modeled the actions of the operators and the emerging security interdependencies, inferring from their findings that operators tend to under-invest in security when they consider security as a matter of the individual rather than acting as a social planner for the good of the system. However, the model considers a state where the presence of security in the system dictates the failure of the attack (perfect security), omitting intermediate situations. Taking into account the attacker’s choice and intermediate states where the level of security determines the probability of attack failure could lead to a more complex yet more accurate and realistic security model.

Post Quantum Cryptography

This week sees a meeting at the Newton Institute in Cambridge on what would happen to cryptography as soon as a quantum computer is built. For those who know nothing about quantum computers, the problem is that a quantum computer would break all our existing public key algorithms. It would also affect symmetric primitives such as block ciphers and hash functions; but for these it is easier to mitigate the threat.

The meeting consisted of a series of talks to motivate research in this area. After scene setting in the first morning, the main talks started in the afternoon. Ashley Montanaro from Bristol gave a nice overview of existing quantum algorithms. Including a method to attack deterministic fully homomorphic encryption using a quantum computer. Nigel Smart from Bristol then gave a talk on the current best-in-class quantum secure public key technology which are based on lattices. Kenny Paterson from Royal Holloway then talked about the problems in legacy applications using deprecated cryptography such as MD5. Tomorrow, the second day, will see talks by Joop van de Pol (Bristol) and others on further applications of lattices to cryptography.

The main issue discussed was about the threat of quantum computing. If it will happen in the next few years (or decades), then we need now to change our cryptographic infrastructure to cope with this. However, even if something does not happen we still need to worry about replacing our current cryptography at scale. Especially for current systems which need to be forward secure.

Robust Combiners: Definitions, Results, and Applications.

Yesterday, the study group given by Nigel was on robust combiners (RC) and their applications. Combining different implementations of the same primitve to enhance its security has been exploited, explicitely or implicitely, for long time in the literature, and is nothing but the cryptographic version of "not placing all your eggs in the same basket". We looked at two papers, the first one studies what cryptographic primitives admit RC, and the second paper is concerned about bounds on the size of OT networks. It uses RC for the Oblivious Transfer primitive to prove some of the upper bounds.

 A description of a cryptographic primitive P includes the semantics, thus what P does (usually one privides a functionality  describing the task), and the security of P, which deals with the ability of an attacker to learn something from an implementation of the functionality. For an interactive primitive, one splits the semantics in two parts: the "next message function" sent by one of the participants, and the "output function". This turns out to be useful to formalize the notion of combiners.

So what is a combiner? It is a box (a PPTM) that takes as input several implementations of the same primitive P, and uses them to implement P. At first it might seem redundant, the goal being that even if some but not all the implementations are insecure, the composition is still secure.  Several notions of RC can be considered depending on the type of access to the candidates. The most general notion is a (k,n)-RC, thus the box takes n candidates, with the property that if at least k of them are secure, then RC implements P securely (also the runtime of RC is polynomial in the security parameter, in n and in the length of P's inputs). However this notion does not necessarily base the security of RC in its candidates, as the construction could ignore the candidates and implement P on its own. A black-box combiner (bbRC)  is one which really uses the candidates in its implementation and security proof. Formally a (k,n)-bbRC is given oracle access to the implementation function of the candidates, and for every adversary breaking the combiner, there are n-k+1 candidates S(i) and n-k+1 adversarial PPTMs R(i), with access to A, such that R(i) breaks S(i). If one looks at interactive primitives, more restrictions can be applied. In a third-party bbRC the candidates act as trusted parties (they give no transcript, only take inputs from the combiner and generate outputs). Also one could consider transparent combiners where the  candidates are used only in the context of the interaction: every call to the next message's function is followed by the message being sent to the appropiate party. Turns out that for non-interactive primitives the three variants of bb combiners are equivalent.

Positive and negative results steam from these definitions. On the negative side, the authors show that there are no transparent (1,2)-bbRC for Oblivious Transfer. The idea of the proof is that any such combiner is equally secure when takes two insecure candidates: one secure only for the sender, and the other secure only for the receiver. This inmediatly gives a contradiction since such faulty OTs can be instantiated without any assumptions at all, giving a secure implementation of OT (those of the combiner) with no hardness assumptions. The actual proof is very evolved and is in the spirit of many other black-box impossibility results, they show a world in which OT exists, but OT-combiners do not.

On the positive side, they make a powerful observation: there exist a (1,2)-RC for OWF. The combiner simply concatenates the two outputs of the candidates. This inmediatly implies that any primitive P equivalent to OWF has also a RC (by equivalence we obviously mean a bidirectional polynomial-time reduction between the two primitives). The construction is simple: the two candidates implementing P are reduced to two OWFs, these in turn are combined into a single one which is used to construct back the primitive P. Although a nice feasibility result for Minicrypt, there are more efficient constructions: for example double-keyed encryption, XORing two PRGs, or concatenating two signatures are secure combiners. The only exception seems to be bit commitments, for which achieving efficiency is not trivial. Also they are able to show a third-party (2,3)-bbRC for OT, which is good news after the impossibility result for transparent (1,2)-bbRC.

A nice application of combiners is found in the second paper of the study group. The authors want to implement the n-ary OT functionality. Thus between n parties, any two want to run an OT between them. This is trivial if every pair has a bidirectional OT channel, but then the network would have a quadratic number (in n) of channels. Using combiners they reduce the size of the network to be linear in n (this is true if the adversary corrupts a constant fraction of the parties, note this also includes dishonest majority). The idea is to divide the parties into committees, each with the same number of members (one party may, and will be part of several committees). Within each committe there is a full OT network. Now if two parties want to run an OT, they additively secret share their inputs within the committees, each giving rise to a candidate OT implementation. The committees compute the OT in MPC (the ouptut of the OT can be  expressed as a function of its inputs). In particular they propose to use the GMW protocol, a natural choice as it builds on OT. If at least one member in a given committee is honest, the corresponding candidate is secure. The candidates are combined in a RC, which is secure if a majority of the candidates is secure. The latter is ensured by giving a collection of committees such that any adversary, corrupting an a priori constant number of parties, can cover less than half of the committes. At bottom they use techniques of disperser graphs to find such collection of committees.