SAP SE

Patent Trials and Appeals Board

Sep 30, 2021

2020005299 (P.T.A.B. Sep. 30, 2021)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
14/939,138 11/12/2015 Florian Hahn 22135-0874001 5156
32864 7590 09/30/2021
FISH & RICHARDSON, P.C. (SAP)
PO BOX 1022
MINNEAPOLIS, MN 55440-1022
EXAMINER
VO, CECILE H
ART UNIT PAPER NUMBER
2153
NOTIFICATION DATE DELIVERY MODE
09/30/2021 ELECTRONIC
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address(es):
PATDOCTC@fr.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte FLORIAN HAHN and FLORIAN KERSCHBAUM
Appeal 2020-005299
Application 14/939,138
Technology Center 2100
BEFORE ALLEN R. MacDONALD, JEAN R. HOMERE, and
JEREMY J. CURCURI, Administrative Patent Judges.
CURCURI, Administrative Patent Judge.
DECISION ON APPEAL
STATEMENT OF THE CASE
Pursuant to 35 U.S.C. § 134(a), Appellant1 appeals from the
Examiner’s decision to reject claims 1–20. Claims App. We have
jurisdiction under 35 U.S.C. § 6(b).
We REVERSE.

1 Appellant to refers to “applicant” as defined in 37 C.F.R.
§ 1.42(a). Appellant identifies the real party in interest as SAP SE. Appeal
Br. 4.
Appeal 2020-005299
Application 14/939,138

2
CLAIMED SUBJECT MATTER
The claims are directed to “[p]oly-logarithmic range queries on
encrypted data.” Spec., Title; see also Fig. 4 (depicting a process executed to
perform range queries over encrypted data). Claim 1, reproduced below, is
illustrative of the claimed subject matter:
1. A computer-implemented method for performing
range queries over encrypted data, the method being executed
by a server-side computing device and comprising:
receiving, by the server-side computing device, a range
query token from a client-side computing device;
determining, by the server-side computing device, one or
more of whether a tree list of an encrypted search index is
empty and a range of the range query token is intersecting with
a range accounted by at least one tree in the tree list, the at least
one tree covering an already searched range, the encrypted
search index comprising the tree list and a point list, the point
list comprising one or more pointers, each pointer pointing to
one of a node of a sub-tree within the encrypted search index,
and a query result set;
receiving, by the server-side computing device,
encrypted query results based on one of a search tree, if the tree
list is not empty and a range of the range query token is at least
a sub-range of a range accounted for in the tree list, and a
pointer of the point list, if the tree list is empty or the range of
the range query token is not at least a sub-range of a range
accounted for in the tree list; and
in response to receiving the range query token, updating,
by the server-side computing device, the encrypted search index
based on the range query token to change one of the tree list to
represent that the range of the range query token has been
searched, and at least one indexed range, updating comprising
executing a client-server protocol comprising actions performed
by the server-side computing device and actions performed by
the client-side computing device on plaintext data provided
from encrypted data that is received from the server-side
Appeal 2020-005299
Application 14/939,138

3
computing device, and using a master key held by the client-
side computing device.

Appeal Br. 21–22, Claims App.
REFERENCES
The Examiner relies upon the following prior art:
Name Reference Date
Kamara US 2013/0046974 A1 Feb. 21, 2013
Roeder US 2013/0262852 A1 Oct. 3, 2013

REJECTION
The Examiner rejects claims 1–20 under 35 U.S.C. § 103 as obvious
over the combination of Roeder and Kamara. Final Act. 3–10.
OPINION
The Examiner finds Roeder and Kamara teach all limitations of claim
1. Final Act. 3–7. The Examiner finds Roeder teaches all limitations of claim
1 except for limitations relating to the tree list. Id. at 3–5 (“[A]n encrypted
index [in Roeder] . . . maps bucketized terms (e.g., a term associated with a
range of values) to encrypted documents [as a point list].” (bolding added)).
In particular, the Examiner finds
Roeder does not directly or explicitly disclose: The list of a
search index is a tree list; each pointer pointing to one of a node
of a sub-tree within the encrypted search index;
updating, by the server-side computing device, the
encrypted search index based on the range query token to change
one of the tree list to represent that the ra[n]ge of the ra[n]ge
query token has been searched, and at least on[e] indexed range.
Appeal 2020-005299
Application 14/939,138

4
Id. at 5. The Examiner finds Kamara teaches the limitations relating to the
tree list. Id. at 5–7 (“[T]he index [in Kamara] can be a data structure that is
in the form of a tree.”). The Examiner reasons
it would have been obvious to a person of ordinary skill in the art
before the effective filing date of the invention to modify
techniques enabling range-based queries in searchable
symmetric encryption (SSE) system as disclosed by Roeder to
Dynamic symmetric searchable encryption as taught by Kamara
to provide an efficient and dynamic Symmetric Searchable
Encryption (SSE) scheme. This scheme may be particularly
advantageous with respect to relative large document (file)
collections that are subject to frequent updates.
Id. at 7.
Among other contentions, Appellant contends Roeder and Kamara do
not teach “the encrypted search index comprising the tree list and a point
list, the point list comprising one or more pointers, each pointer pointing to
one of a node of a sub-tree within the encrypted search index, and a query
result set” (claim 1) and “a range [is] accounted by at least one tree in the
tree list, the at least one tree covering an already searched range” (claim 1).
Appeal Br. 14. In support of this contention, Appellant argues the following:
Roeder does not teach “the encrypted search index comprising the tree
list and a point list, the point list comprising one or more pointers” (claim 1)
and “a range [is] accounted by at least one tree in the tree list, the at least
one tree covering an already searched range” (claim 1). Id. at 14–15.
“Roeder discusses ‘an encrypted search index that maps bucketized terms
(e.g., a term associated with a range of values) to encrypted documents,’ for
example ‘the encrypted index maps “age +(45-55)” to encrypted documents
that include “age” and a value in the range 45-55.’” Id. at 15.
Appeal 2020-005299
Application 14/939,138

5
Kamara does not teach the list of a search index is a tree list and “each
pointer [of the point list] pointing to one of a node of a sub-tree within the
encrypted search index” (claim 1) because Kamara “instead provides that
‘leaf nodes of the tree are pointers to files in the file collection.’” Appeal Br.
15.
In response to these arguments, the Examiner explains “[t]he teaching
of ‘bucketization’ for the term age is [0-10, 11-20, 21-35, 36-50, 51-63, 64-
72, and 73-115], in Roeder, has been interpreted as the tree list.” Ans. 7.
In reply to the Examiner, Appellant argues “the ‘bucketization’ of
Roeder cannot concurrently account for both the tree list and the point list.”
Reply Br. 1. Appellant further argues “Kamara [does not] cure this
deficiency of Roeder.” Reply Br. 2.
We review the appealed rejections for error based upon the issues
identified by Appellant, and in light of the arguments and evidence produced
thereon. Ex parte Frye, 94 USPQ2d 1072, 1075 (BPAI 2010) (precedential).
The key disputed limitations of claim 1 are “the encrypted search
index comprising the tree list and a point list, the point list comprising one or
more pointers, each pointer pointing to one of a node of a sub-tree within the
encrypted search index, and a query result set” (claim 1) and “a range [is]
accounted by at least one tree in the tree list, the at least one tree covering an
already searched range” (claim 1). Importantly, the claim language requires
both a “tree list” and a “point list” in the same search index, and these two
structures are related in a particular way, with pointers in the point list
“pointing to one of a node of a sub-tree within the encrypted search index,
and a query result set” (claim 1).
Appeal 2020-005299
Application 14/939,138

6
Roeder discloses “[a] server device includes or provides access to a
database that stores encrypted documents along with an encrypted index that
maps bucketized terms (e.g., a term coupled with a value range associated
with that term) to encrypted documents.” Roeder, Abstract. In the Final
Action, the Examiner maps the claimed “point list” of the claimed encrypted
search index to Roeder’s index. Final Act. 3–4.
Kamara discloses “the index 112 can be a data structure that is in the
form of a tree, wherein the tree comprises a plurality of layers of nodes, and
wherein leaf nodes of the tree are pointers to files in the file collection 108.”
Kamara ¶ 25. In the Final Action, the Examiner maps the claimed “tree list”
of the claimed encrypted search index to Kamara’s index. Final Act. 5–6.
Appellant’s arguments address Roeder and Kamara. We understand
Appellant to be arguing that neither Roeder nor Kamara teaches or suggests
what is required by the claim— both a “tree list” and a “point list” in the
same search index, and these two structures are related in a particular way,
with pointers in the point list “pointing to one of a node of a sub-tree within
the encrypted search index, and a query result set” (claim 1). We agree with
Appellant. The individual references, based on the Examiner’s findings in
the Final Action, do not meet these specific requirements. And we do not
readily see how the references, taken together, meet these specific
requirements. The Examiner’s reasoning on page 7 of the Final Action (“to
provide an efficient and dynamic Symmetric Searchable Encryption (SSE)
scheme”) is not sufficient to provide a reason for a skilled artisan to make
the specific modifications to Roeder that would have been required to meet
the specific requirements of the claim.
Appeal 2020-005299
Application 14/939,138

7
The Examiner’s explanation in the Examiner’s Answer does not
change our result. In the Examiner’s Answer, the Examiner appears to now
be relying on Roeder’s index for the claimed “point list” and the claimed
“tree list.” Ans. 7. Even if we were to accept this mapping, and assume that a
portion of Roeder’s index constitutes the claimed “point list” and a different
portion of Roeder’s index constitutes the claimed “tree list,” this still does
not show pointers in the point list “pointing to one of a node of a sub-tree
within the encrypted search index, and a query result set” (claim 1). To the
extent that Kamara is supposed to cure this deficiency, we determine
Kamara’s mere disclosure of a tree is insufficient to suggest the rather
specific modifications that would have been required in Roeder to result in
pointers in the point list “pointing to one of a node of a sub-tree within the
encrypted search index, and a query result set” (claim 1). In short, the
references individually do not teach the claimed subject matter, and the
Examiner’s reasoning to combine the references to provide the claimed
subject matter lacks a rational underpinning for reasons explained above.
Thus, we determine Roeder and Kamara do not teach the key disputed
limitations of claim 1.
We, therefore, do not sustain the Examiner’s rejection of claim 1.
We also do not sustain the Examiner’s rejection of claims 2–7, which
depend from claim 1.
Independent claim 8 recites the same key disputed limitations.
We, therefore, do not sustain the Examiner’s rejection of claim 8.
We also do not sustain the Examiner’s rejection of claims 9–14, which
depend from claim 8.
Independent claim 15 recites the same key disputed limitations.
Appeal 2020-005299
Application 14/939,138

8
We, therefore, do not sustain the Examiner’s rejection of claim 15.
We also do not sustain the Examiner’s rejection of claims 16–20,
which depend from claim 15.
CONCLUSION
The Examiner’s decision to reject claims 1–20 is reversed.
DECISION SUMMARY
In summary:
Claim(s)
Rejected
35 U.S.C.
§
Reference(s)/Basis Affirmed Reversed
1–20 103 Roeder, Kamara 1–20

REVERSED