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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-8 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1, “includes a comparison calculation of comparing the input value with a value of one of nodes included in the tree structure is performed” renders the claim indefinite because it is grammatically incorrect and does not convey a clear notion or idea. “Includes…is performed” is nebulous in that it is unclear if some module is being included which performs the claimed action, or if the claimed action is performed and that performance is what is claimed as being included.
Regarding claim 1, “the node” lacks antecedent basis in the claims.
Regarding claim 1, “the nodes” lacks antecedent basis in the claims.
Regarding claim 2, “the nodes” lacks antecedent basis in the claims.
Regarding claim 2, it is generally unclear what is being claimed because it is unclear if “to be disposed” is an action being performed or if it is describing how nodes are already laid out. It is unclear if the claim is describing the re-aligning process.
Regarding claim 3, “the leaf node” lacks antecedent basis in the claim.
Regarding claim 4, “the comparison calculation of comparing the input value with a calculated value” lacks antecedent basis in the claim.
Regarding claim 4, “the segmentation operation” lacks antecedent basis.
Claims 5-8 contain the same deficiencies found in their corresponding claim of claims 1-4.
Claims 2-4 and 6-8 are indefinite by virtue of dependency on an indefinite claim.
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-8 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes. Claim 1 is drawn to a device.
Step 2A, Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes. Claim 1 recites the following abstract ideas:
“making a decision” - This constitutes a concept performed in the human mind, such as an observation, evaluation, judgement, and/or opinion. Furthermore, the courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea. CyberSource Corp. v. Retail Decisions, Inc., 654 F.3d 1366, 1372, 99 USPQ2d 1690, 1695 (Fed. Cir. 2011). See MPEP 2106.04(a)(2).
“performing a reduction operation of reducing the tree structure at least once, wherein, the reduction operation includes a comparison calculation of comparing the input value with a value of one of nodes included in the tree structure is performed, and a comparison calculation result is added to nodes at corresponding positions in a plurality of lower tree structures branching from the node, and then the nodes are combined with each other.” - This constitutes a concept performed in the human mind, such as an observation, evaluation, judgement, and/or opinion. The operation also includes a mathematical concept, which constitutes an abstract idea. Furthermore, the courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea. CyberSource Corp. v. Retail Decisions, Inc., 654 F.3d 1366, 1372, 99 USPQ2d 1690, 1695 (Fed. Cir. 2011). See MPEP 2106.04(a)(2).
Step 2A, Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. Claim 1 recites the following additional elements:
“an electronic device” – This constitutes mere instructions to implement the abstract idea on a computer, which does not render an abstract idea eligible, see MPEP 2106.05(f).
“a memory storing a tree-structured decision-making model for making a decision” – This constitutes mere instructions to implement the abstract idea on a computer, which does not render an abstract idea eligible, see MPEP 2106.05(f).
“an interface for receiving an input value” - This amounts to insignificant extra solution activity in the form of mere data gathering, see MPEP 2106.05(g) and MPEP 2106.05(d), II, (i), regarding receiving or transmitting data.
“a processor” - This constitutes mere instructions to implement the abstract idea on a computer, which does not render an abstract idea eligible, see MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount ot significantly more than the judicial exception?
No. Claim 1 recites the following additional elements:
“an electronic device” – This constitutes mere instructions to implement the abstract idea on a computer, which does not render an abstract idea eligible, see MPEP 2106.05(f).
“a memory storing a tree-structured decision-making model for making a decision” – This constitutes mere instructions to implement the abstract idea on a computer, which does not render an abstract idea eligible, see MPEP 2106.05(f).
“an interface for receiving an input value” - This amounts to insignificant extra solution activity in the form of mere data gathering, see MPEP 2106.05(g) and MPEP 2106.05(d), II, (i), regarding receiving or transmitting data.
“a processor” - This constitutes mere instructions to implement the abstract idea on a computer, which does not render an abstract idea eligible, see MPEP 2106.05(f).
Claim 2
Step 2A, Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes. Claim 2 recites the following abstract ideas:
“perform a preprocessing operation of re-aligning positions of the nodes for the largest number of nodes to be disposed in their corresponding positions among the nodes included in the plurality of lower tree structures with regard to the plurality of lower tree structures branching from one node in the tree structure” - This constitutes a concept performed in the human mind, such as an observation, evaluation, judgement, and/or opinion. The operation also includes a mathematical concept, which constitutes an abstract idea. Furthermore, the courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea. CyberSource Corp. v. Retail Decisions, Inc., 654 F.3d 1366, 1372, 99 USPQ2d 1690, 1695 (Fed. Cir. 2011). See MPEP 2106.04(a)(2).
Step 2A, Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. Claim 2 recites the following additional elements:
“store the re-aligned positions in the memory” – This amounts to insignificant extra solution activity in the form of mere data storage, see MPEP 2106.05(g) and MPEP 2106.05(d), II, (iv), regarding storing and retrieving information in memory.
Step 2B: Does the claim recite additional elements that amount ot significantly more than the judicial exception?
No. Claim 2 recites the following additional elements:
“store the re-aligned positions in the memory” – This amounts to insignificant extra solution activity in the form of mere data storage, see MPEP 2106.05(g) and MPEP 2106.05(d), II, (iv), regarding storing and retrieving information in memory.
Claim 3
Step 2A, Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes. Claim 3 recites the following abstract ideas:
“perform a preprocessing operation of matching depths of final leaf nodes of the lower tree structures each branching from a root node of the tree structure with each other by adding at least one duplicate node to the leaf node disposed at a middle depth in the tree structure” - This constitutes a concept performed in the human mind, such as an observation, evaluation, judgement, and/or opinion. The operation also includes a mathematical concept, which constitutes an abstract idea. Furthermore, the courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea. CyberSource Corp. v. Retail Decisions, Inc., 654 F.3d 1366, 1372, 99 USPQ2d 1690, 1695 (Fed. Cir. 2011). See MPEP 2106.04(a)(2).
Step 2A, Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. Claim 3 does not recite any additional elements.
Step 2B: Does the claim recite additional elements that amount ot significantly more than the judicial exception?
No. Claim 3 does not recite any additional elements.
Claim 4
Step 2A, Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes. Claim 4 recites the following abstract ideas:
“generate a position identification vector corresponding to a root node in the tree structure, perform the comparison calculation of comparing the input value with a calculated value acquired by calculating the position identification vector and a value of a next node branching from the root node, perform an operation of segmenting the tree structure a predetermined number of times while reflecting a comparison calculation result to the next node to update the position identification vector to the position identification vector corresponding to a next depth, combine the segmented tree structures with each other to acquire a reduced tree structure by using the position identification vector updated in the segmentation operation… performing the reduction operation on the reduced tree structure at least once.” - This constitutes a concept performed in the human mind, such as an observation, evaluation, judgement, and/or opinion. The operation also includes a mathematical concept, which constitutes an abstract idea. Furthermore, the courts consider a mental process (thinking) that "can be performed in the human mind, or by a human using a pen and paper" to be an abstract idea. CyberSource Corp. v. Retail Decisions, Inc., 654 F.3d 1366, 1372, 99 USPQ2d 1690, 1695 (Fed. Cir. 2011). See MPEP 2106.04(a)(2).
Step 2A, Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. Claim 4 recites the following additional elements:
“output the result value corresponding to the input value” – This amounts to insignificant extra solution activity in the form of mere data gathering, see MPEP 2106.05(g) and MPEP 2106.05(d), II, (i), regarding receiving or transmitting data.
Step 2B: Does the claim recite additional elements that amount ot significantly more than the judicial exception?
No. Claim 4 recites the following additional elements:
“output the result value corresponding to the input value” – This amounts to insignificant extra solution activity in the form of mere data gathering, see MPEP 2106.05(g) and MPEP 2106.05(d), II, (i), regarding receiving or transmitting data.
Claims 5-8 are ineligible for the same reasons as claims 1-4.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 1 and 5 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Cong (Cong, Kelong, et al. "Sortinghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering." Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022.)
Regarding claim 1, Cong teaches an electronic device comprising: a memory storing a tree-structured decision-making model for making a decision; an interface for receiving an input value; and a processor configured to (§7.2.1, “We evaluate various decision tree models [a memory storing a tree-structured decision-making model for making a decision] using our method with a personal computer running on AMD Ryzen 5 5600X 6-Core Processor @ 3.70 GHz. [an interface for receiving an input value and a processor configured to]”):
acquire a result value of a tree structure that corresponds to the input value by performing a reduction operation of reducing the tree structure at least once (Algorithm 7, line 10, [the input value], Algorithm 8, line 16 [a result value], Algorithm 8, lines 5-15 [of a tree structure that corresponds to the input value], Algorithm 8, line 12 [a reduction operation of reducing the tree structure at least once]), wherein, the reduction operation includes
a comparison calculation of comparing the input value with a value of one of nodes included in the tree structure is performed (Algorithm 8, line 8, which uses PolyComp, see Algorithm 1, which is a comparison calculation of comparing the input value with a value of one of nodes included in the tree structure) and a comparison calculation result is added to nodes at corresponding positions in a plurality of lower tree structures branching from the node (Algorithm 8, line 8, “→bi,j” is a comparison calculation result being added to nodes at corresponding position in a plurality of lower tree structures branching from the node), and then the nodes are combined with each other (Algorithm 8, line 12 to Algorithm 6 line 7, to Algorithm 5, where bl and br are combined with each other to determine which sub-tree structure to travel on.)
To further clarify, the homomorphic traversal of the tree is a reduction operation because as the tree is traversed, a smaller portion of the tree is selected for traversal at each node.
PNG
media_image1.png
244
626
media_image1.png
Greyscale
PNG
media_image2.png
274
624
media_image2.png
Greyscale
PNG
media_image3.png
448
608
media_image3.png
Greyscale
PNG
media_image4.png
396
596
media_image4.png
Greyscale
PNG
media_image5.png
508
596
media_image5.png
Greyscale
Regarding claim 5, Cong according to claim 1 performs the method of claim 5 under normal operation.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 2 and 6 is/are rejected under 35 U.S.C. 103 as being unpatentable over Cong (Cong, Kelong, et al. "Sortinghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering." Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022.) in view of Baer (Baer, J-L., and B. Schwab. "A comparison of tree-balancing algorithms." Communications of the ACM 20.5 (1977): 322-330.)
Regarding claim 2, Cong teaches all of the limitations of claim 1.
Cong does not teach wherein the processor is configured to perform a preprocessing operation of re-aligning positions of the nodes for the largest number of nodes to be disposed in their corresponding positions among the nodes included in the plurality of lower tree structures with regard to the plurality of lower tree structures branching from one node in the tree structure, and store the re-aligned positions in the memory.
Baer teaches a preprocessing operation of re-aligning positions of the nodes for the largest number of nodes to be disposed in their corresponding positions among the nodes included in the plurality of lower tree structures with regard to the plurality of lower tree structures branching from one node in the tree structure (see Figure 2(B), where nodes are realigned such that the largest number of nodes are disposed in their corresponding position among the nodes included in the lower tree structures with regard to the plurality of lower tree structures branching from one node in the tree structure, i.e. GGS, GS, and S are realigned such that the tree is balanced and the largest number of nodes are disposed in the 2nd level of the tree).
PNG
media_image6.png
854
778
media_image6.png
Greyscale
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Cong such that the processor is configured to perform a preprocessing operation of re-aligning positions of the nodes for the largest number of nodes to be disposed in their corresponding positions among the nodes included in the plurality of lower tree structures with regard to the plurality of lower tree structures branching from one node in the tree structure, and store the re-aligned positions in the memory in order to balance the tree before homomorphic traversal in Cong.
Regarding claim 6, Cong as modified according to claim 2 performs the method of claim 6 under normal operation.
Claim(s) 3 and 7 is/are rejected under 35 U.S.C. 103 as being unpatentable over Cong (Cong, Kelong, et al. "Sortinghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering." Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022.) in view of Sarpatwar (Sarpatwar, Kanthi, et al. "Privacy enhanced decision tree inference." 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). IEEE, 2020.)
Regarding claim 3, Cong teaches all of the limitations of claim 1.
Cong does not teach wherein the processor is configured to: perform a preprocessing operation of matching depths of final leaf nodes of the lower tree structures each branching from a root node of the tree structure with each other by adding at least one duplicate node to the leaf node disposed at a middle depth in the tree structure.
Sarpatwar teaches a preprocessing operation of matching depths of final leaf nodes of the lower tree structures each branching from a root node of the tree structure with each other by adding at least one duplicate node to the leaf node disposed at a middle depth in the tree structure (§6.1, “We assume, without loss of generality, that the tree is balanced. Indeed, if the depth of a certain leaf is ℓ′ < ℓ, then we can add replicas of the leaf as its left and right child [adding at least one duplicate node to the leaf node disposed at a middle depth in the tree structure], thus increasing its depth until it becomes ℓ. [matching depths of final leaf nodes of the lower tree structures each branching from a root node of the tree structure]”).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Cong such that the processor is configured to: perform a preprocessing operation of matching depths of final leaf nodes of the lower tree structures each branching from a root node of the tree structure with each other by adding at least one duplicate node to the leaf node disposed at a middle depth in the tree structure in order to balance the tree in Cong.
Regarding claim 7, Cong as modified according to claim 3 performs the method of claim 7 under normal operation.
Allowable Subject Matter
Claims 4 and 8 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Regarding claims 4 and 8, the prior art does not establish anticipation or a prima facie case of obviousness regarding the position identification vector, segmentation, and combination of the segmented structures to reduce the tree structure.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure
Azogagh (Azogagh, Sofiane, et al. "Probonite: Private one-branch-only non-interactive decision tree evaluation." Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography. 2022.) discloses homomorphic decision tree traversal and is generally germane to the claimed invention.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SCHYLER S SANKS whose telephone number is (571)272-6125. The examiner can normally be reached 06:30 - 15:30 Central Time, M-F.
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, Michael Huntley can be reached at (303) 297-4307. 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.
/SCHYLER S SANKS/Primary Examiner, Art Unit 2129
Prosecution Insights