Executing SQL over Encrypted Data in Database-Service-Provider ModelWhat do we want to do?Why is it important anyway?Talk OutlineService Provider ArchitectureSlide 6Slide 7Relational EncryptionBuilding the Index: Partition and Identification FunctionsMapping FunctionsStoring Encrypted DataSlide 12Slide 13Mapping ConditionsMapping Conditions (2)Mapping Conditions (3)Slide 17Relational Operators over Encrypted RelationsSelection OperatorJoin OperatorSlide 21Slide 22Query DecompositionQuery Decomposition (2)Query Decomposition (3)Query Decomposition (4)Slide 27Slide 28Experimental EvaluationEffect of Number of Buckets in Non-Join QuerySlide 31Effect of Number of Buckets in Join QuerySlide 33ConclusionExecuting SQL over Encrypted Data in Database-Service-Provider ModelHakan HacigumusUniversity of California, IrvineBala IyerIBM Silicon Valley Lab.Chen LiUniversity of California, IrvineSharad MehrotraUniversity of California, IrvineSIGMOD 2002, Madison, Wisconsin, USA2What do we want to do?We want to store the data on “a server” UserEncrypted User DatabaseServerUser DataBut the problem is we do not trust “the server” for sensitive information!encrypt the data and store itbut still be able to run queries over the encrypted data do most of the work at the serverIf the server is trusted, ICDE 2002Distrusted3Why is it important anyway?Application Service Provider (ASP) Model for Database DB management transferred to service provider forbackup, administration, restoration, space management, upgrades etc.use the database “as a service” provided by an ASPuse SW, HW, human resources of ASP, instead of your ownUserEncrypted User Database(Distrusted) Application Service ProviderUser DataDistrusted ServerTalk OutlineService Provider ArchitectureHow to create Metadata: Relational Encryption and Storage ModelQuery Decomposition and Relational OperatorsQuery Decomposition – ExamplesExperimental ResultsConclusion5Service Provider ArchitectureEncrypted User DatabaseQuery TranslatorServer SiteTemporary ResultsQuery ExecuterMetadataOriginal QueryServer Side QueryEncrypted ResultsActual ResultsService ProviderUserClient SiteClient Side Query???Talk OutlineService Provider ArchitectureHow to create Metadata: Relational Encryption and Storage ModelQuery Decomposition and Relational OperatorsQuery Decomposition – ExamplesExperimental ResultsConclusionTalk OutlineService Provider ArchitectureHow to create Metadata: Relational Encryption and Storage ModelQuery Decomposition and Relational OperatorsQuery Decomposition – ExamplesExperimental ResultsConclusion8Relational EncryptionNAME SALARYPIDJohn 50000 2Marry 110000 2James 95000 3Lisa 105000 4etuple N_ID S_ID P_IDfErf!$Q!!vddf>></|50 1 10F%%3w&%gfErf!$ 65 2 10&%gfsdf$%343v<l50 2 20%%33w&%gfs##! 65 2 20Server SiteStore an encrypted string – etuple – for each tuple in the original table This is called “row level encryption”Any kind of encryption technique can be used Blowfish encryption algorithm is used for this workCreate an index for each (or selected) attribute(s) in the original table9Building the Index:Partition and Identification FunctionsPartition function divides domain values into partitions (buckets)Partition (R.A) = { [0,200], (200,400], (400,600], (600,800], (800,1000] }partitioning function has an impact on performance as well as privacy2000 400 600 800 10002 7 5 1 4Domain ValuesPartition (Bucket) idsIdentification function assigns a partition id to each partition of attribute A e.g. identR.A( (200,400] ) = 7Any function can be use as identification function, e.g., hash functions10Mapping FunctionsMapping function maps a value v in the domain of attribute A to the id of the partition which value v belongs toe.g. MapR.A( 250 ) = 7, MapR.A( 620 ) = 12000 400 600 800 10002 7 5 1 4Domain ValuesPartition (Bucket) ids11Storing Encrypted DataR = < A, B, C >  RS = < etuple, A_id, B_id, C_id >etuple = encrypt ( A | B | C ) A_id = MapR.A( A ), B_id = MapR.B( B ), C_id = MapR.C( C ) NAME SALARYPIDJohn 50000 2Marry 110000 2James 95000 3Lisa 105000 4Etuple N_ID S_ID P_IDfErf!$Q!!vddf>></|50 1 10F%%3w&%gfErf!$ 65 2 10&%gfsdf$%343v<l50 2 20%%33w&%gfs##! 65 2 20Table: EMPLOYEETable: EMPLOYEESTalk OutlineService Provider ArchitectureHow to create Metadata: Relational Encryption and Storage ModelQuery Decomposition and Relational OperatorsQuery Decomposition – ExamplesExperimental ResultsConclusionTalk OutlineService Provider ArchitectureHow to create Metadata: Relational Encryption and Storage ModelQuery Decomposition and Relational OperatorsQuery Decomposition – ExamplesExperimental ResultsConclusion14Mapping ConditionsQ: SELECT name, pname FROM emp, proj WHERE emp.pid=proj.pid AND salary > 100kServer stores attribute indices determined by mapping functionsClient stores metadata and utilizes that to translate the queryConditions:Condition  Attribute op ValueCondition  Attribute op AttributeCondition  (Condition  Condition) | (Condition  Condition) | (not Condition)15Mapping Conditions (2)Example:Attribute = ValueMapcond( A = v )  AS = MapA( v )Mapcond( A = 250 )  AS = 72000 400 600 800 10002 7 5 1 4Domain ValuesPartition Ids16Mapping Conditions (3)Attribute1 = Attribute2Mapcond( A = B )  N (AS = identA( pk )  BS = identB( pl ))where N is pk  partition (A), pl  partition (B), pk  pl   PartitionsA_id[0,100] 2(100,200] 4(200,300] 3PartitionsB_id[0,200] 9(200,400] 8C : A = B  C’ : (AS = 2  BS = 9)  (AS = 4  BS = 9)  (AS = 3  BS = 8)Talk OutlineService Provider ArchitectureHow to create Metadata: Relational Encryption and Storage ModelQuery Decomposition and Relational OperatorsQuery Decomposition – ExamplesExperimental ResultsConclusion18Relational Operators over Encrypted RelationsPartition the computation of the operators across client and serverCompute (possibly) superset of answers at the serverFilter the answers at the clientObjective : minimize the work at the client and process the answers as soon as they arrive without requiring storage at the clientOperators studied:SelectionJoinGrouping and AggregationSortingDuplicate EliminationSet DifferenceUnionProjection19Selection OperatorA=250TABLE2000