䝕䞊䝍䝧䞊䝇䛻䛚䛡䜛䝉䜻䝳䝸䝔䜱ᶵᵓ• ᪤Ꮡ䛾୺䛺ᡭἲ– 䝡䝳䞊– 䜰䜽䝉䝇ไᚚ୍ᑐከ䝬䝑䝢䞁䜾䛻ᇶ䛵䛟䝸䝺䞊䝅䝵䝘䝹䝕䞊䝍䝧䞊䝇䛾䝥䝷䜲䝞䝅䞊ಖㆤ᳨⣴• 䝴䞊䝄ㄆド• RBAC• ACL• …

ኳ➟ಇஅ– ᬯྕ໬⟃Ἴ኱Ꮫ䝅䝇䝔䝮᝟ሗ⣔• 䜽䝷䜴䝗䛻䛚䛡䜛䝕䞊䝍䝧䞊䝇– Database as a Service (DAS)➨81ᅇ▱ⓗ䝁䝭䝳䝙䝔䜱ᇶ┙◊✲䝉䞁䝍䞊◊✲ㄯヰ఍
2011ᖺ11᭶17᪥ (ᮌ) 14᫬䡚15᫬
12DAS䝰䝕䝹䛻䛚䛡䜛䝥䝷䜲䝞䝅䞊ಖㆤ᳨⣴᝿ᐃ䛥䜜䜛ᨷᧁ䝰䝕䝹䛸䝣䝺䞊䝮䝽䞊䜽• 䝇䝖䝺䞊䝆ୖ䛾䝕䞊䝍䛿ᨷᧁ⪅䛻ㄞ䜎䜜䜛

DAS
Database-asa-Service

ClientUntrusted
Client Data– ᬯྕ໬

Encrypted User
Database• ୺グ᠈ୖ䛾䝕䞊䝍䛿ㄞ䜏ྲྀ䜜䛺䛔• ᨷᧁ⪅䛿䠈䝕䞊䝍䝧䞊䝇䛾ᖹᩥ䛸⤫ィ㔞䜢▱䛳䛶䛔䜛ྍ⬟ᛶ䛒䜚䠊

Serever
Database Service Provider[Hacigumus et al., ICDE 2002]• 䝕䞊䝍䝧䞊䝇– ᬯྕ໬䛧䛯ୖ䛷䜽䝷䜴䝗ୖ䛾DSP䛻᱁⣡䠊• ၥྜ䛫ฎ⌮– ᚟ྕ໬䛻䛿䝕䞊䝍䝧䞊䝇඲య䛾䝎䜴䞁䝻䞊䝗䛜ᚲせ䠊– 䝕䞊䝍䝧䞊䝇䛾䝥䝷䜲䝞䝅䞊䜢ಖㆤ䛧䛴䛴䠈DSP䛾ィ⟬ᶵ㈨※䜢䛺䜛䜉䛟฼⏝䛧䛯᳨⣴䜢ᐇ⌧䛧䛯䛔䠊34㛵㐃◊✲䝕䞊䝍䝧䞊䝇䛾䝥䝷䜲䝞䝅䞊ಖㆤ᳨⣴㡰ᗎಖᏑᬯྕ໬ἲ• ᩘ್䝕䞊䝍• Order preserving encryption for numeric data

– Bucketization/Partitioning [Hacigumus, SIGMOD’02]– Order preserving encryption scheme [Agrawal,SIGMOD’04]– Structure preserving database encryption scheme[Yuval, SDM’04]– Anti-tamper database [Chung, ICDE WS’06]– Agrawal et al. SIGMOD 2004
X1 < X2 < X3 < …. < Xn
ÎEk(X1) < Ek(X2) < Ek(X3) < … < Ek(Xn)• ฼Ⅼ– ୍⮴᳨⣴䠈⠊ᅖ᳨⣴䛺䛹䛜䠈ᬯྕᩥୖ䛷ฎ⌮ྍ⬟䠊– Bᮌ䛺䛹䛾⣴ᘬ䜢䛭䛾䜎䜎฼⏝ྍ⬟䠊• 䝔䜻䝇䝖䝕䞊䝍– [Boneh, EUROCRYPT’04], [Dong, IFIP WS 11.3 ’08]

• ḞⅬ

• XML䝕䞊䝍
– Efficient Secure Query Evaluation over Encrypted
XML Databases [Wang, VLDB’06]㽢• ⪃䛘᪉– ⤫ィⓗᬯྕᨷᧁ䛻ᙅ䛔䠊
65୍ᑐ୍䝬䝑䝢䞁䜾䛻ᇶ䛵䛟ᬯྕ໬䝕䞊䝍䝧䞊䝇ᬯྕ໬䛾౛empEemployee• ୍ᑐ୍䝬䝑䝢䞁䜾䛻ᇶ䛵䛟ᬯྕ໬
X1 = X2 = … = Xn
Î Ek(X1) = Ek (X2) = … = Ek (Xn)• ୍ᑐ୍䝬䝑䝢䞁䜾䛻ᇶ䛵䛟ᬯྕ໬䛿ᨷᧁ䛻ᑐ䛧䛶⬤ᙅ– ᬯྕᩥ䛾⤫ィⓗᛶ㉁䜢฼⏝䛧䛯ᨷᧁ䠊– 䜹䝔䝂䝸ᒓᛶ䛾ሙྜ䠈≉䛻ၥ㢟䠊• ᛶู• ᅜ⡠• ㈍኎ᗑ䝁䞊䝗Salarygender

E_IDSalarygender

111

100

1356344576456

67653

222

200

187685586576

67653

333

350

1324226756765

67653

444

200

164777586576

67653

555

200

277547586576564564

E_ID

P_ID

111

31

222

33

333

33

project

444

34

P_ID

P_Name

222

34

31

projectAS

emp_prj

7

E_ID

E

E

33

projectCZ

34

projectBX

35

projectMM

Plaintext database

EE

E

E_ID

P_ID

35634

21133

87685

65874

projE

32422

65874

P_ID

64777

78554

21133

projectAS

87685

78554

65874

projectCZ

78554

projectBX

96241

projectMM

emp_prjE

P_NameEEE

Encrypted databaseE8䜰䜲䝕䜰䠖୍ᑐከ䝬䝑䝢䞁䜾◊✲䛾┠ⓗMultivalued Order Preserving Encryption Scheme (MV-OPES)• ⤫ィⓗᬯྕᨷᧁ䛻ᑐ䛧䛶㡹೺䛺䠈䝥䝷䜲䝞䝅䞊ಖㆤ䝕䞊䝍䝧䞊䝇ᬯྕ໬䞉ၥྜ䛫ἲ• 㡰ᗎಖᏑ• 䜰䝥䝻䞊䝏• ୍ᑐከ䝬䝑䝢䞁䜾– X1 < X2 < X3 < … < Xn
– Ek(X1) < Ek(X2) < Ek(X3) < …. < Ek(Xn)• V1 = V2• 㧗䛔☜⋡䛷 Ek(V1) z Ek(V2)– 㡰ᗎಖᏑᬯྕ໬ἲ䛻ᇶ䛵䛟䠊– ୍䛴䛾ᖹᩥ䛻ᑐ䛧䠈」ᩘ䛾ᬯྕᩥ䜢ᑐᛂ௜䛡䜛䠊• 䛒䜛ᖹᩥ䛻ᑐ䛧䠈༊㛫ෆ䛾್䜢䝷䞁䝎䝮䛻๭䜚ᙜ䛶䜛䠊• ⤫ィⓗᬯྕᨷᧁ䛻ᑐᛂ䠊

Dmin

DmaxRandom– 䛺䜛䜉䛟ከ䛟䛾㛵ಀ௦ᩘ₇⟬䜢䝃䝫䞊䝖䠊• ᚑ᮶◊✲䛿䠈」ᩘ䝔䞊䝤䝹䛾䝆䝵䜲䞁䛻䛿㠀ᑐᛂ䠊

BDmin

BDMax

BDmin+1

BDMax+1– ᐇ⏝ྍ⬟䛺䝺䝧䝹䛷䛾ᐇ⾜㏿ᗘ䠊
910MV-OPES䛻䜘䜛䝕䞊䝍䝧䞊䝇ᬯྕ໬empEemp

E_ID

P_ID

111

31222

33333

3344434

222

34

MV-OPES䛻䜘䜛ᬯྕ໬EE

E_ID

Salarygender

E_ID

111

100

1E (111)v1E (100)v1

Ek(1)v1

222

200

1Ek(222)v1

Ek(200)v1

Ek(1)v2333350

1Ek(333)v1

Ek(350)v1

Ek(1)v3444200

1Ek(444)v1

Ek(200)v2

Ek(1)v4

555

200

2

Ek(555)v1

Ek(200)v3

Ek(2)v1k

E

genderk– 䝃䜲䝈䛾␗䛺䜛䝞䜿䝒䜢䠈䝗䝯䜲䞁䛾䝃䜲䝈䛰䛡⏕ᡂ䠊• ึᮇ್䛾㑅ᢥ• ቑຍ䠋ῶᑡ㛵ᩘ• ஘ᩘ⏕ᡂ– ᖹᩥ䛻ᑐᛂ䛩䜛䝞䜿䝒䜢㑅ᢥ䠊– 䝞䜿䝒ෆ䛾್䜢䝷䞁䝎䝮䛻㑅ᢥ䠊P_IDk

E (111)v2

Ek(31)v2
projE

Ek(222)v2

Ek(33)v2

P_ID

P_NameEk(333)v2

Ek(33)v3

P_ID

P_Name31

projectAS

Ek(444)v2

Ek(34)v2

Ek(31)v1

projectAS

Ek(33)v1

projectCZ

Ek(34)v1

projectBX

Ek(35)v1

projectMM

proj• 䝞䜿䝒ቃ⏺䛾⏕ᡂ

E

E

E_ID

emp_prj

Salary33

projectCZ

Ek(222)v3

34

projectBX

emp_prjE

35

projectMM

Plaintext databasekE (34)v3

EE
E

Encrypted databaseE1112䝞䜿䝒ቃ⏺䛾⏕ᡂᬯྕ໬• 䝗䝯䜲䞁 [Dmin, Dmax]• ึᮇ್㑅ᢥ• ᖹᩥ䛻ᑐᛂ䛩䜛䝞䜿䝒ෆ䛾್䜢䝷䞁䝎䝮䛻㑅ᢥ䠊– ୍ᵝศᕸ– ṇつศᕸ–…

– Binitial = EncK(initial) , Dmin <= initial <= Dmax• ቑຍ䠋ῶᑡ㛵ᩘ• ᳨⣴ᛶ⬟䛻୚䛘䜛ᙳ㡪– IS: 䝞䜿䝒䛾䝧䞊䝇䝃䜲䝈, DP: 㞄᥋䝞䜿䝒䝃䜲䝈ẚ– 㞄᥋䝞䜿䝒䛸䛾ቃ⏺௜㏆䛻ᬯྕᩥ䛜ศᕸ䛩䜛䛸䠈᳨⣴᫬䛻ᨃ㝧ᛶ䛾⤖ᯝ䛸䛧䛶ሗ࿌䛥䜜䜛ྍ⬟ᛶ䛒䜚䠊– ᳨⣴⤖ᯝ䛾⢭〇䛜ᚲせ䠊– Bi = Bi+1 - [ EncK (IS) + EncK (IS) * DP * Ri ]Dmin<= i < initial– Bi = Bi-1 + [EncK (IS) + EncK (IS) * DP * Ri ]initial< i <=(Dmax+1)
BDmin

BDmin+1

BDMax

Binitial

BDMax+11413᚟ྕ໬㛵ಀ₇⟬䛾ᐇ⌧•ᬯྕᩥ䛾ྵ䜎䜜䜛䝞䜿䝒䜢≉ᐃ䠊
B1B2• 㛵ಀ₇⟬䜢䠈DAS䝕䞊䝍䝧䞊䝇䝃䞊䝞䛾ィ⟬㈨※䜢฼⏝䛧䛺䛜䜙ฎ⌮䠊

B4B3– 䛺䜛䜉䛟ከ䛟䛾ィ⟬䜢䝃䞊䝞ഃ䛷ฎ⌮䠊Y>• 䛔䛟䛴䛛䛾₇⟬䛻䛴䛔䛶䛿䠈ᚋฎ⌮䛜ᚲせ䠊Continue– ᚟ྕ໬䛾ᚋ䛻䠈ᨃ㝧ᛶ䛾⤖ᯝ䜢ྲྀ䜚㝖䛟ᚲせ䛒䜚䠊>• 䝃䝫䞊䝖䛩䜛₇⟬Continue– 㑅ᢥ䠈⤖ྜ䠈ᑕᙳ䠈䝋䞊䝖䠈䜾䝹䞊䝢䞁䜾䠈㞟⣙䠈㞟ྜᕪ䠈㞟ྜ࿴>Continue<Stop (return (i-1))
1516㻝㻢㛵ಀ₇⟬䛾ᐇ⌧䠖㑅ᢥ₇⟬㛵ಀ₇⟬䛾ᐇ⌧䠖㑅ᢥ₇⟬• 㛵ಀ₇⟬䛾᭩䛝᥮䛘– V A T v( R )• 㑅ᢥ᮲௳
– Attribute T Value– VC( R ) = D(VE ( RE ))• Attribute = Value• ౛– ᭩䛝᥮䛘๓: A = v– ᭩䛝᥮䛘ᚋ: AE between Bv and (Bv+1 - 1)

– Ve_id=150( emp ) = D(VE e_idE between B(150) and B(151)-1 ( empE ))• ౛– A=150 Æ AE between B150 and (B151-1)
BDmin

B150B151[)

BDMax+11817㻝㻣㻝㻤㛵ಀ₇⟬䛾ᐇ⌧䠖⤖ྜ₇⟬㛵ಀ₇⟬䛾ᐇ⌧䠖⤖ྜ₇⟬• ⤖ྜ᮲௳• ⤖ྜ᮲௳– Attribute T Attribute– ␗䛺䜛್䛻䝬䝑䝥䛥䜜䛶䛔䜛䛾䛷䠈➼ྕ䛿౑䛘䛺䛔䠊– 䝞䜿䝒ቃ⏺䜒฼⏝୙ྍ䠊– Attribute1 = Attribute2– P = F,
– FE between (PE-MaxDiff) and (PE+Maxdiff)– ᨃ㝧ᛶ䛾⤖ᯝ䜢ྵ䜐䠊

• MaxDiff䛾ᑟධ– ᬯྕᩥ䛸䝞䜿䝒ቃ⏺䛸䛾᭱኱್䜢ಖᏑ䛧䛶฼⏝䠊
BDmin

BDMax

BDmin+1

BDMax+1

BDmin

BDmin

BDMax+1BDmin

BDMax+1

PrimaryP
BDMax

BDmin+1

BDMax+1Foreign

FMaxDiff19㻝㻥20㻞㻜㛵ಀ₇⟬䛾ᐇ⌧䠖⤖ྜ₇⟬ホ౯ᐇ㦂• 㛵ಀ₇⟬䛾᭩䛝᥮䛘
Rc T =V(D(RE• ᥦ᱌ᡭἲ䛾᭷ຠᛶ䜢᳨ドEE– ᬯྕ໬– ⤖ྜ₇⟬T ))CEc• ➼⤖ྜ

Foreign

P_intF_int• 䝕䞊䝍䝉䝑䝖• C: P = F,– 䝗䝯䜲䞁䛾䝃䜲䝈• CE: FE between (PE-MaxDiff) and (PE+Maxdiff)• 10, 100, 1000, 10000, 100000– 䝔䞊䝤䝹䝃䜲䝈• ౛
empPrimary• 100000 tuples.

emp.e_id=emp_proj.e_id

emp_proj =EEEV emp.e_id=emp_proj.e_id( D ( emp– DP

emp_proj.e_id

Ebetween (emp.e_idEE-MaxDiff) and (emp.e_id +Maxdiff)

emp_proj ))• 5%, 15%, 25%, 35%, 45%, 55%2122㻞㻞

ᐇ㦂⤖ᯝ1ᐇ㦂⤖ᯝ2• ᬯྕ໬• ➼⤖ྜ䛾⤖ᯝ0.6

Foreign key (plaintext)

0.5

Primary Key (MV-OPES)

7060
50
40
30
20
1000.4Foreign key (MV-OPES)

0.3

Primary Key (AES)

0.2

0_05

0_15

10102

103

104

105

Domain

10105

102

103

104

Foreign key (AES)(a) False positive percentage.

DomainTime per tuple (in ms) required to insert tuples.

•ᥦ᱌ᡭἲ䛿䠈ᖹᩥ䛸䜋䜌ྠ➼䛾ᛶ⬟䠊
•AES䜘䜚㧗㏿䠊

0.061
0.051
0.041
0.031
0.021
0.011
0.001

10102

103

104

105

Domain(b) Query execution time in server side.
23

Time (ms) per tuple

0.1Time (ms) per tuple

Time per tuple (ms)

0.7

False positive %Primary Key (Plaintext)

0.02510.02010.01510.01010.00510.0001

10

102

103

Domain104105(c) Decryption and filtering cost in client side.
24㻞㻠䛣䜜䛷༑ศ䠛ၥ㢟• ᨷᧁ⪅䛜ᖹᩥ䞉⤫ィ㔞䜢▱䛳䛶䛔䜛ሙྜ䠊• (MV-)OPES䛷䛿䠈್䛾኱ᇦⓗ䛺㡰ᗎ䜢ಖᏑ䠊– ᖹᩥ䠇⤫ィ㔞䜢౑䛳䛯ᨷᧁ䛻ᙅ䛔䠊• せồ– ኱ᇦⓗ䛺㡰ᗎ䜢ಖᏑ䛧䛺䛔䠊– (MV-)OPES䛾䜘䛖䛺ฎ⌮䜢⾜䛔䛯䛔䠊• 䜰䝥䝻䞊䝏– 㒊ศⓗ䛻㡰ᗎ䜢ಖᏑ䠊– Multi-Valued Partial Order Preserving Scheme (MVPOPES)• ᭱኱್䠈᭱ᑠ್䛸ᖹᩥ䛾⤌ྜ䛫䛛䜙䠈㒊ศⓗ䛻್䛜ㄞ䜎䜜䜛䠊2526

䝯䝍䝕䞊䝍MV-POPES• 䝗䝯䜲䞁䜢䝟䞊䝔䜱䝅䝵䞁໬䠈㡰ᗎධ䜜᭰䛘• ୍ᑐከ䝬䝑䝢䞁䜾• 䝟䞊䝔䜱䝅䝵䞁㛫䛾㡰ᗎ㛵ಀ䜢グ㘓䠊• ၥྜ䛫᭩䛝᥮䛘䛻฼⏝䠊• V1 = V2• 㧗䛔☜⋡䛷 Ek(V1) z Ek(V2)• 䝟䞊䝔䜱䝅䝵䞁ෆ䛷䛿㡰ᗎ䜢ಖᏑ– X1 < X2 < X3 < … < Xn– Ek(X1) < Ek(X2) < Ek(X3) < …. < Ek(Xn)2728ၥྜ䛫䛾᭩䛝᥮䛘䝉䜻䝳䝸䝔䜱ศᯒ• MV-OPES䛸䛿␗䛺䜚䠈䝟䞊䝔䜱䝅䝵䞁䛾㡰ᗎ䜢⪃៖䛩䜛ᚲせ䛒䜚䠊2930

䜎䛸䜑䛸௒ᚋ䛾ㄢ㢟ᐇ㦂䠄⠊ᅖၥྜ䛫䠅• 䜎䛸䜑– ୍ᑐከ䝬䝑䝢䞁䜾䛻ᇶ䛵䛟㡰ᗎಖᏑᬯྕ໬᪉ᘧMV-OPES• ከᩘ䛾㛵ಀ₇⟬䜢䝃䝫䞊䝖• ᐇ㦂䛻䜘䜛ホ౯– 㒊ศⓗ䛺㡰ᗎ䜢ಖᏑ䛧䛯MV-POPES• ከᩘ䛾㛵ಀ₇⟬䜢䝃䝫䞊䝖• ᐇ㦂䛻䜘䜛ホ౯• 䝟䞊䝔䜱䝅䝵䞁䛾䝷䞁䝎䝮໬᪉ἲ䜢ᕤኵ䛩䜛䛣䛸䛷䠈ᛶ⬟䛾ຎ໬䜢㜵䛠• ௒ᚋ䛾ㄢ㢟– MV-POPES䛾ヲ⣽䛺ホ౯– ௚䛾䝕䞊䝍䝍䜲䝥䛾䝃䝫䞊䝖31㻟㻞

32Ⓨ⾲ㄽᩥ••••Hasan Kadhem, Toshiyuki Amagasa, and Hiroyuki Kitagawa, “A Secure andEfficient Order Preserving Encryption Scheme for Relational Databases,”Int‘l Conf. on Knowledge Management and Information Sharing (KMIS2010), Valencia, Spain, October 25-28, 2010. [Best Student Paper Award]
Hasan Kadhem, Toshiyuki Amagasa, Hiroyuki Kitagawa, “A Secure andEfficient Order Preserving Encryption Scheme for Relational Databases“,iDB䝽䞊䜽䝅䝵䝑䝥2010, ᮾி, 2010.
Hasan Kadhem, Toshiyuki Amagasa, and Hiroyuki Kitagawa, "MV-OPES:
Multivalued-Order Preserving Encryption Scheme: A Novel Scheme for
Encrypting Integer Value to Many Different Values," IEICE Trans. Info. &Syst., Vol. E93-D, No. 9, pp.2520-2533, Sept. 2010.
Hasan Kadhem, Toshiyuki Amagasa, Hiroyuki Kitagawa, "An Encryption
Scheme to Prevent Statistical Attacks in the DAS Model", ➨2ᅇ䝕䞊䝍ᕤᏛ䛸᝟ሗ䝬䝛䝆䝯䞁䝖䛻㛵䛩䜛䝣䜷䞊䝷䝮 (DEIM 2010), B5-5, 2010ᖺ2᭶28᪥䡚3᭶2᪥.

33