Study Group: Multilinear Maps (I)

This week's student group (30 Apr) was given by Joop and Enrique. They discussed the paper "Candidate Multilinear Maps from Ideal Lattices" (PDF). The paper describes plausible lattice-based constructions with properties that approximate the soughtafter multilinear maps in hard-discrete-logarithm groups. The security of the constructions relies on seemingly hard assumption (which is a multilinear analog of DDH) in ideal lattices.

Definition. Cryptographic Multilinear Maps [BS03]:

For κ+1 cyclic groups G_1,...,G_κ ,G_T (written additively) of the same order p, a κ  multilinear map e : G_1,...,G_κ→ G_T has the following properties:

1. For elements {g_i ∈ G_i}_{i=1,...,κ}, index i ∈ [κ] and integer α∈ Z_p, it holds that e(g_1,...,α· g_i,...,g _κ) = α· e(g_1,...,g _κ).

2. The map e is non-degenerate in the following sense: if the elements {g_i ∈ G_i}_{i=1,...,κ}, are all generators of their respective groups, then e(g_1,...,g_κ ) is a generator of G_T .

A cryptographic multilinear map scheme consists of efficient procedures for instance-generation, element-encoding validation, group-operation and negation, and multilinear map,

MMP = (InstGen, EncTest, add, neg, map). These procedures are as follows.

• Instance Generation. A randomized algorithm InstGen that takes the security parameter λ and the multi-linearity parameter κ , and outputs (G_1,...,G_T,p,e,g_1,...,g_κ ).  G_i's and G_T describe the groups, p ∈Z is their order,  G_1,...,G_κ→ G_T describes an κ -multilinear map as above, and g_i∈{0,1}^{*}  for i = 1,..., κ encode generators in these groups. Denote params=(G_1,...,G_T,p,e).
• Element Encoding. Given the instance params, an index i∈[κ ], and a string x ∈{0,1}^{*},  EncTest(params,i,x) decides if x encodes an element in G_i. Similarly EncTest(params, κ+1; x) efficiently recognizes description of elements in G_T .
• Group Operation. Given x,y∈G_i, add(params,i,x,y) computes x+y ∈G_i and neg(params,i,x) computes -x ∈G_i. This implies also that for any α ∈G_i we can e ciently compute α· x ∈G_i.
• Multilinear Map.For {x_i ∈ G_i}_{i=1,...,κ}, map(params,x_1,...,x_κ) computes e(x_1,...,x_n)∈G_T.

Hardness Assumptions

For the multilinear map to be cryptographically useful, at least the discrete logarithm must be hard in the respective groups, and we usually also need the multilinear-DDH to be hard.

1. Multilinear Discrete-log (MDL). The Multilinear Discrete-Log problem is hard for a scheme MMP, if for all κ > 1, all  i ∈ [κ] and all probabilistic polynomial time algorithms, the discrete logarithm advantage of A, 

AdvDlog_{MMP,A,κ}(λ) = Pr[A(params,i,g_i, α· g_i) = α : (params,g_1,...,g_l) ← InstGen(1^λ,1^κ ), α←Zp], 

is negligible in λ.

2. Multilinear DDH (MDDH). For a symmetric scheme MMP (with G_1 = G_2 = ), the Multilinear Decision-Di e-Hellman problem is hard for MMP if for any and every probabilistic polynomial time algorithms A, the advantage of A in distinguishing between the following two distributions is negligible in : (params, g, α_{0}g, α_{1}g,...,α_{κ}g,( Prod_{i=0,..,κ} α_i)·e(g,..,g)) and (params, g, α_{0}g, α_{1}g,...,α_{κ}g, α·e(g,..,g)).

Graded Encoding Scheme: Efficient Procedure, the Dream Version

The authors first describe  a "dream version" of the efficient procedures which they do not know how to realize, then  modify them to deal with technicalities that arise from their use of lattices in the realization.

Instance Generation. The randomized InstGen(1 ^λ,1^κ ) takes as inputs the parameters λ, κ, and outputs (params, p_{zt}), where params is a description of a κ-Graded Encoding System, and p_{zt} is a zero-test parameter for level κ.

Ring Sampler. The randomized samp(params) outputs a level-zero encoding α ∈ S_{0}^( α) for a nearly uniform element α ∈ R.

Encoding. The possibly randomized enc(params, i, α) takes a level-zero encoding α ∈ S_{0}^( α) for some   α ∈ R and index i ≦ κ , and outputs the level-i encoding u ∈ S_{i}^( α)  for the same α .

Addition and Negation. Given params and two encodings relative to the same index, u_{1} ∈ S_{i}^( α_1) and u_{2} ∈ S_{i}^( α_2), we have add(params, i, u_1, u_2) = u_1 + u_2 ∈ S_{i}^( α_1+ α_2), and neg(params, i, u_1) = -u_1 ∈ S_{i}^(-α).

Multiplication. For u_1 ∈ S_{i_1}^(α_1), u_2 ∈ S_{i_2}^(α_2) such that i_1+ i_2 ≦ κ , we have mul(params, i_1, u_1, i_2, u_2) = u_1 × u_2 ∈ S_{i_1 + i_2}^(α_1 · α_2) .

Zero-test. The procedure isZero(params, u) output 1 if u ∈ S_{κ}^(0) and 0 otherwise.

Extraction. This procedure extracts a canonical and random representation of ring elements from their level-κ encoding. Namely ext(params, p_{zt}, u) outputs s ∈ {0,1}^λ, such that:

(a) For any α ∈ R and two u_1, u_2 ∈ S_{κ }^(α), 

ext(params, p_{zt}, u_1) = ext(params, p_{zt}, u_2),

(b) The distribution {ext(params, p_{zt}, u) : α ∈ R, u ∈ S_{κ }^(α)} is nearly uniform over {0,1}^λ.

New Encoding Scheme

An instance of the scheme relative to the parameters encodes elements of a quotient ring QR = R / I, where I is a principal ideal I = <g> ⊂  R, generated by a short vector g. Namely, the ring elements that are encoded in the scheme are cosets of the form e + I for some vector e. The short generator g itself is kept secret. In addition, the system depends on another secret element z, which is chosen at random in R_q. For higher-level encodings, a level-i encoding of the same coset is a vector of the form c/z^i ∈ R_q with c ∈ e + I short. Speci cally, for i ∈ {0, 1, ..., κ} the set of all level-i encodings is S_i = {c/z_i ∈  R_q :  ||c|| < q^{8/g}}, and the set of levle-i encodings of the plaintext element e + I is
S_{i}^(e + I) = {c/z_i ∈  R_q :  c ∈ e + I, ||c|| < q^{8/g}}.

Instance Generation. The instance-generation procedure chooses at random the ideal-generator g and denominator z. The denominator z  is chosen uniformly at random in R_q. The generator g ∈ R should be chosen so that both g and g^{-1} ∈ K = Q[X]/(X^n +1) are short. Once we have g, z, we choose and publish some other elements in R_q. Speci cally we have m + 1 elements rand_1,..., x_m, y that are used for encoding, and an element p_{zt} that is used as a zero-testing parameter. We also choose a random seed s for a strong randomness extractor. The instance-generation procedure outputs 

params = (n, q, y, {x_i}_i, s) and p_{zt}.

Sampling level-zero encodings. To sample a level-zero encoding of a random coset, we just draw a random short element in R, d ← D_{Z_n, σ'} , where σ' = σ n (for σ  that was used to sample g).

Encodings at higher levels. To allow encoding of cosets at higher levels, we publish as part of our instance-generation a level-one encoding of 1 + I, namely an element y = [a/z]_q where a  ∈ 1 + I is short. A  simplistic method of doing that is drawing a  ←  D_{1+I, σ'} , then computing y from a.

Adding and multiplying encodings. It is easy to see that the encoding as above is additively homomorphic, in the sense that adding encodings yields an encoding of the sum. This follows since if we have many short c_j 's then their sum is still short, || Prod_{j} c_j || ≦ q, and therefore the sum  c = Prod_{j} c_j = [Prod_{j} c_j]_q ∈ R_q belong to the coset Prod_{j} (c_j+I). Hence, if we denote u_j = c_j/z ∈ R_q then each u_j is an encoding of the coset c_j + I, and the sum [Prod_{j} u_j]_q is of the form c/z where c is still a short element in the sum of the cosets.

Zero-testing. isZero(params, p_{zt}, u) = 1 if ||[p_{zt}_q ]||_∞ < q^{3/4}, or otherwise 0.

Extraction. To extract a canonical and random representation of a coset from an encoding u = [c/z ^κ]_q, we just multiply by the zero-testing parameter p_{zt}, collect the (log q)/4 -λ  most-signifi cant bits of each of the n coe fficients of the result, and apply a strong randomness extractor to the collected bits (using the seed from the public parameters). Namely ext(params,  p_{zt}, u) = EXTRACT_s(msbs([u ·  p_{zt}]_q)) (msbs of coe fficient representation). This works because for any two encodings u, u' of the same coset we have ||p_{zt}u - p_{zt}u'|| = ||p_{zt}(u - u')|| < q^{3/4}.

The security of the graded encoding systems relies on new and at present it seems unlikely that they can be reduced to more established assumptions, such as learning-with-errors (LWE),  or even the NTRU hardness assumption.

Is TLS Secure?

TLS is the standard which defines how web traffic is encrypted. It is what keeps your credit card secure when you buy something on the internet, and it is what should be used (but sometimes isn't) to make sure a password is not snooped when you log into a web site. You know when a web site uses TLS, because the location uses the https prefix and not the http prefix.

In recent months we have seen a lot of "attacks" on TLS. Many with cool names such as BEAST, CRIME, Lucky 13 and TIME. There has also been a recent one involving an attack on using RC4 within TLS, which alas does not have a cool name. Many of these attacks make use of timing information leakge (aka side channels) and some (Lucky 13 and the RC4 attack) attack the underlying cryptography.

Before proceeding we should perhaps recap on a bit of history. Firstly TLS comes in three flavours, TLS 1.0, TLS 1.1 and TLS 1.2. Now TLS 1.2 has been around since 2008, and is the latest version, it fixes a number of problems with earlier versions and should be used by default. So now guess how many systems use TLS 1.2? It turns out virtually none. Most browsers and web sites use the old versions of TLS, and the main reason for not upgrading is said to be because people do not see the benefit of moving to the newer standard. Indeed at a recent meeting, one person said to me that all the recent attacks on TLS are not real attacks as they will not affect anyone in the real world.

Let us now look at the problems these attacks show up. 

The timing based attacks are basically a form of side-channel attack, and side-channels have been known in the cryptographic community since the late 1990s. Indeed there is a whole conference, CHES, which devotes much of its discussion to looking at side-channel attacks in their various forms and how to protect against them. It seems rather hard to believe that after so many years, one of the key pieces of security infrastructure we rely on still falls to side-channel attacks. After all they have been known about for years, so why would one not want to defend against them?

The Lucky 13 attack is an attack on the method used to encrypt data. It uses a method known as "MAC-then-Encode-then-Encrypt". It has been known, again since the turn of the century, that methodologies such as "MAC-then-Encrypt" (of which MAC-then-Encode-then-Encrypt is a variant) are not a good design practice. Modern cryptographers have for nearly 15 years been requiring the use of a method known as "Encrypt-then-MAC", which is known to be much more secure. Indeed it comes with a mathematical proof of security, and TLS 1.2 comes with an even better solution, namely a fully integrated Authenticated Encryption algorithm called GCM. For those readers doing undergraduate courses, this basically means that TLS 1.0 and TLS 1.1 do not use an IND-CCA encryption algorithm; whereas TLS 1.2 does. So again we have that the basic internet security infrastructure is using a method which has known to be suspect for a long time, and for which simple fixes have also been known for years.

If you want to avoid some of the problems with "MAC-then-Encode-then-Encrypt" then a simple solution would be to use a stream cipher to do the encryption. And TLS 1.0 and TLS 1.1 allow one to use such a stream cipher; indeed they allow the use of the RC4 stream cipher. But RC4 has been known to have structural weaknesses, which means that the key stream it produces is not random enough for modern cryptographic use. How long have these weaknesses been known? Well about the same length of time.

So we have in all cases that the current attacks show that the deployed software has weaknesses, and these weaknesses have been known for a very long time. All the new attacks do is show how to exploit these weaknesses within TLS. Yet still people are claiming TLS 1.0 and 1.1 is secure. After all the attacks are rather contrived and do not apply to most real world instantiations of TLS!

Does this remind one of another recent case of security engineers ignoring the advice of cryptographers for many years? Well it should. In the mid 1990's various structural weaknesses were found in the MD family of hash functions, including MD5 which was used all over the internet. But since no real world attacks were found the security engineers did not see the point of replacing MD5 in their software. When real attacks on MD5 came along, which compromised security for real world users, cryptographer could claim a great big "We told you so", and engineers then had to spend (and are still spending) a great deal of effort removing uses of MD5 in software.

In some sense the recent attacks are basically an early warning sign, that the security concerns of the cryptographic community re TLS 1.0 and TLS 1.1 are getting closer to real world attacks. It is still probably safe to send your credit card details over the internet, but for how long? When will a total break occur? No one knows. The simplest quick solution is to move to TLS 1.2, and hopefully that is what browser vendors, web sites and software producers will now do. But this is hard, there is no point in your browser using TLS 1.2, unless the web site also uses TLS 1.2.  

Lets hope the change is made, before the cryptographic community has another round of "We told you so".

When two satellites collide.....

Modern cryptography is about so much more than encryption; as follows of this blog will know. Last month I discussed how the technique of secure multi-party computation (MPC) can be used to provide defence mitigation techniques for servers. By splitting up a secret held on one server into two secrets held on two servers one can mitigate against a single server being compromised by an attacker. The functionality provided by the secret is then still accessed, but via a secure multi-party computation protocol. What is surprising is that such a protocol is now really practical; whereas a few years ago it would have been inconceivable to think about implementing it.

But there are all sorts of other cool things one can do with MPC. A recent video by our Estonian friends on YouTube shows an application of MPC to the world of space. The problem statement is quite simple; there are so many man made satellites orbiting the earth that it is likely that two will collide. Given how expensive this is, in terms of replacing the satellite, people want to avoid this. However, the location of each satellite can be a closely gaurded secret; it can even be a national secret. So what we want is a way for two parties to compute whether two satellites are about to hit each other, without either party learning the location of the other satellite in the case where they are not about to hit each other (if they are going to hit each other then the location of the collision is in some sense going to leak by definition).  As expected this is another practical, real world application, for multi-party computation.

So with MPC being used to stop satellites hitting each other cryptographers really are becoming rocket scientists.

Study Group: Signature Schemes from Standard Assumptions

The latest study group, on signature schemes from standard assumptions, was given by Florian Böhl, who is currently visiting Bristol. He discussed three schemes from the (bilinear) Computational Diffie-Hellman assumption: the scheme by Waters from Eurocrypt '05, the scheme by Hohenberger and Waters from Eurocrypt '09 and finally a new scheme which is to appear at Eurocrypt '13. Theoretically, Digital Signature schemes are a weaker primitive than Public Key Encryption, as signatures are equivalent to one-way functions whereas PKE requires something stronger. On the other hand, it seems much more difficult to construct practical signature schemes as opposed to PKE schemes. The most efficient known signature schemes rely on "strong" assumptions, where the adversary only needs to break one instance of the system out of many possible instances. The schemes that Florian discussed are based on simpler assumptions, such as the standard (bilinear) Computational Diffie-Hellman assumption and the standard RSA assumption.

The security notions for signature schemes are slightly different than those of encryption schemes. Consider message indistinguishability of encryption schemes, where the adversary chooses two messages, gets the encryption of one of them and has to guess which message was encrypted. However, for signatures, the adversary sends in several messages and receives accompanying signatures. Finally, he needs to output a valid signature of a new message of his choosing. The only restraint on this message is that it was not queried before by the adversary, which means he has many options in choosing his challenge.

An important notion of security for digital signatures is Existential Unforgeability under Chosen Message Attack, which can be non-adaptive (EUF-naCMA) or adaptive (EUF-CMA). In the non-adaptive case, the adversary chooses q messages and sends them to the challenger. He then receives the public parameters and valid signatures for these q messages and has to output a fresh message with a valid signature for this message. In the adaptive case, the adversary receives the public parameters at the start and can adaptively query q messages one by one, receiving a valid signature every time. As in the non-adaptive case, he needs to output a fresh message with a valid signature.

It is possible to turn a non-adaptively secure scheme into an adaptively secure scheme using something known as a Chameleon Hash Function. A Chameleon Hash Function (CHF) is a special hash function that has a trapdoor which allows you to find collisions. Specifically, it takes a message and some randomness as input and if you are given a new message, the trapdoor allows you to find new randomness such that the CH of the first message and the first randomness is the same as that of the second message and second randomness. By signing the CH with the non-adaptive scheme, the challenger can generate signatures for q random CH's and then find the appropriate randomness for each of the adaptive queries of the adversary. The randomness must also be published as part of the signature to allow verification. An adversary breaking the new scheme must either break the collision-resistance of the CHF or give a forgery for the non-adaptive scheme.

At Eurocrypt '05, Waters presented an Identity-Based Encryption scheme with a security reduction to the decisional Bilinear Diffie-Hellman assumption. It is possible to construct a signature scheme from this Identity-Based Encryption scheme using a generic conversion (due to Boneh and Franklin). An IBE scheme is an encryption scheme where the public key is someone's identity (such as their email address for example) and a master secret key can be used to derive secret keys for each identity. To turn this into a signature scheme, one can view the message to be signed as an 'identity' and then give the associated secret key as the signature of the message. To verify the signature of a message, the verifier can encrypt a random value with the message (the public key in the IBE scheme) and then decrypt it using the signature (the associated secret key for this identity). The security of this signature scheme is equivalent to the security of the underlying IBE scheme, which is decisional BDH in Waters' scheme. However, Waters shows that it is possible to use the bilinear map to verify signatures deterministically, which results in a signature scheme with a security reduction to the weaker Computational Diffie-Hellman assumption.

It turns out that this scheme implicitly contains a Programmable Hash Function, a concept later formalized by Kiltz and Hofheinz (Crypto '08), which will be the topic of a study group in the near future. The PHF proposed by Waters has some adaptive properties and hence the scheme does not require the use of a CHF to be adaptively secure. However, this particular PHF is unfortunately not very efficient and therefore the resulting signature scheme is also not very efficient. In the scheme by Hohenberger and Waters from Crypto '09, they instead use a slightly weaker notion which is due to Boneh and Boyen, from their selectively-secure signature scheme. The security of the resulting scheme is based on the RSA assumption and the scheme is stateful, in the sense that the signer must maintain a state that counts the number of signatures issued. Hohenberger and Waters state that they believe that the statefulness of the scheme can be removed and that their scheme is a step towards realizing stateless signature schemes.

Consequently, the new paper that was discussed at the study group, which is to appear at Eurocrypt '13, will show how to convert such stateful schemes to efficient stateless schemes. They use a CHF and a 'weakly programmable hash function' as in the scheme by Hohenberger and Waters. In their work, they provide new and more efficient schemes, based on the RSA, bilinear CDH and SIS assumptions.

2012 Turing Award Goes to Cryptographers

The Turing Award (a kind of Noble Prize for Computer Science) has been awarded for 2012 to two cryptographers; Shafi Goldwasser and Silvio Micali. The announcement of this award came last week and is for their pioneering work on the foundations of cryptography. Over the years the list of Turing Award winners reads like a who's who of famous computer scientists (Hamming, Dijkstra, Knuth, Ritchie etc etc) and has included prior work in cryptography; Andrew Yao (2000) and Rivest, Shamir and Adleman (2002).

Goldwasser and Micali's work forms the foundation of almost everything that modern cryptographers do. In a ground breaking series of papers in the 1980's they defined the notion of semantic security, this is the de-facto modern security definition for encryption schemes. They also presented the first encryption scheme which met this definition (the Goldwasser-Micali scheme). This public key scheme is not very efficient, but the ideas behind it's construction form the basis of all modern encryption algorithms.

With Rivest they produced the GMR security definition for digital signature schemes, otherwise known as universal forgery under chosen message attack (UF-CMA). This definition again forms the basis of all modern constructions of digital signatures; such as the ones used to verify the validity of digital certificates in your browser or chip-and-pin cards.

However, their most interesting contribution is the idea of zero-knowledge. In many areas of computer science one is interested in a computer learning some information; say about a data set in biology etc. Areas such as Machine Learning try to develop algorithms which take data and learn from that data. In security we are interested in the opposite to some extent; namely we want to know that an algorithm cannot learn certain information (for example a secret key). To formalise this notion Goldwasser and Micali introduced the notion of zero-knowledge; i.e. they formally defined what it means for an algorithm or process to learn nothing. 

This has important practical importance. When you go into a shop to purchase something with your chip-and-pin card, the card is used to authenticate you to the shop, it also is used to authenticate the transaction. These authentication steps require using the secret key embedded into the card. However, we do not want the shop to learn the underlying secret even if it sees a large number of transactions performed with your card. This is where zero-knowledge protocols come in. They gaurantee that no matter how many transactions are seen by the merchant, the merchant cannot use these to validate an invalid transaction. They also form the basis behind protocols used in electronic locks; for example the key fob for opening your car door.

These three topics (semantic security, GMR security and zero-knowledge) form the basis of the cryptography teaching at Bristol University, and none of this would have been possible without the ground breaking work of Goldwasser and Micali. It is also fitting that the 2012 award should go to cryptographers; after all 2012 was the 100th anniversary of the birth of Alan Turing, and in a previous blog post we have discussed Turing's central contributions to cryptography.

Study Group: A New Approach to Practical Active-Secure Two-Party Computation

This week's study group, given by Nigel, concerned the paper A New Approach to Practical Active-Secure Two-Party Computation (CRYPTO 2012) by J.B. Nielsen et al. In this paper the authors propose a 2-party UC protocol computational secure against a semi-honest adversary in the random oracle model, in which two parties, Alice and Bob, with some private input bits x and y, respectively, jointly compute a boolean function f(x,y). The main motivation for the paper is to give  a PRACTICAL efficient 2-party protocol with the standard requirements of 1) Correctness (the output of the computation is correct) and 2) Privacy (the output is kept secret). To this purpose they use a new approach based on Oblivious Transfer (OT), actually getting  efficiency from a highly inefficient tool. In particular they introduce a new way of extending OTs: from a small number of seed OTs they can derive, in an actively secure way, a large number of committed OT-like primitives.

Their approach is based on the passive-secure 2-party protocol of [GMW87], that extensively uses OT. The input bits x and y are secret shared in such a way that Alice holds x_A, y_A and Bob holds x_B, y_B, with x=x_A⊕ x_B, y = y_A⊕ y_B. Then the boolean circuit computing the function f(x,y) is evaluated gate-by gate.  Suppose the parties want to compute an AND gate: they need to calculate a random sharing  z_A, z_B  of  z= xy = x_Ay_A ⊕ x_A y_B ⊕ x_B y_A ⊕ x_B y_B. So they locally compute t_A=x_Ay_Aand t_B=x_By_B, and  then, using OT, they compute the cross products u=x_Ay_B and v=x_By_A such that xy=t⊕u⊕v. To achieve active security the authors add information theoretic Message Authentication Code (MAC) to all the shares. The first step is the oblivious authentication of bits (aBit): A party (for example Bob) holds a global key Δ _A ∈ {0,1}^k , where k is the security parameter, and, for each of the Alice's bit x, a local key K_x ∈ {0,1}^k . Alice inputs x in a OT and she receives the MAC   M_x= K_x⊕ x Δ _A. Notice that if y is another message and  M_y=K_y⊕ y Δ _A its corresponding MAC, then Alice can locally compute M_x⊕ M_y=(K_x⊕ K_y)⊕(x⊕y) Δ _A. It is important to note that Bob has to  use the same global key  Δ _A for each of the OT. To ensure this  a cut-and-choose-like technique is proposed in which one authenticates twice as many bits as he needs and then he sacrifices  half of them checking that they were done with the same global key. Using aBit, the authors describe  Authenticated AND (aAnd) and Authenticated OT (aOT). If Alice holds authenticated random bits a,b,c, aAnd allows to compute c=ab and  obtain an authentication of this result; aOT permits to perform OT of previously authenticated bits and   produce an authentication on the result.

Summing up  the authors describe a secure 2-party protocol for boolean function in the preprocessing model. During the preprocessing phase  they prepare random authenticated messages, random authenticated multiplication triples and random authenticated OTs, using aBit, aAnd and aOT. In particular aAnd is used to get a MAC on t_A=a_Ab_A and  t_B=a_Bb_B and aOT to secure compute u=a_Ab_B and v=a_Bb_A (u,v are the cross products in c=ab=a_Ab_A ⊕ a_A b_B ⊕ a_B b_A ⊕ a_B b_B), that will be used  in the AND gates during the online phase, where the preprocessed data is used to actually evaluate the circuit. The efficiency  is guaranteed by the OT-extension technique, that from a small number of long MACs on Bob 's random bits permits to derive many, short MACs on Alice's random bits.  Intuitively the OT-extension works as follows:

1) Long MAC for Bob: this first step consists in generating   a few aBit using very long keys. Bob inputs some random bits y_j, j=1, ..., h,  in a OT and receives 

N_j=L_j⊕ y_jΓ_B, 

for j=1, ..., h and N_j, L_j, Γ_B∈ {0,1}ⁿ, with h small (around 128) and n very big. This step is also called LaBit (Leacking Bits) as the key holder (Alice in this case) can learn a few of Bob's bits y_j.

2) Short MAC for Alice. This step consists in generating a lot of aBit with short keys: 

• Rewrite the MACs created in 1) in matrix form N_ij=L_ij⊕ y_jΓ_Bi , i=1,...,n and j=1,...,h:

       [ N₁ |  . . . | N_h ] = [ L₁ | . . . |  L_h  ] ⊕ [ y₁Γ_B1 | . . . | y_hΓ_Bh].

•  Swap the position of the MACs and the keys:     

     [ L₁ |  . . . | L_h ] = [ N₁ | . . . |  N_h  ] ⊕ [ y₁Γ_B1 | . . . | y_hΓ_Bh].

•  Flip the values of columns and rows:   

                      [ L_1j   . . .  L_nj ]   =   [ N_1j  . . .  N_nj  ] ⊕ [ y_j (Γ_B1  . . .  Γ_Bn) ],  j=1, . . ., h. 

•  Rename M_ij = L_ji,  K_ij = N_ji, x_i =  Γ_Bi  and Γ_Aj  = y_j, from which we get the n MACs

 M_i=K_i⊕ x_iΓ_A,

           i=1, ..., n and M_i, K_i, Γ_A∈ {0,1}^k.

This step is called WaBit (Weak Bits) as a few bit of the global key Γ_A may leak to the MAC holder. 

3) Fix the problems obtaining a fully secure global key Δ _A.  

Using these ideas the authors obtain the first practical 2-party computation protocol based on OT at a rate of about 20000 gates for seconds.  

 

     
  
    

Crypto is Dead; Long Live Crypto!

At last week's RSA conference, in the Cryptographer's Panel, Adi Shamir said that we need to prepare for a post-crypto world. The same basic idea was put forward by Jonathan Zittrain in his invited talk at last years CRYPTO conference, which was entitled "The End of Crypto". The basic idea behind both statements is that in the modern world the attacker is already inside the box, so no matter how much encryption you use the bad guy will always get your data.

Let us elaborate on this idea a bit more. In the consumer field you may use your smart phone to store all sorts of important data on it (email addresses, passwords, banking data etc), but most users also download apps. Very few of these apps have had any form of code or security review, and so could contain malicious code which can compromise your phone, and your security.

In the enterprise space the problem is even more acute. The existance of APTs (Advanced Persistant Threats) means that enterprises need to assume that the attacker is already within their perimeter. This has always been true, in that often attacks come from the inside, but now we have seen external attacks which are based on dorment code, lying in wait, within an enterprises security perimeter.

The usual cryptographic model is that there is at least one honest person in a protocol. This is still true, the user of a system may be honest, but if we cannot trust the system they are on to not be compromised, we can essentially not trust anything. What is the point of encrypting data if the attacker already has the key? Even if the data has been encrypted successfully, at some point it needs to be decrypted so as to process it. At the point of decryption, if the attacker controls the machine, he also controls the decrypted data. So with such all pervasive threats, how can crypto be of any use what-so-ever? In some sense this means "Crypto is Dead!".

Luckily, however, cryptography is about more than just encryption and authentication. Modern cryptography gives us a number of tools which we can use to secure systems. In Bristol we have been working for a number of years in turning a theoretical technology called multi-party computation (MPC) into a practical reality. The basic idea behind MPC is the following: Suppose a set of n parties have their own secret inputs, for example party i has input x_i. Now suppose they want to compute some function on these inputs say

f(x₁,...,x_n) 

MPC allows us to do this, via a protocol, in such a way that the parties learn the output of the function, but no one learns anything about the other parties inputs.  Traditional use-cases which have been proposed for MPC are the sharing of databases etc. 

However, MPC also allows one to solve the problem of what hardware to trust in an enterprise environment such as that described above. In other words we can use MPC as a threat mitigation strategy to avoid APTs and other malware on our systems. We do this by altering the standard use case of MPC, instead of having multiple parties we have one party who just happens to be using multiple computers.

Suppose we expect that an attacker is inside our network. If we put in place enough protection to ensure he is not on all of our computers at once, then we may be able to hold a secret key on that uncompromised computer. But we do not know which computer is uncompromised. Using MPC we can get around this. Consider the simplified situation where we have two computers, where we know it is likely one is compromised and the other is not. We now "split" the encryption key between the two servers, for example via a one-time pad. So each party essentially has a random string, but the two parties together when combining their random string have the secret key.  We treat the two random strings as the inputs x₁ and x₂ above, and now consider f as the encryption function. In this way the two servers can perform the encryption, without anybody ever knowing the underlying secret key itself.

We could use the same idea for messages. Instead of having one server needing to decrypt some ciphertext, with the obvious problem of what happens when the server is compromised, a combination of servers could use MPC to decrypt the ciphertext and then use MPC to process the plaintext. In this way no single party ever sees the underlying key, and the underlying plaintexts, at all.

This might seem like pie in the sky, but we can actually perform such computations today, using protocols developed in Bristol and at other places around the world. For example when we first implemented the AES functionality in a covertly secure manner back in 2009 we could evaluate a single AES block encryption between two partes in 60 seconds. Now this can take as little at 0.012 seconds, and we can process around 1000 such encryptions per second. With these latencies and throughputs we can actually implement solutions which help mitigate against the problem of servers being compromised by APTs.

Of course MPC only acts as a threat mitigation defence in such situations. If all machines are compromised, then all bets are off. But that is the same as with all security mechanisms, one needs to combine them together to provide a secure system. But the key message is that with MPC one no longer needs to place ones secrets all in one place. So whilst the traditional cryptographic model may be dead in the modern world, the application of cryptography to address security problems is far from dead. So Long Live Crypto!