`
`
`as) United States
`
`
`
`
`
`
`
`
`
`a2) Patent Application Publication co) Pub. No.: US 2009/0300351 Al
`
`
`
`
`
`
`
`(43) Pub. Date: Dec. 3, 2009
`
`Lei et al.
`
`
`
`US 20090300351A1
`
`
`
`
`
`
`(54) FAST SEARCHABLE ENCRYPTION
`METHOD
`
`
`
`
`(75)
`
`
`
`Inventors:
`
`
`
`
`
`
`
`
`
`
`
`
`Hao Lei, Beijing (CN); Ye Tian,
`
`
`
`
`Beijing (CN); Ke Zeng, Beijing
`
`
`
`
`(CN); Liming Wang, Beijing (CN);
`
`
`
`Toshikaza Fukushima, Beijing
`
`(CN)
`
`
`Correspondence Address:
`
`
`
`SUGHRUE MION, PLLC
`
`
`
`
`2100 PENNSYLVANIA AVENUE, N.W., SUITE
`800
`
`
`
`
`WASHINGTON,DC 20037 (US)
`
`
`
`
`
`NEC (China) Co., Ltd., Beijing
`
`(CN)
`
`
`(73) Assignee:
`
`
`
`Publication Classification
`
`
`
`
`(51)
`
`
`
`
`
`Int. Cl.
`
`
`
`(2006.01)
`HOAL 9/00
`
`
`(2006.01)
`GO6F 17/30
`
`
`
`(2006.01)
`HOAL 9/08
`
`
`
`
`
`
`
`(52) US. Ch. eccccccccee. 713/165; 707/5; 380/44; 380/277;
`
`707/E17.014; 707/E17.032
`
`
`
`
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`
`The present invention provides a method, apparatus and sys-
`
`
`
`
`
`
`
`
`
`tem for fast searchable encryption. The data owner encrypts
`
`
`
`
`
`
`
`
`
`
`files and stores the ciphertext to the server. The data owner
`
`
`
`
`
`
`generates an encrypted index according to each keyword of
`
`
`
`
`
`
`
`
`
`
`the files, and stores the encrypted index to the server. The
`
`
`
`
`
`
`
`
`index is composed ofkeyworditem sets each being identified
`
`
`
`
`
`
`
`
`
`by a keyword item set locator and containing at least one or
`
`
`
`
`
`
`
`morefile locators of the files associated with the correspond-
`
`
`
`
`
`
`
`
`ing keyword. Each file locator contains ciphertext of infor-
`
`
`
`
`
`
`
`
`
`
`mation for retrieval of an encrypted file and only with the
`
`
`
`
`
`
`
`
`
`correct file locator decryption key can the ciphertext be
`
`
`
`
`
`
`
`
`decrypted. Data owner issues a keyword item set locator as
`
`
`
`
`
`
`
`
`well as file locator decryption key to a searcher to enable the
`
`
`
`
`
`
`
`
`searcher to search on the encrypted index andretrieve files
`
`
`
`related to a certain keyword.
`
`
`
`
`
`
`
`
`
`
`
`(21) Appl. No.:
`
`
`
`
`(22)
`
`Filed:
`
`(30)
`
`12/474,785
`
`May29, 2009
`
`
`
`Foreign Application Priority Data
`
`
`
`
`
`May 30, 2008
`(CN) wee ceeeeeeeeees 200810098359.1
`
`
`
`
`
`Aug. 1, 2008 (CN) eee 200810145083.8
`
`
`
`
`
`
`
`
`Page 1 of 27
`
`Netskope Exhibit 1016
`
`Page 1 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 1 of 13
`
`
`US 2009/0300351 Al
`
`
`
`
`e
`
`
`c—————— Storage
`Service
`Tj
`
`
`Alice
`
`
`
`
`
`
`Research.ppt
`
`Novel.paf
`
`
`Petsipg
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5 Relative
`
`Friend
`
`=5 Colleague
`
`
`
`
`Fig. 1
`
`Ez
`
`Searcher Terminal
`
`
`
`Communication
`
`Network
`
`
`
`
`
`
`
`
`
`
`
`Data Owner Terminal
`
`
`
`
`Searcher, Terminal
`
`
`
`
`Fig. 2
`
`Page 2 of 27
`
`Netskope Exhibit 1016
`
`Page 2 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 2 of 13
`
`
`US 2009/0300351 Al
`
`
`
`
`
`103
`
`
`
`
`
`
`
`
`
`
`
`Kieyword Unit
`KIS Locator Generation Unit
`
`
`104
`101
`
`
`
`
`
`
`
`
`
`
`Encryption/Decryption
`File Locator Generation Unit
`
`
`
`
`
`Setting Unit 102
`
`105
`
`
`
`
`
`
`
`
`File Encryption Unit
`Index Forming Unit
`
`
`106
`
`
`100
`
`LO J
`
`
`
`
`Fig. 3
`
`Start
`
`
`
`
`
`
`
`
`Set keywords
`
`
`
`
`5201
`
`$202
`
`
`
`
`
`
`
`203
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Set file encryption and decryption keys for eachfile
`
`
`
`
`
`
`
`
`Set file locator generation and decryption keys of each
`
`
`privacy level
`
`Encrypteachfile witha correspondingfile encryption key F 3204
`
`
`
`
`
`
`
`
`
`
`
`
`Generate an encrypted index
`
`torthe encrypted files and encrypted index on server
`° $206
`
`
`
`
`
`
`
`
`
`I|s
`
`
`
`
`
`
`
`End
`
`
`
`
`Fig. 4
`
`Page 3 of 27
`
`Netskope Exhibit 1016
`
`Page 3 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 3 of 13
`
`
`US 2009/0300351 Al
`
`
`
`
`
`Generate a KIS locator for each keyword
`
`
`
`
`
`
`
`
`$301
`
`
`
`
`
`
`
`
`
`
`
`
`
`$302
`For each file, generate one or morefile locators by encryptfile
`
`
`
`
`
`
`
`
`
`acquisition information with one or more file locator generation keys>~~~
`
`
`
`
`
`
`
`
`
`of one or more privacy levels at which the file is revealable
`
`
`
`
`
`
`
`
`
`
`
`
`
`Form a KIS for each keyword by a corresponding KIS locatorandall|<$303
`
`
`
`
`
`
`file locators offiles related to the keyword
`
`
`
`
`
`Form encrypted index by all KISes
`
`$304
`
`
`Fig. 5
`
`Page 4 of 27
`
`Netskope Exhibit 1016
`
`Page 4 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 4 of 13
`
`
`US 2009/0300351 A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`S[aAd]ADRACJog
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (Ty)loye90]SPYsye1909H)
`
`
`
`uondAOUdJayseyy]
`
`poidAroug fea a a eea ee ee ee eer een
`ydAroug <My01poreporstS77{Tt}2TY>
`age}Surddeyy Ora)40%
`
`
`
`
`
`(Mayq/“Aayy:uijadaz}
`
`ue‘nySIOJCIOTSTHsyeIOUSL)
`
`SDoesouan
`
`xepuy]
`
`
`
`{<{""T}!Ty>}
`
`ayyArana
`
`
`
`[eUTULIAT,JOUMOBe
`
`
`
`foondAérouso]Ly
`
`
`
`shayuondAroop
`
`Page 5 of 27
`
`Netskope Exhibit 1016
`
`Page 5 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 5 of 13
`
`
`US 2009/0300351 Al
`
`
`
`
`
`
`
`
`
`
`
`
`Storage Unit
`
`401
`
`
`
`
`
`Index Search Unit
`
`402
`
`
`
`
`
`File Search Unit
`
`403
`
`
`
`
`
`
`
`
`Fig. 7
`
`
`
`
`
`Search Request Unit
`
`SO1
`
`
`
`
`
`
`File Locator Decryption
`
`
`Unit
`502
`
`204
`
`
`
`File Acquisition Unit
`
`303
`
`
`
`
`
`File Decryption Unit
`
`
`
`
`
`
`
`Fig. 8
`
`Page 6 of 27
`
`Netskope Exhibit 1016
`
`Page 6 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 6 of 13
`
`
`US 2009/0300351 Al
`
`
`
`Start
`
`
`
`
`
`
`
`
`Data ownerissues a KIS locator and a file locator decryption
`
`
`key to searcher
`
`
`
`nNBPel
`
`
`
`
`
`
`
`
`
`Searcher send a search request containing a KIS locator to|—~$602
`
`server
`
`
`
`
`
`
`
`Server locates corresponding KIS in the encrypted index
`
`
`
`
`
`
`
`ea iioKao
`
`
`
`
`
`
`
`
`
`
`
`
`Server sendsfile locators contained in the KIS to searcher
`
`
`
`
`
`
`
`
`
`
`
`
`Searcher decrypts the file locators to derive encrypted
`
`
`
`
`
`
`resource identifiers and correspondingfile decryption keys
`
`
`
`
`
`
`
`
`Searcher sendsa file acquisition request containing
`
`
`
`
`encrypted resource identifiers to server
`
`
`
`
`
`
`
`CanNoOtla
`
`8606
`
`
`
`
`
`
`
`
`
`
`
`
`Server locates and sendsthe encrypted files identified by the|<S607
`
`
`
`
`encrypted resource identifiers to searcher
`
`
`
`
`
`
`
`
`
`
`Searcher decrypts the encrypted files with the corresponding|<S608
`
`
`
`file decryption keys
`
`End
`
`
`
`
`Fig. 9
`
`Page 7 of 27
`
`Netskope Exhibit 1016
`
`Page 7 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`
`Dec. 3, 2009 Sheet 7 of 13
`
`
`US 2009/0300351 A1
`
`
`
`
`
`Patent Application Publication
`
`lLnewweeeneeeeeeweeeeeeeeeenaeeeeeaaeenneeeeeeenee4
`
`FOAIOS
`
`oqyperdAroug
`
`
`
`
`
`sorypaydArougxaputpaydAsoug
`
`LOJLOOTSTYBurpoyewvBSulaeySpyoe90°]
`
`
`
`
`
`XOpulpoydAr9U9sy]UI
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`soySuryoyeyy
`
`
`
`
`
`7x9}UreydutuondAs190(]SIL]
`
`
`
`jeuTuLay,Joyoreag
`
`
`
`uondAoepa]Ly
`
`Ay
`
`IMpiomAayArand
`
`S,JOYOIBASSBJOASe
`
`Ayuapt
`
`IOUMCBe
`
`(“dayMaya:ui
`
`
`
` jada}!aquiSurddepy!a[euUTULIAT,
`
`Page 8 of 27
`
`Netskope Exhibit 1016
`
`Page 8 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`xapulpedAroug
`
`
`
`
`PesceesseesPESOSE5888FSCOF866OBROSeESSdaCODOeMCSEOOSSEReTFEFTEBABOOOCOPOFFCOPEESSBOOSPSeMeEcoreFFeaseEoOMeoseosSosSeeSaaenecooa@aesos
` TOUSMA
`
`
`
`sayypoyoreyy
`
`3X9}Uleyduw
`
`isey=sey
`
`
`
`
`
`
`
`uondéroapAqndingSJOJBOO]OL
`
`oy
`
`
`
`MLNplomAayAlong)
`
`$,JOYaIeOsSe[JOMSe
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10jJeOO]SPYBunpoyewvBBulavygpyaye007T
`
`
`
`
`
`xapulpaidArouaoy}ut
`
`SeyAyquept!
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 8 of 13
`
`
`
`
`
`PSRseeOOSOEOEOeREODOOEECOOOROSEOMOEESOAPeeeSTCOOBOOREsoeHeeBeemODAOe@eeseecoeWPcccmeesofooweeeenomedomesoosenoas°54
`
`
`US 2009/0300351 A1
`
`
`
`TY=V BeeBORRRSSSSASSMANSTSHOSCEHESSSSHDAESASAISSOTA
`SOARESTAHDOOTEARAOEPeonenenemaaanofOEOADODDODPeOMRawmeOo
`2192)Surddey“ayaa
`
`
`
`
`
`
`
`(“dayq/*dayy:utjanay}
`
`
`
`Page 9 of 27
`
`Netskope Exhibit 1016
`
`Page 9 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`
`
`
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 9 of 13
`
`
`US 2009/0300351 Al
`
`
`
`
`
`
`
`
`
`Keyword Unit
`
`101
`
`
`
`
`KIS Locator Generation Unit
`
`104
`
`
`
`
`
`
`
`
`Encryption/Decryption
`File Locator Generation Unit
`
`
`
`
`105
`Setting Unit
`102
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`File Encryption Unit
`
`103
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Index Forming Unit
`
`106
`
`
`
`
`
`Index Locator Generation Unit
`
`702
`
`
`
`
`Index Locating Indicator
`
`
`
`Generation Unit
`701
`
`
`
`00
`
`
`Fig. 12
`
`Page 10 of 27
`
`Netskope Exhibit 1016
`
`Page 10 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 10 of 13
`
`
`US 2009/0300351 A1
`
`
`
`
`
`ee ee we a aee ee ee ew eee ene
`
`Joyeo0]OI}188
`
`
`
`a1qe1suriddeyy
`
`“TT
`
`wf:WA;:<“fayq/Aayy+ulSI0}L90]O]TJo1eIaUIADjaaay>
`
`
`
`
`sXoyuondA1ap/uoreloues
`
`(Ty)Jows0]SPYs1eIETEH
`
`
`Peeeaafaeeaaeeaweeeemnmeeeeeemeeeeeeeeeemeeweeeeeeeee
`
`poydArougq
`
`{<{“lqTTT}!Tx} xapuy
`
`
`
`
`
`S10}B90TXOputSyBIOUOL)
`
`wy
`
`
`
`SplOMADYJORUXY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`wondAIsap/aondArousofl
`
`
`
`STIyoua10yshox
`
`Jase]
`
`
`
`AoyuondAisua
`
`Cy)
`
`1
`
`t
`
`;
`
`Page 11 of 27
`
`Netskope Exhibit 1016
`
`Page 11 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`
`
`

`

`
`
`Patent Application Publication
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 11 of 13
`
`
`US 2009/0300351 Al
`
`
`
`
`
`
`
`
`
`
`
`File Search Unit
`
`403
`
`
`
`
`
`Index Updating Unit
`
`
`
`
`
`
`
`Storage Unit
`
`401
`
`
`
`
`
`Index Search Unit
`
`402
`
`
`
`
`Fig. 14
`
`
`
`
`
`
`
`
`
` Receive an index locating indicator from data owner
`computed from the received index locating indicator
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Find out file locators having the same index locatoras that
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Update the index by deleting the matching file locators as
`
`
`
`
`well as corresponding index locators
`
`|
`
`
`End
`
`
`Fig. 15
`
`Page 12 of 27
`
`Netskope Exhibit 1016
`
`Page 12 of 27
`
`Netskope Exhibit 1016
`
`

`

`Pott tc ee ewes cee co meme es oes Bases o ees sas BSCS eRe eS
`
`
`
`
`
`ScocncocessecogoCobGeesBSSeseGaNBoweooEsecacemaseemoneeaseseeebeeoenoelesO68B86DERESEEEABOADeCTOROAMESSGONFOODSSesBsMaassooDoofous
`
`
`
`
`
`
`Dec. 3, 2009 Sheet 12 of 13
`
`
`US 2009/0300351 A1
`
`
`
`
`
`
`
`aypoidArous9]9]/9q
`
`NADAqpoynuap!
`
`pours);
`
`
`
`SO[I}PoydArouS
`
`SIIwoy“97pue“7.7ayspoq
`
`MP=!LTT
`
`
`
`dxrsugC4"“qlzy)usey="77SOTPet
`
`aindwios™f7,7pue"TyyoRe10,4
`
`
`
`xepuypoydApug
`
`TyTTT}ETI>
`
`Page 13 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`vf
`
`‘Uttttt6é‘‘i t0008E4péeaai'1444aa48aa10ap0a04ataaD0000aq00t&4a4a4aDD000v0a1‘
`
`44aaaD0'6:4a414584a513‘:é'‘i2tt5a0aa0aaaaa‘‘111tt5Q'''
`
`poussmocacessecaenam
`
`
`
`
`
`(x)JoyeorputSuyeoo]xeputayndurog(ys)Koyyo199g
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[EUTULID]JOUMOBIEq
`
`
`
`
`
`Patent Application Publication
`
`Page 13 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`
`
`
`

`

`
`
`
`
`
`Dec. 3, 2009 Sheet 13 of 13
`
`
`US 2009/0300351 A1
`
`
`
`''1541i1'a1|||t41 '‘i1‘)ttfiI|l''i11'it'11|l|l' t 11'tt‘1tti111|11'‘i111‘ii1l11'|i'11'1i'11q1tt15i‘' ‘1111 '1iE'11t'‘11i',111'i
`
`NAD£qpoynnept
`
`=“177Tt
`
`
`s[ypoydAsousajojoq
`Mywag“77pue“17.7oy[9d
`
`
`soytypardArouq(x|"
`
`qallE)usey=".77
`
`paataoalAqpalyuoptSTyyoreUy
`
`
`
`aynduios“Ty
`
`
`
`xopuypoydéroug
`
`eyeTT}ETD
`
`eeeeekeeewenreeeneeoeaeoeeenemeeeeeeenm
`
`
`
`
`
`Suyes0]xoputajnduoa
`
`
`
`(x)Joyeorput
`
`Ady3210235
`MN40}*TYJOSV
`
`(75)
`
`NAO9}payee
`
`
`
`
`
`[eUTULI}JOUMOBIE
`
`
`
`wememenneeebeeoeeeeeSeoeeOPOESSEesoeReAnCOROSMMCdoceeeeeeeemeeeeeeeCeeweeeePgSSSeeeRECSOOOMEeamSSeS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`eo
`
`Page 14 of 27
`
`Netskope Exhibit 1016
`
`POR ee rm a ew ee mR eR mememe
`
`
`
`Patent Application Publication
`
`
`
`mesocomeeeSeOMOoOCODERRODDP88PSOEDEMEEOOOSTEBMOSSSCSSaSOSPESOoheESOoPeeFeBPOCORSEOSoeReeESHAGSMDSODOSRoEDeesoOTOSSONOSmMeamaaoneenS
`
`Page 14 of 27
`
`Netskope Exhibit 1016
`
`
`
`
`
`
`
`
`

`

`
`
`
`US 2009/0300351 Al
`
`
`Dec. 3, 2009
`
`
`
`FAST SEARCHABLE ENCRYPTION
`
`
`METHOD
`
`
`
`
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`[0001] The invention relates generally to information
`
`
`
`
`
`
`
`retrieval techniques, and moreparticularly to a method, appa-
`
`
`
`
`
`
`
`ratus and system for fast searchable encryption.
`
`BACKGROUND
`
`
`
`
`
`
`
`potentially semi-trusted server needs to know decryption
`
`
`
`
`
`
`
`keys, and the latter compromises performance because of
`
`
`
`hugedata transfers.
`
`
`
`
`
`
`
`[0008] A solution called “ciphertext global search technol-
`
`
`
`
`
`
`ogy” is proposed by Xin Li in Chinese patent application
`
`
`
`
`
`
`
`publication No. CN1588365A.In the ciphertext global search
`
`
`
`
`
`
`
`technology, during an indexing phase, a data ownercreates an
`
`
`
`
`
`
`
`
`
`index forall files firstly; then encrypts keywords in the index
`
`
`
`
`
`
`
`
`
`
`using a key yielding cipher index, encrypts the files using the
`
`
`
`
`
`
`
`
`
`
`
`same key yielding encryptedfiles, and encrypts the key with
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a public key; lastly, the data ownerstores the cipher index,the
`[0002] With wide use of network and communication tech-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted files, and the encrypted key to the storage server.
`nique, data storage and managementservices become popu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`During a searching phase, the data ownerfirstly downloads
`lar. In somesituations, user stores some, even massive, data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the encrypted key from the storage server and decryptsit with
`on a remote server(s) maintained by a third party storage
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a private key that correspondsto the public key before search-
`vendor for various reasons, for example,
`limited storage
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing; secondly, the data owner encrypts a querying keyword
`capacity at the user’s terminal,
`incapability of providing
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`with the key, and sends the encrypted keywordto the storage
`stable or long time continuous access of data at the user’s
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`server;thirdly, the storage server looks up the cipher index for
`terminal, cost of data maintenance in view ofthat the cost of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the same encrypted keyword;
`fourthly,
`the data owner
`storage managementis generally 5-10 times higher than the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`retrieves the encryptedfiles according to the matchingresults
`cost of initial acquisition of data, and so on.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and decrypts them with the key. If the data owner wants to
`[0003] However, most third party storage vendors do not
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`authorize a searcher to search on the cipher index and
`provide strong assurances of data confidentiality and integ-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encryptedfiles, he encrypts the key with the public key ofthe
`rity. If sensitive data is being stored on a storage server main-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`intended searcher and sends the encrypted key to the searcher.
`tained by a semi-trusted third party, a security system is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[0009] With such solution, the data owneruses one single
`needed to offer assurances of data confidentiality and access
`
`
`
`
`
`
`
`
`
`
`
`key to encrypt all the files. File encryption in most cases
`pattern privacy.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`utilizes stream cipher. However, encrypting more than one
`[0004] FIG.1illustrates a scenario in which Alice, a data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`file with a single key is known as an insecure approach. In
`owner, outsources her files to a semi-trusted third party,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`addition, the data owner uses the same key to encryptall the
`namely the storage service provider, and shestill intends to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`files and all the keywords. Thus, a searchercanretrieve all the
`share some files with specific searchers, e.g. her friends,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`data owner’s files ifthe searcher ever performsa search of any
`colleagues, and/orrelatives. In other words, she would like to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`keyword on the data owner’s files. So, the above-mentioned
`let the searchers search directly her files on the storage ser-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ciphertext global search technology cannot well ensure secu-
`vice, instead of issue queries to Alice herself. On the other
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`rity in the application shown in FIG.1.
`hand, Alice wants to define and enforce access rights on the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sharedfiles. In the example shownin FIG.1, Alice wouldlike
`[0010] Another solution which is more complex is pro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`to make the files Novel-pdf, Pets.jpg and Financial.doc
`posed by D. Boneh, G. D. Crescenzo, R. Ostrovsky, G. Per-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`searchable and accessible by herrelatives, but otherfiles blind
`siano, “Public Key Encryption with Keyword Search”, Euro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to her relatives. Similarly, Alice wouldlike to make somefiles
`Crypt 2004; and R. Curtmola,
`J. Garay, S. Kamara,
`
`
`
`
`
`
`
`
`
`
`
`
`
`searchable and accessible by her friends and colleagues
`“Searchable Symmetric Encryption: Improved Definitions
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and Efficient Constructions”, CCS 2006. With such solution,
`respectively, but other files not. To archive this goal, data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`security and access control measures are needed.
`during an indexing phase, a data ownerfirstly chooses some
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Since the storage service provideris semi-trusted,it
`[0005]
`special fields in the files (such as the keyword “urgent”in an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is required that Alice’s files are all encrypted andthe storage
`email) to create an index. To be concretely, for each file, the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`service provider cannot disseminate file decryption keys to
`data owner encrypts special keywords. For example, <A=g’,
`
`
`
`
`
`
`
`
`
`
`
`
`
`the searchers. Furthermore, Alice may notrely on the storage
`B=H,(e(H, (KW),h’)> is an “encrypted keyword”, where KW
`
`
`
`
`
`
`
`
`
`
`
`
`service provider to enforce access control onherfiles.
`isakeyword, e: G,xG,->G,, gis a generator ofG,, H, and H,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`are twodifferent hash functions, r is a random numberin Z*,,,
`In view of the abovesituation, there are following
`[0006]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`his equalto g”, x is secret key andalso in Z*,,. Thus, the secure
`challenges: how to enable the searchers to search and further
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`index is composedofa set of tuples, the form ofthe i-th tuple
`accessthe files; how to disseminate file decryption keysto the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is <ciphertext,: (A,,B,), ...,(A,,,B,,)>, where ciphertext,is the
`searchers; how to distinguish different file access rights with
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ciphertextofFile, encryptedwith thefile encryption key Ky,,,.
`respectto different searchers; how to maintain the service ifa
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`During a searching phase, the data ownerfirst authorizes a
`file is updated or removed; and how to make the solution
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`searcher to query keyword by computing and issuing to the
`efficient in terms of computation and communication con-
`
`
`
`
`
`
`searcher a trapdoor for a keyword KW as T,,=H,*(KW).
`sumption.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Then, the searcher submits T,.,,to the storage server. For each
`[0007] The ability to search easily and efficiently within
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted keywordofeach file, the storage server computes
`remote data is a very important feature. Someefficient con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B'=H,(e(Tz,, A)) to test whether the file contains KW.If
`tent-based keyword search indexing schemesexist up to date.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B=B', the encryptedfile is a matching output, and vice versa.
`However, supporting content-based search with privacy in a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`If the searcher wants to decrypt the encrypted file, another
`secure remote storage is difficult, and often tends to compro-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`round-trip with the data owneris necessary to fetch the cor-
`mise either security or performance significantly. For
`
`
`
`
`
`
`
`
`
`responding decryption keys.
`example, if data is stored in an encrypted form on a remote
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`server, to perform content-based search, one cannotafford to
`[0011] With the above solution, the computation complex-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`decryptit at the server nortransfer the bulk of encrypted data
`ity that the storage server spends on searching is O(mxn),
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to the client. The former compromises security since the
`where m is the numberoffiles, n is the average number of
`
`Page 15 of 27
`
`Netskope Exhibit 1016
`
`Page 15 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`
`US 2009/0300351 Al
`
`
`Dec. 3, 2009
`
`
`
`
`
`
`
`
`
`
`
`
`distinct keywordsin eachfile. For instance, given 1000files
`
`
`
`
`
`
`
`and 10 keywords, it requires 30 seconds per search on the
`
`
`
`
`
`
`
`storage server equipped with 8 CPUs. Another disadvantage
`
`
`
`
`
`
`
`
`
`
`of such solution is that after the storage server returns match-
`
`
`
`
`
`
`
`
`
`
`ing results, i.e. encrypted files that contain the keyword, the
`
`
`
`
`
`
`
`
`
`searcherhas to contact the data ownerfor the decryption keys
`
`
`
`of the encryptedfiles.
`
`
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`[0012] The present invention is made in view ofthe prob-
`
`
`
`
`
`
`
`
`
`lems in the prior art and provides a method, apparatus and
`
`
`
`
`system for searchable encryption.
`
`
`
`
`
`
`
`
`[0013] With the novel fast searchable encryption solution
`
`
`
`
`
`
`according to the invention, one or more of the following or
`
`
`
`
`
`
`
`
`other important security dimensions are provided for out-
`
`
`
`
`
`
`
`
`sourced storage with semi-trusted storage servers in the con-
`text of advanced content-based search:
`
`
`
`
`
`
`
`
`
`
`
`
`[0014] Confidentiality—The data being stored on the
`
`
`
`
`
`
`
`server is not decipherable either during client-servertransit,
`
`
`
`
`
`
`
`or at the server side, even by a malicious server.
`
`
`
`
`
`
`
`[0015]
`Privacy of search—The keyword concernedin the
`
`
`
`
`
`
`
`
`search as well as the privacy level of the searcher will not be
`
`
`
`
`
`
`
`revealed to the server throughout the process of the search.
`
`
`
`
`
`
`[0016] Multi-level retrieval—Every specific searcher can
`
`
`
`
`
`
`
`only obtain files revealable at his/her privacy level.
`
`
`
`
`
`
`
`[0017] Confirmable decryption—Searchers are able to
`
`
`
`
`
`
`
`confirm the correctness of decryption of encrypted item in the
`
`
`
`
`index performedat searcherside.
`
`
`
`
`
`
`
`
`
`[0018] Virtual deletion. The server can screen out deleted
`
`
`
`
`
`
`
`
`encrypted files from the search result to be provided to the
`
`
`
`
`
`
`
`
`searcher. The updating ofthe index after file deletion may be
`
`
`
`
`
`
`
`
`performed later with lower frequency and reduced influence
`on the service.
`
`
`
`
`
`
`
`
`
`
`
`[0019] Locating itemsin the encrypted index—theserveris
`
`
`
`
`
`
`
`provided with a capability of locating a file locator related to
`
`
`
`
`
`
`
`
`
`a specific file in the index with help of an additional param-
`eter.
`
`
`
`
`
`
`
`
`[0020] Updating of the encrypted index—the encrypted
`
`
`
`
`
`
`
`
`
`index can be fast updated to add or delete items about added
`or deleted files.
`
`
`
`
`
`
`
`
`[0021]
`Fine-grained authorization—the authorization of
`
`
`
`
`
`
`
`
`search may be controlled in accordance with not only privacy
`
`
`
`
`levels but also keywords.
`
`
`
`
`
`[0022] Chained authorization—a searcher at any privacy
`
`
`
`
`
`
`level is able to search on the files dominatedat his/her privacy
`
`
`
`
`
`
`
`level, anda higherprivacy level will dominate a lowerprivacy
`level.
`
`
`
`
`
`
`
`[0023] According to one aspectof the invention, a method
`
`
`
`
`
`
`for searchable encryption is provided, comprising: setting
`
`
`
`
`
`
`
`
`one or morefile locator generation keys; generating one or
`
`
`
`
`
`
`
`
`more keyworditem set locators by mapping a string contain-
`
`
`
`
`
`
`
`ing at least a keyword to a unique value; generating one or
`
`
`
`
`
`
`
`morefile locators by encrypting file acquisition information
`
`
`
`
`
`
`
`
`
`of each of a plurality of files with at least one file locator
`
`
`
`
`
`
`
`generation key; and forming an encrypted index by one or
`
`
`
`
`
`
`
`
`more keyword item sets each being identified by a keyword
`
`
`
`
`
`
`
`
`
`item set locator and containing at least one or morefile loca-
`
`
`
`
`
`
`
`tors ofthe files associated with the corresponding keyword.
`
`
`
`
`
`
`
`[0024] According to another aspect of the invention, an
`
`
`
`
`
`
`apparatus for searchable encryption is provided, comprising:
`
`
`
`
`
`
`
`an encryption/decryption setting unit configured to set one or
`
`
`
`
`
`
`
`
`morefile locator generation keys; a keyword item set locator
`
`
`
`
`
`
`
`generation unit configured to generate one or more keyword
`
`
`
`
`
`
`
`item set locators by mapping a string containing at least a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`keyword to a unique value; anda file locator generation unit
`
`
`
`
`
`configured to generate one or morefile locators by encrypting
`
`
`
`
`
`
`file acquisition information of each ofa plurality offiles with
`
`
`
`
`
`
`
`
`
`at least onefile locator generation key; and an index forming
`
`
`
`
`
`
`unit configured to form an encrypted index by one or more
`
`
`
`
`
`
`
`
`keyword item sets each containing at least a keyword item set
`locator and one or morefile locators of the files associated
`
`
`
`
`
`
`
`
`
`
`
`
`with the corresponding keyword.
`
`
`
`
`
`
`[0025] According to yet another aspect of the invention, a
`
`
`
`
`
`
`
`methodused in encryptedfile search is provided, comprising:
`
`
`
`
`
`
`
`storing an encrypted index comprising one or more keyword
`
`
`
`
`
`
`
`
`
`item sets, each keyword item set being identified by a key-
`
`
`
`
`
`
`
`
`
`word item set locator and containing at least one or morefile
`
`
`
`
`
`
`locators each accompanied by an index locator; receiving an
`
`
`
`
`
`
`
`
`index locating indicator; and deleting a file locator from a
`
`
`
`
`
`
`
`
`
`keyword item set if the index locator accompanyingthe file
`
`
`
`
`
`
`
`locator equals to a value calculated by mapping a string
`
`
`
`
`
`
`
`
`
`
`containingat least thefile locator, the keyword item set loca-
`
`
`
`
`
`
`
`
`
`
`tor identifying the keyword item set and the received index
`
`
`locating indicator.
`
`
`
`
`
`
`[0026] According to yet another aspect of the invention, an
`
`
`
`
`
`
`
`apparatus usedin encryptedfile search is provided, compris-
`
`
`
`
`
`
`
`ing: a storage unit configured to store an encrypted index
`
`
`
`
`
`
`
`
`comprising one or more keyword item sets, each keyword
`
`
`
`
`
`
`
`
`
`item set being identified by a keyword item set locator and
`
`
`
`
`
`
`
`
`containing at least one or morefile locators each accompa-
`
`
`
`
`
`
`
`
`nied by an index locator; and an index updating unit config-
`
`
`
`
`
`
`
`
`
`ured to delete a file locator from a keyword item set if the
`
`
`
`
`
`
`
`index locator accompanyingthefile locator equals to a value
`
`
`
`
`
`
`
`calculated by mapping a string containing at least the file
`
`
`
`
`
`
`
`
`
`locator, the keyword item set locator identifying the keyword
`
`
`
`
`
`
`
`item set, and a received index locating indicator.
`
`
`
`
`
`
`
`[0027] According to another aspect of the invention, a
`
`
`
`
`
`
`
`method for encrypted file search is provided, comprising:
`
`
`
`
`
`
`
`
`
`receiving a keyword item set locator anda file locator decryp-
`
`
`
`
`
`
`
`
`
`tion key;retrieving one or morefile locators with the keyword
`
`
`
`
`
`
`
`
`
`
`item set locator; decrypting each file locator with the file
`
`
`
`
`
`
`
`locator decryption key to derive one or more encrypted
`
`
`
`
`
`
`
`resource identifiers and corresponding file decryption keys;
`
`
`
`
`
`
`
`
`retrieving one or more encryptedfiles identified by the one or
`
`
`
`
`
`
`
`more encrypted resource identifier; and decrypting each
`
`
`
`
`
`
`
`
`encrypted file with the correspondingfile decryption key.
`
`
`
`
`
`
`
`[0028] According to another aspect of the invention, an
`
`
`
`
`
`
`
`apparatus for encryptedfile search is provided, comprising: a
`
`
`
`
`
`
`
`search request unit configured to generate a search request
`
`
`
`
`
`
`
`
`containing at least a keyword item set locator; a file locator
`
`
`
`
`
`
`
`
`decryption unit configured to decrypt one or more file loca-
`
`
`
`
`
`
`
`
`
`tors with a file locator decryption key to derive one or more
`
`
`
`
`
`
`
`encrypted resourceidentifiers and correspondingfile decryp-
`
`
`
`
`
`
`
`
`tion keys; a file acquisition unit configuredto retrieve one or
`
`
`
`
`
`
`
`more encryptedfiles identified by the one or more encrypted
`
`
`
`
`
`
`
`resource identifier; and a file decryption unit configured to
`
`
`
`
`
`
`
`
`decrypt each encrypted file with the corresponding file
`
`
`decryption key.
`
`
`
`
`
`
`
`
`[0029] This invention enables the data owner to apply
`
`
`
`
`
`
`
`attribute-based and multi-level retrieval on the encrypted
`inverted index. All data and associated meta-data are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`encrypted at the data owner side using encryption, before
`
`
`
`
`
`
`
`
`
`being sent to the server. The data remains encrypted through-
`out its lifetime at the server. To enable content-based search
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`on encrypted data, any storedfiles are indexed securely in the
`
`
`
`
`
`
`
`
`
`
`indexing phase at the data owner’s site. This results in the
`
`
`
`
`
`
`
`confidential storage of the index structuresat the server side,
`available for future secure client access. Virtual deletion is
`
`
`
`
`
`
`
`
`
`Page 16 of 27
`
`Netskope Exhibit 1016
`
`Page 16 of 27
`
`Netskope Exhibit 1016
`
`

`

`
`
`
`US 2009/0300351 Al
`
`
`Dec. 3, 2009
`
`
`
`
`
`
`
`
`
`
`
`assured through filtering in the search result. Multi-level
`
`
`
`
`
`
`retrieval is achieved by limitation and the deployment of
`
`
`
`
`
`
`
`decryption keys corresponding to the searchers, either in
`
`
`
`
`
`
`accordance with the privacy level or keywords.
`
`
`
`
`
`
`
`[0030] The invention adopts efficient search algorithms so
`
`
`
`
`
`
`
`
`as to scale the search to a large number of documents and
`
`
`
`
`
`
`
`keywords. Bythis invention, the searching time is O(log(N))
`
`
`
`
`
`
`
`
`
`to O(1) where N is the numberoftotal distinct keywordsin the
`
`
`
`
`
`
`
`
`whole setoffiles. Therefore, comparedto the prior art which
`
`
`
`
`
`
`
`
`requires O(mxn), this invention provides an efficient and
`viable solution.
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`
`
`[0031] The present invention will be better understood
`
`
`
`
`
`
`
`
`from the following detailed description of the preferred
`
`
`
`
`
`
`embodiments of the invention, taken in conjunction with the
`
`
`
`
`
`
`accompanying drawings in which like reference numerals
`
`
`
`
`
`refer to like parts and in which:
`
`
`
`
`
`
`[0032]
`FIG. 1isa diagram illustrating an example of use of
`
`
`storage service;
`
`
`
`
`
`
`FIG. 2 is a diagram schematically illustrating an
`[0033]
`
`
`
`
`
`example of configuration ofthe system in which the invention
`
`
`is applied;
`
`
`
`
`
`
`[0034]
`FIG. 3 is a block diagram schematically illustrating
`
`
`
`
`
`
`
`
`an example of configuration of the data owner terminal
`
`
`
`
`according one embodimentof the invention;
`
`
`
`
`
`
`FIG.4 is a flow chart schematically illustrating the
`[0035]
`
`
`
`
`
`
`
`operation of the data owner terminal according to one
`
`
`embodimentof the invention;
`
`
`
`
`
`
`FIG. 5 is a flow chart schematically illustrating an
`[0036]
`
`
`
`
`
`
`
`example of process of generating the encrypted inverted
`
`
`
`
`
`