Abstract:
Records in a secure database include attributes. A query homomorphically encrypts indices identifying one record and attribute. A secret key is generated at a certain query count and is divided into randomly generated key shares. A key share sequence is homomorphically encrypted. A table is formed by encrypting the indices, secret key and attributes. The key shares are decrypted sufficient to recover the secret key subject to a non-inference enabling query. In a further embodiment, a query count is maintained. Records in a secure database include attributes, with an attributes set forming inference channels. A data structure includes ciphertext keys. A pseudorandom function seed and non-malleable encryption secret key are chosen. A query provides indices identifying one record and attribute. A secure function evaluation is executed. A table combines the attributes with the pseudorandom function applied to the seed and indices. A table entry for the indices is provided.

Description:
FIELD  
       [0001]     This application relates in general to secure information retrieval and, in particular, to a system and method for providing private inference control.  
       BACKGROUND  
       [0002]     On-line databases, particularly databases available over a network, such as the Internet, can provide virtually unlimited access to various stored forms of information, whether by design or inadvertence. As a result, maintaining sensitive information securely in on-line databases has become increasingly important, especially in light of concerns over identity theft and compliance with medical information privacy laws. Ensuring the safety of sensitive information requires protecting the privacy interests of the user against unauthorized users and from the server seeing the user&#39;s queries.  
         [0003]     Unauthorized users attempt to gain surreptitious access to sensitive information either directly or by inference. Direct access requires obtaining the sensitive information by circumventing security safeguards and compromising the data by direct attack. Inferential access is an indirect attempt to determine sensitive information through a sequence of queries of non-sensitive information whose answers, taken together, allow an improper inference to be drawn about the sensitive information. Such query sequences are known as inference channels. Access and inference control can respectively protect against direct or inferential sensitive information compromise by controlling each response to a query.  
         [0004]     As repositories of the sensitive information, servers are generally viewed as disinterested in the nature of the sensitive information stored. However, the act of submitting a query to a server presents the possibility of a loss of privacy interests to an honest but “curious” server, where the user suffers a loss of privacy due to exposure of the query to the server. The mere fact of the attribute being searched, the frequency of searching and whether the response is blocked can be revealing, even if actual sensitive information is not compromised. Private information retrieval allows users to retrieve information from a server privately and without compromise due to queries.  
         [0005]     Sensitive information must be safeguarded against compromise from unauthorized users, especially with respect to indirect means of compromise through inference channels. Similarly, a server is expected to safeguard against both unauthorized direct access and inference channels, even though the blocking of a query can remain secret. Thus, protecting the privacy interests of a user against unauthorized users and curious but honest servers creates a dilemma over how best to ensure that unauthorized users are not able to infer sensitive information without letting the server know what information is being retrieved.  
         [0006]     U.S. Patent Application Publication No. US2003/0145004, published Jul. 21, 2003 to Egilsson et al., describes an inference control method in a data cube. Attributes used to determine how data is aggregated and viewed are rearranged by modifying hypercube realizations in such a way that modified schemes satisfy identity protection requirements for inference control. The same processes can also be used to enforce rewriting of hierarchies in such a way that modified structure reveals colorations and patterns in a dataset. However, the Egilsson reference fails to describe ensuring privacy of queries relative to an honest but curious server.  
         [0007]     B. Aiello et al., “Priced Oblivious Transfer: How to Sell Digital Goods,” Advances in Cryptology-Eurocrypt &#39;01 (2001), describes an inference channel control scheme that associates prices with attributes of records. Buyers can successfully retrieve selected items as long as the buyers&#39; balance contains sufficient funds. Items whose costs exceed the remaining budget cannot be retrieved and the vendor, that is, server, learns nothing except the amount of interaction and initial deposit amount. However, the inference channel control scheme provides a specific solution to a subclass of inference control problems cannot be applied to an arbitrary subset of inference channels selected from a set of potentially searchable data.  
         [0008]     B. Chor et al., “Private Information Retrieval,” Proc. of FOCS &#39;95 (1995), describes private inference control, whereby the server learns nothing about the query. However, the Chor reference fails to provide control over arbitrary inference channels.  
         [0009]     X. Qian et al., “Detection and Elimination of Inference Channels in Multilevel Relational Database Systems,” Proc. of IEEE Symp. on Research in Security and Privacy, pp. 196-205 (1993), describes a tool for assisting database designers in detecting and eliminating potential sources of inference problems in multilevel relational database schemas. Inferences can be blocked by upgrading the security classification of some foreign key relationships. However, the Qian reference fails to provide protection against a server seeing the user&#39;s queries.  
         [0010]     Therefore, there is a need for providing secure control over inference channels in combination with private information retrieval.  
       SUMMARY  
       [0011]     One embodiment provides a system and method for providing private inference control. A secure database is maintained and includes a plurality of records. Each record includes a plurality of attributes. A query is specified by encrypting indices identifying one such record and attribute by homomorphic encryption. A secret key is generated upon reaching a certain query count. The secret key is divided into randomly generated key shares and a sequence of the key shares is provided, which are each encrypted by homomorphic encryption. A table of entries is formed by encrypting the indices, the secret key and each of the attributes for each of the records of the database. The table is provided and a plurality of the key shares is decrypted sufficient to recover the secret key subject to a non-inference enabling query.  
         [0012]     A further embodiment provides a system and method for providing private inference control. A query count and a secure database are maintained and include a plurality of records. Each record includes a plurality of attributes, wherein a set of the attributes forms one or more inference channels. A regular data structure is constructed including a set of ciphertext keys, which each relate to one such attribute and record in the secure database. A seed for a pseudorandom function and a secret key for non-malleable encryption are chosen. A query is specified by providing indices identifying one such record and attribute by homomorphic encryption and a secure function evaluation is executed dependent upon the inference channels, the seed, the secret key, the query count, and the set of ciphertext keys. An output is generated from the secure function evaluation including the pseudorandom function and an updated set of ciphertext keys subject to sum-consistency of the set of ciphertext keys and a non-inference enabling query. A table of entries is formed by combining each of the attributes for each of the records of the database with an output from the pseudorandom function as applied to the seed and the indices. The entry is provided from the table corresponding to the indices.  
         [0013]     Still other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein are described embodiments by way of illustrating the best mode contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and the scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a block diagram showing, by way of example, a user system and a server system upon which private inference control is provided.  
         [0015]      FIG. 2  is a block diagram showing a user system for providing stateful private inference control, in accordance with one embodiment.  
         [0016]      FIG. 3  is a block diagram showing a server system for providing stateful private inference control, in accordance with one embodiment.  
         [0017]      FIG. 4  is a flow diagram showing a method for providing stateful private inference control, in accordance with one embodiment.  
         [0018]      FIG. 5  is a flow diagram showing a routine for performing preprocessing for use in the method of  FIG. 4 .  
         [0019]      FIG. 6  is a flow diagram showing a routine for sending query information for use in the method of  FIG. 4 .  
         [0020]      FIG. 7  is a flow diagram showing a routine for generating authorizations for use in the method of  FIG. 4 .  
         [0021]      FIG. 8  is a flow diagram showing a routine for performing key recovery for use in the method of  FIG. 4 .  
         [0022]      FIG. 9  is a flow diagram showing a routine for processing a query for use in the method of  FIG. 4 .  
         [0023]      FIG. 10  is a flow diagram showing a routine for recovering a target attribute for use in the method of  FIG. 4 .  
         [0024]      FIG. 11  is a data structure diagram showing, by way of example, a balanced binary tree containing database keys.  
         [0025]      FIG. 12  is a block diagram showing a user system for providing private inference control, in accordance with a further embodiment.  
         [0026]      FIG. 13  is a block diagram showing a server system for providing private inference control, in accordance with a further embodiment.  
         [0027]      FIG. 14  is a flow diagram showing a method for providing private inference control, in accordance with a further embodiment.  
         [0028]      FIG. 15  is a flow diagram showing a routine for performing preprocessing for use in the method of  FIG. 14 .  
         [0029]      FIG. 16  is a flow diagram showing a routine for generating query information for use in the method of  FIG. 14 .  
         [0030]      FIG. 17  is a flow diagram showing a routine for performing a secure function evaluation for use in the method of  FIG. 14 .  
         [0031]      FIG. 18  is a flow diagram showing a routine for building a table for use in the method of  FIG. 14 .  
         [0032]      FIG. 19  is a flow diagram showing a routine for recovering a target attribute for use in the method of  FIG. 14 . 
     
    
     DETAILED DESCRIPTION  
       [0000]     Private Inference Control Environment  
         [0033]      FIG. 1  is a block diagram  10  showing, by way of example, a user system  11  and a server system  12  upon which private inference control is provided. A user system  11  remotely accesses a server system  12  over a network  14 , such as the Internet. The server system  12  is coupled to a storage device  13 , in which a database storing sensitive information is maintained. Access to the sensitive information is provided through private inference control, as further described below beginning with reference to  FIG. 2  et seq.  
         [0034]     Preferably, the user system  11  and server system  12  are general-purpose computers executing operating system and providing an application execution environment. The user system  11  and server system  12  include components conventionally found in a personal computer or server, such as, for example, a central processing unit, display, keyboard, mouse, and various components for interconnecting these components. Program code, including software programs and data is loaded into memory for execution and processing by the central processing unit and results are generated for display, output, transmittal, or storage.  
         [0000]     Overview  
         [0035]     Two protocols for providing private inference control are described. In the first protocol, the server system  12  maintains state by storing encrypted information about the queries of each user system  11 . In the second protocol, the server system  12  operates with minimal state and only maintains the cumulative total number of queries made by each user system  11 . The protocols apply to single-server computationally-private inference control schemes. All users and servers execute efficient probabilistic algorithms.  
         [0036]     For notational convenience, the following conventions will be followed:  
         [0037]     For an integer m, [m] denotes the set {1, . . . , m}. Further, let 2 [m]  denote the set of all subset of [m].  
         [0038]     For a vector s, s i  refers to its ith coordinate, and if s i  is itself a vector, s i,j  denotes the ith coordinate of s i . This notation is repeated indefinitely, so if s i,j  is also a vector, s i,j,k  denotes its kth coordinate. For i≦j, let s i, . . . , j  denote the (j−i+1)-tuple (s i , s i+1 , . . . , s j−1 , s j ).  
         [0039]     For two strings or vectors s and t, let s∘t denote their concatenation. Let |s| denote the length of s.  
         [0040]     An arbitrary negligible function is denoted by η(a,b), for example, a function of a, b, which is less than any inverse polynomial in a, b for a and b sufficiently large.  
         [0041]     Two families of random variables U n  and V n  are computationally indistinguishable if, for all probabilistic polynomial time (PPT) algorithms A, |P[A(U n )=1]−Pr[A(V n )=1]|&lt;η(n).  
         [0042]     The notation Õ suppresses terms that are polylogarithmic in the number of database records n.  
         [0043]     All entries in the database are single bits, but the definitions can extend to handle entries in {0,1} for constant 1.  
         [0044]     A database is a string xε({0,1} m ) n . x i  denotes the ith record of the database, and x i,j  denotes the jth attribute value of the ith record. In a general asymptotic analysis, the number of attributes, m, is at most O(log log n), whereas the number of records n is very large, as is the case for many relational databases.  
         [0045]     Given the description of x, there is a mechanism for generating a collection C of sets F ⊂ [m] denoting the inference channels in x. The meaning of C is that, for all iε[n] and FεC, the user should not learn x i,j  for all jεF. We take C to be an input to the server.  
         [0046]     C is monotone, that is, if AεC and A ⊂ B, then BεC. C is nonempty and C is an input to the user.  
         [0047]     A query sequence T of distinct pairs is permissible if the query sequence does not complete any inference channels, that is, for all FεC and all iε[n], there exists an lεF, such that (i, l)∉T. T=T(U, x), where U denotes the code of U and T is a random variable induced by the uniform distribution on ρ and γ, where ρ and γ are random strings stored by the user system  11  and server system  12 , respectively. If U is honest, T assumes a particular permissible query sequence for fixed ρ and γ.  
         [0000]     Stateful Private Inference Control  
         [0048]     The stateful private inference control protocol makes use of a homomorphic encryption function, E hom (•). With E hom (•) the user system  11  can privately send query information to the server system  12 . Using the homomorphic property of E hom (•), the server system  12  can encrypt a secret, S, in such a way that the user system  11  can only recover the sent S if the user system  11  is not in danger of making an undesired inference with the current query. Finally, the user system  11  and server system  12  engage in a secure private information retrieval (SPIR) protocol on a table encrypted under the sent key S and the encrypted query information sent by the user system  11 . Hence, recovery of the sent key S effectively authorizes the user system  11  to receive the query answer.  
         [0000]     User System for Providing Stateful Private Inference Control  
         [0049]      FIG. 2  is a block diagram  20  showing a user system  11  for providing stateful private inference control, in accordance with one embodiment. The user system  21  generates a private key  24  and a public key (not shown) that is shared with the server system. The user system  11  includes a query generator  22  and reconstructor  23 . The query generator  22  engages with the server system to execute a SPIR protocol based on query information  28  that is sent to the server system, as further described below with reference to  FIG. 6 . The reconstructor  23  identifies key shares  25  received from the server system to generate a reconstructed key  26  that is used to recover a target attribute  27 , as further described below with reference to  FIG. 10 .  
         [0000]     User System for Providing Stateful Private Inference Control  
         [0050]      FIG. 3  is a block diagram  30  showing a server system  12  for providing stateful private inference control, in accordance with one embodiment. The server system  31  stores the set of inference channels  37 . The server system  31  receives a public key  34  from the user system  21  that has been generated from the private key  24 . The server system  31  receives a query  44 , consisting of the query information  28  homomorphically encrypted by the user system  21 . The query  44  identifies a record  39  and attribute  40  stored securely in a database  38  maintained by the server system  31 .  
         [0051]     The server system  31  includes an authorization generator  32  and query processor  33 . The authorization generator  32  generates a secret key  35  and randomly generated key shares  36 , which are sent to the user system  21  as authorizations  45 , as further described below with reference to  FIG. 7 . The query processor  33  forms a table  41  that includes records  42  and attributes  43 , which correspond to the records  39  and attributes  40  of the database  38 . The entries in the table  41  are provided to the user system  21  as responses  46  through execution of the SPIR protocol, as further described below with reference to  FIG. 9 .  
         [0000]     Stateful Private Inference Control Method  
         [0052]      FIG. 4  is a flow diagram  50  showing a method for providing stateful private inference control, in accordance with one embodiment. The purpose of the method is to provide private inference control by providing key shares  36  to a user system  21  which, in conjunction with authorizations  45 , prevent the completion of inference channels  37  to unauthorized users while not revealing information to the server system  31 . The method is described as a sequence of process operations or steps, which can be executed, for instance, by a user system  21  and server system  31 .  
         [0053]     Initially, the user system  21  performs preprocessing (block  51 ) to provide a public key  34  to the server system  31 , as further described below with reference to  FIG. 5 . The user system  21  then sends query information  28  (block  52 ) to the server system  31 , as further described below with reference to  FIG. 6 . In response, the server system  31  generates authorizations  45  (block  53 ), which are provided to the user system  21 , as further described below with reference to  FIG. 7 . Upon receipt of a sufficient number of key shares  25 , the user system  21  recovers a reconstructed key (block  54 ), as further described below with reference to  FIG. 8 . The server system  31  processes the query  44  (block  55 ), as further described below with reference to  FIG. 9 , and the user system  21  recovers the target attribute  27  (block  56 ), as further described below with reference to  FIG. 10 .  
         [0000]     Preprocessing  
         [0054]      FIG. 5  is a flow diagram  60  showing a routine for performing preprocessing for use in the method of  FIG. 4 . The purpose of this routine is to begin a query sequence by generating a private key  24  and public key  34 .  
         [0055]     The number of queries t is initialized (block  61 ). If the current number of queries t is equal to one (block  62 ), a private key  24  and public key  34  are generated by the user system  21  (block  63 ) and the public key  34  is sent to the server system  31  (block  64 ).  
         [0000]     Sending Query Information  
         [0056]      FIG. 6  is a flow diagram  70  showing a routine for sending query information  28  for use in the method of  FIG. 4 . The purpose of this routine is to send encrypted query information  28  to the server system  31  coupled with satisfactory proof of knowledge.  
         [0057]     Initially, the user system  21  identifies a target record i and attribute j (block  71 ). The target record i and attribute j are homomorphically encrypted as E hom (i t ) and E hom (j t ) and are sent to the server system  31  (block  72 ). Finally, as an optional step, the user system  21  can execute a zero-knowledge proof of knowledge to demonstrate that the ciphertexts maintained in the database  38  are well-formed (block  73 ). Intuitively, a zero-knowledge proof of knowledge allows a prover to convince a verifier of some fact in zero-knowledge if and only if the prover knows something. Zero-knowledge proofs are described in S. Goldwasser et al., “The Knowledge Complexity of Interactive Proof Systems,” SIAM J. Comp., Vol. 18 (1), pp. 186-208 (1999), the disclosure of which is incorporated by reference.  
         [0000]     Generating Authorizations  
         [0058]      FIG. 7  is a flow diagram  80  showing a routine for generating authorizations  45  for use in the method of  FIG. 4 . The purpose of this routine is to generate the secret key  35  and to provide key shares  36  to the user system  21  as authorizations  45 .  
         [0059]     If the count of queries t is less than the number of inference channels m (block  81 ), the server system  31  sets the secret key as S t  to zero (block  82 ). Otherwise, the server generates a secret key S t  and randomly generates key shares y 1 , . . . , y t−1 , (block  83 ). Finally, the server system  31  sends the key shares homomorphically encrypted with an index value as E hom ((i−i t )y 1 ), . . . , E hom ((i t−1 −i t )y t−1 ) to the user system  21  (block  84 ).  
         [0000]     Key Recovery  
         [0060]      FIG. 8  is a flow diagram  90  showing a routine for performing key recovery for use in the method of  FIG. 4 . The purpose of this routine is to recover the secret key  35  upon receiving a sufficient number of key shares  36 .  
         [0061]     The key recovery is performed in an iterative processing loop (blocks  91 - 93 ) from 1 to t−m+1, that is, up to the query count t plus m less one. During each iteration, the user system  21  homomorphically decrypts the authorization E hom ((i h −i t )y h (block  92 ). The user system  21  will be able to decrypt and recover at least t−m+1 of the key shares  36  in {y 1 , . . . , y t−1 } if the user system  21  has made a permissible sequence of queries and will thus be able to recover the secret key S t  (block  94 ).  
         [0000]     Query Processing  
         [0062]      FIG. 9  is a flow diagram  100  showing a function for processing a query  44  for use in the method of  FIG. 4 . The purpose of this function is to build the table  41 , from which query responses  46  are provided.  
         [0063]     Initially, the server system  31  generates a pair of random values v i,j   (1)  and v i,j   (2)  for 1≦i≦n, 1≦j≦m (block  101 ), which are used to perturb the corresponding attributes  40  stored in the database  38 . The server system  31  then builds the table  41  by storing each of the attributes  40  as homomorphically encrypted attributes  43  formed as τ=(E hom (v i,j   (1) (j−j t )+v i,j   (2) (i−i t )+S t +x ij )) i,j  (block  102 ). The server system  31  receives the query information  28 , and returns the encrypted attribute T i,j  through execution of the SPIR protocol (block  103 ) with the user system  21 .  
         [0000]     Target Attribute Recovery  
         [0064]      FIG. 10  is a flow diagram  110  showing a routine for recovering a target attribute  27  for use in the method of  FIG. 4 . The purpose of this routine is to recover the requested target attribute  27  from a table entry received through execution of the SPIR protocol with the server system  12 .  
         [0065]     Initially, the user system  21  homomorphically decrypts the encrypted attribute T i,j  (block  111 ). If the record index i and attribute j index match the perturbed record index i t  and attribute index j t  (block  112 ), the corresponding parameters in the table τ=(E hom (v i,j   (1) (j−j t )+v i,j   (2) (i−i t )+S t +x ij )) i,j  are zeroed-out and the secret key S t  can be subtracted to recover the target attribute x i,j  (block  113 ).  
         [0000]     Private Inference Control  
         [0066]     In accordance with a further embodiment, a private inference control protocol makes use of a balanced binary tree data structure to hierarchically store keys paired with a query count for an associated attribute in the database.  FIG. 11  is a data structure diagram  150  showing, by way of example, a balanced binary tree  151  containing database keys. Without loss of generality, n is a power of 2. The balanced binary tree  151  has n leaves  153  beginning at a root node  152 , where in addition, m children  154  are connected to each leaf of the binary tree  151 . The leaves  155  denote entries x i,j  of the database, and the parents of the leaves denote records x i,j . The user system obtains keys K(w, z) associated with each leaf w indicating whether the value at the leaf has been accessed. Here, zε{0,1}. Internal nodes w also have associated keys K(w, z), where z is an integer indicating the total number of times that the leaves in the subtree rooted at w have been accessed. The keys are used for inference control. When a user system retrieves a database entry, the keys are used to traverse the tree upwards. If the user system tries to use “older” keys indicating that nodes have been accessed fewer times the actual query count, the keys will be inconsistent with the server system knowledge of the total number of queries made and the user system will not be able to recover the desired database entry.  
         [0067]     Notationally, α denotes the root of the binary balanced tree B. Node wεB is at height d if node w is d levels above the leaves. The leaves are at height 0. Each node w in B of height 1 is denoted by i for some iε[n], and each of the m children of i are denoted by (i, j) for some jε[m]. For a non-root node w in B, let sib(w) denote w&#39;s siblings, which are either 1 or m−1. For a non-leaf node w, let children (w) denote w&#39;s children. For a leaf node w, let anc(w) denote the set of log n+1 ancestors along the path from w to α, inclusive. Node w is considered accessed whenever x i,j  is successfully retrieved by the user system for which wεanc(i, j). Finally, for leaves w, the set of 2 log n+m−1 nodes that is the set of ancestors together with the siblings of the ancestors, the following relation is defined: 
 
sibanc( w )=anc( w )∪{ u|∃v εanc( w ) s.t.u =sib( v )}
 
         [0068]     When an honest user system queries x i,j , the user system will use the set of keys π={K(w,f w )|wεsibanc(i, j)}, where f w  is the number of times w has been assessed. If the user system is dishonest, for some wεsibanc(i, j), the user system may substitute K(w, z) in place of K(w, f w ) for some integer z With all but negligible probability, any dishonest user system cannot determine K(w, z), for any z&gt;f w  and if K(w, z) is substituted for K(w, f w ), z&lt;f w  holds. If the user system is given x i,j , the user system will also obtain the updated set of keys π={K(w, f w )|wεsibanc(i, j)}.  
         [0069]     Inference control is enforced by sum-consistency. For any non-leaf node w and children nodes, children (w), the keys K(w,i), {K(u, j u )|uεchildren(w)} are sum-consistent if i=Σ uεchildren(w) j u . Suppose an honest system wants to retrieve x i,j  on the (t+1)st query. The set of keys π gives a proof that the user system is not in danger of completing an inference channel. Indeed, if the user system is honest, π has the following three properties: 
        1. For each non-leaf node w in anc(i, j), K(w, f w ) and {K(u, f u )|uεchildren(w)} are sum-consistent.     2. f α =t.     3. If the user system is not in danger of completing an inference channel by learning x i,j , then for all inference channels FεC, there is some j′εF such that j′≠j for which K((i, j′),0)επ.        
 
         [0073]     A dishonest user system will not be able to furnish a proof π to obtain x i,j  when learning x i, j  completes an inference channel F. Indeed, if the dishonest user system does not substitute K(w, z) for K(w, f w ) for some z≠f w  and wεsibanc(i, j), the third property described above cannot hold. On the other hand, by the invariant described above, if the dishonest system substitutes K(w, z) for K(w, f w ) for some z≠f w  for some node w, then z is necessarily less than f w  and properties (1) and (2) cannot hold simultaneously.  
         [0074]     For user privacy, the user system cannot simply give π to the server system. Instead, the user system proves knowledge of π via a secure function evaluation (SFE) circuit. The user system inputs π to the SFE circuit, which will give the user system a certain secret if and only if π is a valid proof. If the server were to use truly random keys, the server would have to input all possible user keys into the SFE circuit to perform the comparisons since the server cannot know which keys the user system will use. However, this problem is avoided by making the keys dependent upon each other through the use of a non-malleable encryption scheme. Intuitively, all of the keys appear to be independent of each other, unless one key has a special, master key. This approach allows less communication overhead, as the server need only give the master key to the SFE circuit.  
         [0000]     User System for Providing Private Inference Control  
         [0075]      FIG. 12  is a block diagram  120  showing a user system  121  for providing private inference control, in accordance with a further embodiment. The user system  121  maintains a set of keys  124  hierarchically structured into a balanced binary tree, as described above with reference to  FIG. 11 . Each key  124  reflects the node and frequency count corresponding to a record and attribute in the database. In addition, the user system  121  maintains a reject count  125  and repeat count  126  respectively reflecting failed and duplicated queries.  
         [0076]     The user system  121  includes a query generator  122  and reconstructor  123 . The query generator  122  includes a secure function evaluation (SFE) circuit  137 , which receives inputs from the user system  121  that include a set of keys  124 , record i, attribute index j, a reject count  125 , and repeat count  126 . The SFE circuit  137  also receives inputs from the server system that include a secret key  127 , query count  128 , set of inference channels  129 , and seed value  130 , which is used for a pseudorandom function. The SFE circuit  137  outputs a set of updated keys  133  and pseudorandom function  134  if the set of keys  124  is sum-consistent, as further described below with reference to  FIG. 17 . Otherwise, the SFE circuit  137  outputs a non-malleably encrypted reject count  131  or repeat count  132 , as applicable. The query generator  122  generates query information  136 , which is provided to the server. The reconstructor  123  recovers the target attribute  135  upon successfully receiving a pseudorandom function  134  from the SFE circuit  137 , as further described below with reference to  FIG. 19 .  
         [0000]     Server System for Providing Private Inference Control  
         [0077]      FIG. 13  is a block diagram  140  showing a server system  141  for providing private inference control, in accordance with a further embodiment. The server system  141  includes a query processor  142  that forms a table  146  that includes records  147  and attributes  148  corresponding to the records  144  and attributes  145  of the database  143 , as further described below with reference to  FIG. 18 . The query processor  142  also that maintains a query count  128  for the user system  121  and a secret key  127  and seed  130  that are provided to the secure function evaluation circuit  137  of the user system  121 , along with the set of inference channels  129 .  
         [0000]     Private Inference Control Method  
         [0078]      FIG. 14  is a flow diagram  160  showing a method for providing private inference control, in accordance with a further embodiment. The purpose of the method is to provide private inference control by maintaining a balanced binary tree of keys corresponding to records and attributes in the database and by confirming permissible query counts through sum-consistency performed through a secure function evaluation. The method is described as a sequence of process operations or steps, which can be executed, for instance, by a user system  121  and server system  141 .  
         [0079]     Initially, the server system  141  performs preprocessing (block  161 ) to choose a seed for a pseudorandom function, as further described below with reference to  FIG. 15 . The user system  121  then generates query information  136  (block  162 ), as further described below with reference to  FIG. 16 . The user system  121  executes a secure function evaluation using inputs from both the user system  121  and server system  141  (block  163 ), as further described below with reference to  FIG. 17 . The server system  141  builds a table of entries (block  164 ), as further described below with reference to  FIG. 18 . Finally, the user system  121  recovers the target attribute  135  (block  165 ), as further described below with reference to  FIG. 19 .  
         [0000]     Preprocessing  
         [0080]      FIG. 15  is a flow diagram  170  showing a routine for performing preprocessing for use in the method of  FIG. 14 . The purpose of this routine is to select a seed and encryption key.  
         [0081]     The server system  141  randomly chooses a seed s for a pseudorandom function h and a key k for a non-malleable encryption scheme I (block  171 ).  
         [0000]     Generating Query Information  
         [0082]      FIG. 16  is a flow diagram  180  showing a routine for generating query information  136  for use in the method of  FIG. 14 . The purpose of this routine is to construct the balanced binary tree  151  storing the keys  124  corresponding to the attributes  145  stored in the database  143 .  
         [0083]     Initially, the user system  121  identifies a target record i and attribute j (block  181 ). The user system  121  next constructs a set of keys π={K(w, f w |wεsibanc(i, j)} for the tree B (block  182 ).  
         [0000]     Secure Function Evaluation Performance  
         [0084]      FIG. 17  is a flow diagram  190  showing a function for performing a secure function evaluation  137  for use in the method of  FIG. 14 . The purpose of this function is to generate an output from a secure function evaluation, such as described in S. Goldreich et al., “How to Play Any Mental Game,” Proc. of 19 th  STOCL, pp. 218-229 (1987), and A. C. Yao, “Protocols for Secure Computations,” Proc. of 23 rd  FOCS, pp. 160-164 (1982), the disclosure of which are incorporated by reference.  
         [0085]     Initially, the inputs from the user system  121 , which include the set of keys π={K(w, f w )|wεsibanc(i, j)}, record index iε[n], attribute index jε[m], and two k-bit numbers p, q, which, if the user system  121  is honest, denote E K (“reject”, z 1 ) and E K (“repeat”, z 2 ) for some integers z 1  and z 1  (block  191 ). The inputs from the server system  141  include the secret key K, cumulative total number of queries t, collection of inference channels C and seed s to the pseudorandom function h. The output of the secure function evaluation is then determined as follows (block  192 ).  
         [0086]     Let C be a secure circuit implementing the functionality of the secure function evaluation. U constructs the set of keys π={K(w, f w )|wεsibanc(i t , j t )}, and feeds these keys along with keys E K (“reject”, z 1 ) and E K (“repeat”, z 2 ) into C, where z 1 , z 2  denote the number of rejected and repeated queries made thus far. If no such queries have been made in one of these two cases, that is, z 1  or z 2  are 0, then U substitutes a random value in the range of E. S then feeds s, K, and the inference channels C into C. S gets no output from C, while U&#39;s output is divided into the following cases: 
        (a) If learning x i     t     ,j     t   , is inference-enabling (block  193 ), U&#39;s output is E(“reject”, z 1 +1) (block  194 ).     (b) If x i     t     ,j     t   , was previously queried (block  195 ), U&#39;s output is E(“repeat”, z 2 +1) together with h(s, i t , j t ) (block  196 ).     (c) Otherwise U&#39;s output is h(s, i t , j t ) and the updated keys {K(w, f w +1)|K(w, f w )επ} (block  197 ). 
 
 Table Building 
       
 
         [0090]      FIG. 18  is a flow diagram  200  showing a function for building a table  146  for use in the method of  FIG. 14 . The purpose of this routine is to fill the table  146  with entries corresponding to the attributes  145  of the database  143 .  
         [0091]     The server system  141  prepares the table  146  by generating each ith and jth entry set to x i,j ⊕h(s,i,j) (block  201 ). The user system  121  and server system  141  then engage in an SPIR protocol (block  202 ) and the server system  141  returns the encrypted attribute T i     t     ,j     t   .  
         [0000]     Target Attribute Recovery  
         [0092]      FIG. 19  is a flow diagram  210  showing a routine for recovering a target attribute  135  for use in the method of  FIG. 14 . The purpose of this routine is to recover the requested target attribute  135 .  
         [0093]     If learning x i     t     ,j     t    is not inference-enabling (block  211 ), the user system  121  reconstructs x i     t     ,j     t    from h(s,i t ,j t ) and T i     t     ,j     t   =x i     t     ,j     t   δh(s,i t ,j t ) (block  212 ).  
         [0094]     While the invention has been particularly shown and described as referenced to the embodiments thereof, those skilled in the art will understand that the foregoing and other changes in form and detail may be made therein without departing from the spirit and scope.