`
`
`as) United States
`
`
`
`
`
`
`
`
`
`a2) Patent Application Publication co) Pub. No.: US 2014/0359282 Al
`
`
`
`
`
`
`
`
` Shikfaet al. (43) Pub. Date: Dec. 4, 2014
`
`
`
`US 20140359282A1
`
`
`
`
`
`
`
`
`(54) SYSTEMS AND METHODS FOR ENABLING
`
`
`SEARCHABLE ENCRYPTION
`
`
`
`
`(71) Applicant: Alcatel- Lucent, Paris (FR)
`cece
`.
`
`
`
`
`Inventors: Abdullatif Shikfa, Villebon-sur-Yvette
`
`
`
`
`
`(FR); Serge Papillon, Paris (FR)
`
`
`
`
`(73) Assignee: ALCATEL-LUCENT,Paris (FR)
`
`
`
`
`(21) Appl. No.: 13/907,044
`
`
`
`(72)
`
`(22)
`
`
`
`Filed:
`
`
`
`May 31, 2013
`
`
`Publication Classification
`
`
`
`
`(51)
`
`
`
`Int. Cl.
`GO6F 21/60
`
`
`
`(2006.01)
`
`
`
`
`10
`
`
`
`
`
`
`
`
`
`
`
`
`(52) U.S. CL
`
`
`
`
`CPC vieccccseseeseseetenscnesenees GO06F 21/602 (2013.01)
`USPC wiecesssesctesseseseseecssseecsnecensensseseeansentes 713/165
`
`
`
`
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`
`A system and method for enabling searchable encryption of
`
`
`
`
`
`
`
`encrypted documents stored by a client on one or morestor-
`
`
`
`
`
`
`
`age providers includesa brokerserver in communication with
`
`
`
`
`
`
`
`
`
`
`the client and the one or more storage providers. The broker
`
`
`
`
`
`
`
`
`server
`is adapted to transfer the encrypted documents
`
`
`
`
`
`
`
`
`
`betweenthe client and the one or more storage providers and
`
`
`
`
`
`
`
`to maintain information indicating where the encrypted docu-
`mentsare transferred. The broker server further stores infor-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`mation for at least one encrypted index for the encrypted
`
`
`
`
`
`
`
`
`
`
`
`
`documents and a test function for a searchable encryption
`
`
`
`
`
`
`
`
`mechanism used to encryptthe at least one encrypted index.
`
`
`
`
`
`
`
`El3|SP5
`
`Client
`
`LEIS|SPo.
`
`
`
`
`Searchable
`
`Encryption
`
`Broker
`
`
`Cloud
`Providers
`
`
`
`Page 1 of 11
`
`Netskope Exhibit 1006
`
`Page 1 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`
`Dec. 4, 2014 Sheet 1 of 4
`
`
`
`US 2014/0359282 Al
`
`
`
`FIG.1
`
`Cloud
`
`Providers
`
`Searchable
`
`EncryptionBroker
`
`Page 2 of 11
`
`Netskope Exhibit 1006
`
`Page 2 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 4, 2014 Sheet 2 of 4
`
`
`
`US 2014/0359282 Al
`
`
`
`Cloud
`
`Providers
`
`FIG.2
`
`Searchable
`
`EncryptionBroker
`
`Page 3 of 11
`
`Netskope Exhibit 1006
`
`Page 3 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 4, 2014 Sheet 3 of 4
`
`
`
`US 2014/0359282 Al
`
`Cloud
`
`Searchable
`
`EncryptionBroker
`
`FIG.3
`
`
`
`
`
`EncryptedDocuments
`
`Providers
`
`
`Page 4 of 11
`
`Netskope Exhibit 1006
`
`Page 4 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 4, 2014 Sheet 4 of 4
`
`
`
`US 2014/0359282 Al
`
`
`
`
`
`Searchable
`
`EncryptionBroker
`
`
`
`Providers
`
`
`
`Cloud
`
`FIG.4
`
`Page 5 of 11
`
`Netskope Exhibit 1006
`
`Page 5 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`US 2014/0359282 Al
`
`
`Dec. 4, 2014
`
`
`
`SYSTEMS AND METHODS FOR ENABLING
`
`
`
`SEARCHABLE ENCRYPTION
`
`
`
`
`
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`[0001] The present invention relates to data storage.
`
`
`
`
`
`BACKGROUNDOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`[0002] Many cloud-basedservices(e.g. data storage, web-
`
`
`
`
`
`
`
`mail services, advertising, geolocation services, and the like)
`
`
`
`
`
`
`
`
`provide the ability to operate on a client’s stored data (e.g.
`
`
`
`
`
`
`
`
`files, email, location, etc.) by providing access to the stored
`
`
`
`
`
`
`
`
`
`
`data. This allowsthe client to search for specific pieces ofdata
`
`
`
`
`
`
`
`
`stored using the cloud-based services. However, this ability to
`
`
`
`
`
`
`
`
`operate on the client’s stored data may be at odds with the
`
`
`
`
`
`
`
`
`client’s data privacy needs, which often require encryption to
`
`
`
`
`
`
`
`
`
`protect the data, because many storage providers do not sup-
`
`
`
`
`
`
`
`port searchable encryption. Therefore, the client’s ability to
`
`
`
`
`
`
`
`
`operate on encrypted data that is stored by one or more cloud
`
`
`
`
`storage providers can be limited.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`methodalso includesstoring, at the broker server, informa-
`
`
`
`
`
`
`
`
`
`tion relating to the at least one encrypted index and a test
`
`
`
`
`
`
`
`function for the searchable encryption mechanism used to
`
`
`
`
`encrypt the encrypted index.
`
`
`
`
`
`
`[0011] According to an embodiment,
`the computerized
`
`
`
`
`
`
`
`
`method mayadditionally comprise the steps of sending the at
`
`
`
`
`
`
`
`
`
`least one encrypted index to the storage provider and main-
`
`
`
`
`
`
`
`
`taining, at the broker server, a secondtranslation table indi-
`
`
`
`
`
`
`
`
`
`cating the encrypted indexesthat are transferred to each stor-
`
`
`age provider.
`
`
`
`
`
`
`[0012] According to an embodiment,
`the computerized
`
`
`
`
`
`
`
`method may additionally comprise the steps of receiving, at
`
`
`
`
`
`
`
`
`the broker server, an encrypted query from the client to be
`
`
`
`
`
`
`
`
`
`searched and executing,at the brokerserver, the test function
`
`
`
`
`
`
`
`
`for the searchable encryption mechanism using the encrypted
`
`
`
`
`
`
`
`
`query andthe encrypted index. The methodfurther comprises
`
`
`
`
`
`
`
`transferring, by the broker server, encrypted documents
`
`
`
`
`
`
`
`
`returned from the test function as satisfying the encrypted
`
`
`
`
`
`
`
`
`
`query from the at least one storage providerto the client.
`
`
`
`
`
`
`[0013] According to an embodiment,
`the computerized
`
`
`
`
`
`
`
`
`
`method may also comprise the steps of sending the at least
`SUMMARY
`
`
`
`
`
`
`
`
`one encrypted index to the storage provider and maintaining,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`at the brokerserver, a secondtranslation table indicating the
`[0003] According to an embodiment, a broker system
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted indexes that are transferred to each storage pro-
`enables searchable encryption ofencrypted documents stored
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`vider. The method may also compriseretrieving the at least
`by a client on one or more storage providers. The broker
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`one encrypted index from the at least one storage provider.
`system includes a broker server in communication with the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0014] According to an embodiment, the broker server may
`client and the storage providers. The broker server is adapted
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`be in communication with a plurality of storage providers.
`to transfer the encrypted documents between the client and
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0015] According to an embodiment, the broker server may
`the storage providers and to maintain a table indicating the
`
`
`
`
`
`
`
`
`
`
`
`
`
`be in communication with a plurality of clients.
`encrypted documentsthatare transferred to each storage pro-
`
`
`
`
`
`vider. The broker server also stores information for at least
`
`
`
`
`
`
`
`
`
`[0016] According to an embodiment, the step of sending
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`one encrypted index for the encrypted documents anda test
`the encrypted documentsto the storage provider may include
`
`
`
`
`
`
`
`
`
`
`
`
`function for a searchable encryption mechanism used to
`sending a particular encrypted documentto at least two stor-
`
`
`
`
`
`
`
`
`
`
`encrypt the at least one encrypted index.
`age providers to provide redundancy.
`
`
`
`
`
`
`
`
`
`
`[0004] According to an embodiment, the information for
`[0017] According to an embodiment, a non-transitory, tan-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the at least one encrypted index is the encrypted index.
`gible computer-readable medium stores instructions adapted
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0005] According to an embodiment, the broker server
`to be executed by a computer processorat a broker server to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`transfers the at least one encrypted index to the one or more
`enable searchable encryption of encrypted documents stored
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`storage providers and the information for the at least one
`on at least one storage provider by a client to perform a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted index is a table indicating the encrypted indexes
`method comprising the steps of receiving, at a broker server,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`that are transferred to each storage provider.
`the encrypted documents, at least one encrypted index for the
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted documents, the encrypted index being encrypted
`[0006] According to an embodiment, the broker server is in
`
`
`
`
`
`
`
`
`
`
`by a searchable encryption mechanism, andidentification of
`communication with a plurality of clients.
`
`
`
`
`
`
`
`
`
`
`
`
`
`the searchable encryption mechanism used to encrypt the
`[0007] According to an embodiment, the broker serveris
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted index. The method further includes sending the
`adapted to send a particular encrypted documentto at least
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted documentsto theat least one storage provider and
`twostorage providers to provide redundancy.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`maintaining, at the broker server, a translation table indicat-
`[0008] According to an embodiment, the broker server
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing the encrypted documents that are transferred to each
`executes the test function upon receipt of an encrypted query
`
`
`
`
`
`
`
`
`from the client.
`
`
`
`storage provider. The method also includes storing, at the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`broker server,
`information relating to the at
`least one
`[0009] According to an embodiment,the brokerserver uses
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted index andatest function for the searchable encryp-
`the encrypted query and the encrypted index as input for the
`
`
`
`
`
`
`
`test function.
`
`
`tion mechanism used to encrypt the encrypted index.
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0018] According to an embodiment, the method may fur-
`[0010] According to an embodiment, a computerized
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ther comprise the steps of sending the at least one encrypted
`method for enabling searchable encryption of encrypted
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`index to the storage provider and maintaining, at the broker
`documents stored on at least one storage provider by a client
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`server, a second translation table indicating the encrypted
`includes receiving, at a broker server, the encrypted docu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`indexesthat are transferred to each storage provider.
`ments, at least one encrypted index for the encrypted docu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ments, the encrypted index being encrypted by a searchable
`[0019] According to an embodiment, the method may fur-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encryption mechanism, and identification of the searchable
`ther comprise the steps of receiving, at the broker server, an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encryption mechanism used to encrypt the encrypted index.
`encrypted query from the client to be searched and executing,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`at the broker server, the test function for the searchable
`The method further includes sending the encrypted docu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ments to the at least one storage provider and maintaining,at
`encryption mechanism using the encrypted query and the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the brokerserver, a translation table indicating the encrypted
`encrypted index. The method may further comprise transfer-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`documents that are transferred to each storage provider. The
`ring, by the broker server, encrypted documents returned
`
`Page 6 of 11
`
`Netskope Exhibit 1006
`
`Page 6 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`US 2014/0359282 Al
`
`
`Dec. 4, 2014
`
`
`
`
`
`
`
`
`
`
`
`
`
`from the test function as satisfying the encrypted query from
`
`
`
`
`
`
`
`the at least one storage providerto theclient.
`
`
`
`
`
`
`
`[0020] According to an embodiment, the method mayalso
`
`
`
`
`
`
`
`
`
`comprise the steps of sending theat least one encrypted index
`
`
`
`
`
`
`
`
`
`to the storage provider and maintaining, at the brokerserver,
`
`
`
`
`
`
`
`
`a secondtranslation table indicating the encrypted indexes
`
`
`
`
`
`
`
`
`
`thatare transferred to each storage provider. The method may
`
`
`
`
`
`
`
`
`
`also comprise retrieving the at least one encrypted index from
`
`
`
`
`
`the at least one storage provider.
`
`
`
`
`
`[0021] According to an embodiment,the broker server may
`
`
`
`
`
`
`be in communication with a plurality of storage providers.
`
`
`
`
`
`
`[0022] According to an embodiment, the step of sending
`
`
`
`
`
`
`
`
`the encrypted documentsto the storage provider may include
`
`
`
`
`
`
`
`sending a particular encrypted documentto at least two stor-
`
`
`
`
`age providers to provide redundancy.
`
`
`
`
`
`
`
`
`[0023] These and other embodiments of will become
`
`
`
`
`
`
`apparentin light of the following detailed description herein,
`
`
`
`
`
`with reference to the accompanying drawings.
`
`
`
`
`
`
`
`
`
`
`
`client 16 encrypts the one or more indexes 24 using a search-
`
`
`
`
`
`
`
`
`able encryption mechanism to generate one or more
`
`
`
`
`
`
`
`encrypted indexes 28. The searchable encryption mechanism
`
`
`
`
`
`
`
`
`used to encrypt the indexes 24 may be any searchable encryp-
`
`
`
`
`
`
`
`
`tion mechanism known in the art and is typically different
`
`
`
`
`
`
`
`
`than the encryption mechanism used to encrypt the docu-
`
`
`
`
`
`
`
`ments 26 since the searchable encryption mechanism is spe-
`
`
`
`
`
`
`cific to searchable encryption. Exemplary searchable encryp-
`tion mechanisms are described in the article Boolean
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`symmetric searchable encryption, by Tarik Moataz and
`
`
`
`
`
`
`
`
`Abdullatif Shikfa. 2013. In Proceedings of the 8th ACM
`
`
`
`
`
`
`SIGSAC symposium on Information, computer and commu-
`
`
`
`
`
`
`
`
`
`nications security (ASIA CCS 713). ACM, New York, N.Y.,
`
`
`
`
`
`
`
`
`USA, 265-276, and in the article Semantic Search Over
`
`
`
`
`
`
`
`Encrypted Data, by Tarik Moataz; Abdullatif Shikfa; Nora
`
`
`
`
`
`
`Cuppens-Boulahia and Frederic Cuppens. 2013. In Proceed-
`
`
`
`
`
`
`ings of the 20th IEEE International Conference on Telecom-
`
`
`
`
`
`
`
`
`munications (ICT 2013), which are both hereby incorporated
`
`
`
`
`
`
`by reference in their entireties. As should be understood by
`
`
`
`
`
`
`
`
`
`
`those skilled in the art, the broker system 10 may work with
`
`
`
`
`
`
`
`any searchable encryption mechanism andis not limited to
`
`
`
`
`
`
`
`the exemplary mechanisms described in the articles refer-
`
`
`
`
`
`
`
`enced above. The numberof encrypted indexes 28 generated
`
`
`
`
`
`
`
`
`by the client 16 for a particular number of encrypted docu-
`
`
`
`
`
`
`
`ments 14 may depend onthe specific searchable encryption
`
`
`
`
`
`
`
`
`
`mechanism usedto encrypt the index 24. For example, some
`
`
`
`
`
`
`searchable encryption mechanisms may generate one
`
`
`
`
`
`
`
`
`encrypted index 28 per encrypted document 14, while other
`
`
`
`
`
`
`searchable encryption mechanisms may generate a single
`
`
`
`
`
`encrypted index 28forall ofthe encrypted documents 14. The
`
`
`
`
`
`
`specific encryption mechanism for encrypting the documents
`
`
`
`
`
`
`
`
`26 and the specific searchable encryption mechanism for
`DETAILED DESCRIPTION
`
`
`
`
`
`
`
`
`
`
`searchably encrypting the one or more indexes 24 are not
`
`
`
`
`
`
`described in detail as a variety of encryption mechanisms and
`
`
`
`
`
`
`[0028] Referring to FIG. 1, a broker system 10 includes a
`
`
`
`
`
`
`searchable encryption mechanisms should be knownto those
`
`
`
`
`
`
`
`
`broker server 12 that enables searchable encryption of
`skilled in the art.
`
`
`
`
`
`
`
`
`
`encrypted documents 14 stored by a client 16 on one or more
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0030] Theclient 16 sends the encrypted documents 14 and
`cloud storage providers 18. The broker server 12 is in com-
`
`
`
`
`
`
`
`munication with the client 16 overa first communication link
`
`
`
`
`
`
`
`
`the corresponding encrypted index 28 (which maybe one or
`
`
`
`
`
`
`
`20 that allows the broker server 12 and client 16 to transfer
`
`
`
`
`
`
`
`
`
`several
`indexes depending on the searchable encryption
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`mechanism used) to the broker server 12 over the first com-
`data, such as the encrypted documents 14 (e.g. files, docu-
`munication link 20. The client 16 also informs the broker
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ments, email, location data, or any other similar data), ther-
`
`
`
`
`
`ebetween. The broker server 12 is also in communication with
`
`
`
`
`
`
`
`server 12 of the searchable encryption mechanism used to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypt the encrypted indexes 28 over the communication
`each cloud storage provider 18 over second communication
`
`
`
`
`
`
`
`
`
`link 20, which allows the broker module 12 to executea test
`links 22 that also allows the broker server 12 and the one or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`function for the searchable encryption mechanism to search
`more cloud storage providers 18 to transfer data, such as the
`
`
`
`
`
`
`
`
`
`
`
`
`
`the encrypted documents 14 as will be discussed below.
`encrypted documents 14, therebetween. Thefirst communi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0031] The broker server 12 receives the encrypted docu-
`cation link 20 and the second communication links 22 may be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ments 14, the encrypted index(es) 28, and the information on
`any suitable communication network for connecting elec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the searchable encryption mechanism from the client 16. The
`tronic devices, such as a computer network that may include
`
`
`
`
`
`
`
`connections across the World Wide Web. The broker server 12
`
`
`
`
`
`
`
`
`broker server 12 sends the encrypted documents 14 to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cloud storage providers 18 since the brokerserver 12 relies on
`acts as an intermediary between the client 16 and the cloud
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the cloud storage providers 18 to store data. The broker server
`storage provider 18 to provide searchable encryption so that
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`12 generates and stores in memoryatranslation table T1
`client may execute encrypted searches ofthe encrypted docu-
`
`
`
`
`
`
`
`
`ments 14.
`
`
`indicating which encrypted documents 14 (e.g. D1, D2, D3,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`etc) are stored on which cloud storage provider 18 (e.g. SP1,
`[0029] Referring to FIG. 2, for the broker system 10 to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SP2, SP3, SP4, SPS, etc.). The broker server 12 may transmit
`provide searchable encryption at the broker server 12, the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`one or more of the encrypted documents 14 to more than one
`client 16 generates one or more indexes 24 for one or more
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cloud storage provider 18. In this case, the translation table T1
`documents 26 that are to be encrypted as encrypted docu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`may be generated/updated to indicate that a particular
`ments 14 and stored on the storage providers 18. Each index
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted document14 (e.g., D1) is stored on multiple cloud
`24 includes one or more keywords for the encrypted docu-
`
`
`
`
`
`
`
`
`
`
`
`
`storage providers 18 (e.g., SP1, SP2).
`ments 14 and pointers to the encrypted documents 14 con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`taining the keywords. The client 16 encrypts the one or more
`[0032] The broker server 12 maystore the encrypted index
`
`
`
`
`
`
`
`
`
`
`
`
`
`documents 26 using any desired encryption mechanism
`(es) 28 directly in a locally accessible memory or may send
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`knownin the art to provide the encrypted documents 14. The
`the encrypted index(es) 28 to one or more ofthe cloud storage
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`[0024]
`FIG. 1 is a schematic diagram of a broker system
`
`
`according to an embodiment;
`
`
`
`
`
`[0025] FIG.2isa schematic diagram of an embodimentfor
`
`
`
`
`
`
`
`providing searchable encryption throughthe broker system of
`
`FIG.1;
`
`
`
`
`
`[0026] FIG.3isa schematic diagram of an embodimentfor
`
`
`
`
`
`
`
`executing an encrypted query through the broker system of
`
`
`FIG.1; and
`
`
`
`
`
`[0027]
`FIG. 4isa schematic diagram of an embodimentfor
`
`
`
`
`
`
`
`
`redundantly storing data through the broker system of FIG.1.
`
`Page 7 of 11
`
`Netskope Exhibit 1006
`
`
`
`
`
`Page 7 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`US 2014/0359282 Al
`
`
`Dec. 4, 2014
`
`
`
`
`
`
`
`
`
`
`providers 18 to minimize storage requirements for local
`
`
`
`
`
`
`
`
`memory. When the broker server 12 sends the encrypted
`
`
`
`
`
`
`
`
`index(es) 28 to one or more ofthe cloud storage providers 18,
`
`
`
`
`
`
`
`
`the broker server 12 generates and stores in memory a trans-
`
`
`
`
`
`
`
`lation table T2 indicating which encrypted index(es) (e.g.
`
`
`
`
`
`
`
`
`
`
`E11, E12, E13, etc.) are stored on which cloud storage pro-
`
`
`
`
`
`
`
`
`
`
`vider 18 (e.g. SP1, SP2, SP3, SP4, SP5, etc.). As with the
`
`
`
`
`
`
`
`
`
`encrypted documents 14, the broker server 12 may send one
`
`
`
`
`
`
`
`or more of the encrypted index(es) for storage on multiple
`
`
`
`cloud storage providers.
`
`
`
`
`
`
`
`
`[0033] The broker server 12 also stores the information on
`
`
`
`
`
`
`
`the searchable encryption mechanism from the client 16 used
`
`
`
`
`
`
`
`
`to searchably encrypt the encrypted index(es) 28 in local
`
`
`
`
`
`
`
`
`memory. The broker server 12 uses the information on the
`
`
`
`
`
`searchable encryption mechanism to perform searchesof the
`
`
`
`
`
`
`
`encrypted documents 14, as discussed in greater detail below.
`
`
`
`
`
`
`
`[0034] Referring to FIG. 3, when the client 16 wants to
`
`
`
`
`
`
`
`search for a encrypted document 14 containing one or more
`
`
`
`
`
`
`
`keywords, the client 16 generates an encrypted search query
`
`
`
`
`
`
`
`
`30 for the keywordsas per the searchable encryption mecha-
`
`
`
`
`
`
`
`
`
`nism usedto encrypt the encrypted index(es) 28 and sends the
`
`
`
`
`
`
`
`
`encrypted query 30 to the broker server 12 over the commu-
`nication link 20.
`
`
`
`
`
`
`
`
`
`
`[0035] When the broker server 12 receives the encrypted
`
`
`
`
`
`
`
`
`
`
`search query 30 from the client 16, the broker server 12
`
`
`
`
`
`
`
`
`
`implements the specific test function for the specific search-
`
`
`
`
`
`
`able encryption mechanism to determine which encrypted
`
`
`
`
`
`
`
`documents 14 correspondsto the encrypted query 30, if any.
`
`
`
`
`
`
`
`
`
`Asdiscussed above, the broker server 12 knows which spe-
`
`
`
`
`
`
`
`
`
`
`cific test function to select and apply for the specific search-
`
`
`
`
`
`
`
`able encryption mechanism becausethe client 16 previously
`
`
`
`
`
`
`
`
`provided the broker server 12 with the information on the
`
`
`
`
`
`
`
`searchable encryption mechanism used to encrypt
`the
`
`
`
`encrypted index(es) 28.
`
`
`
`
`
`
`
`
`
`[0036] The specific test function selected for the specific
`
`
`
`
`
`
`
`searchable encryption mechanism uses the encrypted query
`
`
`
`
`
`
`
`30 and the encrypted index(es) 28 as input forits determina-
`
`
`
`
`
`
`
`
`tion. Thus, when the broker server 12 receives the encrypted
`
`
`
`
`
`
`
`
`
`
`query 30 from the client 16, the broker server 12 only obtains
`
`
`
`
`
`
`
`
`
`the encrypted index(es) 28 for that client 16 to execute the
`
`
`
`
`
`
`
`specific test function. As discussed above, in some embodi-
`
`
`
`
`
`
`
`ments, the encrypted index(es) 28 may bestored locally in
`
`
`
`
`
`
`
`
`memory on the broker server 12 and, therefore, may be
`
`
`
`
`
`
`readily available. In other embodiments, where the encrypted
`
`
`
`
`
`
`
`index(es) 28 is stored at one or more cloud storage providers
`
`
`
`
`
`
`
`
`
`18, the broker server 12 may use the translation table T2
`
`
`
`
`
`
`
`stored in local memory toretrieve the encrypted index(es) 28
`
`
`
`
`
`
`
`
`from the cloud storage provider 18 at which it was stored
`
`
`
`
`
`
`
`
`
`using the second communication links 22. For example, in the
`
`
`
`
`
`
`
`exemplary embodiment of FIG. 3,
`the broker server 12
`
`
`
`
`
`
`
`
`
`retrieves encrypted indexes E11, E12 and E13. The broker
`
`
`
`
`
`
`
`
`
`
`server 12 then appliesthe specific test functionfor the search-
`
`
`
`
`
`
`
`able encryption mechanism to the encrypted indexes, which
`
`
`
`
`
`
`
`
`
`returns identifiers (e.g. D1, D2, D3, etc.) of the one or more
`
`
`
`
`
`
`
`
`encrypted documents 14 that satisfy the encrypted query 30.
`
`
`
`
`
`
`
`
`For example, in the exemplary embodimentof FIG.3, the test
`function returns identifier D2. The broker server 12 uses the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`translation table T1, which is stored in local memory, to look
`
`
`
`
`
`
`
`
`up the identifier(s) returned bythetest function (e.g. D2) and
`
`
`
`
`
`
`then retrieves the corresponding encrypted document(s) 14
`
`
`
`
`
`
`
`from the storage providers 18 according to standard methods
`
`
`
`
`
`
`
`
`(e.g. using the storage provider’s application program inter-
`
`
`
`
`
`
`
`
`
`face) over the second communication link(s) 22. The broker
`
`
`
`
`
`
`
`server 12 then returnstheretrieved encrypted document(s) 14
`
`to the client 16 over the first communication link 20. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`client 16 may then unencrypt the encrypted document(s) 14
`
`
`
`
`
`
`
`
`
`
`since the client 16 knows the encryption that was used to
`
`
`
`
`initially encrypt the document26.
`
`
`
`
`
`
`
`
`[0037] Thus, the broker server 12 allowsclients 16 to store
`
`
`
`
`
`
`
`encrypted (i.e. secure) documents 14 on cloud storage pro-
`
`
`
`
`
`
`
`viders 18 by providing searchable encryption that enables the
`
`
`
`
`
`
`
`clients 16 to search andretrieve the encrypted documents 14.
`
`
`
`
`
`
`
`
`In order to provide the searchable encryption, the broker
`
`
`
`
`
`
`
`
`
`server 12 needsto locally store only the translation table T1,
`
`
`
`
`
`
`
`
`the translation table T2 (or the encrypted index(es) 28), and
`
`
`
`
`
`
`
`
`
`the test function for the at least one searchable encryption
`mechanism.
`
`
`
`
`
`
`
`[0038] Additionally, the broker server 12 may act as an
`
`
`
`
`
`aggregator of searchable encryption mechanisms to support
`
`
`
`
`
`
`many different searchable encryption mechanismsby storing
`
`
`
`
`
`
`
`
`test functions for the many different searchable encryption
`
`
`
`
`
`
`
`
`mechanismsin local memory. The clients 16 may then select
`
`
`
`
`
`
`
`
`which searchable encryption mechanism bestsuits their secu-
`
`
`
`
`
`
`
`
`
`rity needs when using the brokerserver 12 to store encrypted
`
`
`
`
`
`documents 14 on cloud storage providers 18.
`
`
`
`
`
`
`
`[0039] Referring to FIG. 4, in embodiments, the broker
`
`
`
`
`
`
`
`
`server 12 may also provide redundancy whenstoring data
`
`
`
`
`
`
`
`from clients 16 by storing specific encrypted documents 14,
`
`
`
`
`
`
`
`
`
`encrypted indexes 28, or parts thereof, on multiple cloud
`
`
`
`
`
`storage providers 18 to guarantee availability of the stored
`
`
`
`
`
`
`
`
`
`data, particularly in case there are defects at one or more
`
`
`
`
`
`
`
`
`storage providers 18. For example, in embodiments, the bro-
`
`
`
`
`
`
`
`ker system 10 may implementan error correcting code to
`
`
`
`
`
`
`
`correct defects of a particular storage provider 18 whentrans-
`
`
`
`
`
`
`
`
`ferring the encrypted documents 14 to the brokerserver 12, as
`
`
`
`
`
`
`
`
`
`should be understood by those skilled in the art, so that the
`
`
`
`
`
`
`
`
`data being stored on any particular storage provider 18 may
`
`
`
`
`
`
`be a function ofpart of a particular encrypted document. In
`
`
`
`
`
`
`
`the exemplary embodiment of FIG. 4, the broker server 12
`
`
`
`
`
`
`
`stores the encrypted document D1 on storage providers SP1
`
`
`
`
`
`
`
`
`
`and SP4 andstores the encrypted index E11 on storage pro-
`
`
`
`
`
`
`
`
`
`vider SP3 and SPS. In these embodiments, the broker server
`12 extends the translation table T1 and the translation table
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`T2, if the encrypted indexes 28 are being stored on storage
`
`
`
`
`
`
`
`
`providers 18, to encompass the case of several storage pro-
`
`
`
`
`
`
`
`viders 18 are storing the same encrypted documents 14 or
`
`
`
`
`
`
`
`
`indexes 28. Ifthe broker server 12 redundantly stores parts or
`
`
`
`
`
`
`portions of specific encrypted documents 14 and/or specific
`
`
`
`
`
`
`
`encrypted indexes 28 on different storage providers 18, the
`translation tables Tl and T2 should also be extended to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`include how theparts or portions of the specific encrypted
`
`
`
`
`
`
`
`
`documents 14 and/or specific encrypted indexes 28 are
`recombined.
`
`
`
`
`
`
`
`
`
`[0040] The broker server 12 may update the translation
`
`
`
`
`
`
`
`
`
`tables T1 and T2 at each action on the storage side (i.e. each
`
`
`
`
`
`
`
`
`time the broker server 12 stores another encrypted document
`
`
`
`
`
`
`
`
`14, encrypted index 28, or portion thereof, on one or more of
`
`
`
`
`
`
`
`
`
`the storage providers 18). For example,ifthe broker server 12
`
`
`
`
`
`
`determines that a particular storage provider 18 is defective,
`
`
`
`
`
`
`
`
`
`
`the broker module 12 maystore the data, or any portion
`
`
`
`
`
`
`
`
`thereof, that was stored on the defective storage provider 18
`
`
`
`
`
`
`
`on another storage provider 18 to maintain redundancy. The
`
`
`
`
`
`
`
`
`broker server 12 then updatesthe translation tables T1 and T2
`to reflect this modification.
`
`
`
`
`
`
`
`
`
`
`
`
`[0041] Although the broker server 12 has been described
`
`
`
`
`
`
`
`
`above as being separate from the storage providers 18 and in
`
`
`
`
`
`
`communication with a plurality of storage provider 18 over
`
`
`
`
`
`
`
`second communication links 22, in embodiments, the broker
`
`Page 8 of 11
`
`Netskope Exhibit 1006
`
`Page 8 of 11
`
`Netskope Exhibit 1006
`
`

`

`
`
`US 2014/0359282 Al
`
`
`Dec. 4, 2014
`
`
`
`
`
`
`
`
`
`
`
`
`server 12 may, itself, be a storage provider 18 and may pro-
`
`
`
`
`
`
`vide similar functionality to that discussed herein.
`
`
`
`
`
`
`
`
`[0042] The broker system 10 has the necessary electronics,
`
`
`
`
`
`
`software, memory, storage, databases, firmware, logic/state
`
`
`
`
`
`machines, microprocessors, communication links, displays
`
`
`
`
`
`
`
`
`
`or other visual or audio user interfaces, printing devices, and
`
`
`
`
`
`
`
`
`any other input/output interfaces to perform the functions
`described herein and/or to achieve the results described
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`herein. For example, the broker server 12 may includeat least
`
`
`
`
`
`
`
`one processor, system memory,
`including random access
`
`
`
`
`
`
`
`memory (RAM) and read-only memory (ROM), an input/
`
`
`
`
`
`
`
`
`
`output controller, and one or more data storage structures. All
`ofthese latter elements are in communication withtheatleast
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`one processorto facilitate the operation of the broker server
`
`
`
`
`
`
`
`
`12 as discussed above. Suitable computer program code may
`
`
`
`
`
`
`
`be provided for executing numerous functions,
`including
`those discussed above in connection with the broker server
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`12, client 16 and storage provider 18. The computer program
`
`
`
`
`
`
`
`
`code mayalso include program elements such as an operating
`
`
`
`
`
`
`
`system, a database management system and “device drivers”
`
`
`
`
`
`
`
`
`
`
`that allow the broker server 12, client 16 and storage provider
`
`
`
`
`
`
`
`
`18 to interface with computer peripheral devices (e.g., a video
`
`
`
`
`
`display, a keyboard, a computer mouse,etc.).
`
`
`
`
`
`
`
`[0043] The at least one processor of the broker server 12
`
`
`
`
`
`
`
`may include one or more conventional microprocessors and
`
`
`
`
`
`
`one or more supplementary co-processors such as math co-
`
`
`
`
`
`
`
`processorsorthe like. The processor may be in communica-
`
`
`
`
`
`
`
`
`tion with a communication interface unit, which may include
`
`
`
`
`
`
`
`multiple communication channels, e.g. the first communica-
`tion link 20 and the second communication link 22 for simul-
`
`
`
`
`
`
`