Eurocrypt 2013, Day 3, Session 'Secure Computation': How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation

The second talk in the secure computation session on the third day of Eurocrypt was on the paper   "How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation", authored by Payman Mohassel and Saeed Sadeghian from University of Calgary. Saeed gave the talk. This post also covers the more elaborate talk given by Payman after Eurocrypt at University of Bristol.

The paper revisited the problem of Private function evaluation (PFE), a relatively less explored problem compared to the well-known problem of secure function evaluation (SFE)/multi-party computation (MPC).  In a PFE protocol among n parties, say P₁,....,P_n, the goal is to compute a function f represented by a circuit C, held privately by the first party P₁ on the private inputs of the n parties. Unlike secure function evaluation (SFE), the circuit is not public, rather it is the private input of the first party. In particular, nothing else other than the size (number of gates) is leaked about the circuit. PFE is particularly useful in scenarios where learning the function compromises privacy, reveals security vulnerabilities, or when service providers need to hide the function or specific implementation of it to protect their Intellectual Property. Another important motivation is that PFE yields efficient program obfuscation (if interaction is allowed).  The paper investigates PFE in the most basic setting of semi-honest adversaries and report the most efficient constructions to date.  The main contribution is a general framework that can be instantiated to either two party or multi party PFE considering either Boolean or  arithmetic circuits.  

History. A bit of history of PFE is given below. The problem of PFE can be solved by reducing it to SFE of a universal circuit U_g that takes as input the  circuit C (containing g gates and representing function f) and the parties' private inputs x₁,....,x_n and outputs f(x₁,....,x_n).  The main objective is then to design smaller size universal circuits. Two approaches are known so far for boolean circuits. Valiant showed a construction of a Boolean universal circuit achieving (asymptotically) optimal circuit size of 19glog(g) for any given Boolean circuit of size g. An alternative construction is due to Kolesnikov and Schneider. They obtain a worse bound of 1.5 g log² g. Nonetheless, the construction of Kolesnikov and Schneider seems to yield smaller universal circuits than Valiant's construction for circuit size less than 5000. Unfortunately,  the universal circuit approach does not lead to satisfactory solutions for arithmetic circuits due to the fact that the universal circuits are too large for any practical purpose (state of the art: size of  U_g becomes as high as O(g⁵)). Noting the bounds on the size of universal circuits and current state of the art SFE constructions (e.g. Yao for two party and GMW for multi party), it can be concluded that PFE constructions based on the Universal circuit approach do not achieve complexity that is linear in the circuit size g.  The second, and perhaps asymptotically optimal approach of designing PFE is via FHE (where even the circuit size could be kept private). Due to the high computational overhead, this solution can not be considered practical given the current state of the art of FHE. In a novel attempt, Katz and Malka designed two party PFE based on singly homomorphic encryption that attains linear complexity. Specifically, their constructions require number of public key operations that is linear in the number of gates in the circuit. The construction of Katz and Malka does not extend to the multi-party settings for n>2. In light of the above history, it can be concluded that the existing solutions are more expensive compared to their SFE counterparts (the current state of the art SFE constructions require linear number of symmetric key operations) and no multi party construction or arithmetic circuit based PFE with linear complexity (even asymptotically) is known thus far. This leads to the interesting question:

Can we design PFE with linear complexity in all standard settings (without resorting to FHE based trivial constructions), namely for any settings that is a cross product of (two party, multi party) and (Boolean circuit, arithmetic circuit)?

Contribution of the paper. This paper  answers the above question in affirmative when semi-honest security is concerned with and improves the state of the art of PFE notably by presenting a general framework that can be instantiated in any of the above mentioned settings. To fully hide a circuit C in PFE one needs to hide (i) the circuit topology and (ii) the function of the gates in the circuit (AND, OR, XOR etc.). The framework addresses the above two important issues independently. They introduce two functionalities:  circuit topology hiding (CTH) functionality and  private gate evaluation (PGE) functionality. Then they show how these two functionalities can be composed to realize PFE. And lastly, the paper presents a number of ways to realize the functionalities.  In what follows, I present intuitive treatment of these functionalities and try to describe how they are composed in a PFE. I also briefly mention how the functionalities are realized in the paper:

PGE functionality. The problem of PGE is as follows: let G be a gate that is to be evaluated. It's type is known only to P₁. The parties wish to evaluate G on inputs a and b that are secret shared among the parties (according to some secret sharing scheme) so that the output remains shared and the type of G remains hidden from everyone except P₁. The ideal functionality PGE is described as follows: it takes the gate G from P₁, the shares of a and b from all the parties, computes G(a,b), finds secret sharing of G(a,b) and finally passes the ith share to the ith party.
Note that PGE can be seen as a PFE protocol where the circuit to be evaluated is a single gate. Very efficient solutions for implementing PGE is shown in the paper based on 4-out-of-1 OT  and singly homomorphic encryptions.

CTH functionality. A bit of background is needed first. To hide the circuit topology, the first task is to conceive it as a mathematical object. The authors note that a circuit topology can be described by a mapping. Let us describe the mapping. First find a topological ordering of the circuit C consisting of g gates. Label the input wires to the jth gate as iw_2j-1 and iw_2j (assume for simplicity that the circuit consists of only two input gates).  The set of incoming wires, say IW are the set of input wires to all the gates in the circuit. IW contains 2g elements. Next define another set OW, the set of outgoing wires. OW is defined as the union of the set of circuit input wires and the output wires for each non-output gate in the circuit. OW contains n + g - o wires where n defines the number of input wires and o defines the number of the output wires in the circuit. The outgoing wires are labeled as follows: The n input wires are labeled as ow₁,....,ow_n. Next output wire of the jth non-output gate (i.e. the output of this gate is not a part of the circuit output) is labeled as ow_n+j. Now the topology of a circuit C can be fully described using the following mapping Π_C: {1,...,|OW|}--> {1,...,|IW|} from OW to IW. The mapping Π_C maps i to j if the ith outgoing wire ow_i is connected to jth incoming wire iw_j. To be more clear, have a look at the following example circuit and its corresponding mapping shown using arrows.      

While Π_C is not a function, its inverse is. Given C, the mapping can be computed efficiently. Further the mapping defined above is an extended permutation since it not only permutes the elements in {1,...,OW} but also can replicate them as many times as needed. More formally, a mapping is called an extended permutation if every element in the co-domain (which is IW for Π_C) has been mapped from a unique element in the domain (which is OW for Π_C).  But a single element from the domain can be mapped to multiple entries in the co-domian. Unlike a permutation, an extended permutation can have domain and co-domain of different sizes.

The goal of CTH functionality is to enable oblivious evaluation of the mapping in an on-demand fashion as and when a gate is computed using PGE and the gate output wire needs to be mapped to the gate input wires it is connected to, to continue further computation. To understand what CTH functionality is expected to do for us, let me detail below how PGE and CTH functionalities are composed  to build PFE. The PFE protocol starts with an initialization phase. In this phase P₁, knowing the circuit C, sorts the gates topologically and computes Π_C. Next every party shares its input (according to some secret sharing scheme) among all. The shared inputs are labeled as the first n wires in the set OW. From now on, the idea is to map an outgoing wire to incoming wire(s) (according to Π_C) as soon as it is ready (meaning the value associated with the wire is available in the shared format among the parties). Once all the parties share their inputs in the initialization phase, the parties perform the mapping via CTH functionality obliviously so that Π_C is not leaked to anyone other than P₁. The CTH functionality enables this via two types of queries (which the parties are allowed to issue to CTH). By issuing a mapping query OMAP([x],j), the parties wish to map the jth outgoing wire where [x] is the associated sharing for the outgoing wire ([] is used to denote sharing). On receiving such a query, CTH takes Π_C from P₁ and the shares of x from the parties. It computes Π_C(j) and for each l where j is mapped to lth incoming wire, CTH internally associate and store a re-randomised sharing of x. Note that neither the indices to which j is mapped to and nor the rerandomized sharings are revealed to the parties at this stage (information on circuit topology leaks otherwise). Rather the re-randomized sharings corresponding to the mapped input wires will be distributed on-demand; meaning as and when the parties want to evaluate a gate with those mapped input wires. So once OMAP([*],j) is queried for all j corresponding to n input wires, the parties proceed to evaluate the first gate. The sharings corresponding to the input wires of the first gate are stored in the CTH functionality and is not yet available to the parties. The parties issue REVEAL query (the second allowed query) to CTH to get the sharings. A reveal query REVEAL(j) implies the parties wish to know the sharing associated with jth incoming wire. CTH distributes the stored re-randomized sharing corresponding to jth incoming wire; so P_i receives the ith share from CTH. In general for evaluating jth gate, the parties send REVEAL(2j-1) and REVEAL(2j) and on receiving the corresponding shares they invoke PGE functionality to compute the sharing of the gate output.

To get a more clear picture, see the figure below that explains how party P_i interacts with CTH and PGE functionalities to evaluate jth gate. The numbers in the blue colored square boxes indicate the orders in which P_i proceeds. First P_i issues REVEAL(2j-1) and REVEAL(2j) to CTH and in return receives re-redomized shares of values a and b that are associated with (2j-1) and 2j th incoming wires. Then it invokes PGE and once it receives the share of the output of the jth gate, it makes an OMAP query to CTH to map the outgoing wire of jth gate.

One of the major contributions of this paper is to instantiate  CTH.  They show how to evaluate an extended permutation obliviously i.e. without leaking the permutation. There are two known solutions for the problem in the literature; one based on general MPC (e.g Yao for two party) which are inefficient and other based on homomorphic encryption. The authors present an alternative that takes the approach of efficiently implementing extended permutation using a switching network and then showing how to efficiently implement the switches using OT. They show how to construct a switching network consisting of O(g log g) switches for an extended permutation corresponding to a circuit of size g. Due to OT extension, evaluations of the switching network turns out to require O(g log g) symmetric key operations. In contrast, the homomorphic encryption based solutions from the existing works require O(g) public key operations. Though asymptotically worse, the approach based on switching network shows better concrete complexity over the other two alternatives. I skip the details on how to construct the switching network for an extended permutation and how to securely evaluate the switches. The major building block here is an efficient protocol for oblivious shuffling. Please refer to the paper for the technical details.

Open problems. Loads of open questions are posed at the end. One interesting direction is to investigate PFE with other security notions. This paper considers semi-honest setting.  Designing PFE with malicious and covert security  is a good open question in itself. It can be further investigated if the above notions of security can be achieved while maintaining linear complexity. PFE in information theoretic settings with linear complexity is another open question.  It is also important to find PFE that hides even the number of the gates in the circuit (known solution is via using FHE).

Studying the round complexity of PFE is another important direction (even considering the most basic setting of semi-honest adversary).  Known SFE construction with linear complexity for two party requires 2 rounds (Yao). PFEs with linear complexity on the other hand require at least 3 rounds. Can the round complexity of PFE with linear complexity be brought down to 2? Note that universal  circuit based approach gives 2 round PFE, but the PFE does not provide linear complexity. BMR90 reports SFE with constant round in multi-party settings. Can we achieve  constant round PFE in multi-party setting?

Study of concrete efficiency of PFE is another interesting direction. Asymptotically, the best solution for PFE requires linear in g public key operations.  The solution in this paper (based on switching network) requires g log g symmetric key operations. When concrete efficiency is concerned with, the latter solution may be more useful due to the gap between the efficiency of public and symmetric key operations. In the SFE world, the current state of the art achieves g symmetric key operations. It is interesting to find PFE that matches the state of the art of SFE.  

Eurocrypt 2013, Day 4: How to Garble RAM Programs

The last talk  of Eurocrypt 2013 was given by  Steve Lu on  secure two-party computation via garbling RAM programs (joint work with Rafail Ostrovsky).  He started with  the  motivating example of secure cloud computing, in which there is a client that wants to store some data remotely and then repeatedly a remote server have to perform computations on that data, without knowing the data or the nature of the computation, and the result of the computation. 

The goal of their work is to obtain an analogue Yao's garbled circuits construction for RAM programs, more specifically they show how to garble any RAM program π that runs in t time and has size n in O(t· poly(k,log n)) time, keeping all the non-interactive properties of the Yao’s Garbled circuits and assuming the existence of one-way functions.  This problem  can be trivially solved by representing the program π  as a circuit and then garble it, but unfortunately in some cases this approach can lead to a big blow-up in program size.

The main two ingredients of their solution are Obliviuos RAMs, firstly introduced by  Ostrovsky  and Yao’s Garbled Circuits. The former   enables a client storing only a small amount of data locally to remotely store a large amount of data  and access them while hiding the identities of the items being accessed. The RAM model of computation is used with stored programs and a small stateful CPU that executes a sequence of reads and writes to locations stored on a large memory. Given the CPU state ∑ and the most recently read element x, CPU(∑, x) performs add/mult, updates program counter, executes PRF, outputs the next read/write command and updates the new state ∑’. As for the Yao’s garbled circuit , the construction  is based on three PT algorithms (G,GI,GE), where G is the program garbling algorithm, GI is the input garbling algorithm and GE is the evaluation algorithm.

Steve Lu described these algorithms. In order to garble a RAM program π_t that runs in time t, G generates the garbled circuits  necessary to execute t steps of π_t. Each step consists of a garbled ORAM query followed by a garbled CPU computation in such a way that  the garbling is independent of the actual program path. The garbled program is then sent to the server that can evaluate the program. The GI  algorithm for garbling input is just a time labeled encoding and the GE algorithm performs evaluation of the garbled program executing the same steps as the program garbling algorithm G but evaluating garbled circuits instead of generating them.

The talk ended with the interesting open problem of how to achieve reusable   garbled RAM programs, as has been done in (GKPVZ12) for garbled circuits.

 

Eurocrypt 2013: Day Three, Secure Computation

On the third day of Eurocrypt, there were three presentations on secure computation. This post will cover two of them.

Tore Frederiksen from Aarhus University presented an efficiency improvement for active two party computation based on Yao's garbled circuits. The core component is an XOR-homomorphic commitment based on OT, which makes the approach compatible with garbled circuit optimizations like free-XOR. This was not the case for a previous work by the same group where they used Pedersen commitments. However, both use cut-and-choose at gate level as opposed to at circuit level to achieve active security.

Most of the talk was devoted to the XOR-homomorphic commitment scheme based on OT and a linear error correcting code. The latter is required to have secret-sharing properties in order to achieve hiding. To produce a commitment, the input is encoded using the code and then input to a k-out-of-n random-OT. For the binding property, the receiver selects some bits of the encoded vector to check them against the output of the OT protocol.

By using OT extension, the usage of asymmetric cryptography can be reduced to depend only on the security parameter. Furthermore, all protocols are parallelizable, which leads to an overall constant number of rounds.

At the end of the session, Hoeteck Wee from George Washington University gave a pleasant talk about a result on secure computation with limited interaction. In the so-called one-pass model, the parties interact with a server once in a fixed order, after which the server announces the result. There is some inherent leakage: If the server colludes with the last k parties, they can evaluation the function with all possible inputs from those parties

Previous work in this model covered symmetric functions like sum and majority, and proved that pseudo-random functions are impossible to compute. The contribution presented at the conference extends the achievable functions to sparse multi-variate polynomials (e.g., variance) and read-once branching programs (e.g., string matching, finite automata, second-prize auctions), which allow branching once per player.

The protocol works as follows: The server encrypts all possible outputs under the keys of all parties and the server in order according to the branching in the program, that is, the outer-most encryption is under the key of the party associated with the last branching. The parties then interact with the server in the reverse order, that is, the party associated to the last branching comes first. Every party picks the possible ciphertexts according to his input, decrypts them and sends them to the server, who forwards them to the next party. At the end, the server decrypts the result.

The complexity of the protocol is determined by the width of the branching program. If the server is honest, secrecy is guaranteed by the encryption under the public key of the server. However, if the server colludes with the last k parties, the protocol inherently leaks information as described above, but not more. To achieve active security, non-interactive zero-knowledge arguments can be used. Finally, the biggest open question is the gap between the functions known how to compute in this model and the impossibility result.

Godel Prize goes to a "Tripartite Pairing" of Cryptographers

The 2013 Godel Prize winners have just been announced as being Antoine Joux, Dan Boneh and Matt Franklin; for their work in pairing based cryptography. The press release can be found here.

In the early 2000's the world of cryptography was revolutionized by two papers by these authors. A bit of background is probably needed to understand the revolution. In 1985 Victor Miller and Neal Koblitz introduced the idea of using elliptic curves as a means of building cryptographic systems; and since then elliptic curves have become deployed in a number of application domains such as on the web, in your mobile phone, or in your games console.

However, quite early on it was realised that some elliptic curves are weaker than others; in particular those for which there exists an efficiently computable bilinear pairing (sometimes called a bilinear map). In its basic form this is a map from two groups G₁ and G₂ into a new group G_T which is linear in the first two coordinates. In practice one instantiates these with G₁ and G₂ being subgroups of an elliptic curve and G_T being a subgroup of a finite field. Only a small subset of elliptic curves have an efficiently computable pairing, and since the early 1990's these had been avoided in normal applications of elliptic curves in cryptography.

However, in a paper in the ANTS conference in 2000 Antoine Joux showed how if we carefully chose the parameters of elliptic curves with a pairing then we could achieve a cryptographic functionality which we could not achieve with other techniques. This first application was to allowing three parties to agree a secret key using only one round of interaction; so called Tripartite Diffie-Hellman.

Then in 2001 at the CRYPTO conference Boneh and Franklin showed how the same technique could be used to create an identity based encryption scheme. This is an encryption scheme in which the receivers key is simply their name. Again this is something which had not be possible before.

Over the first decade of this century the number of papers on so-called Pairing Based Cryptography exploded. For example, according to Google Scholar, Joux's paper has been cited 886 times and the Boneh/Franklin paper has been cited 4527 times. The following work has ranged from algorithms to efficiently compute the various pairings needed (including the work in Bristol on the Ate-pairing algorithm) through to work on using pairings in advanced protocols such as group signatures, credentials, functional and attribute based encryption and our own work recent work on DAA protocols.

We have all just returned from Eurocrypt where the best paper award was given to some new ground breaking work which showed how one can construct pairings between more than two objects efficiently; so called multi-linear maps. We have discussed new work a lot in this blog in recent months; so I refer the reader to the previous posts on this topic.  It can be expected that the development of multi-linear maps is going to have the same profound effect that the development of bilinear pairings had in the last decade.

Eurocrypt 2013: Day Three, Session Two

The second talk in the 'Public Key Encryption' session of this year's Eurocrypt was given by Dennis Hofheinz, on his paper 'Circular Chosen-Ciphertext Security with Compact Ciphertexts'. The work gives the first KDM-CCA secure scheme with ciphertexts that have O(1) group elements, building on the past work of Boneh et al. who give a KDM-CPA secure scheme. For comparison the other CIRC-CCA secure scheme in the literature has ciphertexts with O(k) group elements. In the KDM-CCA security game, the adversary submits a (length-regular) function to the challenger and receives an encryption of either the function acting upon the secret keys in the system or an encryption of a zero message, and naturally the scheme is secure under this notion if all (efficient) adversaries cannot distinguish between these cases. Note that CIRC-CCA security (called clique security by Boneh et al.) is the scenario where the adversary is restricted to functions that on input take the secret keys in the system and output one of these secret keys. This is a special case of (and implied by) KDM-CCA security.

The KDM-CPA secure scheme of Boneh et al. relies on the possibility of constructing encryptions of secret keys (under their corresponding public keys) publicly, something that will clearly deem it KDM-CCA insecure. Consequently, something else is needed to realise a KDM-CCA scheme from this starting point. The main technical tool used to ramp up to KDM-CCA security is the 'Lossy Algebraic Filter', a family of functions indexed by a public key and a tag. A function LAF from this family takes as input a vector of elements X_i in Z_p. For an injective tag, LAF will be injective. If the tag is lossy, then LAF only depends on a linear combination of the input elements. Crucially, different input vectors with the same linear combination (Σ_i=1ⁿ ω_i X_i mod p) are mapped to the same value. The coefficients only depend on the public key of the filter, and not on the tag. Three properties are necessary for this definition to acheive its purpose. First of all, lossy and injective tags must be computationally indistinguishable; lossy tags can be generated using a special trapdoor; and finally that new lossy tags cannot be found efficiently without this trapdoor, even given polynomially many lossy tags before. The paper details how to construct LAFs based on the DLIN assumption with a suitable cryptographic pairing, and each tag corresponds to n DLIN-encrypted Waters signatures (if the signatures are valid then the tag is lossy).

The constructed CIRC-CCA secure PKE scheme adds an authentication tag (an encrypted image of the plaintext message under an LAF), and decryption queries are disallowed where the authentication tag is invalid. To prove security, all tags for key-dependent encryptions are made with respect to lossy filter tags, so little information about the secret key is released (information-theoretically speaking). But the fact that adversarial decryption queries must correspond to injective tags, the adversary needs to be able to guess the whole secret key to make any valid decryption query. The resulting scheme is secure under a combination of the DCR, DLIN and DDH assumptions (in appropriate groups).

Eurocrypt 2013: Homomorphic Cryptography session

The first afternoon session of day 2 was on homomorphic cryptography. There were three talks: the first was on fully homomorphic encryption, and the next two on the slightly lesser-known topics of homomorphic MACs and authenticated data structures. In this post I will talk about the first two talks, which captivated me the most.

Tancrède Lepoint gave the first talk, on integer-based fully homomorphic encryption, which was a merge of two papers. Much recent work on FHE has focussed on constructions based on ring-LWE, whilst Gentry's scheme and the integer-based DGHV variant are often ignored due to large parameter sizes. The talk aimed to bridge this gap and show that actually, the integer scheme can be competitive with ring-LWE. Following on from last year's Eurocrypt paper, which allowed for better 'noise control' using modulus switching,  Tancrède described how batching techniques can be used to perform parallel homomorphic operations on ciphertexts. Batching allows multiple plaintexts to be 'packed' into a single ciphertext, so that when a homomorphic operation is performed on a ciphertext, it is applied to every plaintext element in parallel. These techniques were originally developed by Smart and Vercauteren, for plaintext spaces of polynomial rings, and it turns out that the CRT can similarly be used for the scheme over the integers. The use of batching makes a huge practical difference: previously a ciphertext of size 20 million bits could only encrypt a single bit; now the same-sized ciphertext can encrypt around 300 bits.

In addition to parallel operations, effective use of batching also requires the ability to permute plaintext elements within a single ciphertext. This is possible with ring-LWE based schemes because of their nice algebraic structure, however it seems more difficult over the integers. Instead, they take advantage of the bootstrapping step, which homomorphically decrypts a ciphertext, to perform a permutation. Using these techniques, they present an implementation of homomorphic AES that takes 12 minutes per block on average, compared with 5 minutes per block for the implementation from Crypto last year. This shows that integer-based FHE is still a viable option, although it is worth noting that the Crypto implementation did not use bootstrapping; it would be interesting to see if adding bootstrapping could put it much further ahead or not.

The second talk of the session was given by Dario Catalano, on homomorphic MACs for arithmetic circuits. In the scenario of delegating computation to a server, it is often important to be able to verify that the computation was carried out on the correct data, which was previously authenticated by the client. Using homomorphic MACs allows the client to verify the server's output, with respect to the function computed and the original, authenticated inputs. The key element is a mechanism whereby anyone can take a set of MAC'd messages and compute a MAC valid for the output of any function of the messages. Previous work in this area was only homomorphic for linear functions, or required the use of FHE, which is undesirable. Their construction allows homomorphism for polynomially sized circuits, is secure based only on the existence of PRFs, and is very efficient to compute the MACs. However, the complexity of verification grows with the degree of the circuit, which seems unfortunate, especially for the application of outsourced computation. Another open problem Dario mentioned was to construct a fully homomorphic MAC, for circuits of arbitrary size.

EuroCrypt 2013: Day one, part three

The first talk on Monday afternoon at EuroCrypt'13 was given by Nicolas Veyrat-Charvillon on "Security Evaluations Beyond Computing Power - How to Analyze Side-Channel Attacks you Cannot Mount?" (with B. Gérard and F.-X. Standaert as coauthors). The paper addresses an issue faced by certification labs that have to assess the security of a device against side channel attacks: In certification you know everything about the device that you are attacking, you know the key that you're attacking but if, after having made a certain effort, the side-channel attack doesn't yield the correct key you want to know how far away of the correct key you are.

Let's look at the example of a side channel attack on AES: After the attack, you have for each 0<=i<16 word of the state a probability distribution D_i that contains the probability of every possible value for this word. So you can compute for all of the possible 2¹²⁸ keys their probability as returned by the attack. In particular, you can compute the probability of the most likely key and the probability of the correct key. (Of course, a real attacker wouldn't know the correct key; you know the correct key only because you're a certification lab staging an attack on something you already know.) The big question that remains is: How many other keys have a probability higher than the correct key? If the certification lab can answer that question with a good enough approximation, then they know how much additional effort is needed to complete the attack by brute force.

The stupid way to answer that question is to check the probabilities of all 2¹²⁸ keys. But of course, if you were able to do that, you wouldn't need a side-channel attack in the first place, you could just brute force AES.  The authors present in their paper the first feasible method to answer this question with a reasonably good approximation. Their primary idea is to arrange all the possible keys in a suitable hyper cube representation where they can make suitable time-memory trade-offs in the arrangement. This enables effective carving out of key candidate volumes that all have bigger or smaller probability. So they only have to keep track of the size of the carved out volumes and, when the remaining volume is small enough, they have their answer.

Obviously, being able to tell how much additional brute force effort is needed after a failed side-channel attack is important for certification labs to make a qualified judgement about the device's security. So the biggest remaining question for follow-up work in this direction is:  Does the remaining brute-force effort relate to the additional number of traces that need to measured, stored & processed for a pure side-channel attack to be successful? Would the attacker be better of continuing with more measurements instead of brute-forcing at the end?