Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 02/27/2026 has been entered.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 04/22/2026 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Response to Amendment
Examiner has fully considered Applicant’s amendments to the Claims in the arguments filed on 02/27/2026. Claims 1-17 remain pending in the application.
Response to Arguments
Applicant arguments filed 02/27/2026, with respect to the rejections of claims 1-17 under 35 USC 103 have been fully considered, but they are not persuasive. Examiner respectfully submits that the amended limitation “a combination of two or more different variables” is not sufficient to overcome the outstanding rejection under 101.
Applicant Arguments asserts that the bin mask is a data structure which produces an improvement in known techniques for performing operations on homomorphic ciphertexts, and adds that the amendment explicitly addresses the concern that the capability for processing complex multi-condition queries on homomorphic ciphertexts was not reflected in the pending claim language. While the amended limitation modifies the claimed variable combination, Examiner respectfully submits that the modified combination is not meaningfully tied to the surrounding claim elements in a significant way as to amount to more than the judicial exceptions. The amended claim continues to recite a series of broadly stated data processing operations performed on homomorphic ciphertexts with the aid of a generically stated computing component.
The bin mask corresponds to a combination of two or more different variables of each of the homomorphic ciphertexts, is generated by performing integer comparison operations on variable values corresponding to the combination, coincides with a specific condition within the homomorphic ciphertexts, and is used with the stored plurality of variable data to generate the number data (homomorphic ciphertext). Thus, the steps involving the creation and implementation of the bin mask remain broadly stated, and amount to collecting, comparing, classifying, and generating data, which are abstract ideas. The application of these abstract ideas to homomorphic ciphertexts does not, by itself, amount to significantly more – merely performing data processing operations on encrypted data does not serve to integrate the judicial exceptions into a practical application.
Applicant Arguments refer to at least specification paragraphs [0003], [0006], [0142], [0166], [0342], and [0428]. Paragraphs [0003], [0006], and [0428] discuss deficiencies of existing methods for performing operations on homomorphically encrypted datasets. Paragraph [0166] points to figures 3 and 4, which demonstrate example bin masks related to example datasets. Paragraph [0342] suggests an enhancement of computational efficiency related to the use of a bin mask. However, the potential benefits discussed in the listed paragraphs in addition to the rest of the specification are not clearly demonstrated in the amended limitation “a bin mask corresponding to a combination of two or more different variables”. Moreover, the claim does not clearly recite an operational relationship among the correspondence of the bin mask to the combination of variables, the classifying of the ciphertext variable data by the bin mask, the generation of the bin mask by the recited integer comparison operations on variable values of the combination, and the bin mask coincidence with the specific condition within the homomorphic ciphertexts. The interactions and/or cooperations of the individually recited limitations are not clearly explained in the claim. As such, the claim does not explicitly reflect how these limitations collectively produce the improvements described in the instant specification.
Although Applicant identifies improvements throughout the specification, the claims do not clearly recite structural or operational features that achieve the stated improvements. As discussed above, the claims broadly recite generating a bin mask which corresponds to a variable combination and using the bin mask to generate number data. The pending claims do not recite a particular implementation that would appear to reduce computational complexity, reduce multiplication operations and/or decryptions, or otherwise improve the performance of homomorphic computations.
Therefore, the claim remains ineligible under 35 USC 101.
Updated rationale for maintaining the rejection is provided below.
Applicant’s arguments filed 02/27/2026, with respect to the rejections of claims 1-17 under 35 USC 103 have been fully considered, but they are not persuasive. In view of an updating search and review of previously applied references, Examiner respectfully submits that the previously applied combination of Laine and Kim is sufficient to teach at least the pending independent claims, including the amended limitation “a bin mask corresponding to a combination of two or more different variables”.
Applicant Arguments asserts that the combination of Laine and Kim fails to disclose the specific bin mask structure and multi variable filtering function as defined in the claims (e.g. “a bin mask corresponding to a combination of two or more different variables of the stored plurality of variable data of each of the plurality of homomorphic ciphertexts”). Examiner respectfully disagrees, as Laine’s disclosure includes multiple examples of methods for performing operations on homomorphically encrypted data which include some generation of a data structure interpretable as the claimed bin mask. Laine teaches multiple techniques for processing encrypted dataset queries to derive statistical information from a stored encrypted dataset. The stored encrypted dataset includes “N (bit) strings of some length L … which are encrypted using homomorphic encryption … one bit of data at a time”, each of which may be reasonably interpreted as a combination of two or more different variables of a corresponding homomorphic ciphertext. An encrypted query string is received to check against the encrypted datasets to find any matches among the datasets. A multiply-then-add technique is implemented, which outputs, for each row (string) in the stored dataset, a “1” if the string matches and a “0” if the string does not match. The “1”s can be counted to discover the number of matching strings in the dataset (Laine – Paragraph [0020]-[0021]). An add-then-multiply technique is implemented, which inversely outputs a “0” when a stored string “precisely matches” the query string, and some non-zero value if there was no match. The non-zero value can be randomized in order to prevent any data leakage with regard to the stored encrypted dataset, while preserving the “0” outcomes (Laine – Paragraph [0022]-[0024]). Laine also discloses a compare-multiply-add (CMA) technique in which “given the batch count is B, then the party that encrypts the dataset includes with it B additional ciphertexts that contain masks for the batches, invalidating (i.e., setting to zero) all locations that are empty in the hash table. Similarly, the party that submits the query includes an extra ciphertext that encrypts a mask that invalidates all locations that are empty in the query hash table … Mask(H(D)).sub.i is a batched ciphertext that has a one (1) in each slot that corresponds to a non-zero hash table bin in H(D.sup.(i)), and a zero (0) in the rest of the slots, as well as Mask(H(X)) is a batched ciphertext that has a one (1) in the slots that correspond to non-empty bins, and a zero (0) in other slots. The masks will now automatically invalidate all rows that are not supposed to be included in the comparison by setting them to zero”. The masks applied in the CMA method eliminate potentially unnecessary computations (Laine – Paragraph [0051]-[0054]; [0068]). Therefore, any of the multiply-then-add, add-then-multiply, and/or compare-multiply-add techniques are sufficient to teach the generation of the bin mask, as recited in the claims.
Applicant Arguments additionally asserts that Kim is directed to a simple size comparison between two encrypted datasets, and thus, does not support or suggest statistical operations involving combinations of multiple variables. Examiner respectfully submits that Kim is primarily relied upon to teach the particular claim limitation “performing integer comparison operations on variable values corresponding to the combination”. Kim explicitly teaches a comparison primitive (Kim – Paragraph [0037]-[0046]) that one of ordinary skill in the art would find it obvious to replace or supplement Laine’s string comparison operations.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-17 are rejected under 35 USC 101 because the claimed invention is directed to abstract ideas without significantly more.
Claim 1 is directed to an electronic device capable of storing, generating, and processing various information. The recited device is an apparatus which falls within one of the statutory categories.
Claim 1 recites judicial exceptions in generating the bin mask, performing integer comparison operations on variable values, and generating number data with the bin mask and the homomorphic ciphertexts. These processes, under broadest reasonable interpretation, can be categorized as mental processes and mathematical concepts performable in the mind except for the recitation of generic computer components. That is, the recited limitations “generate … a bin mask corresponding to a combination of two or more different variables …”, “performing integer comparison operations on variable values corresponding to the combination”, and “generate number data … by using the bin mask and the stored plurality of variable data …” and are merely data gathering/processing with computer components recited at a high level of generality (electronic device, memory, processor). The recited limitation “store a plurality of homomorphic ciphertexts …” merely describes how to generally apply the concept of storing data in a generically stated computer environment and is nothing but insignificant extra-solution activity. Therefore, the claim, as a whole, represents an abstract idea as it only covers performance of the data gathering, mathematical operations, and storing processes except for the recitation of generic computer components.
These judicial exceptions are not integrated into a practical application. Additional elements of the claim include the aforementioned electronic device, memory, and processor. The hardware elements are recited at a high level of generality. Further elements include a plurality of homomorphic ciphertexts, generated number data which is homomorphic ciphertext, and an instruction to perform an operation on homomorphic ciphertexts. These are broadly stated data elements that do not substantially enhance or specify the performance of the judicial exceptions. Therefore, these additional elements do not serve to integrate the abstract ideas into a practical application because they do not serve to impose any meaningful limits on practicing the abstract ideas.
The claim does not incorporate the additional elements in a manner that is sufficient to amount to significantly more than the judicial exceptions. The additional elements, as stated above, are recited at a high level of generality—the claim language does not meaningfully connect the abstract idea/concept of generating a bin mask, performing integer comparisons, and generating number data to the operation of the electronic device as a whole, nor to the homomorphic ciphertext storing function. The broad recitation of “homomorphic ciphertexts” on/with which the claimed operations are to be performed is not, by itself, sufficient to amount to significantly more than the judicial exceptions. Therefore, nothing in the claim adds significantly more than the abstract ideas, and the claim is ineligible.
A similar rejection applies to corresponding method claim 9, which recites similar limitations to those of claim 1.
A similar rejection applies to corresponding computer readable medium claim 17, which recites steps similar to those of claims 1 and 9 and does not integrate the abstract ideas into a practical application.
Claims 2-8 and 10-16 are also rejected due to their respective dependence on claims 1 and 9.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-4, 9-12, and 17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Laine et al. (US 20180198601 A1), hereinafter Laine, in view of Kim et al. (US 20200136798 A1), hereinafter Kim.
Regarding Claim 1:
Laine teaches an electronic device, comprising: a memory configured to store at least one instruction (Laine – Paragraph [0075]: Some operations of the example methods may be described in the general context of executable instructions stored on computer-readable storage memory that is local and/or remote to a computer processing system, and implementations can include software applications, programs, functions, and the like), and store a plurality of homomorphic ciphertexts (Laine – Paragraph [0018]: In this example, homomorphic encrypted data is stored in the memory 104 as a homomorphic encrypted data in a dataset 106. The homomorphic encrypted data in the dataset 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. The encrypted bits in the dataset 106 can be denoted as R.sub.{1,1}, R.sub.{N,L}, in rows and columns of the encrypted bits); each homomorphic ciphertext of the plurality of homomorphic ciphertexts storing a plurality of variable data in an encrypted state (Laine – Paragraph [0018]: In this example, homomorphic encrypted data is stored in the memory 104 as a homomorphic encrypted data in a dataset 106. The homomorphic encrypted data in the dataset 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time); and a processor configured to execute the at least one instruction, wherein the processor is configured to: generate, by executing the at least one instruction (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102), a bin mask corresponding to a combination of two or more different variables of the stored plurality of variable data of each of the plurality of homomorphic ciphertexts, the bin mask classifying different variable data for each homomorphic ciphertext of the plurality of homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results); wherein the bin mask is generated … to derive statistical information from the plurality of homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results) wherein the bin mask coincides with a specific condition within the homomorphic ciphertexts (Laine – Paragraph [0054]: The CMA method is effective when l (i.e., the length of the strings) is short. In this case the multiplicative depth does not depend on the number of rows in the dataset, which makes this method particularly suitable for situations where level (1+┌log.sub.2 l┐) circuits can be computed with reasonable parameters. However, the computational complexity and the multiplicative depth quickly become very high when f grows. Another significant advantage of the CMA approach is that the signal of success comes in a much more useful form than in the CAM approach. For example, in the case of only one batch, if a match is found, the result of CMA is a ciphertext with a one (1) exactly in the slot(s) where the match occurred, and zero (0) elsewhere. Thus, the result of CMA can be used to perform conditional computations depending on whether a match was found or not. Furthermore, CMA always shows the exact number of matches that were found, which may not always be true for CAM, but will be when the features of hashing are implemented) and generate number data corresponding to the combination by using the bin mask and the stored plurality of variable data (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset); wherein the generated number data is homomorphic ciphertext (Laine – Paragraph [0029]: The matching data strings 114 can then be returned to the computing device 100 as the returned matching strings 206, which are encrypted).
Laine does not expressly teach in response to a received instruction to perform an operation on the plurality of homomorphic ciphertexts; by performing integer comparison operations on variable values corresponding to the variable combination to derive statistical information from the plurality of homomorphic ciphertexts.
However, Kim teaches in response to a received instruction (Kim – Paragraph [0021]: The one or more programs may include one or more computer executable instructions which may be configured to enable the computing apparatus 12 to perform operations according to an example embodiment when they are executed by the processor 14) to perform an operation on the plurality of homomorphic ciphertexts (Kim – Paragraph [0038]: In detail, the computing apparatus 12 may perform homomorphic evaluation of subtraction between the first real-number data and the second real-number data using the first ciphertext and the second ciphertext in an encrypted state); by performing integer comparison operations on variable values corresponding to the variable combination to derive statistical information from the plurality of homomorphic ciphertexts (Kim – Paragraphs [0037]: When the first ciphertext and the second ciphertext are acquired, the computing apparatus 12 generates a ciphertext for a result of comparison in size between the first real-number data and the second real-number data using homomorphic evaluation of the first ciphertext, the second ciphertext, and an approximation function for approximating a signum function (220); and Equation 2 – signum function to express comparison of number data of 2 ciphertexts; and Equation 3 – approximation function of the signum function; and Paragraph [0042]: The computing apparatus 12 according to an embodiment of the present disclosure may generate the ciphertext for the result of the comparison in size between the first real-number data and the second real-number data using the homomorphic evaluation algorithm of the above-described approximate homomorphic encryption algorithm (i.e., Eval(evk,f,c)) as shown in Equation 4 below: Eval(evk,sgn.sub.approx(x−y),Enc(pk,a),Enc(pk,b)).fwdarw.Enc(pk,sgn.sub.approx(a−b)) [Equation 4]; and Paragraph [0043]: where a is the first real-number data, b is the second real-number data, Enc(pk,a) is the first ciphertext, Enc(pk,b) is the second ciphertext, and Enc(pk,sgn.sub.approx(a−b) is a ciphertext for a result value obtained by applying a−b to sgn.sub.approx(x)).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine, further incorporating Kim to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Kim’s teaching to perform integer comparison operations on ciphertexts to derive some information from the ciphertexts while maintaining their encrypted state into Laine’s device that generates bin masks over homomorphically encrypted data sets and performs mathematical operations on the data sets. Kim provides an efficient integer comparison primitive that could be applied in combination with the teachings of Laine to replace or supplement the comparison operations performed therein.
Regarding Claim 2:
The combination of Laine and Kim teaches the electronic device of claim 1.
Laine further teaches wherein each of the plurality of homomorphic ciphertexts comprises a plurality of slots, and each of the plurality of slots comprises one variable data (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results).
The motivation to combine the arts is the same as that of Claim 1.
Regarding Claim 3:
The combination of Laine and Kim teaches the electronic device of claim 1.
Laine further teaches wherein the processor is further configured to (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102) generate a plurality of bin masks, each of the plurality of bin masks corresponding to each of the plurality of variable data comprised in each of the plurality of the homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results; and Paragraph [0104]: The method further comprising representing the dataset bits and the query bits of the encrypted query string in an integer base larger than two (2). The method further comprising applying a randomization algorithm effective to mask the homomorphic encrypted data that may otherwise be exposed by the computing the sum and the multiplying operations. The method further comprising querying the dataset of the homomorphic encrypted data for multiple encrypted query strings; and determining multiple matching strings of the multiple encrypted query strings in the dataset. The method further comprising reducing a size of the encrypted query string prior to the addition and multiplication operations that provide the one or more matching strings of the encrypted query string in the dataset), wherein each of the plurality of bin masks comprises a plurality of slots, wherein each of the plurality of slots comprises data on whether one variable value is present (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results), select at least one bin mask corresponding to the combination from among the plurality of generated bin masks (Laine – Paragraph [0068]: For example, given the batch count is B, then the party that encrypts the dataset includes with it B additional ciphertexts that contain masks for the batches, invalidating (i.e., setting to zero) all locations that are empty in the hash table. Similarly, the party that submits the query includes an extra ciphertext that encrypts a mask that invalidates all locations that are empty in the query hash table), and generate the number data with the combination by multiplication between the at least one bin mask (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset).
Kim further teaches the plurality of the homomorphic ciphertexts (Kim – Paragraph [0038]: In detail, the computing apparatus 12 may perform homomorphic evaluation of subtraction between the first real-number data and the second real-number data using the first ciphertext and the second ciphertext in an encrypted state).
The motivation to combine the arts is the same as that of Claim 1.
Regarding Claim 4:
The combination of Laine and Kim teaches the electronic device of claim 1.
Laine further teaches wherein the processor is further configured to (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102) generate a plurality of bin masks, each of the plurality of bin masks corresponding to each of the homomorphic ciphertexts (Laine – Paragraph [0068]: For example, given the batch count is B, then the party that encrypts the dataset includes with it B additional ciphertexts that contain masks for the batches, invalidating (i.e., setting to zero) all locations that are empty in the hash table. Similarly, the party that submits the query includes an extra ciphertext that encrypts a mask that invalidates all locations that are empty in the query hash table) wherein each of the plurality of bin masks comprises a plurality of slots, and each of the plurality of slots comprises a plurality of sub slots comprising data on whether one variable value is present (Laine – Paragraph [0068]: Mask(H(D)).sub.i is a batched ciphertext that has a one (1) in each slot that corresponds to a non-zero hash table bin in H(D.sup.(i)), and a zero (0) in the rest of the slots, as well as Mask(H(X)) is a batched ciphertext that has a one (1) in the slots that correspond to non-empty bins, and a zero (0) in other slots. The masks will now automatically invalidate all rows that are not supposed to be included in the comparison by setting them to zero), and generate number data with the combination by using the sub slots in at least one of the plurality of bin masks which correspond to the combination (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset).
The motivation to combine the arts is the same as that of Claim 1.
Regarding Claim 9:
Laine teaches a method of processing ciphertext on a homomorphic ciphertext, the method comprising (Laine – Paragraph [0006]: The string matching application is also implemented to apply a randomization algorithm effective to mask the homomorphic encrypted data that may otherwise be exposed by the computed sum and the multiply operations. Generally, the result of a homomorphic computation might reveal extra information about the dataset, beyond simply whether a match was found. Further, the string matching application can be implemented to simultaneously query the dataset of the homomorphic encrypted data for multiple encrypted query strings, and determine multiple matching strings of the multiple encrypted query strings in the dataset): storing a plurality of homomorphic ciphertexts (Laine – Paragraph [0018]: In this example, homomorphic encrypted data is stored in the memory 104 as a homomorphic encrypted data in a dataset 106. The homomorphic encrypted data in the dataset 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. The encrypted bits in the dataset 106 can be denoted as R.sub.{1,1}, R.sub.{N,L}, in rows and columns of the encrypted bits), each homomorphic ciphertext of the plurality of homomorphic ciphertexts stores a plurality of variable data in an encrypted state (Laine – Paragraph [0018]: In this example, homomorphic encrypted data is stored in the memory 104 as a homomorphic encrypted data in a dataset 106. The homomorphic encrypted data in the dataset 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time); generating a bin mask corresponding to a combination of two or more different variables of the stored plurality of variable data of each of the plurality of homomorphic ciphertexts, the bin mask classifying different variable data for each homomorphic ciphertext of the plurality of homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results); wherein the bin mask is generated … to derive statistical information from the plurality of homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results); wherein the bin mask coincides with a specific condition within the homomorphic ciphertexts (Laine – Paragraph [0054]: The CMA method is effective when l (i.e., the length of the strings) is short. In this case the multiplicative depth does not depend on the number of rows in the dataset, which makes this method particularly suitable for situations where level (1+┌log.sub.2 l┐) circuits can be computed with reasonable parameters. However, the computational complexity and the multiplicative depth quickly become very high when f grows. Another significant advantage of the CMA approach is that the signal of success comes in a much more useful form than in the CAM approach. For example, in the case of only one batch, if a match is found, the result of CMA is a ciphertext with a one (1) exactly in the slot(s) where the match occurred, and zero (0) elsewhere. Thus, the result of CMA can be used to perform conditional computations depending on whether a match was found or not. Furthermore, CMA always shows the exact number of matches that were found, which may not always be true for CAM, but will be when the features of hashing are implemented); generating an encrypted number data corresponding to the combination by using the generated bin mask and the stored plurality of variable data (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset) wherein the generated encrypted number data is homomorphic ciphertext (Laine – Paragraph [0029]: The matching data strings 114 can then be returned to the computing device 100 as the returned matching strings 206, which are encrypted) and outputting the encrypted number data (Laine – Paragraph [0020]: In aspects of string matching in encrypted data, the string matching application 112 can receive the encrypted query string 108 as a query of the homomorphic encrypted dataset 106. The string matching application 112 can then apply one or more of the various algorithms to perform addition and multiplication operations, and determine whether there are matching data strings 114 of the encrypted query string in the dataset 106, where the matching data strings 114 are an output 116 of the string matching application. In an implementation, a multiply-then-add algorithm 118 of the string matching application 112 is implemented to compute, for each row of the dataset 106, a product over some function of dataset bits and query bits for a row result, such as denoted by 1−(query.sub.bit−dataset.sub.bit).sup.2. The multiply-then-add algorithm 118 then adds the respective row results of the computed rows to determine a total number of the matching data strings 114. In another implementation, an add-then-multiply algorithm 120 of the string matching application 112 is implemented to compute, for each row of the dataset 106, a sum of some function of dataset bits and query bits for a row result. The add-then-multiply algorithm 120 then multiplies the respective row results of the computed rows to determine the matching data strings 114).
Laine does not expressly teach receiving an instruction to perform an operation on the plurality of homomorphic ciphertexts; by performing integer comparison operations on variable values corresponding to the combination to derive statistical information from the plurality of homomorphic ciphertexts.
However, Kim teaches receiving an instruction (Kim – Paragraph [0021]: The one or more programs may include one or more computer executable instructions which may be configured to enable the computing apparatus 12 to perform operations according to an example embodiment when they are executed by the processor 14) to perform an operation on the plurality of homomorphic ciphertexts (Kim – Paragraph [0038]: In detail, the computing apparatus 12 may perform homomorphic evaluation of subtraction between the first real-number data and the second real-number data using the first ciphertext and the second ciphertext in an encrypted state), by performing integer comparison operations on variable values corresponding to the combination to derive statistical information from the plurality of homomorphic ciphertexts (Kim – Paragraphs [0037]: When the first ciphertext and the second ciphertext are acquired, the computing apparatus 12 generates a ciphertext for a result of comparison in size between the first real-number data and the second real-number data using homomorphic evaluation of the first ciphertext, the second ciphertext, and an approximation function for approximating a signum function (220); and Equation 2 – signum function to express comparison of number data of 2 ciphertexts; and Equation 3 – approximation function of the signum function; and Paragraph [0042]: The computing apparatus 12 according to an embodiment of the present disclosure may generate the ciphertext for the result of the comparison in size between the first real-number data and the second real-number data using the homomorphic evaluation algorithm of the above-described approximate homomorphic encryption algorithm (i.e., Eval(evk,f,c)) as shown in Equation 4 below: Eval(evk,sgn.sub.approx(x−y),Enc(pk,a),Enc(pk,b)).fwdarw.Enc(pk,sgn.sub.approx(a−b)) [Equation 4]; and Paragraph [0043]: where a is the first real-number data, b is the second real-number data, Enc(pk,a) is the first ciphertext, Enc(pk,b) is the second ciphertext, and Enc(pk,sgn.sub.approx(a−b) is a ciphertext for a result value obtained by applying a−b to sgn.sub.approx(x)).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine, further incorporating Kim to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Kim’s teaching to perform integer comparison operations on ciphertexts to derive some information from the ciphertexts while maintaining their encrypted state into Laine’s method for generating bin masks over homomorphically encrypted datasets and performing mathematical operations on the datasets. Kim provides an efficient integer comparison primitive that could be applied in combination with the teachings of Laine to replace or supplement the comparison operations performed therein.
Regarding Claim 10:
The combination of Laine and Kim teaches the method of claim 9.
Laine further teaches wherein each of the plurality of homomorphic ciphertexts comprises a plurality of slots, and each of the plurality of slots comprises one variable data (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results).
The motivation to combine the arts is the same as that of Claim 9.
Regarding Claim 11:
The combination of Laine and Kim teaches the method of claim 9.
Laine further teaches further comprising generating a plurality of bin masks, each of the plurality of bin masks corresponding to each of the plurality of variable data comprised in each of the plurality of the homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results), wherein each of the plurality of bin masks comprises a plurality of slots, wherein each of the plurality of slots comprises data on whether one variable value is present (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results), wherein the generating the encrypted number data comprises selecting at least one bin mask corresponding to the combination from among the plurality of generated bin masks (Laine – Paragraph [0068]: For example, given the batch count is B, then the party that encrypts the dataset includes with it B additional ciphertexts that contain masks for the batches, invalidating (i.e., setting to zero) all locations that are empty in the hash table. Similarly, the party that submits the query includes an extra ciphertext that encrypts a mask that invalidates all locations that are empty in the query hash table), and using multiplication between the at least one selected bin mask to generate the encrypted number data with the combination (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset).
The motivation to combine the arts is the same as that of Claim 9.
Regarding Claim 12:
The combination of Laine and Kim teaches the method of claim 9.
Laine further teaches further comprising generating a plurality of bin masks, each of the plurality of bin masks corresponding to each of the homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results), wherein each of the plurality of bin masks comprises a plurality of slots, and each of the plurality of slots comprises a plurality of sub slots comprising data on whether one variable value is present (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results), wherein the generating the encrypted number data comprises using the sub slots in at least one of the plurality of bin masks corresponding to the combination to generate the encrypted number data with the combination (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset).
The motivation to combine the arts is the same as that of Claim 9.
Regarding Claim 17:
Laine teaches a non-transitory computer readable recording medium (Laine – Paragraph [0075]: Some operations of the example methods may be described in the general context of executable instructions stored on computer-readable storage memory that is local and/or remote to a computer processing system, and implementations can include software applications, programs, functions, and the like) comprising a program for executing a ciphertext processing method, the method comprising: (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102): storing a plurality of homomorphic ciphertexts (Laine – Paragraph [0018]: In this example, homomorphic encrypted data is stored in the memory 104 as a homomorphic encrypted data in a dataset 106. The homomorphic encrypted data in the dataset 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time. The encrypted bits in the dataset 106 can be denoted as R.sub.{1,1}, R.sub.{N,L}, in rows and columns of the encrypted bits), each homomorphic ciphertext of the plurality of homomorphic ciphertexts stores a plurality of variable data in an encrypted state (Laine – Paragraph [0018]: In this example, homomorphic encrypted data is stored in the memory 104 as a homomorphic encrypted data in a dataset 106. The homomorphic encrypted data in the dataset 106 can include N (bit) strings of some length L, all of which are encrypted using homomorphic encryption to encrypt one bit of the data at a time); generating a bin mask corresponding to combination of two or more different variables of the stored plurality of variable data of each of the plurality of homomorphic ciphertexts, the bin mask classifying different variable data for each homomorphic ciphertext of the plurality of homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results); wherein the bin mask is generated … to derive statistical information from the plurality of homomorphic ciphertexts (Laine – Paragraph [0024]: A randomization algorithm 124 of the string matching application 112 implements an efficient randomization technique that masks the extra information in a cryptographically secure way. The randomization algorithm 124 can be applied effective to mask the homomorphic encrypted data in the dataset 106 that may otherwise be exposed by the addition and multiplication operations of the add-then-multiply algorithm 120. The results of the add-then-multiply method gives a zero (0) if a match was found, and some non-zero value if there was no match. However, this non-zero value can reveal information about the dataset 106, and the randomization technique can be utilized to randomize it by multiplying by a random non-zero number (modulo some integer t). This randomization keeps the zero (0) a zero (0), and hides all information leak from non-zero results); wherein the bin mask coincides with a specific condition within the homomorphic ciphertexts (Laine – Paragraph [0054]: The CMA method is effective when l (i.e., the length of the strings) is short. In this case the multiplicative depth does not depend on the number of rows in the dataset, which makes this method particularly suitable for situations where level (1+┌log.sub.2 l┐) circuits can be computed with reasonable parameters. However, the computational complexity and the multiplicative depth quickly become very high when f grows. Another significant advantage of the CMA approach is that the signal of success comes in a much more useful form than in the CAM approach. For example, in the case of only one batch, if a match is found, the result of CMA is a ciphertext with a one (1) exactly in the slot(s) where the match occurred, and zero (0) elsewhere. Thus, the result of CMA can be used to perform conditional computations depending on whether a match was found or not. Furthermore, CMA always shows the exact number of matches that were found, which may not always be true for CAM, but will be when the features of hashing are implemented); generating an encrypted number data corresponding to the variable combination by using the bin mask (Laine – Paragraph [0005]: String matching in encrypted data is described. In aspects, a computing device includes memory that stores homomorphic encrypted data as a dataset. A string matching application is implemented that can receive an encrypted query string as a query of the homomorphic encrypted data. The string matching application can then apply one or more algorithms to perform addition and multiplication operations, and determine whether there are matching strings of the encrypted query string in the dataset); wherein the generated encrypted number data is homomorphic ciphertext (Laine – Paragraph [0029]: The matching data strings 114 can then be returned to the computing device 100 as the returned matching strings 206, which are encrypted) and outputting the encrypted number data (Laine – Paragraph [0020]: In aspects of string matching in encrypted data, the string matching application 112 can receive the encrypted query string 108 as a query of the homomorphic encrypted dataset 106. The string matching application 112 can then apply one or more of the various algorithms to perform addition and multiplication operations, and determine whether there are matching data strings 114 of the encrypted query string in the dataset 106, where the matching data strings 114 are an output 116 of the string matching application. In an implementation, a multiply-then-add algorithm 118 of the string matching application 112 is implemented to compute, for each row of the dataset 106, a product over some function of dataset bits and query bits for a row result, such as denoted by 1−(query.sub.bit−dataset.sub.bit).sup.2. The multiply-then-add algorithm 118 then adds the respective row results of the computed rows to determine a total number of the matching data strings 114. In another implementation, an add-then-multiply algorithm 120 of the string matching application 112 is implemented to compute, for each row of the dataset 106, a sum of some function of dataset bits and query bits for a row result. The add-then-multiply algorithm 120 then multiplies the respective row results of the computed rows to determine the matching data strings 114).
Laine does not expressly teach receiving an instruction to perform an operation on the plurality of homomorphic ciphertexts; by performing integer comparison operations on variable values corresponding to the variable combination to derive statistical information from the plurality of homomorphic ciphertexts.
However, Kim teaches receiving an instruction (Kim – Paragraph [0021]: The one or more programs may include one or more computer executable instructions which may be configured to enable the computing apparatus 12 to perform operations according to an example embodiment when they are executed by the processor 14) to perform an operation on the plurality of homomorphic ciphertexts (Kim – Paragraph [0038]: In detail, the computing apparatus 12 may perform homomorphic evaluation of subtraction between the first real-number data and the second real-number data using the first ciphertext and the second ciphertext in an encrypted state), by performing integer comparison operations on variable values corresponding to the variable combination to derive statistical information from the plurality of homomorphic ciphertexts (Kim – Paragraphs [0037]: When the first ciphertext and the second ciphertext are acquired, the computing apparatus 12 generates a ciphertext for a result of comparison in size between the first real-number data and the second real-number data using homomorphic evaluation of the first ciphertext, the second ciphertext, and an approximation function for approximating a signum function (220); and Equation 2 – signum function to express comparison of number data of 2 ciphertexts; and Equation 3 – approximation function of the signum function; and Paragraph [0042]: The computing apparatus 12 according to an embodiment of the present disclosure may generate the ciphertext for the result of the comparison in size between the first real-number data and the second real-number data using the homomorphic evaluation algorithm of the above-described approximate homomorphic encryption algorithm (i.e., Eval(evk,f,c)) as shown in Equation 4 below: Eval(evk,sgn.sub.approx(x−y),Enc(pk,a),Enc(pk,b)).fwdarw.Enc(pk,sgn.sub.approx(a−b)) [Equation 4]; and Paragraph [0043]: where a is the first real-number data, b is the second real-number data, Enc(pk,a) is the first ciphertext, Enc(pk,b) is the second ciphertext, and Enc(pk,sgn.sub.approx(a−b) is a ciphertext for a result value obtained by applying a−b to sgn.sub.approx(x)).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine, further incorporating Kim to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Kim’s teaching to perform integer comparison operations on ciphertexts to derive some information from the ciphertexts while maintaining their encrypted state into Laine’s method for generating bin masks over homomorphically encrypted datasets and performing mathematical operations on the datasets. Kim provides an efficient integer comparison primitive that could be applied in combination with the teachings of Laine to replace or supplement the comparison operations performed therein.
Claim(s) 5 and 13 is/are rejected under 35 U.S.C. 103 as being unpatentable over Laine, in view of Kim and Masters et al. (US 11239996 B2), hereinafter Masters.
Regarding Claim 5:
The combination of Laine and Kim teaches the electronic device of Claim 4.
The combination of Laine and Kim does not expressly teach wherein the plurality of sub slots is configured to be disposed in one slot with a preset bit distance.
However, Masters teaches wherein the plurality of sub slots is configured to be disposed in one slot with a preset bit distance (Masters – Col. 11, Lines 6-17: In one aspect, computing unit A 410 may encode selected or relevant data into plaintext space so as to encrypt and perform a homomorphic encryption weighted lookup. First, a database such as, for example, database 470 may include N number of rows and M number of columns, where N and M are positive integers. Each entry in database 470 may be a “small” datum, such as a fixed-length integer and denoted by the variable “l” which is the number of bits of the fixed-length integer (and not the integer itself) required for each datum, so that all entries in database 470 may be uniformized as members of {0, 1, 2, . . . , 2.sup.l−1} (e.g., values where l is equal to 32)).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine and Kim, further incorporating Masters to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Masters’s teaching to organize encrypted data in uniform, fixed-length spaces into Laine and Kim’s device that generates masks for finding common data in encrypted data sets in order to perform computations on the data. This combined functionality would enhance the data organization, and thus the computational efficiency of the device.
Regarding Claim 13:
The combination of Laine and Kim teaches the method of Claim 12.
The combination of Laine and Kim does not expressly teach wherein the plurality of sub slots is configured to be disposed in one slot with a preset bit distance.
However, Masters teaches wherein the plurality of sub slots is configured to be disposed in one slot with a preset bit distance (Masters – Col. 11, Lines 6-17: In one aspect, computing unit A 410 may encode selected or relevant data into plaintext space so as to encrypt and perform a homomorphic encryption weighted lookup. First, a database such as, for example, database 470 may include N number of rows and M number of columns, where N and M are positive integers. Each entry in database 470 may be a “small” datum, such as a fixed-length integer and denoted by the variable “l” which is the number of bits of the fixed-length integer (and not the integer itself) required for each datum, so that all entries in database 470 may be uniformized as members of {0, 1, 2, . . . , 2.sup.l−1} (e.g., values where l is equal to 32)).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine and Kim, further incorporating Masters to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Masters’s teaching to organize encrypted data in uniform, fixed-length spaces into Laine and Kim’s combined method for generating masks to find common data in encrypted data sets in order to perform computations on the data. This combined functionality would enhance the data organization, and thus the computational efficiency of the method.
Claim(s) 6, 7, 14 and 15 is/are rejected under 35 U.S.C. 103 as being unpatentable over Laine, in view of Kim and Blatt et al. (US 62939723), hereinafter Blatt.
Regarding Claim 6:
The combination of Laine and Kim teaches the electronic device of claim 1.
Laine further teaches wherein the processor is configured to (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102).
The combination of Laine and Kim does not expressly teach join a first homomorphic ciphertext and a second homomorphic ciphertext into one homomorphic ciphertext, wherein the first homomorphic ciphertext and the second homomorphic ciphertext each comprise a plurality of data on a same feature.
However, Blatt teaches join a first homomorphic ciphertext and a second homomorphic ciphertext into one homomorphic ciphertext, wherein the first homomorphic ciphertext and the second homomorphic ciphertext each comprise a plurality of data on a same feature (Blatt – P. 1: Embodiments of the invention provide devices, systems, and methods for linking two or more encrypted datasets based on common identifiers (IDs) (or their hashes or other derivative thereof). The IDs (or their hashes or derivatives) may also be encrypted ... Embodiments of the invention discussed here are tailored for fully homomorphic encryption (FHE) ...).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine and Kim, further incorporating Blatt to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Blatt’s teaching to merge two homomorphic ciphertexts based on common data into Laine and Kim’s device that generates masks for finding common data in encrypted data sets in order to perform computations on the data. This combined functionality would facilitate the performance of computational operations on encrypted data in the device.
Regarding Claim 7:
The combination of Laine, Kim, and Blatt teaches the electronic device of claim 6.
Laine further teaches wherein the processor is configured to (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102).
Blatt further teaches use a first position data in the first homomorphic ciphertext and a second position data in the second homomorphic ciphertext on common data in the first homomorphic ciphertext and the second homomorphic ciphertext (Blatt – P. 3-4: 1.5 – Linking the Hashes to Encrypted Features: … 1. Perform a component-wise computation, and sum up each encrypted feature over all common IDs. 2. Perform a component-wise computation, and sum up all features for each common ID (as in linear or logistic regression inference)) to join the first homomorphic ciphertext and the second homomorphic ciphertext into one homomorphic ciphertext (Blatt – P. 4: ... the linking result is encrypted).
The motivation to combine the arts is the same as that of Claim 6.
Regarding Claim 14:
The combination of Laine and Kim teaches the method of claim 9.
The combination of Laine and Kim does not expressly teach further comprising: joining a first homomorphic ciphertext and a second homomorphic ciphertext into one homomorphic ciphertext, wherein the first homomorphic ciphertext and the second homomorphic ciphertext each comprise a plurality of data on a same feature.
However, Blatt teaches further comprising: joining a first homomorphic ciphertext and a second homomorphic ciphertext into one homomorphic ciphertext, wherein the first homomorphic ciphertext and the second homomorphic ciphertext each comprise a plurality of data on a same feature (Blatt – P. 1: Embodiments of the invention provide devices, systems, and methods for linking two or more encrypted datasets based on common identifiers (IDs) (or their hashes or other derivative thereof). The IDs (or their hashes or derivatives) may also be encrypted ... Embodiments of the invention discussed here are tailored for fully homomorphic encryption (FHE) ...).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine and Kim, further incorporating Blatt to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Blatt’s teaching to merge two homomorphic ciphertexts based on common data into Laine and Kim’s method for generating masks to find common data in encrypted data sets in order to perform computations on the data. This combined functionality would facilitate the performance of computational operations on encrypted data in the method.
Regarding Claim 15:
The combination of Laine, Kim, and Blatt teaches the method of claim 14.
Blatt further teaches wherein the joining comprises using a first position data in the first homomorphic ciphertext and a second position data in the second homomorphic ciphertext on common data in the first homomorphic ciphertext and the second homomorphic ciphertext (Blatt – P. 3-4: 1.5 – Linking the Hashes to Encrypted Features: … 1. Perform a component-wise computation, and sum up each encrypted feature over all common IDs. 2. Perform a component-wise computation, and sum up all features for each common ID (as in linear or logistic regression inference)), and joining the first homomorphic ciphertext and the second homomorphic ciphertext into one homomorphic ciphertext (Blatt – P. 4: ... the linking result is encrypted).
The motivation to combine the arts is the same as that of Claim 14.
Claim(s) 8 and 16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Laine, in view of Kim, Blatt, and Hayasaka et al. (US 20210067317 A1), hereinafter Hayasaka.
Regarding Claim 8:
The combination of Laine, Kim, and Blatt teaches the electronic device of claim 7.
Laine further teaches wherein the processor is configured to (Laine – Paragraph [0019]: The computing device 100 implements the string matching application 112 that can include various algorithms to implement the techniques of string matching in encrypted data, as described herein. The application and algorithms can be implemented as software applications or modules, such as computer-executable software instructions that are executable with the processing system 102).
Blatt further teaches compare, based on the plurality of data comprised in the first and second homomorphic ciphertexts (Blatt – P. 2: 1.1 - Matching Two IDs: A Subroutine for Linking: … 2. Multiply the inner product results for all digits using the binary tree multiplication technique. If the result is 1, two IDs match. If the result is 0, the IDs do not match …); and position data in the first and second homomorphic ciphertexts on the encrypted data being input (Blatt – P. 2: 1.1 - Matching Two IDs: A Subroutine for Linking: … 2. Multiply the inner product results for all digits using the binary tree multiplication technique. If the result is 1, two IDs match. If the result is 0, the IDs do not match …), encrypted data on the first homomorphic ciphertext with encrypted data on the second homomorphic ciphertext (Blatt – P. 1: Embodiments of the invention provide devices, systems, and methods for linking two or more encrypted datasets based on common identifiers (IDs) (or their hashes or other derivative thereof). The IDs (or their hashes or derivatives) may also be encrypted ... Embodiments of the invention discussed here are tailored for fully homomorphic encryption (FHE) ...), and check the first position data and the second position data which comprise common data between the two homomorphic ciphertexts (Blatt – P. 2: 1.1 - Matching Two IDs: A Subroutine for Linking: … 2. Multiply the inner product results for all digits using the binary tree multiplication technique. If the result is 1, two IDs match. If the result is 0, the IDs do not match …).
The combination of Laine, Kim, and Blatt does not expressly teach wherein the plurality of data of each ciphertext is encrypted with a one-direction encryption scheme using a preset common key.
However, Hayasaka teaches wherein the plurality of data of each ciphertext is encrypted with a one-direction encryption scheme using a preset common key (Hayasaka – Paragraph [0101]: As shown in FIG. 2, at step 202, process 200 may include establishing a secret key. For example, transaction service provider system 102 may communicate with user device 106 and/or user device 108 to establish a secret key for encrypting messages and/or data communicated between user device 106 and user device 108. In some non-limiting embodiments or aspects, the secret key established between user device 106 and user device 108 may be a symmetric encryption key, a pair of asymmetric keys, and/or the like).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Laine, Kim, and Blatt, further incorporating Hayasaka to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Hayasaka’s teaching of using a common key to perform one-way encryption of data into Laine, Kim, and Blatt’s combined device for generating masks to find common data in encrypted data sets in order to perform computations on the data. This combined functionality would further enhance the device by providing a means to conceal sensitive data for secure processing.
Regarding Claim 16:
The combination of Laine, Kim, and Blatt teaches the method of claim 15.
Blatt further teaches wherein the joining comprises comparing, based on … the plurality of data comprised in the first and second homomorphic ciphertexts (Blatt – P. 2: 1.1 - Matching Two IDs: A Subroutine for Linking: … 2. Multiply the inner product results for all digits using the binary tree multiplication technique. If the result is 1, two IDs match. If the result is 0, the IDs do not match …); and position data in the first and second homomorphic ciphertexts on the encrypted data being input (Blatt – P. 2: 1.1 - Matching Two IDs: A Subroutine for Linking: … 2. Multiply the inner product results for all digits using the binary tree multiplication technique. If the result is 1, two IDs match. If the result is 0, the IDs do not match …), encrypted data on the first homomorphic ciphertext with encrypted data on the second homomorphic ciphertext (Blatt – P. 1: Embodiments of the invention provide devices, systems, and methods for linking two or more encrypted datasets based on common identifiers (IDs) (or their hashes or other derivative thereof). The IDs (or their hashes or derivatives) may also be encrypted ... Embodiments of the invention discussed here are tailored for fully homomorphic encryption (FHE) ...), and checking the first position data and the second position data which comprise common data between the two homomorphic ciphertexts (Blatt – P. 2: 1.1 - Matching Two IDs: A Subroutine for Linking: … 2. Multiply the inner product results for all digits using the binary tree multiplication technique. If the result is 1, two IDs match. If the result is 0, the IDs do not match …).
The combination of Laine, Kim, and Blatt does not expressly teach data encrypted with a one-direction encryption scheme using a preset common key with respect to each of the plurality of data.
However, Hayasaka teaches data encrypted with a one-direction encryption scheme using a preset common key with respect to each of the plurality of data (Hayasaka – Paragraph [0101]: As shown in FIG. 2, at step 202, process 200 may include establishing a secret key. For example, transaction service provider system 102 may communicate with user device 106 and/or user device 108 to establish a secret key for encrypting messages and/or data communicated between user device 106 and user device 108. In some non-limiting embodiments or aspects, the secret key established between user device 106 and user device 108 may be a symmetric encryption key, a pair of asymmetric keys, and/or the like).
It would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to modify Kim and Blatt, further incorporating Hayasaka to arrive at the conclusion of the claimed invention. One would be motivated to incorporate Hayasaka’s teaching of using a common key to perform one-way encryption of data into Kim and Blatt’s combined method for generating masks to find common data in encrypted data sets in order to perform computations on the data. This combined functionality would further enhance the method by providing a means to conceal sensitive data for secure processing.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Lu et al. (Lu, W., Kawasaki, S., & Sakuma, J. (2016). Using fully homomorphic encryption for statistical analysis of categorical, ordinal and Numerical Data. Proceedings 2017 Network and Distributed System Security Symposium. https://doi.org/http://dx.doi.org/10.14722/ndss.2017.23119) teaches techniques for performing statistical calculations on homomorphic ciphertexts, including evaluations of contingency tables representing overlaps of multiple conditions in at least two datasets
Kelly et al. (US 10097351 B1) teaches generation of a binary mask corresponding to a condition within an encrypted dataset, including homomorphically encrypted data
Hackenjos et al. (US 20200034547 A1) teaches bucketization of data prior to encryption in order to associate user-specified coinciding conditions for stored, encrypted data
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NICHOLAS JOSEPH DILUZIO whose telephone number is (703)756-1229. The examiner can normally be reached Mon - Fri -- 7:30 AM - 5 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Yin-Chen Shaw can be reached at 571-272-8878. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/NICHOLAS JOSEPH DILUZIO/Examiner, Art Unit 2498
/YIN CHEN SHAW/Supervisory Patent Examiner, Art Unit 2498
Prosecution Insights