Patent Publication Number: US-2021165906-A1

Title: Secure multiparty differentially private median computation

Description:
TECHNICAL FIELD 
     This document generally relates to systems and methods for use data storage and analysis. More specifically, this document relates to secure multiparty differentially private function computation. 
     BACKGROUND 
     With the rise of cloud computing and distributed architectures, it is quite common for related data to be stored across multiple devices and/or systems. Indeed, in some circumstances, related data can actually be held and managed by multiple parties, with some parties holding and managing certain portions of the data and at least one other party holding and managing other portions of the data. Thus, no single party has access to all of the data. 
     Companies often collect data such as telemetry, usage statistics, and frequent settings from users. It can be useful for these companies to evaluate the data using various functions, such as rank-based statistical functions. Median, for example, is an important robust statistical method used in enterprise benchmarking, such as by companies comparing typical employee salaries, insurance companies evaluating median life expectancy to adjust insurance premiums, and banks comparing credit scores of their customers. When the data itself, however, is maintained and held by multiple parties, there are various legal and privacy concerns with sharing this data with at least one other party. For example, in the case of medical data, federal regulations such as Health Insurance Portability and Accountability (HIPAA) regulations may prevent the sharing of individual medical data without explicit permission from the patient. Indeed, in certain circumstances, exact computations of rank-based statistical functions may be used maliciously or accidentally to reveal data about a specific user. For example, if one queried a system for a total number of users having been diagnosed as HIV+, and the result was given as 100, and then one queried a system for a total number of users not named X having been diagnosed as HIV+, and the result was given as 99, then one could deduce that X has been diagnosed as HIV+, despite no specific data regarding X being specifically requested or revealed. 
     A technical problem is therefore encountered in that it is difficult to protect privacy of users while still gaining insights using functions performed on the underlying data, without sharing the data across multiple parties and without permitting individual data to be deduced. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
       The present disclosure is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements. 
         FIG. 1  is a block diagram illustrating a system for differentially private function computation in accordance with an example embodiment. 
         FIG. 2  is a flow diagram illustrating a method of computation of a secure multiparty differentially private function, in accordance with an example embodiment. 
         FIG. 3  is a flow diagram illustrating a method of using selection probabilities to select one of a plurality of subranges, in accordance with an example embodiment. 
         FIG. 4  is a flow diagram illustrating a method for computing selection probabilities for each subrange in accordance with an example embodiment. 
         FIG. 5  is a flow diagram illustrating a method for computing selection probabilities for each subrange in accordance with another example embodiment. 
         FIG. 6  is a block diagram illustrating an architecture of software, which can be installed on any one or more of the devices described above. 
         FIG. 7  illustrates a diagrammatic representation of a machine in the form of a computer system within which a set of instructions may be executed for causing the machine to perform any one or more of the methodologies discussed herein, according to an example embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     The description that follows discusses illustrative systems, methods, techniques, instruction sequences, and computing machine program products. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide an understanding of various example embodiments of the present subject matter. It will be evident, however, to those skilled in the art, that various example embodiments of the present subject matter may be practiced without these specific details. 
     In an example embodiment, a differentially private function is computed via secure computation. Secure computation allows multiple parties to compute a function without learning details about the data. The differentially private function defines a probability distribution, which then permits computation of a result that is likely to be very close to the actual value without being so exact that it can be used to deduce the underlying data itself. 
       FIG. 1  is a block diagram illustrating a system  100  for differentially private function computation in accordance with an example embodiment. System  100  may include, for example, three parties  102 A,  102 B,  102 C, although more parties are possible. Each party may maintain or otherwise control its own database  104 A,  104 B,  104 C. Each party may also maintain or otherwise control its own server  106 A,  106 B,  106 C. Each server  106 A,  106 B,  106 C may act to obtain local queries from users and query their own corresponding databases  104 A,  104 B,  104 C for results. In cases where the queries involve functions that require the analysis of data not stored in their own corresponding databases  104 A,  104 B,  104 C, a secure multiparty private function computation component  108 A,  108 B,  108 C located on each server  106 A,  106 B,  106 C may be utilized to evaluate the corresponding function(s) based on information stored on other of the databases  104 A,  104 B,  104 C. This may be accomplished via multi-party communication among the various secure multiparty private function computation components  108 A,  108 B,  108 C, as will be described in more detail below. 
     In an example embodiment, the secure multiparty private function computation component  108 A,  108 B  108 C may be in the form of software code that is made and distributed to the parties  102 A,  102 B,  102 C by a third-party software developer. In some example embodiments, this software code may be included with the distribution of another product, such as a database server application or a workbench component. 
     As described briefly above, one technical problem that is encountered is how to protect the privacy of user&#39;s data while still gaining insights from this data, when the data is stored by multiple parties. In an example embodiment, both differential privacy and secure computation are used to accomplish this goal. 
     It should be noted that while the techniques described in this disclosure can be applied to any differentially private functions performed on a data set, one example of such a function is the median function. For ease of discussion, the present disclosure may refer specifically to the median function when describing some of all of the functionality. This shall not, however, be taken to mean that the score of the present disclosure is limited to median functions. 
     Differential privacy is a privacy notion used when statistical properties of a dataset can be learned but information about any individual in the data set needs to be protected. Specifically, databases D and D′ are called neighbors, and are neighboring when database D can be obtained from D′ by adding or removing one element. Informally a differentially private algorithm limits the impact that the presence or absence of any individual&#39;s data in the input database can have on the distribution of outputs. Specifically, in differential privacy: 
     DEFINITION 1 (D IFFERENTIAL  P RIVACY ). A mechanism M satisfies ∈-differential privacy, where ∈≥0, if for all neighboring databases D and D′, and all sets S⊆Range(M) 
         Pr [ M ( D )∈ S ]≤exp(∈)· Pr [ M ( D ′)∈ S ],
 
     where Range(M) denotes the set of all possible outputs of mechanism M. 
     One way to accomplish differential privacy is to use what is called the Laplace mechanism, which acts to add Laplace distributed noise to a function evaluated on the data. This has the effect, however, of making the underlying function less reliable (due to the introduction of noise into the data). 
     Another technique to accomplish differential privacy is called the exponential mechanism, which is more complex but offers better accuracy. Another advantage of the exponential mechanism is that, as will be shown, it can be efficiently implemented as a scalable secure computation. Furthermore, the exponential mechanism can implement any differentially private algorithm. 
     The exponential mechanism expands the application of differential privacy to functions with non-numerical output, or when the output is not robust to additive noise, such as when the function is a median function. The exponential mechanism selects a result from a fixed set of arbitrary outputs   while satisfying differential privacy. This mechanism is exponentially more likely to select “good’ results, where “good” is quantified by a utility function u(D,r), which takes as input a database Dϵ  (where   denotes the set of all possible databases) and a potential output rϵ . Informally, higher utility means the output is more desirable and its selection probability is increased accordingly. Thus:
         For any utility function u: (   n × )→  and a privacy parameter ϵ, the exponential mechanism M u   ϵ  (D) outputs rϵ  with probability proportional       

     
       
         
           
             
               to 
                
               
                   
               
                
               
                 exp 
                  
                 
                   ( 
                   
                     
                       ϵu 
                        
                       
                         ( 
                         
                           D 
                           , 
                           r 
                         
                         ) 
                       
                     
                     
                       2 
                        
                       Δ 
                        
                       u 
                     
                   
                   ) 
                 
               
             
             , 
             
               
                 where 
                  
                 
                     
                 
                  
                 Δ 
                  
                 
                     
                 
                  
                 u 
               
               = 
               
                 
                   max 
                   
                     
                       ∀ 
                       
                         r 
                         ∈ 
                         iR 
                       
                     
                     , 
                     
                       D 
                        
                       
                           
                       
                       ≃ 
                       
                           
                       
                        
                       
                         D 
                         ′ 
                       
                     
                   
                 
                  
                 
                    
                   
                     
                       u 
                        
                       
                         ( 
                         
                           D 
                           , 
                           r 
                         
                         ) 
                       
                     
                     - 
                     
                       u 
                        
                       
                         ( 
                         
                           
                             D 
                             ′ 
                           
                           , 
                           r 
                         
                         ) 
                       
                     
                   
                    
                 
               
             
           
         
       
         
         
           
              is the sensitivity of the utility function. That is, 
           
         
       
    
     
       
         
           
             
               P 
                
               
                 r 
                  
                 
                   [ 
                   
                     
                       
                         M 
                         u 
                         ϵ 
                       
                        
                       
                         ( 
                         D 
                         ) 
                       
                     
                     = 
                     r 
                   
                   ] 
                 
               
             
             = 
             
               
                 
                   exp 
                    
                   
                     ( 
                     
                       
                         ϵ 
                          
                         
                             
                         
                          
                         
                           u 
                            
                           
                             ( 
                             
                               D 
                               , 
                               r 
                             
                             ) 
                           
                         
                       
                       
                         2 
                          
                         Δ 
                          
                         u 
                       
                     
                     ) 
                   
                 
                 
                   
                     Σ 
                     
                       
                         r 
                         ′ 
                       
                        
                       ϵR 
                     
                   
                    
                   
                     exp 
                      
                     
                       ( 
                       
                         
                           ϵu 
                            
                           
                             ( 
                             
                               D 
                               , 
                               
                                 r 
                                 ′ 
                               
                             
                             ) 
                           
                         
                         
                           2 
                            
                           Δ 
                            
                           u 
                         
                       
                       ) 
                     
                   
                 
               
               . 
             
           
         
       
     
     There are two types of privacy techniques that are used in exponential mechanisms. The first is a trusted model, in which a central “curator” computes and anonymizes data centrally. While accuracy in the trusted model is high, privacy is not, and as described briefly above there are certain types of data that are unable to be shared with even a trusted curator for legal reasons. The second type is an untrusted model. Here, computations and anonymization is performed locally, which results in more privacy but less accuracy. 
     Secure computation is used for input secrecy, namely the data itself is never shared between parties. In an example embodiment, secure computation is used to simulate a central (trusted) model in a local (untrusted) model. This is accomplished by the parties simulating trusted third-party techniques via cryptographic protocols. 
     More particularly, in an example embodiment, a “restricted” exponential mechanism is computed for subranges of data. By restricting the exponential mechanism, efficiency in computing the function is increased. Specifically, the “restriction” involved is to only consider “composable functions”. Composable functions are those that are easy to combine, to allow for efficient computation. Specifically, first the parties compute the partial result locally, without interaction with others, without secure computation, then the parties combine the partial results into a global one, with interaction with others, with secure computation. 
     By dividing a potentially very large data universe (e.g., billions of possible values) into subranges and computing selection probabilities for them, this solution is much faster (sublinear in universe size) than computing selection probabilities for each possible data element (linear in universe size). 
     Assume n parties, each holding a single value d i ∈D (we can generalize to multiple values). To combine local utility scores per player into a global score for all, the utility functions may be composable: 
     DEFINITION 3 (C OMPOSABILITY ). We call a utility function u: (   n × )→  composable w.r.t. function u′: (   n × )→  if 
     
       
         
           
             
               u 
                
               
                 ( 
                 
                   D 
                   , 
                   x 
                 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                 
                   u 
                   ′ 
                 
                  
                 
                   ( 
                   
                     
                       d 
                       i 
                     
                     , 
                     x 
                   
                   ) 
                 
               
             
           
         
       
     
     for xϵ  and D={d 1 , . . . , d n }. 
     We use composability to easily combine utility scores in Weights ln(2)/2     d   , and to avoid secure evaluation of the exponential function in Weights*. General secure exponentiation is complex (e.g., binary expansions, polynomial approximations) and we want to avoid its computation overhead. If u is composable, users can compute weights locally, and securely combine them via simple multiplications: 
     
       
         
           
             
               
                 ∏ 
                 . 
               
                
               
                 exp 
                  
                 
                   ( 
                   
                     
                       
                         u 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             D 
                             i 
                           
                           , 
                           x 
                         
                         ) 
                       
                     
                      
                     ϵ 
                   
                   ) 
                 
               
             
             = 
             
               
                 exp 
                  
                 
                   ( 
                   
                     
                       ∑ 
                       . 
                     
                      
                     
                       
                         
                           u 
                           ′ 
                         
                          
                         
                           ( 
                           
                             
                               D 
                               i 
                             
                             , 
                             x 
                           
                           ) 
                         
                       
                        
                       ϵ 
                     
                   
                   ) 
                 
               
               = 
               
                 
                   exp 
                    
                   
                     ( 
                     
                       
                         u 
                          
                         
                           ( 
                           
                             D 
                             , 
                             x 
                           
                           ) 
                         
                       
                        
                       ϵ 
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
     There are a wide variety of selection problems that satisfy this composability definition. This includes rank-based statistics such as median, convex operations, unlimited supply auctions, and frequency-based statistics. For purposes of this discussion, a composable median utility function is described. Here, we quantify an element&#39;s utility via its rank relative to the median. The rank of Xϵ  with respect to D is the number of values in D smaller than x. We use the following composable median utility function: 
     The median utility function u med   c : (   n × )→Z gives a utility score for a range R=[r l , r u ) of   w.r.t Dϵ   n  as 
     
       
         
           
             
               
                 u 
                 
                   m 
                    
                   e 
                    
                   d 
                 
                 c 
               
                
               
                 ( 
                 
                   D 
                   , 
                   R 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         r 
                          
                         a 
                          
                         n 
                          
                         
                           
                             k 
                             D 
                           
                            
                           
                             ( 
                             
                               r 
                               u 
                             
                             ) 
                           
                         
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             
                               rank 
                               D 
                             
                              
                             
                               ( 
                               
                                 r 
                                 u 
                               
                               ) 
                             
                           
                         
                         &lt; 
                         
                           n 
                           2 
                         
                       
                     
                   
                   
                     
                       
                         n 
                         - 
                         
                           r 
                            
                           a 
                            
                           n 
                            
                           
                             
                               k 
                               D 
                             
                              
                             
                               ( 
                               
                                 r 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             
                               rank 
                               D 
                             
                              
                             
                               ( 
                               
                                 r 
                                 u 
                               
                               ) 
                             
                           
                         
                         &gt; 
                         
                           n 
                           2 
                         
                       
                     
                   
                   
                     
                       
                         n 
                         2 
                       
                     
                     
                       else 
                     
                   
                 
                 . 
               
             
           
         
       
     
     The sensitivity of u med   c  is ½ since adding an element increases n/2 by ½ and j either increases by 1 or remains the same [25]. Thus, the denominator 2Δu in the exponents of Equation (1) equals 1, and we will omit it in the rest of this work. 
       FIG. 2  is a flow diagram illustrating a method  200  of computation of a secure multiparty differentially private function, in accordance with an example embodiment. At operation  202 , all elements in a data universe are divided into k subranges. All elements in a data universe may be defined as all the possible values output by the function. At operation  204 , selection probabilities are computed for each subrange. This will be described in more detail with respect to  FIGS. 4 and 5  below. Generally, however, either method  400  of  FIG. 4  or method  500  of  FIG. 5  is used to compute the selection probabilities. The choice between using method  400  or method  500  is based on how important privacy and speed are to a user controlling the software. Method  400  is faster but has less privacy, while method  500  is slower but has more privacy. A user defined privacy parameter c can be used to represent the user&#39;s choice, and method  400  may be used if c can be expressed as ϵ=ln(2)/2 d  for some integer d). 
     At operation  206 , the selection probabilities (which can also be called weights) are used to select one of the subranges (essentially, the subrange most likely to contain the actual function result, e.g., the subrange most likely to contain the median). This will be described in more detail respect to  FIG. 3  below. At operation  208 , it is determined if the selected subrange has a size of one element. If so, then at operation  210  the value of that one element is considered to be the “answer” to the function (e.g., the median). If not, then at operation  212 , the data universe is replaced with the selected subrange and the method  200  returns to operation  202  to subdivide the selected subrange. Thus, method  200  recursively evaluates each smaller and smaller subrange until the specific output value is determined. Furthermore, by dividing a potentially large data universe into subranges, this process is much more efficient than computing selection probabilities for each possible value. 
     It should be noted that the selection probabilities are non-normalized weights, rather than probabilities that have been normalized to sum to 1. 
       FIG. 3  is a flow diagram illustrating a method  206  of using selection probabilities to select one of a plurality of subranges, in accordance with an example embodiment. The selection probabilities (weights) inform as to how likely each subrange is to be selected. In other words, they define a probability distribution over the subranges. At operation  300 , the sum of all weights is computed. This may be called s. Then, at operation  302 , an element t at uniform random between 2 to the power of −32 to 1 is selected. Then, at operation  304 , t is multiplied by s to get a random value r between nearly 0 and s. These are the initial selection probabilities. 
     A loop is then begun where each of the selection probabilities (weights) are stepped through in order, stopping when a condition is met and choosing the subrange corresponding to the current selection probability in the loop. Specifically, beginning with the first subrange, at operation  306 , a sum of the selection probabilities of all subranges evaluated in the loop is determined. Thus, the first time in the loop this sum will simply be the selection probability for the first subrange, the second time in the loop this sum will be the sum of the selection probabilities for the first and second subrange, the third time in the loop this sum will be the selection probability for the first, second, and third subranges, and so on. 
     At operation  308 , it is determined whether the sum from operation  306  is greater than r. If so, then at operation  310  the subrange currently being evaluated in this loop is selected and method  300  ends. If not, then the method  300  loops back to operation  306 , for the next subrange. 
       FIG. 4  is a flow diagram illustrating a method  400  for computing selection probabilities for each subrange in accordance with an example embodiment. Here, the selection probabilities use complicated computations (exponential functions of the product of the privacy parameter and the rank, where the rank is the position of an element in the sorted data). They are slow with secure computation. Thus, this may be avoided by letting parties compute the rank and compute powers of two instead of an exponential function. 
     A loop is begun at the first of the k subranges. At operation  402 , the rank of the subrange for the current private data is computed. The current private data is the data available to the party executing the method  400 , thus, in the example of  FIG. 1 , party  102 A evaluates operation  402  with respect to data in database  104 A, party  102 B evaluates operation  402  with respect to data in database  104 B, and so on. At operation  404 , the rank determined at operation  402  is shared with the at least one other party. Thus, if method  400  is currently being executed by party  102 A, the calculated rank is shared with parties  102 B and  102 C. The result is that each of the parties&#39; version of method  400  will now have the ranks computed by each of the at least one other party, without having access to the underlying data of the at least one other party. At operation  406 , the ranks are combined into a global rank. This may be performed by, for example, adding the ranks together. 
     At operation  408 , the utility of the subrange is determined using the global rank. This is determined by taking the smallest distance between a boundary of the subrange and the median rank in the subrange. Thus, for example, if the subrange considers elements 1 through 5, the utility is determined by computing the distance between the value for element 1 in the global rank and the median for the global rank, and computing the distance between the value for element 5 in the global rank and the median in the global rank, and then taking the lesser of these computed distances. The median in the global rank is computed as n/2, where n is the size of the combined datasets. Thus, if the combined dataset has 8 elements, the median is at rank 4. If element 1 in the subrange is at rank 2 in the combined rank, while element 5 in the subrange is at rank 7, then the closest of these two elements is element 1, which is at a distance of 2 from the median (2 spots away from rank 4). Thus, the utility of this subrange is calculated at 2. There are three options:
         (1) The median is contained in the subrange, then the utility score for the subrange is the same as the utility for the median (n/2)   (2) The subrange does not contain the median and the subrange endpoints are smaller than the median (e.g., median=4 and subrange contains elements 1, 2, 3), then the utility is the same as for the subrange endpoint that is closer to the median (e.g., endpoints for subrange containing elements 1, 2, 3 are 1 and 2 and the latter is closer to median 4 than 1, thus we use the utility for endpoint 2). Here the utility is n/2 minus the rank of the larger subrange endpoint.   (3) Same as (2) but endpoints are larger than the median. Here the utility is the rank of the smaller subrange minus n/2.       

     Note that in case (2), one can always the larger endpoint (denoted r u  in [0030]), and in case (3), one can always use the smaller one (r l ) 
     At operation  410 , a selection probability (weight) for this subrange is computed using a fixed value and the utility. This fixed value may be designated as ε. In an example embodiment, ε is set to ln(2), and the selection probability (weight) for the subrange is computed as exp(utility*ε). The result is that in this example embodiment, the weight is equal to 2 utility  which can be more efficiently computed with secure computation than general exponentiation. At operation  412 , it is determined if this is the last subrange in the k subranges. If so, then the method  400  ends. If not, then the method  400  loops back to operation  402  for the next subrange. 
       FIG. 5  is a flow diagram illustrating a method  500  for computing selection probabilities for each subrange in accordance with another example embodiment. Here, rather than the parties computing the local ranks, they compute local (or partial) weights. The local weights are then combined into global ranks. This results in a method that is slower than method  400  but offers better privacy. 
     A loop is begun at the first of the k subranges. At operation  502 , the utility of the subrange for the current private data is computed. The current private data is the data available to the party executing the method  500 , thus, in the example of  FIG. 1 , party  102 A evaluates operation  502  with respect to data in database  104 A, party  102 B evaluates operation  502  with respect to data in database  104 B, and so on. The weight (i.e., unnormalized selection probability) of the subrange for the current private data may be computed by performing an exponent function on the rank of the subrange in the current private data. This involves bringing a constant to the power of a function applied on the rank. In an example embodiment, this constant is e. At operation  504 , the utility determined at operation  502  is used in a joint secure computation with the at least one other party. Thus, if method  500  is currently being executed by party  102 A, this joint secure computation is additionally performed with parties  102 B and  102 C. At operation  506 , the weights are combined into a global weight. This may be performed by, for example, multiplying the weights together. This global weight is the selection probability (weight) of this subrange. At operation  508 , it is determined if this is the last subrange in the k subranges. If so, then the method  500  ends. If not, then the method  500  loops back to operation  502  for the next subrange. 
     At a programming level, these methods may be implemented using a series of pseudocode algorithms, as follows: 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm MEDIANSELECTION 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: Number of subranges k, size n of combined data D, and ∈. 
               
               
                  Data universe    is known to all parties. 
               
               
                 Output: Differentially private median of D. 
               
               
                  1: r l , r u , ← 0, |    | 
               
               
                  2: for 1 to┌log k |   |┐ do 
               
               
                   
               
               
                  3: 
         r   #     ←     ⌊         r   u     -     r   l       k     ⌋         
 
               
               
                   
               
               
                  4: Define array W of size k 
               
               
                  5: if ∈ = ln(2)/2 d  then 
               
               
                  6:    W    ← Weights ln(2)/2d  (r l , r u , r # , k, n, d) 
               
               
                  7: else 
               
               
                  8:    W    ← Weights* (r l , r u , r # , k, n, ∈) 
               
               
                  9: end if 
               
               
                 10: i ← INDEXSAMPLING(   W    ) 
               
               
                 11: r l  ← r l  + i · r #   
               
               
                 12:  r u  ← r u  if i = k − 1 else r l  + (i + 1) · r #   
               
               
                 13: end for 
               
               
                 14: return    [r l ] 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                   
               
               
                 Algorithm INDEXSAMPLING. 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Input: List     W     of weights with size k. 
               
               
                   
                 Output: Index i ϵ [0, k - 1] sampled according to     W    . 
               
            
           
           
               
               
               
            
               
                   
                  1:  
                     s     ← 0 
               
               
                   
                  2:  
                 for j ← 0 to k - 1 do 
               
               
                   
                  3: 
                      s     ← FLAdd(    s    ,     W[i]    ) 
               
               
                   
                  4:  
                 end for 
               
               
                   
                  5:  
                     t     ← FLRand(32) 
               
               
                   
                  6:  
                     r     ← FLMul(    s    ,     t    ) 
               
               
                   
                  7:  
                 for j ← 0 to k - 1 do 
               
               
                   
                  8: 
                      r     ←FLAdd(    r    ,     -W[j]    ) 
               
               
                   
                  9: 
                  return j if FLLTZ(    r    ) 
               
               
                   
                 10:  
                 end for 
               
               
                   
                 11:  
                 return k - 1 
               
               
                   
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                   
               
               
                 Algorithm Weights ln(2)/2d . 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Input: Range [r l , r u ), subrange size r # , number k of subranges, data 
               
               
                  size n, and parameter d ∈ {0, 1}. Subrange ranks rank D     p    (·) are 
               
               
                  input by each party p ∈ {1, . . . , q). 
               
               
                 Output: List of weights. 
               
               
                  1: Define arrays R l , R u , W of size k, initialize R l , R u  with zeros 
               
               
                  2: for p ← 1 to q do //Get input from each party 
               
               
                  3: for j ← 0 to k − 1 do //Divide range into k subranges 
               
               
                  4:  r l  ← r l  + j · r #   
               
               
                  5:    R l [j]    ← Add(   Rl[j]   ,    rank D     p    (  [r l ])   ) 
               
               
                  6:    R u  [j − 1]    ← Add(    R u [j − 1]   ,   rank D     p   (  [r l )   ) if j &gt; 0 
               
               
                  7: end for 
               
               
                  8:   R u [k − 1]    ← Add(   R u [k − 1]   ,   rank D     p   (  [r u ])   ) 
               
               
                  9: end for 
               
               
                 10: for j ← 0 to k − 1 do 
               
               
                 11:   rank l     ← Add(   n   ,   −R l [j]    ) 
               
               
                   
               
               
                 12: 
         〈     c   u     〉     ←     L        T        (       〈       R   u          [   j   ]       〉     ,                〈     n   2     〉       )             
 
               
               
                   
               
               
                 13: 
         〈     c   l     〉     ←     L        T        (       〈     n   2     〉     ,     〈       R   l          [   j   ]       〉       )             
 
               
               
                   
               
               
                 14: 
         〈   u   〉                ←     CondSel                   (       〈       R   u          [   j   ]       〉     ,     〈     rank   l     〉     ,         〈     n   2     〉     ,          〈     c   u     〉       ,     〈     c   l     〉       )           
 
               
               
                   
               
               
                 15: if d = 0 then 
               
               
                 16:    W[j]    ← FLExp2(   u    ) 
               
               
                 17: else 
               
               
                 18:    t    ← Trunc(   u   , d) 
               
               
                 19:    e    ← FLExp2(   t   ) 
               
               
                 20:    r    ← Mod2m(   u   , d) 
               
               
                 21:    c    ← EQZ(    r   ) 
               
               
                 22:    s    ← FLSwap(   1  ,   {square root over (2)}   ,   c   ) 
               
               
                 23:    W[j]    ← FLMul(   e   ,   s    ) 
               
               
                 24: end 
               
               
                 25: end for 
               
               
                 26: return   W    
               
               
                   
               
            
           
         
       
     
                             4 Algorithm Weights*.                                    Input: Range [r l , r u ), subrange size r # , number k of subranges,        data size n, and ∈. Subrange weights e ∈(·)  are input by each        party p ∈ {1, . . . , q}.       Output: List of weights.        1: Define arrays W l , W u , W of size k, initialize W l , W u  with ones                2: 
         w     m      e      d       ←     exp        (       n   2        ϵ     )           
                3: for p ← 1 to q do //Get input from each party        4: for j ← 0 to k − 1 do //Divide range into k subranges        5:  r l  ← r l  + j · r #          6:  r u  ← r u  if j = k − 1 else r l  + (j + 1) · r #          7:    W l [j]    ← FLMul(   W l [j]   ,          )        8:    W u [j]    ← FLMul(   W u [j]   ,          )        9: end for       10: end for       11: for j ← 0 to k − 1 do       12:   c u     ← FLLET(   W u [j]   ,   w med    )       13:   c l     ← FLLT(   W l [j]   ,   w med    )       14:   W[j]    ← FLCondSel(   W u [j]   ,   W l [j]   ,   w med    ,            c u    ,   c l    )       15: end for       16: return   W                      
With the following secure computation protocols:
 
     
       
         
           
               
               
             
               
                   
               
               
                 Secure Protocol 
                 Functionality/Output 
               
               
                   
               
             
            
               
                 Add(    a    ,     b    ) 
                 a + b 
               
               
                 LT(    a    ,     b    ) 
                 returns 1 if the first operand is 
               
               
                   
                 less than the second and 0 
               
               
                   
                 otherwise 
               
               
                 LET(    a    ,     b    ) 
                 1 if a ≤ b else 0 
               
               
                 EQZ(    a    ) 
                 1 if a = 0 else 0 
               
               
                 EQ(    a    ,     b    ) 
                 1 if a equals b else 0 
               
               
                 Mod2m(    a    , b) 
                 a mod 2 b  for public b 
               
               
                 Trunc(    a    , b) 
                 [a/2 b ] for public b 
               
               
                 CondSel(    x    ,     y    ,     z    ,     c 1     ,     c 2     ) 
                 x if c 1  = 1, y if c 2  = 1, and z if 
               
               
                   
                 both c 0  and c 1  are zero (a new 
               
               
                   
                 sharing is output) 
               
               
                 FLMul(    a    ,     b    ) 
                 a · b 
               
               
                 FLExp2(    a    ) 
                 2 a   
               
               
                 FLLTZ(    a    ) 
                 1 if a less than zero else 0 
               
               
                 FLRand(b) 
                 a uniform random float in (2 −b , 
               
               
                   
                 1.0] for public b 
               
               
                 FLSwap(    a    ,     b    ,     c    ) 
                 a if c = 1 otherwise b (a new 
               
               
                   
                 sharing is output) 
               
               
                   
               
               
                 FLAdd(    a    ,     b    ), FLLT(    a    ,     b    ) , FLLET(    a    ,     b    ), FLCondSel(    x    ,     y    ,     z    ,     c 1     ,     c 2     ) are the float versions of the integer protocols with the same name 
               
            
           
         
       
     
     Floating points are marked with the prefix FL. All inputs and outputs may be secret shared, denoted by angle brackes &lt; &gt;, which is a cryptographic primitive for secure computation. 
     Examples 
     Example 1. A system comprising: 
     at least one hardware processor; and 
     a computer-readable medium storing instructions that, when executed by the at least one hardware processor, cause the at least one hardware processor to perform operations comprising, at a first party in a multiparty system having a plurality of parties with their own independent databases: 
     identifying a function to be evaluated over a range of data contained in a database of the first party; 
     dividing the range into a plurality of subranges of data; 
     computing, for each of the plurality of subranges of data, a selection probability for the subrange, based on information received about each of the plurality of subranges of data from at least one other party in the multiparty system; 
     selecting one of the plurality of subranges of data based on the selection probability; 
     dividing the selected subrange into additional subranges; and 
     recursively iterating the computing, the selecting, dividing, and repeating for the additional subranges, until the selected subrange has a size of one, each iteration being performed on subranges of the selected subrange from an immediately previous iteration. 
     Example 2. The system of Example 1, wherein the selecting includes: 
     for each of the plurality of subranges:
         computing the rank of the subrange for data contained in the database of the first party;   jointly securely computing the rank of the subrange for data with at least one other party in the multiparty system;   combining the rank of the subrange of data from the at least one other party and the rank of the subrange for data contained in the database of the first party in to a global rank;   determining a utility of the subrange using the global rank; and   calculating a selection probability for the subrange using a fixed value and the utility.
 
Example 3. The system of Example 2, wherein the combining includes adding the ranks.
 
Example 4. The system of Examples 2 or 3, wherein the fixed value is ln(2).
 
Example 5. The system of any of Examples 1-4, wherein the selecting includes:
       

     for each of the plurality of subranges:
         computing the rank of the subrange for data contained in the database of the first party;   calculating a utility for the subrange based on the rank;   jointly securely computing the weight of the subrange for data with at least one other party in the multiparty system; and   determining a selection probability for the subrange by combining the weights for the subrange.
 
Example 6. The system of Example 5, wherein the combining includes multiplying the weights.
 
Example 7. The system of Example 1, wherein a selection probability for a particular subrange is a likelihood that the particular subrange will be selected.
 
Example 8. A method comprising:
       

     at a first party in a multiparty system having a plurality of parties with their own independent databases: 
     identifying a function to be evaluated over a range of data contained in a database of the first party; 
     dividing the range into a plurality of subranges of data; 
     computing, for each of the plurality of subranges of data, a selection probability for the subrange, based on information received about each of the plurality of subranges of data from at least one other party in the multiparty system; 
     selecting one of the plurality of subranges of data based on the selection probability; 
     dividing the selected subrange into additional subranges; and 
     recursively iterating the computing, the selecting, dividing, and repeating for the additional subranges, until the selected subrange has a size of one, each iteration being performed on subranges of the selected subrange from an immediately previous iteration. 
     Example 9. The method of Example 8, wherein the selecting includes: 
     for each of the plurality of subranges:
         computing the rank of the subrange for data contained in the database of the first party;   jointly securely computing the rank of the subrange for data with at least one other party in the multiparty system;   combining the rank of the subrange of data from the at least one other party and the rank of the subrange for data contained in the database of the first party in to a global rank;   determining a utility of the subrange using the global rank; and   calculating a selection probability for the subrange using a fixed value and the utility.
 
Example 10. The method of Example 9, wherein the combining includes adding the ranks.
 
Example 11. The method of Example 9 or 10, wherein the fixed value is ln(2).
 
Example 12. The method of any of Examples 8-11, wherein the selecting includes:
       

     for each of the plurality of subranges:
         computing the rank of the subrange for data contained in the database of the first party;   calculating a utility for the subrange based on the rank;   jointly securely computing the weight of the subrange for data with at least one other party in the multiparty system; and   determining a selection probability for the subrange by combining the weights for the subrange.
 
Example 13. The method of Example 12, wherein the combining includes multiplying the weights.
 
Example 14. The method of Example 12, wherein the calculating a utility includes bringing e to the power of the rank.
 
Example 15. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform operations comprising:
       

     at a first party in a multiparty system having a plurality of parties with their own independent databases: 
     identifying a function to be evaluated over a range of data contained in a database of the first party; 
     dividing the range into a plurality of subranges of data; 
     computing, for each of the plurality of subranges of data, a selection probability for the subrange, based on information received about each of the plurality of subranges of data from at least one other party in the multiparty system; 
     selecting one of the plurality of subranges of data based on the selection probability; 
     dividing the selected subrange into additional subranges; and 
     recursively iterating the computing, the selecting, dividing, and repeating for the additional subranges, until the selected subrange has a size of one, each iteration being performed on subranges of the selected subrange from an immediately previous iteration. 
     Example 16. The non-transitory machine-readable medium of Example 15, wherein the selecting includes: 
     for each of the plurality of subranges:
         computing the rank of the subrange for data contained in the database of the first party;   jointly securely computing the rank of the subrange for data with at least one other party in the multiparty system;   combining the rank of the subrange of data from the at least one other party and the rank of the subrange for data contained in the database of the first party in to a global rank;   determining a utility of the subrange using the global rank; and   calculating a selection probability for the subrange using a fixed value and the utility.
 
Example 17. The non-transitory machine-readable medium of Example 16, wherein the combining includes adding the ranks.
 
Example 18. The non-transitory machine-readable medium of Example 16 or 17, wherein the fixed value is ln(2).
 
Example 19. The non-transitory machine-readable medium of any of Examples 15-18, wherein the selecting includes:
       

     for each of the plurality of subranges:
         computing the rank of the subrange for data contained in the database of the first party;   calculating a utility for the subrange based on the rank;   jointly securely computing the weight of the subrange for data with at least one other party in the multiparty system; and   determining a selection probability for the subrange by combining the weights for the subrange.
 
Example 20. The non-transitory machine-readable medium of Example 19, wherein the combining includes multiplying the weights.
       

       FIG. 6  is a block diagram  600  illustrating a software architecture  602 , which can be installed on any one or more of the devices described above.  FIG. 6  is merely a non-limiting example of a software architecture, and it will be appreciated that many other architectures can be implemented to facilitate the functionality described herein. In various embodiments, the software  602  is implemented by hardware such as a machine  700  of  FIG. 7  that includes processors  710 , memory  730 , and input/output (I/O) components  750 . In this example architecture, the software architecture  602  can be conceptualized as a stack of layers where each layer may provide a particular functionality. For example, the software architecture  602  includes layers such as an operating system  604 , libraries  606 , frameworks  608 , and applications  610 . Operationally, the applications  610  invoke API calls  612  through the software stack and receive messages  614  in response to the API calls  612 , consistent with some embodiments. 
     In various implementations, the operating system  604  manages hardware resources and provides common services. The operating system  604  includes, for example, a kernel  620 , services  622 , and drivers  624 . The kernel  620  acts as an abstraction layer between the hardware and the other software layers, consistent with some embodiments. For example, the kernel  620  provides memory management, processor management (e.g., scheduling), component management, networking, and security settings, among other functionality. The services  622  can provide other common services for the other software layers. The drivers  624  are responsible for controlling or interfacing with the underlying hardware, according to some embodiments. For instance, the drivers  624  can include display drivers, camera drivers, BLUETOOTH® or BLUETOOTH® Low-Energy drivers, flash memory drivers, serial communication drivers (e.g., Universal Serial Bus (USB) drivers), Wi-Fi® drivers, audio drivers, power management drivers, and so forth. 
     In some embodiments, the libraries  606  provide a low-level common infrastructure utilized by the applications  610 . The libraries  606  can include system libraries  630  (e.g., C standard library) that can provide functions such as memory allocation functions, string manipulation functions, mathematic functions, and the like. In addition, the libraries  606  can include API libraries  632  such as media libraries (e.g., libraries to support presentation and manipulation of various media formats such as Moving Picture Experts Group-4 (MPEG4), Advanced Video Coding (H.264 or AVC), Moving Picture Experts Group Layer-3 (MP3), Advanced Audio Coding (AAC), Adaptive Multi-Rate (AMR) audio codec, Joint Photographic Experts Group (JPEG or JPG), or Portable Network Graphics (PNG)), graphics libraries (e.g., an OpenGL framework used to render in 2D and 3D in a graphic context on a display), database libraries (e.g., SQLite to provide various relational database functions), web libraries (e.g., WebKit to provide web browsing functionality), and the like. The libraries  606  can also include a wide variety of other libraries  634  to provide many other APIs to the applications  610 . 
     The frameworks  608  provide a high-level common infrastructure that can be utilized by the applications  610 , according to some embodiments. For example, the frameworks  608  provide various graphical user interface (GUI) functions, high-level resource management, high-level location services, and so forth. The frameworks  608  can provide a broad spectrum of other APIs that can be utilized by the applications  610 , some of which may be specific to a particular operating system  604  or platform. 
     In an example embodiment, the applications  610  include a home application  650 , a contacts application  652 , a browser application  654 , a book reader application  656 , a location application  658 , a media application  660 , a messaging application  662 , a game application  664 , and a broad assortment of other applications, such as a third-party application  666 . According to some embodiments, the applications  610  are programs that execute functions defined in the programs. Various programming languages can be employed to create one or more of the applications  610 , structured in a variety of manners, such as object-oriented programming languages (e.g., Objective-C, Java, or C++) or procedural programming languages (e.g., C or assembly language). In a specific example, the third-party application  666  (e.g., an application developed using the ANDROID™ or IOS™ software development kit (SDK) by an entity other than the vendor of the particular platform) may be mobile software running on a mobile operating system such as IOS™, ANDROID™, WINDOWS® Phone, or another mobile operating system. In this example, the third-party application  666  can invoke the API calls  612  provided by the operating system  604  to facilitate functionality described herein. 
       FIG. 7  illustrates a diagrammatic representation of a machine  700  in the form of a computer system within which a set of instructions may be executed for causing the machine  700  to perform any one or more of the methodologies discussed herein, according to an example embodiment. Specifically,  FIG. 7  shows a diagrammatic representation of the machine  700  in the example form of a computer system, within which instructions  716  (e.g., software, a program, an application, an applet, an app, or other executable code) for causing the machine  700  to perform any one or more of the methodologies discussed herein may be executed. For example, the instructions  716  may cause the machine  700  to execute the methods of  FIGS. 2-5 . Additionally, or alternatively, the instructions  716  may implement  FIGS. 1-5  and so forth. The instructions  716  transform the general, non-programmed machine  700  into a particular machine  700  programmed to carry out the described and illustrated functions in the manner described. In alternative embodiments, the machine  700  operates as a standalone device or may be coupled (e.g., networked) to other machines. In a networked deployment, the machine  700  may operate in the capacity of a server machine or a client machine in a server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. The machine  700  may comprise, but not be limited to, a server computer, a client computer, a personal computer (PC), a tablet computer, a laptop computer, a netbook, a set-top box (STB), a personal digital assistant (PDA), an entertainment media system, a cellular telephone, a smart phone, a mobile device, a wearable device (e.g., a smart watch), a smart home device (e.g., a smart appliance), other smart devices, a web appliance, a network router, a network switch, a network bridge, or any machine capable of executing the instructions  716 , sequentially or otherwise, that specify actions to be taken by the machine  700 . Further, while only a single machine  700  is illustrated, the term “machine” shall also be taken to include a collection of machines  700  that individually or jointly execute the instructions  716  to perform any one or more of the methodologies discussed herein. 
     The machine  700  may include processors  710 , memory  730 , and I/O components  750 , which may be configured to communicate with each other such as via a bus  702 . In an example embodiment, the processors  710  (e.g., a central processing unit (CPU), a reduced instruction set computing (RISC) processor, a complex instruction set computing (CISC) processor, a graphics processing unit (GPU), a digital signal processor (DSP), an application-specific integrated circuit (ASIC), a radio-frequency integrated circuit (RFIC), another processor, or any suitable combination thereof) may include, for example, a processor  712  and a processor  714  that may execute the instructions  716 . The term “processor” is intended to include multi-core processors that may comprise two or more independent processors (sometimes referred to as “cores”) that may execute instructions  716  contemporaneously. Although  FIG. 7  shows multiple processors  710 , the machine  700  may include a single processor  712  with a single core, a single processor  712  with multiple cores (e.g., a multi-core processor  712 ), multiple processors  712 ,  714  with a single core, multiple processors  712 ,  714  with multiple cores, or any combination thereof. 
     The memory  730  may include a main memory  732 , a static memory  734 , and a storage unit  736 , each accessible to the processors  710  such as via the bus  702 . The main memory  732 , the static memory  734 , and the storage unit  736  store the instructions  716  embodying any one or more of the methodologies or functions described herein. The instructions  716  may also reside, completely or partially, within the main memory  732 , within the static memory  734 , within the storage unit  736 , within at least one of the processors  710  (e.g., within the processor&#39;s cache memory), or any suitable combination thereof, during execution thereof by the machine  700 . 
     The I/O components  750  may include a wide variety of components to receive input, provide output, produce output, transmit information, exchange information, capture measurements, and so on. The specific I/O components  750  that are included in a particular machine will depend on the type of machine. For example, portable machines such as mobile phones will likely include a touch input device or other such input mechanisms, while a headless server machine will likely not include such a touch input device. It will be appreciated that the I/O components  750  may include many other components that are not shown in  FIG. 7 . The I/O components  750  are grouped according to functionality merely for simplifying the following discussion, and the grouping is in no way limiting. In various example embodiments, the I/O components  750  may include output components  752  and input components  754 . The output components  752  may include visual components (e.g., a display such as a plasma display panel (PDP), a light-emitting diode (LED) display, a liquid crystal display (LCD), a projector, or a cathode ray tube (CRT)), acoustic components (e.g., speakers), haptic components (e.g., a vibratory motor, resistance mechanisms), other signal generators, and so forth. The input components  754  may include alphanumeric input components (e.g., a keyboard, a touch screen configured to receive alphanumeric input, a photo-optical keyboard, or other alphanumeric input components), point-based input components (e.g., a mouse, a touchpad, a trackball, a joystick, a motion sensor, or another pointing instrument), tactile input components (e.g., a physical button, a touch screen that provides location and/or force of touches or touch gestures, or other tactile input components), audio input components (e.g., a microphone), and the like. 
     In further example embodiments, the I/O components  750  may include biometric components  756 , motion components  758 , environmental components  760 , or position components  762 , among a wide array of other components. For example, the biometric components  756  may include components to detect expressions (e.g., hand expressions, facial expressions, vocal expressions, body gestures, or eye tracking), measure biosignals (e.g., blood pressure, heart rate, body temperature, perspiration, or brain waves), identify a person (e.g., voice identification, retinal identification, facial identification, fingerprint identification, or electroencephalogram-based identification), and the like. The motion components  758  may include acceleration sensor components (e.g., accelerometer), gravitation sensor components, rotation sensor components (e.g., gyroscope), and so forth. The environmental components  760  may include, for example, illumination sensor components (e.g., photometer), temperature sensor components (e.g., one or more thermometers that detect ambient temperature), humidity sensor components, pressure sensor components (e.g., barometer), acoustic sensor components (e.g., one or more microphones that detect background noise), proximity sensor components (e.g., infrared sensors that detect nearby objects), gas sensors (e.g., gas detection sensors to detect concentrations of hazardous gases for safety or to measure pollutants in the atmosphere), or other components that may provide indications, measurements, or signals corresponding to a surrounding physical environment. The position components  762  may include location sensor components (e.g., a Global Positioning System (GPS) receiver component), altitude sensor components (e.g., altimeters or barometers that detect air pressure from which altitude may be derived), orientation sensor components (e.g., magnetometers), and the like. 
     Communication may be implemented using a wide variety of technologies. The I/O components  750  may include communication components  764  operable to couple the machine  700  to a network  780  or devices  770  via a coupling  782  and a coupling  772 , respectively. For example, the communication components  764  may include a network interface component or another suitable device to interface with the network  780 . In further examples, the communication components  764  may include wired communication components, wireless communication components, cellular communication components, near field communication (NFC) components, Bluetooth® components (e.g., Bluetooth® Low Energy), Wi-Fi® components, and other communication components to provide communication via other modalities. The devices  770  may be another machine or any of a wide variety of peripheral devices (e.g., coupled via a USB). 
     Moreover, the communication components  764  may detect identifiers or include components operable to detect identifiers. For example, the communication components  764  may include radio-frequency identification (RFID) tag reader components, NFC smart tag detection components, optical reader components (e.g., an optical sensor to detect one-dimensional bar codes such as Universal Product Code (UPC) bar code, multi-dimensional bar codes such as QR code, Aztec code, Data Matrix, Dataglyph, MaxiCode, PDF417, Ultra Code, UCC RSS-2D bar code, and other optical codes), or acoustic detection components (e.g., microphones to identify tagged audio signals). In addition, a variety of information may be derived via the communication components  764 , such as location via Internet Protocol (IP) geolocation, location via Wi-Fi® signal triangulation, location via detecting an NFC beacon signal that may indicate a particular location, and so forth. 
     The various memories (i.e.,  730 ,  732 ,  734 , and/or memory of the processor(s)  710 ) and/or the storage unit  736  may store one or more sets of instructions  716  and data structures (e.g., software) embodying or utilized by any one or more of the methodologies or functions described herein. These instructions (e.g., the instructions  716 ), when executed by the processor(s)  710 , cause various operations to implement the disclosed embodiments. 
     As used herein, the terms “machine-storage medium,” “device-storage medium,” and “computer-storage medium” mean the same thing and may be used interchangeably. The terms refer to a single or multiple storage devices and/or media (e.g., a centralized or distributed database, and/or associated caches and servers) that store executable instructions and/or data. The terms shall accordingly be taken to include, but not be limited to, solid-state memories, and optical and magnetic media, including memory internal or external to processors. Specific examples of machine-storage media, computer-storage media, and/or device-storage media include non-volatile memory, including by way of example semiconductor memory devices, e.g., erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM), field-programmable gate array (FPGA), and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The terms “machine-storage media,” “computer-storage media,” and “device-storage media” specifically exclude carrier waves, modulated data signals, and other such media, at least some of which are covered under the term “signal medium” discussed below. 
     In various example embodiments, one or more portions of the network  780  may be an ad hoc network, an intranet, an extranet, a virtual private network (VPN), a local-area network (LAN), a wireless LAN (WLAN), a wide-area network (WAN), a wireless WAN (WWAN), a metropolitan-area network (MAN), the Internet, a portion of the Internet, a portion of the public switched telephone network (PSTN), a plain old telephone service (POTS) network, a cellular telephone network, a wireless network, a Wi-Fi® network, another type of network, or a combination of two or more such networks. For example, the network  780  or a portion of the network  780  may include a wireless or cellular network, and the coupling  782  may be a Code Division Multiple Access (CDMA) connection, a Global System for Mobile communications (GSM) connection, or another type of cellular or wireless coupling. In this example, the coupling  782  may implement any of a variety of types of data transfer technology, such as Single Carrier Radio Transmission Technology (1×RTT), Evolution-Data Optimized (EVDO) technology, General Packet Radio Service (GPRS) technology, Enhanced Data rates for GSM Evolution (EDGE) technology, third Generation Partnership Project (3GPP) including 3G, fourth generation wireless (4G) networks, Universal Mobile Telecommunications System (UMTS), High-Speed Packet Access (HSPA), Worldwide Interoperability for Microwave Access (WiMAX), Long-Term Evolution (LTE) standard, others defined by various standard-setting organizations, other long-range protocols, or other data transfer technology. 
     The instructions  716  may be transmitted or received over the network  780  using a transmission medium via a network interface device (e.g., a network interface component included in the communication components  764 ) and utilizing any one of a number of well-known transfer protocols (e.g., Hypertext Transfer Protocol (HTTP)). Similarly, the instructions  716  may be transmitted or received using a transmission medium via the coupling  772  (e.g., a peer-to-peer coupling) to the devices  770 . The terms “transmission medium” and “signal medium” mean the same thing and may be used interchangeably in this disclosure. The terms “transmission medium” and “signal medium” shall be taken to include any intangible medium that is capable of storing, encoding, or carrying the instructions  716  for execution by the machine  700 , and include digital or analog communications signals or other intangible media to facilitate communication of such software. Hence, the terms “transmission medium” and “signal medium” shall be taken to include any form of modulated data signal, carrier wave, and so forth. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. 
     The terms “machine-readable medium,” “computer-readable medium,” and “device-readable medium” mean the same thing and may be used interchangeably in this disclosure. The terms are defined to include both machine-storage media and transmission media. Thus, the terms include both storage devices/media and carrier waves/modulated data signals.