Secure Computation from Millionaire

In the last session of AsiaCrypt2015, Muthuramakrishnan Venkitasubramaniam presented  his paper ``Secure Computation from  Millionaire'', joint work with abhi shelat.  Given a function f , the standard way to perform secure computation for f consists of two different steps: in the first f is transformed into either an arithmetic/boolean circuit or a RAM program, in the second a generic secure computation protocol (for example Yao/GMW based, or information theoretic) is applied to perform the actual evaluation. In his talk Muthuramakrishnan described a different approach for designing secure computation protocols.

The method he described appeared first at Eurocrypt 2004,  in the work of Aggarwal, Mishra and Pinkas,  where it was used for computing the median: Alice holds  a private dataset S_A and Bob a private dataset S_B,  each party computes the median of its own dataset, say m_A for Alice and m_B for Bob,   and jointly compare them. If  for example m_A < m_B, then Alice deletes  all the values in S_A smaller than m_A and Bob deletes all the values in his dataset bigger than m_B. Thereafter, they recursively repeat this step on the smaller dataset.  By replacing each comparison with a small secure protocol, it is possible to prove security of  the overall protocol in the semi-honest model.  This technique was later generalized by Brickell and Shmatikov and applied to solve shortest path problem.

The natural question which now arises is: what else can we compute using the comparison (millionaire) function? The authors generalized the techniques from both the aforementioned papers to a large class of problems (matroid optimizations, convex hull,  job scheduling, set cover)  that can be seen as instantiations of the greedy-algorithms paradigm.  The main idea is that of reducing these problems to iterative comparison operations and gradually revealing the answer, as for the median computation.  Unfortunately, this implies that simulation-based security can only be guaranteed (under certain conditions) in the   semi-honest and covert setting, because a malicious adversary  could adaptively abort in the middle of the computation.

Muthuramakrishnan  concluded his talk with interesting  open problems, i.e.  trying to  find examples that admit malicious security and  generalize their framework to other primitives or paradigm.

Workshop On Lattice Cryptography

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

---

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

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

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

---

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

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

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

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

---

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

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

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

Garbling with constant gate size

In the final MPC session of Asiacrypt, Carmen Kempka from NTT presented a Garbling scheme for formulas with constant size of garbled gates. The talk described an interesting new technique for garbling Boolean formulas (i.e. circuits with one output) based on trapdoor permutations and "backwards" garbling that, remarkably, achieves a constant size of just 4 bits per garbled gate.

Garbling schemes are a popular technique for constructing secure two-party computation schemes, and most practical approaches are based on the classic technique of Yao, where for each gate of the circuit, the resulting garbled circuit contains several ciphertexts that must be transmitted in the 2-PC protocol, where each ciphertext is of size $O(k)$ bits. At Eurocrypt this year, Zahur, Rosulek and Evans proposed the half-gate technique for garbling with just two ciphertexts per gate, and also showed that any "linear" garbling scheme cannot possibly do better than this. So, to reduce gate size any more, new non-linear techniques are needed; in Carmen's talk, some possible such techniques were given.

The main idea of the scheme is to use randomly generated, independent ciphertexts for each gate, so that the circuit evaluator can reconstruct these from just a single seed. The main difficulty is to ensure that the evaluator cannot then do the same as the circuit constructor, and create additional garbled circuits other than the one specified. To overcome this problem, they use trapdoor permutations (as opposed to typical garbling schemes, which just use hash functions) combined with a backwards garbling technique, where the input wire keys for each gate are chosen by solving a system of equations in the output keys and the ciphertexts.

The overall size of a garbled circuit is 4 bits per garbled gate, plus a ciphertext for each input, so this is the first scheme to achieve a constant gate size without a huge expansion in the input key size (as in Kolesnikov's scheme from 2005). However, since each input wire is uniquely determined by the output wires, gates can only have fan-out one, so the scheme is restricted to garbling formulas only. Extension to general circuits is possible, but at the cost of including 2 ciphertexts per gate.

Overall, the idea is neat, and it seems like a very interesting open problem to overcome the limitations of the scheme for general circuits, and reduce the size of the TDP-based ciphertexts for input gates.

Asiacrypt 2015: The Moral Character of Cryptographic Work

The distinguished IACR lecture at this year's Asiacrypt was given by Phillip Rogaway, who chose to talk more about the political implications of cryptographic work rather than the technology itself. This was certainly refreshing to see.

Phil started his talk by highlighting some historical events on the relationship of ethics and sciences: the nuclear bomb, the Nazi doctors, and the environmental movement. There is now the general idea that scientists should not harm society, but actually contribute to the social good as an obligation from the professional role. This manifests itself in various ethical codes and organizations; even the IACR bylaws oblige it to serve the public welfare. According to the talk, however, these values are in decline. The military has no problems recruiting scientists, and it provides more and more funding for science. At the same time, cryptography, like any technology, is used as a tool of power, which is recognized much more by popular culture than by cryptographers themselves.

An older generation of cryptographers seems to more aware of this, for example David Chaum, who mentions big data collection as early as in the 1980s as well as the possible effects on behavior. Comparing the citations of David Chaum's most cited paper on electronic mail with Goldwasser and Micali's on probabibilistic encryption, one can see that only the latter is picked up by the usual cryptography conferences. Phil argues that this split is more political than anything else and that cryptographic primitives do not inherently favor individuals or powerful entities. For example, conventional encryption can be used as well to protect one's information as to take control from the user as in trusted computing.

All these issues gained much more attention by the Snowden leaks in the summer of 2013. It was revealed that mass surveillance is rife, obscured both by secrecy and complexity. Unsurprisingly, there is significant disagreement between government agencies and surveillance studies. While the former argue that cryptography destroys the balance between security and privacy, the latter show that surveillance simply is an instrument of power that makes people conformant (or killed by drones). Furthermore, they also argue that security and privacy are not necessarily mutually exclusive. There is historic evidence of unsavory uses of political surveillance from the FBI's letter to Martin Luther King Jr. trying to convince him of suicide to totalitarian regimes of today.

Considering all this, Phil claimed that while cryptography for security is a success, cryptography for privacy is not, and moreover, that cryptography becomes more and more self-serving ("crypto-for-crypto"). To counter this, he presented a few suggestions for interesting problems such xMail and big-key cryptography. The former is about sending messages via an untrusted server without allowing the server to link sender and receiver, the latter assumes that an attacker has already subverted the machine holding a key, but only has limited bandwidth to send information.

The last part of the talk consisted of twelve suggestions for cryptographers essentially calling for a more holistic view of our work. The suggestions cover quite a range from thinking twice about military funding to stopping to draw cute little devils for the adversary when it is in fact a large state-sponsored agency. The most interesting suggestions in my opinion is that we should taste our own medicine, that is, we should use privacy tools and improve them if necessary. However, there was also the suggestion to write fewer but more relevant papers, which is orthogonal to the current incentives in science.

Phil concluded with the quote "Just because you don't take an interest in politics doesn't mean politics won't take an interest in you."

There is an accompanying essay on his website.

Games of Timing for Security in Dynamic Environments

Last week I had the pleasure of attending the 6th International Conference of Decision and Game Theory for Security based in the (very swanky) Grand Royale Hotel next to Hyde Park. The first of these conferences occured in 2010 and has continued to attract
international scholars and researchers. Decision and Game theory has proved to be a valuable and systematic framework used to deal with the intricacies involved in making rational decisions in security.

Games of timing have been an interest of game theorists for quite some time now. However, according to recent literature, most have been assuming that the cost and effectiveness of actions are time-independent. An example of this is the game of FlipIt[1]
between an attacker and defender playing for possession of a resource.
 A talk at this year's conference given by Ben Johnson removes this assumption by setting up a model that captures the discovery, repair and exploitation of software vulnerabilities. An example given by Ben was Microsoft officially stopping all support of Windows XP in 2014. Security professionals conjectured that attackers would begin ``stockpiling'' vulnerabilities until this time in order to exploit them fully.
The question that Johnson et. al.'s paper [2] and his talk tries to answer is whether the attacker should wait to exploit these vulnerabilities considering there is a risk of the internal security team discovering them. If you require a more in depth description of anything discussed here then please refer to the authors' paper.[2]

The authors consider the life cycle of the software as finite with an end time $t = T$.  The rate of vulnerability discovery is an arbitrary function of time $V(t)$. The defender's security investment $d(t):[0,T] \to \mathbb{R}_{\geq 0}$ is a function of time representing the level of her security investment. The timing of the attacker's exploitation of vulnerabilities is $a(t):[0,T] \to \mathbb{R}_{\geq 0}$. This is the amount of time the attacker will wait to exploit the vunerability when discovered at time $t$.

The repair process for vulnerabilities is determined by an exponential decay function $e^{-\lambda \tau}$. This represents the probability that a vulnerability remains exploitable at a time $\tau$ after discovery. The authors consider their model in both continuous and discrete time. For the purpose of this blog post, i'll just discuss continuous-time.

The defender's total cost over the time interval $[0,T]$ is simply $\int^T_{t=0} d(t) dt$. The expected loss to the defender if the attacker waits for time $a(t)$ to exploit a vulnerability found at time $t$ is $e^{-\lambda a(t)} \frac{R}{d(t + a(t))}$ where $R$ is a scaling factor between security costs and losses. These can be combined to find the defenders total payoff
$$
 U_d = - \int^T_{t=0} \bigg{(}d(t) + V(t)  e^{-\lambda a(t)} \frac{R}{d(t + a(t))}\bigg{)}dt
$$
Likewise, the attacker's payoff is given by
$$
 U_a =  \int^T_{t=0} \bigg{(} V(t)  e^{-\lambda a(t)} \frac{R}{d(t + a(t))}\bigg{)}dt
$$
The authors then turn to looking for conditions for useful Nash Equilibria[3] to exist.
Interestingly, it can be shown that the attacker will never wait if the vulnerability function satisfies
$$
\frac{V(t+a)}{V(t)} \geq e^{-\lambda a(t)}
$$
for every $t \in [0,T]$ and $a(t) \in [0, T-t]$. This begins to provide guidelines for finding vulnerability repair rates in order to stop the attacker from stockpiling vulnerabilities. Further work suggested by Ben is to study the Stackelberg equilibria[4] of the game.


References
[1] -  https://eprint.iacr.org/2012/103.pdf
[2] -  http://aronlaszka.com/papers/johnson2015games.pdf
[3] - https://en.wikipedia.org/wiki/Nash_equilibrium
[4] - https://en.wikipedia.org/wiki/Stackelberg_competition

Sardinia eCrypt School, October 2015

As I was standing in the sweltering heat, the burning light from above with the hustle bustle of the busy bodies rushing all around me, I thought to myself "in about three hours I'll finally get through Stansted airport security".

One of the reasons I applied for a PhD at the University of Bristol was to travel; to travel all around the world attending conferences, networking with other academics in my field and collaborating on applicable pieces of work. However, I hadn't anticipated that I would arrive at Bristol and meet my supervisors (Elisabeth Oswald and Daniel Page) for them to say "thank goodness you're here, now pack your bags and head to Sardinia for a week".

I didn't argue.

The school I'm referring to is the "School on Design and Security of Cryptographic Algorithms and Devices", and this year it was co-sponsored by the International Association for Cryptologic Research (IACR). A total of roughly 80 Academics and Professionals from all around the globe attended the conference, many of whom were new PhD students (comme moi), and a few were seasoned Crypto School Veterans. As a newbie I experienced the excitement of meeting all these new faces, and getting to know them over a few glasses of wine (the magnificent hotel resort was very generous with its distribution of wine, particularly to my table).

The Summer School took the form of a crash course in all different aspects of cryptography, focusing on covering a lot of ground with introductory lectures. For my first blog post I really wanted to focus on one particular talk, but after attending them all it became clear that I had quite a few favourites; for their content, Benedikt Gierlichs "Introduction to Implementation Attacks" and Josep Balash "Introduction to Fault Attacks" were fascinating. With a background of little knowledge of practical attacks on embedded security, I was shocked to see just how easy one could manipulate theoretically secure devices, simply by making minor alterations to the embedded circuit (see slides from Benedikt Gierlich "Introduction to Implementation Attacks" for more detail).

As for the presentation of the talk, I give a special mention to Gregor Leander. He was able to introduce Lightweight Block Cipher design whilst holding the attention of his audience through quick wit; he told stories of multiple attempts to create nifty lightweight block ciphers, for them to be proven weak and useless within several months of publication. My favourite was the story of Keeloq - a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register. It was sold to Microchip Technology Inc in 1995 for $10 million (wow), and it was (maybe is) used in many remote keyless entry systems by companies such as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, Jaguar, etc. However, the Keeloq algorithm does not use cryptographic nonces (for simplicity), nor does it include time stamping (due to clock drift). This means, of course, that the algorithm is vulnerable to replay attacks: simply jam the channel while intercepting the code, and one can obtain a code that may still be usable at a later stage. If your car still uses Keeloq, you should probably either invest in a steering wheel lock, or paint your car bright pink.

To summarise, the organisers of the School did a fantastic job of bringing everyone together, the speakers were all fantastic and engaging, and I learnt a great deal about Cryptography whilst having the greatest week in Sardinia. I would strongly recommend this school to anyone who has just started a PhD in cryptography, regardless of their topic title. I will most certainly be getting involved in as many of these schools as I can!

Finally, a big shout out to all the friends I made at the School - you are all brilliant and I can't wait for the next one. Also, sorry for my atrocious dancing throughout the week. Blame the bar for playing 'Barbie Girl'.

Obfuscation: Hiding Secrets in Software

Last week the HEAT-hosted summer school on FHE and multi-linear maps took place. On the final day we learned about indistinguishability obfuscation from the eminent cryptographer Amit Sahai. The talk was entitled 'Obfuscation: Hiding Secrets in Software' and a summary is presented here.

Suppose you want to keep a secret, but some adversary has taken over your brain: whenever you think about the secret, the adversary is able to read it. While this Orwellian nightmare is not realisable for us (at the moment!), in software this happens all the time. This is the fundamental question of obfuscation; i.e., Can we keep a secret from some adversary if all of the functionality is known? Indistinguishability obfuscation is an attempt to realise this.

One early idea on the way to program obfuscation was secure multi-party computation (MPC). The rough idea of secure MPC is to allow each individual of a party to compute some function on everyone's input without anyone learning too much about the input of any other person. In such a situation, an adversary may be one member of the party, or even act as multiple members in order to try to work out something about the input of one of the other party members. In this case, the adversary has a lot of information he can exploit; for true obfuscation, however, we want that nothing at all be revealed to an adversary.

Now we ask the important question, Which programs allow for secrets to be kept? Suppose we have a program with some secret $s$ accepting an integer $x$ as input such that it outputs 1 if $x<s$ and 0 otherwise. By a simple binary search, $s$ can be determined by the adversary. Plausible security requires unknowable queries, so if we are to succeed in obfuscation we need to have a 'virtual black box'.

However, back in 2001, black box obfuscation was suggested and ruled out in the same paper: it cannot be achieved for all programs. The authors go on to describe and define indistinguishability obfuscation (iO) -- obfuscating two programs with the same functionality so the programs are computationally indistinguishable. Interestingly, if P=NP then any circuit can be obfuscated, and so iO cannot produce hardness itself.

This well-known paper was the first construction of iO for NC$^{1}$ circuits. The authors describe a useful possible application: crippleware. Suppose you are a software vendor and have written a program with lots of functionality, and you want to distribute a trial version of the software which is somewhat restricted. In order to block out trial users from using content for which they have not yet paid, one possibility is for you to go through the code and manually remove the blocks of code for which a full licence should be required. In a large program this very cost- and time-inefficient. However, if instead you simply restrict the functionality of the user interface and release an obfuscated version of the program, this version will not have any functionality beyond that which was intended.

Very recently, there have been many attacks on multi-linear maps, many of which rely on obtaining top-level encodings of zero. Because in obfuscation the adversary never has access to encodings of zero, it is resistant to these attacks. Thus the hope remains that obfuscation will not be broken.