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.