DETAILED ACTION
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 .
Status of Claims
The following is a Final Office Action in response to applicant’s filing on August 06, 2026. Claims 1-20 are pending, of which claims 1, 9 and 17 are in independent form.
Response to Amendment
The Amendment filed on August 06, 2026 has been entered. Claims 1, 2, 9, 10, 17 and 18 were amended. As a result, claims 1-20 are pending, of which claims 1, 9 and 17 are in independent form.
Applicant’s amendments to the Specification, obviate the objection. Therefore, the specification objection is withdrawn.
Applicant’s amendments to the drawing obviate the objection, therefore the drawing objection is withdrawn.
Applicant’s amendments regarding claims 1-20 obviate the claim rejection, therefore the claim rejection under 35 USC § 112(b) is withdrawn.
Response to Arguments
Applicant's arguments filed on August 06, 2026 have been fully considered but they are not persuasive.
On pages 8-9 of remarks, Applicant argues that “CEBERE fails to disclose or suggest the claimed "splitting" as recited in the amended claim 1 “splitting, by the one or more processors, the converted number into a shard index and a bucket identifier;”. The examiner disagrees.
In view of amended claim 1, the Examiner relies on Laine for the newly recited conversion, splitting, encrypted-query, transmission, and encrypted-result limitations.
Laine represents a database index i within [0, n-1], i.e.,[0,n), and encrypts the index to generate a client query, see paragraph [0036]. Laine further teaches selectable database parameters, including using the next power of two and selecting N as 2048 or 4096 based on security and performance considerations, see Laine paragraphs [0040] and [0046].
Laine also teaches functionally splitting a global index into a database portion and a local position. For example, global index 2050 in a 4096 element database is represented by the second 2048 entry portion and local index 2, see paragraph [0047]. The examiner maps the database portion to the claimed shared index and the local position to the bucket identifier.
Further, and encrypted PIR query is generated using a selected bucket j and the index idx_j within that bucket, see paragraph [0076] and table 5. The client encrypts and sends the query to the server, see paragraphs [0024], [0036], and [0080]. The server, further returns multiple encrypted ciphertexts or bucket responses to the client, see paragraphs [0044], [0054], and [0076].
Accordingly, Laine teaches using a range-limited database index, dividing that index into portion and local-position components, generating and transmitting an encrypted query using these components, and receiving encrypted server results. The fact that Laine uses “database portion”, “bucket”, and “index” does not distinguish the claimed functionality. Therefore, the rejection is maintained.
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.
Claims 1-6, 8-14, and 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over Williams et al. (US 2018/0212751 A1), hereinafter Williams in view of Laine et al. (US 2019/0325082 A1), hereinafter Laine.
Regarding claim 1, Williams discloses a computer-implemented method, comprising:
obtaining, by one or more processors, a server encrypted identifier (Williams, Para. 0028, when data source 322 1-322 N includes an encrypted “social security number” field, the social security numbers are all encrypted, as opposed to some social security numbers being encrypted and others unencrypted. Data stored in and/or retrieved from target data source 322 1-322 N can be encrypted and/or decrypted as described in relation to FIG. 1.);
generating, by the one or more processors and using a hash function on the server encrypted identifier, an unsigned integer (Williams, Para. 0034, the keyed hash function and term generation function can be used to divide data in target data source 322 1-322 N, so the correct records in target data source 322 1-322 N are mapped to the correct encrypted query piece, so the operation can be conducted in the right way) and (Williams, Para. 0036, each of one or more servers 320 1-320 N can extract a set of term components {T} from target data source 322 1-322 N using the term generation function);
Williams does not explicitly disclose converting, by the one or more processors, the unsigned integer into a converted number within a specified range of [0, n), wherein n is a tunable parameter;
splitting, by the one or more processors, the converted number into a shard index and a bucket identifier;
generating, by the one or more processors, a client encrypted a query using the shard index and the bucket identifier;
transmitting, by the one or more processors, the client encrypted query to a server; and
receiving, by the one or more processors and from the server, a set of server encrypted results in response to submission of the client encrypted query.
However, Laine teaches converting, by the one or more processors, the unsigned integer into a converted number within a specified range of [0, n), wherein n is a tunable parameter (Laine, Para. 0036, a client that wishes to retrieve the ith element from the server's database using disclosed embodiments generates an FV plaintext that encodes the ith index. The client does so by representing i∈[0,n−1] as the monomial xi∈Rt) and (Laine, Para. 0040, in cases where n is not a power of 2, the next power of 2 may be used, and the first n output ciphertexts as the client's query) and (Laine, Para. 0046, recommended security parameters set N to 2048 or 4096. Larger values of N improve security but reduces performance. In various examples, databases may have more than N elements);
splitting, by the one or more processors, the converted number into a shard index and a bucket identifier (Laine, Para. 0047, as an example, if N is 2048, the database has 4096 elements, and the client wishes to get the element at index 2050, the client sends two ciphertexts: the first encrypts 0 and the second encrypts x2. The server expands both ciphertexts into two 2048-entry vectors and concatenates them to get a 4096-entry vector where the entry at index 2050 encrypts 1, and all entries encrypt 0) and (Laine, Para. 0076);
generating, by the one or more processors, a client encrypted a query using the shard index and the bucket identifier (Laine, Para. 0080, for example, the query may be a vector with a value of 1 for each element that is to be retrieved and 0 otherwise. This vector may be encrypted by a client. The server may use this encrypted vector without having to decrypt the vector);
transmitting, by the one or more processors, the client encrypted query to a server (Laine, Para. 0036, the client then encrypts this plaintext to obtain query=Enc(xi), which is then sent to the server); and
receiving, by the one or more processors and from the server, a set of server encrypted results in response to submission of the client encrypted query (Laine, Para. 0036, these ciphertexts may be sent by the server to the client. The client may then decrypt all of the ciphertexts and combines the results to obtain Enc(M[r,c])).
Williams and Laine are considered to be analogous to the claim invention because they are in the same field of partitioning the queries based on the provided index that is submitted with each query. Therefore, it would have been obvious to someone ordinary skill in the art before the effective filling date of the claimed invention to have modified Williams to incorporate the teachings of Laine to include converting, by the one or more processors, the unsigned integer into a converted number within a specified range of [0, n), wherein n is a tunable parameter (Laine, Para. 0036) and (Laine, Para. 0040) and (Laine, Para. 0046); splitting, by the one or more processors, the converted number into a shard index and a bucket identifier (Laine, Para. 0047); generating, by the one or more processors, a client encrypted a query using the shard index and the bucket identifier (Laine, Para. 0080); transmitting, by the one or more processors, the client encrypted query to a server (Laine, Para. 0036); and receiving, by the one or more processors and from the server, a set of server encrypted results in response to submission of the client encrypted query (Laine, Para. 0036). Doing so would aid to put the benefits and costs in context, the multi-query PIR scheme found in Pung was evaluated. Pung's protocol, like PBCs, was probabilistic and significantly improved over existing batch codes in terms of costs (Laine, Para. 0099).
Regarding claim 2, the combination of Williams in view of Laine teaches the computer-implemented method of claim 1, wherein generating the client encrypted query comprises:
generating an indicator vector, wherein an element having an index equal to the bucket identifier is set to a value of 1, and other elements of the indicator vector are set to a value of 0 (Laine, Para. 0080, for example, the query may be a vector with a value of 1 for each element that is to be retrieved and 0 otherwise) and (Laine, Para. 0025, table 1 and table 5);
encrypting the indicator vector using fully homomorphic encryption (FHE) to obtain a corresponding FHE encrypted bucket vector (Laine, Para. 0080, this vector may be encrypted by a client. The server may use this encrypted vector without having to decrypt the vector) and (Laine, table 1 and Para. 0030, using a fully homomorphic encryption (FHE) scheme); and
including the corresponding FHE encrypted bucket vector and the shard index in the query (Laine, Para. 0076, this produces a set of buckets, each of which can be treated as an independent database on which clients can perform PIR) and (Laine, Table 5). Therefore, it would have been obvious to someone ordinary skill in the art before the effective filling date of the claimed invention to have modified Williams to incorporate the teachings of Laine to include generating an indicator vector, wherein an element having an index equal to the bucket identifier is set to a value of 1, and other elements of the indicator vector are set to a value of 0 (Laine, Para. 0080) and (Laine, Para. 0025, table 1 and table 5); encrypting the indicator vector using fully homomorphic encryption (FHE) to obtain a corresponding FHE encrypted bucket vector (Laine, Para. 0080) and (Laine, table 1 and Para. 0030); and
including the corresponding FHE encrypted bucket vector and the shard index in the query (Laine, Para. 0076) and (Laine, Table 5). Doing so would aid to put the benefits and costs in context, the multi-query PIR scheme found in Pung was evaluated. Pung's protocol, like PBCs, was probabilistic and significantly improved over existing batch codes in terms of costs (Laine, Para. 0099).
Regarding claim 3, the combination of Williams in view of Laine teaches the computer-implemented method of claim 2, wherein generating the indicator vector comprises generating the indicator vector to have a length based on a number (P) of database shards in a results database (Laine, Para. 0054, the number of buckets b, as a function of the database size (n)). Therefore, it would have been obvious to someone ordinary skill in the art before the effective filling date of the claimed invention to have modified Williams to incorporate the teachings of Laine to include wherein generating the indicator vector comprises generating the indicator vector to have a length based on a number (P) of database shards in a results database (Laine, Para. 0054). Doing so would aid to put the benefits and costs in context, the multi-query PIR scheme found in Pung was evaluated. Pung's protocol, like PBCs, was probabilistic and significantly improved over existing batch codes in terms of costs (Laine, Para. 0099).
Regarding claim 4, the combination of Williams in view of Laine teaches the computer-implemented method of claim 3, wherein generating the indicator vector comprises generating the indicator vector to have a length based on the number of database shards in the results database and a largest possible value (n) of the converted number (Laine, Para. 0061, using w hash functions to hash a key to w candidate buckets approximates an independent and uniform random assignment of a ball to w bins). Therefore, it would have been obvious to someone ordinary skill in the art before the effective filling date of the claimed invention to have modified Williams to incorporate the teachings of Laine to wherein generating the indicator vector comprises generating the indicator vector to have a length based on the number of database shards in the results database and a largest possible value (n) of the converted number (Laine, Para. 0061). Doing so would aid to put the benefits and costs in context, the multi-query PIR scheme found in Pung was evaluated. Pung's protocol, like PBCs, was probabilistic and significantly improved over existing batch codes in terms of costs (Laine, Para. 0099).
Regarding claim 5, the combination of Williams in view of Laine teaches the computer-implemented method of claim 4, wherein generating the indicator vector comprises generating the indicator vector to have a length of n/P (Laine, Para. 0061, the max load is n/w where all balls map to the same w candidate buckets, but there are useful bounds that hold with high probability). Therefore, it would have been obvious to someone ordinary skill in the art before the effective filling date of the claimed invention to have modified Williams to incorporate the teachings of Laine to wherein generating the indicator vector comprises generating the indicator vector to have a length of n/P (Laine, Para. 0061). Doing so would aid to put the benefits and costs in context, the multi-query PIR scheme found in Pung was evaluated. Pung's protocol, like PBCs, was probabilistic and significantly improved over existing batch codes in terms of costs (Laine, Para. 0099).
Regarding claim 6, the combination of Williams in view of Laine teaches the computer-implemented method of claim 1, further comprising generating a decryption key based on the server encrypted identifier (Williams, Para. 0025, it would accept an encrypted employee name and output an encrypted answer) and (Williams, Para. 0028, By way of further non-limiting example, when data source 322 1-322 N includes an encrypted “social security number” field, the social security numbers are all encrypted).
Regarding claim 8, the combination of Williams in view of Laine teaches the computer-implemented method of claim 6, further comprising decrypting the server encrypted results using the generated decryption key (Williams, Para. 0036, using techniques of the homomorphic encryption scheme E and the keyed hash function, each of one or more servers 320 1-320 N can extract a set of term components {T} from target data source 322 1-322 N using the term generation function, evaluate Q_M over the set of term components {T}, and produce encrypted result E(R). At step 460, encrypted result E(R) can be provided by one or more servers 320 1-320 N (FIG. 3) and received by one or more clients 310 1-310 M).
Regarding claim 9, the claim is interpreted and rejected for the same rational set forth
in claim 1.
Regarding claim 10, the claim is interpreted and rejected for the same rational set forth
in claim 2.
Regarding claim 11, the claim is interpreted and rejected for the same rational set forth
in claim 3.
Regarding claim 12, the claim is interpreted and rejected for the same rational set forth
in claim 4.
Regarding claim 13, the claim is interpreted and rejected for the same rational set forth
in claim 5.
Regarding claim 14, the claim is interpreted and rejected for the same rational set forth
in claim 2.
Regarding claim 16, the claim is interpreted and rejected for the same rational set forth
in claim 8.
Regarding claim 17, the claim is interpreted and rejected for the same rational set forth
in claim 1 and 9.
Regarding claim 18, the claim is interpreted and rejected for the same rational set forth
in claim 2 and 10.
Regarding claim 19, the claim is interpreted and rejected for the same rational set forth
in claim 3 and 11.
Regarding claim 20, the claim is interpreted and rejected for the same rational set forth
in claim 4 and 12.
Claims 7 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Williams et al. (US 2018/0212751 A1), hereinafter Williams in view of Laine et al. (US 2019/0325082 A1), hereinafter Laine and further in view of the article entitled “HMAC-based Extract-and-Expand Key Derivation Function (HKDF)” by Krawczyk.
Regarding claim 7, the combination of Williams in view of Laine does not explicitly teach the computer-implemented method of claim 6, wherein generating the decryption key comprises implementing a hash-based message authentication code cryptographic key derivation function that results into at least one secret key.
However, Krawczyk teaches wherein generating the decryption key comprises implementing a hash-based message authentication code cryptographic key derivation function that results into at least one secret key (Krawczyk, Page 5, A major goal of key derivation functions is to ensure that, when applying the KDF to any two values IKM and IKM' sampled from the (same) source distribution, the resultant keys OKM and OKM' are essentially independent of each other (in a statistical or computational sense)). Williams, Laine and Krawczyk are considered to be analogous to the claim invention because they are in the same field of partitioning the queries based on the provided index that is submitted with each query. Therefore, it would have been obvious to someone ordinary skill in the art before the effective filling date of the claimed invention to have modified Williams and Laine to incorporate the teachings of Krawczyk to include wherein generating the decryption key comprises implementing a hash-based message authentication code cryptographic key derivation function that results into at least one secret key (Krawczyk, Page 5). Doing so would aid to accommodate a wide range of KDF requirements while minimizing the assumptions about the underlying hash function (Krawczyk, Page. 1).
Regarding claim 15, the claim is interpreted and rejected for the same rational set forth
in claim 7.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. See PTOL-892.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to GITA FARAMARZI whose telephone number is (571)272-0248. The examiner can normally be reached Monday- Friday 9:00 am- 6:00 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, Jorge L. Ortiz-Criado can be reached at (571)272-7624. 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.
/GITA FARAMARZI/Examiner, Art Unit 2496
/JORGE L ORTIZ CRIADO/Supervisory Patent Examiner, Art Unit 2496
Prosecution Insights