JAIST Repository: 閾値を設けた秘匿マッチングプロトコルに関する研究

JAIST Repository

https://dspace.jaist.ac.jp/ Title 閾値を設けた秘匿マッチングプロトコルに関する研究 Author(s) 権田, 陽彦 Citation Issue Date 2017-03

Type Thesis or Dissertation Text version author

URL http://hdl.handle.net/10119/14144 Rights

修士論文

閾値を設けた秘匿マッチングプロトコルに関する

研究

1510018

    権田 陽彦

主指導教員

金子 峰雄

審査委員主査

金子 峰雄

審査委員

宮地 充子

審査委員

上原 隆平

北陸先端科学技術大学院大学 情報科学研究科 平成 29 年 2 月

1 1 1.1 . . . 1 1.2 . . . 3 1.3 . . . 4 2 5 2.1 . . . 5 2.1.1 . . . 5 2.1.2 . . . 5 2.1.3 . . . 6 2.2 . . . 6 2.3 . . . 8 2.4 . . . 9 2.5 Paillier . . . 10 2.5.1 . . . 10 2.5.2 . . . 10 2.5.3 . . . 10 2.5.4 . . . 10 2.5.5 . . . 11 2.5.6 . . . 11 2.5.7 . . . 12 3 13 3.1 . . . 13 3.2 FNP04 [8] . . . 14

3.2.1 Private Matching for Set Intersection PM . . . 14

3.2.2 Private Matching for Set Cardinary PMC . . . 15

3.3 KLP11 [15] . . . 16

3.3.1 Map To Prime (MTP) . . . 16

3.3.2 Mutual PSI Protocol . . . 16

3.3.3 . . . 17

3.5 ZDLG13 [31] . . . 20 3.5.1 . . . 20 3.5.2 BVT . . . 21 3.5.3 FACFM . . . 23 3.5.4 . . . 24 3.5.5 . . . 25 3.5.6 . . . 27 3.6 TLSL15 [27] . . . 27 3.6.1 . . . 28 3.6.2 . . . 29 3.6.3 L1P . . . 29 3.6.4 L2P . . . 29 3.6.5 L3P . . . 30 3.7 ZLJCL14 [32] . . . 31 3.8 . . . 34 4 35 4.1 . . . 35 4.2 BVT . . . 37 4.2.1 . . . 37 4.2.2 . . . 37 4.2.3 . . . 38 4.3 . . . 39 4.3.1 . . . 40 4.4 . . . 41 4.4.1 . . . 41 5 43 5.1 . . . 43 5.2 . . . 44 5.3 . . . 45 5.3.1 . . . 45 5.3.2 . . . 46 5.4 . . . 47 5.4.1 . . . 47 5.4.2 . . . 47 5.4.3 BVT . . . 49 5.4.4 . . . 50 5.4.5 [31] . . . 51

5.4.6 . . . 52 6 54 6.1 . . . 54 6.2 ZDLG13 [31] . . . 55 7 56 8 57 8.1 . . . 57

1

1.1

VentureBeat SNS 1.1: 1.1 A B 2 1.1 A 20 B

20 A B

SKOUT [1] Tagged [2] hi5 [3] Badoo [4] Like/No

Like

Meet Me

POF [5] 200 4

1.2:

2 [31]

1.2

[31] [12] 2 semi-honest

1.3

2 Paillier 3 4 3 5 6 7

2

Paillier

2.1

2.1.1

P I P n Q p1, p2,· · · , pn P := [p1, p2,· · · , pn]. (2.1) I i1, i2,· · · , in I := [i1, i2,· · · , in]. (2.2)

2.1.2

A, B (Pa, Ia), (Pb, Ib) Pa∩ Ib, Pb∩ Ia |Pa∩ Ib|, |Pb∩ Ia| |Pa∩ Ib| = 0 |Pb∩ Ia| [31] _|Pa∩ Ib| + ∆b

2.1.3

A, B τa, τb B A |Pa∩ Ib| ! τb. (2.3) A B |Pb ∩ Ia| ! τa. (2.4) |Pa∩ Ib| |Pa∩ Ib| + ∆b ! τb+ ∆b, (2.5) |Pb∩ Ia| + ∆a! τa+ ∆a (2.6) ∆a, ∆b (2.3),(2.4) (2.5),(2.6) ! |Pa∩ Ib| ≥ τb∧ |Pb∩ Ia| ≥ τa =⇒ match, |Pa∩ Ib| < τb ∨ |Pb ∩ Ia| < τa =⇒ mismatch. (2.7) (2.3),(2.4) (2.3),(2.4) 3 • |Pb∩ Ia| ≥ τa∧ |Pa∩ Ib| < τb A B B A • |Pb∩ Ia| < τa∧ |Pa∩ Ib| ≥ τb B A A B • |Pb∩ Ia| < τa∧ |Pa∩ Ib| < τb A B B A

2.2

2.1 2

2.1:

Setting

Private Matching

A, B A B B A Private Matching [31] A B B A B A A A _|Pa∩ Ib| + ∆b ∆b A B A _|Pa∩ Ib|

B τb ∆b ˆ vb := |Pa∩ Ib| + ∆b, vb := τb+ ∆b, ∆b > 0. (2.8) B A ∆a A τa ∆a ˆ va:= |Pb ∩ Ia| + ∆a, va := τa+ ∆a, ∆a > 0. (2.9)

Verification

Verification ˆ vb ≥ vb∧ ˆva≥ va ˆ vb < vb ∨ ˆva < va vˆb ! vb, ˆva ! va ˆ vb ≥ vb∧ ˆva ≥ va (True) ˆvb < vb∨ ˆva< va (False) A B A B A B B A

2.3

6 [19, 27, 32] [7, 12, 31]

Q P I

2.4

[24] SSL/TLS semi-honset semi-honset [9, 12, 18, 21, 25, 31]

2.5

Paillier

Paillier [22] [21–23] Paillier

2.5.1

Paillier ∀x ∈ N (1 + N )x _{≡ 1 + xN (mod N}2_{). (2.10)} y := (1 + N )x x = y− 1 N (mod N 2_{). (2.11)} L(x) L(x) := x− 1 N . (2.12)

2.5.2

gcd(pq, (p− 1)(q − 1)) = 1 2 p← PU N, q U ← PN N = pq, g = (1 + ¯αN ) ¯βN _{λ = lcm(p− 1, q − 1)} ¯ α_{← Z}U ∗ N2, ¯β U ← Z∗ N2

2.5.3

gcd(r, N ) = 1 r _{← Z}U ∗ N2 ∀m ∈ ZN c Enc c = Enc(m) := gmrN (mod N2). (2.13)

2.5.4

λ (2.12) L Dec Dec(c) := L(c λ _{(mod N}2₎₎ L(gλ _{(mod N}2₎₎ = m (mod N ). (2.14) (2.14) rλN _{≡ 1 (mod N}2₎

1. _{∀r ∈ Z}∗ N2. gcd(r, N ) = 1 =⇒ rλN ≡ 1 (mod N2) Proof. Euler ϕ(N2_{) = N (p− 1)(q − 1) gcd(pq, (p− 1)(q − 1)) = 1} Z∗ N2 N (p− 1)(q − 1) gcd(r, N ) = 1 ∀r ∈ Z∗ N2 Euler rλ _{≡ 1 (mod N).} (2.15) γ rλ _{:= 1 + N γ} rλN = 1 + N2(γ +· · · ) ≡ 1 (mod N2_{). (2.16)} 1 1 L(cλ _{(mod N}2_{)) gcd(¯α, N ) = gcd( ¯β, N ) = 1}

L(cλ (mod N2)) = L(gmλ (mod N2))_{≡ ¯αmλ (mod N).} (2.17)

2.5.5

Paillier Enc _∀m1 ∈ ZN,∀m2 ∈ ZN

Enc(m1) Enc(m2)

Enc(m1)· Enc(m2) = Enc(m1+ m2) (mod N2). (2.18)

∀N ∈ ZN

{Enc(m)}N = Enc(N · m) (mod N2_{). (2.19)}

(2.18), (2.19)

2.5.6

P = [p1, p2,· · · , pn]

Enc(P ) := [Enc(p1), Enc(p2),· · · , Enc(pn)].

C = [c1, c2,· · · , cn]

2.5.7

[23] Paillier D-CR (Decision Composite Residuosity assumption) D-PDL (Decision Partial Discrete Log assumption) IND-CPA

D-CR _{∀x ∈ Z}∗ N,∃ˆα ∈ Z∗N,∃ ˆβ ∈ ZN∗ . xN = ˆα + ˆβ· N (mod N2), ˆr U ← Z∗ N (ˆα, ˆβ) (ˆα, ˆr) D-PDL Dec IND-CPA c c (advantage) (CPA chosen plaintext attack) c (IND indistinguishability) 2 m1, m2 cj cj m1, m2 Paillier r D-CR D-PDL Paillier

3

3.1

2004 M. Freedman Private Matching (PM) [8] Private Set Intersection (PSI)

PSI Oblivious Polynomial Evaluation (OPE) [20]

[15] Map To Prime (MTP) PSI [31] 4 Blind Vector Transforming (BVT) PSI [6–8] 2 [31] BVT FACFM [31] [27, 31] [12] MTP

[12]

MTP

Euclid [14, 30] Manhattan [10] [19, 32] Social Proximity [27]

[28] [29] Dice [11] [31] SNS

Shamir [26] Secure Multiparty Computation(SMT)

[13, 16, 17]

[8, 12, 15, 31] [27, 32]

3.2

FNP04 [8]

Client X =_{x1, x2,· · · , xkc} Server Y ={y1, y2,· · · , yks}

Private Matching for Set Intersection PM X_{∩ Y} Private Matching for Set Cardinary PMC |X ∩ Y | Client Server semi-honest

3.2.1

Private Matching for Set Intersection PM

X ={x1, x2,· · · , xkc}, Y = {y1, y2,· · · , yks} X_{∩ Y} 1. Client (a) Paillier (b) X P (y) αj P (y) = (x1− y)(x2− y) · · · (xkc− y) = kc " j=0 αjyj. (3.1)

(c) kc+ 1 α0, α1,· · · , αkc Server

Enc(α0), Enc(α1),· · · , Enc(αkc). (3.2)

2. Server

(a) Horner Enc(P (y1)), Enc(P (y2)),· · · , Enc(P (yks))

α0, α1, α2, α3 P (y1) Enc(P (y1)) = #$ Enc(α3)y1 · Enc(α2) %y1 · Enc(α1) &y1 · Enc(α0). (3.3) (b) r ks Server

Enc(rP (yi) + yi) = {Enc(P (yi))}r· Enc(yi). (3.4)

3. Client

P (yi) = 0 yi

X X∩ Y

3.2.2

Private Matching for Set Cardinary PM

C

X ={x1, x2,· · · , xkc}, Y = {y1, y2,· · · , yks} |X ∩ Y | 1. Client (a) Paillier (b) X P (y) αj P (y) = (x1− y)(x2− y) · · · (xkc− y) = kc " j=0 αjyj. (3.5) (c) kc+ 1 α0, α1,· · · , αkc Server

Enc(α0), Enc(α1),· · · , Enc(αkc). (3.6)

2. Server

(b) r ks Server Enc(rP (yi)) = {Enc(P (yi))}r. (3.7) 3. Client rP (yi) = 0 |X ∩ Y |

3.3

KLP11 [15]

A XA = {a1, a2,· · · , ak} B XB = {b1, b2,· · · , bk} A, B MTP XA∩ XB A B semi-honest

3.3.1

Map To Prime (MTP)

A, B p :_{{0, 1}}∗ _{→ P} η αi = p(ai), βi = p(bi), (3.8) H :_{{0, 1}}∗ _{→ {1, 2, · · · , l} {B} j}lj=1

3.3.2

Mutual PSI Protocol

XA={a1, a2,· · · , ak}, XB ={b1, b2,· · · , bk}

XA∩ XB

1. A, B MTP

2.

AH(ai)← AH(ai)· p(ai), BH(bi) ← BH(bi)· p(bi). (3.9)

3. A r1 U

← Z⌊N/4⌋, r2 U

← Z⌊N/4⌋ B Encb(r2), Encb(A2j), Encb(r1A2j)

B s1 U

← Z⌊N/4⌋, s2 U

← Z⌊N/4⌋ A

4. A

Enca((r1+ s1)A2j + (r2+ s2)Bj2) = Enca(r1A2j)· Enca(s1)A

2 j · Enc

a(Bj2)r2 · Enca(s2Bj2).

(3.10) B

Encb((r1+ s1)A2j + (r2+ s2)Bj2) = Encb(r1A2j)· Encb(A2j)s1 · Encb(r2)B

2 j · Enc b(s2Bj2). (3.11) 5. A, B (r1+ s1)A2j + (r2+ s2)Bj2 6. A (r1 + s1)A2j + (r2 + s2)Bj2 Bj p(ai) 2 p(ai)2|((r1+ s1)Aj2+ (r2+ s2)Bj2) B p(bi)2|((r1+ s1)A2j + (r2+ s2)Bj2) XA∩ XB

3.3.3

l [12, 21] MTP k (=_|XA| = |XB|) (3.10),(3.11) [12, 21] k k

3.4

IO16 [12]

(False) XA∩XB A B semi-honest 3.1 A B S S S A, B semi-honest

3.1: [12] S k _{S1,S2,· · · , Sk} Sj ={p(j)1 , p (j) 2 ,· · · , p(j)n } ∈ Pn. (3.12) S = 'Sj, Si ∩ Sj = ∅ (i ̸= j) A, B S A XA={a1, a2,· · · , ak} B XB = {b1, b2,· · · , bk} A XA′ = {a′1, a′2,· · · , a′δ} B X′ B = {b′1, b′2,· · · , b′δ′} a′i B i bi = a′i A XA, XA′ , XB, XB′ XA∩ XB/False 1. A, B Paillier 2. A a = k ( j=1 aj, ac = δ ( j a′_j. (3.13)

a A B Enca(a), Encb(a), ac S B

b = k ( j=1 bj, bc = δ′ ( j b′_j. (3.14) b A B Enca(b), Encb(b), bc S

3. S 4 raa, rab, rba, rbb |na|, |nb| t p(i)_j |raa| = |na| − (k + δ) · t − 1, (3.15) |rab| = |na| − (k + δ′)· t − 1, (3.16) |rba| = |nb| − (k + δ) · t − 1, (3.17) |rbb| = |nb| − (k + δ′)· t − 1. (3.18) Enca(a)raaa −1 c _{· Enc} a(b)rabb −1 c _{= Enc} a(araaa−1c + brabb−1c ), (3.19) Encb(a)rbaa −1 c _{· Enc} b(b)rbbb −1 c _{= Enc} b(arbaa−1c + brbbb−1c ). (3.20)

Enca(araaa−1c + brabb−1c ) A Encb(arbaa−1c + brbbb−1c ) B

4. A araaa−1c + brabb−1c ≡ XAB XAB aj aj|XAB a−1 c , b−1c aj|XAB XA∩ XB 5. B arbaa−1c + brbbb−1c ≡ XBA XBA bj bj|XBA

3.5

ZDLG13 [31]

3.5.1

3.2: [31] 2 BVT 1 FACFM BVT FACFM

Setting Private Matching Verification 3 Setting

Private Matching BVT Verification FACFM

Setting

A Pa Ia

Pb Ib eb αb, βb lb Private Matching A Pa B Ib, lb, eb BVT A sˆb B sb sb eb ∆b(lb) ∆b(lb) B A ˆsb |Pa∩ Ib| B Pb A Ia, la, ea BVT B sˆa A sa sa ea ∆a(la) ∆a(la) A B ˆsa |Pb∩ Ia| Verification A sa, ˆsb, αa, βa B sb, ˆsa, αb, βb FACFM sa= ˆsa∧ sb = ˆsb A B True/False αa, βa αb, βb sa = ˆsa∧ sb = ˆsb

3.5.2

BVT

A Pa B Ib B lb eb A sb |Pa∩ Ib| ˆ sb 1. A B A Pa B Enca(Pa) 2. A B (i) B Enca(Pa) rb ˆ Pa := Enca(Pa+ rb), )Ib := Ib+ rb. (3.21) (ii) lb yb yˆb := Enca(yb) yb kb y)b kb U ← {1, 2, · · · , lb}

3.3: BVT (iii) ˆPa, )Ib yˆb,y)b P_a′ := ˆPa⊕ ˆyb, Ib′ := )Ib⊕ )yb. (3.22) (iv) Pa′ Ib′ P_a′′ := Shuffle [P_a′] , I_b′′:= Shuffle [I_b′] . (3.23) 3. A B P′′ a Ib′′ A 4. B 2 B Pa Ib eb 2 (i)−(iv) sb := eb+ lb− kb. (3.24) 5. A A P′′ a Ib′′ sˆb ˆ sb :=|Deca(Pa′′)∩ Ib′′|. (3.25)

3.4: FACFM

3.5.3

FACFM

BVT A (sa, ˆsb) B (sb, ˆsa) sa= ˆsa∧ sb = ˆsb ea=|Pb∩ Ia| ∧ eb =|Pa∩ Ib| A B FACFM sa, sb, ˆsa, ˆsb sa||ˆsb = ˆsb||sa A B (αa, βa), (αb, βb) FACFM (sa, ˆsb), (sb, ˆsa) A αa, βa B αb, βb sa||ˆsb = ˆsa||sb 1. A sa||ˆsb Enca(sa||ˆsb) B 2. B αb, βb,Enca(sa||ˆsb) A

Enca(sa||ˆsb)αb· Enca(βb) = Enca(αb· sa||ˆsb + βb). (3.26)

3. B αb· ˆsa||sb+ βb Encb(αb· ˆsa||sb+ βb) A

5. A αa, βa,Encb(αb· ˆsa||sb+ βb) B

Encb(αb· ˆsa||sb+ βb)αa· Encb(βa) = Encb(αa· (αb · ˆsa||sb+ βb) + βa). (3.27)

6. B Encb(αa· (αb· ˆsa||sb+ βb) + βa) αa· (αb· ˆsa||sb+ βb) + βa

7. 2 True

False A B

3.5.4

2. BVT

proof. _{∃x ∈ P}a∩ Ib,∃y /∈ Pa∩ Ib,∃y′ ∈ P/ a∩ Ib,∃y ∈ Pa,∃y′ ∈ Ib BVT

4 (Enca(Pa), Ib) (Pa′′, Ib′′)

(i)

∀r← ZU N Paillier

!

Deca(Enca(x)· Enca(r)) = Deca(Enca(x + r)) = x + r,

Deca(Enca(y)· Enca(r)) = Deca(Enca(y + r))̸= y′+ r.

(3.28) (ii) d Deca(Enca(d)) = d d′ (̸= d) Deca(Enca(d)) ̸= d′ (iii) (iv) (i)_−(iv) |Pa∩ Ib| = |Deca(Pa′′)∩ Ib′′| − (lb− kb). (3.29) lb = kb BVT |Pa∩ Ib| lb ̸= kb 3. FACFM .

proof. sa = ˆsa sb = ˆsb fa, fb fa αa y βa fb αb y βb fa A fb B ! fa(x) := αa· x + βa, fb(x) := αb· x + βb. (3.30) A Paillier fa(fb(sa||ˆsb)) (= αa· (αb· sa||ˆsb + βb) + βa) Enca(sa||ˆsb) B B αb, βb,Enca(sa||ˆsb) Enca(fb(sa||ˆsb)) A

Enca(sa||ˆsb)αb· Enca(βb) = Enca(αb · sa||ˆsb + βb). (3.31)

fa xa xa := αa· Deca(Enca(αb· sa||ˆsb + βb)) + βa= fa(fb(sa||ˆsb)). (3.32) B fa(fb(ˆsa||sb)) (= αa· (αb· ˆsa||sb+ βb) + βa) fb(ˆsa||sb) = αb· ˆ sa||sb+βb A A αa, βa,Encb(fb(ˆsa||sb)) Encb(fa(fb(ˆsa||sb))) B

Encb(αb · ˆsa||sb+ βb)αa · Encb(βa) = Encb(αa· (αb· ˆsa||sb+ βb) + βa) = Encb(fa(fb(ˆsa||sb))).

(3.33) xb xb := Decb(Encb(αa· (αb · ˆsa||sb + βb) + βa)) = fa(fb(ˆsa||sb)). (3.34) • sa = ˆsa∧ sb = ˆsb sa||ˆsb = ˆsa||sb Hash(xa) = Hash(xb). • sa||ˆsb ̸= ˆsa||sb Hash(xa)̸= Hash(xb). FACFM .

3.5.5

4. BVT

proof. A B I_b′′ Ib BVT I′′ b Ib A Deca(Pa′′) Ib′′ sˆb Pa∩ Ib kb X Pa∩ Ib Y lb kb lb Pa′′ Pa lb =|Pa′′| − n. (3.35) kb kb ={1, 2, · · · , lb} Pr(X ) Pr(X ) = 1 lb . (3.36) kb sˆb =|Deca(Pa′′)∩ Ib′′| Pa∩ Ib Deca(Pa′′)∩ Ib′′ ˆ sb − (lb− kb) lb − kb 1 Pr(Y|X ) Pr(Y|X ) = lb " kb=1 1 nCsˆb−(lb−kb) . (3.37) A ˆsb Pa∩ Ib Pr(X ∧ Y) n≥ 5 Pr(_{X ∧ Y) =} 1 lb lb " kb=1 1 nCˆsb−(lb−kb) ≤ _nl3 b . (3.38) 5. FACFM A αa· (αb · ˆsa||sb+ βb) + βa sˆa||sb

proof. FACFM Hash

αa· (αb · ˆsa||sb+ βb) + βa A (αa, βa)

αb· ˆsa||sb + βb sˆa||sb α, β

α· x + β 2 x

3.5.6

3.1 3.2 BVT FACFM BVT n FACFM n 3.1: 2 BVT A B [bit] 2tN · (2n + lb) 2tN · (2n + la) -[bit] 2tN · (n + la) 2tN · (n + lb) -O(n + la+ lb) O(n + la+ lb) -O(n + la+ lb) O(n + la+ lb) -3.2: FACFM A B [bit] 4tN + 1 4tN + 1 512 [bit] 4tN + 256 4tN + 256 2

O(1) O(1) O(1) O(1) O(1) O(1)

3.6

TLSL15 [27]

(Social Proximity) Social Proximity 3 3 1 (L1P) [8] PM 2 Social Proximity False (L1P) Social Proximity True/False semi-honest

3.6.1

i Ci Ci ={Ci1, Ci2,· · · , Cici}, ci =|Ci|. (3.39) ¯ Ci Ni ¯ Ci = * j∈Ni∪{i} Cj. (3.40) j _{∈ N}i ∪ {i} C¯i βj( ¯Ci) 0_{≤ β}j( ¯Ci)≤ βmax Ni F Ci F Ci ={F Ci1, F Ci2,· · · , F C fi i }, fi =|F Ci|, Ni = fi * j=1 F C_ij. (3.41) l F Ci F C(i, l) F C(i, i) = 0 l∈ F Ck i ⇐⇒ k = F C(i, l). (3.42) F Ck i αki 0≤ αki ≤ αmax α0 i = αmax Social Proximity i∈ ¯CR R Ψi_R←I Ψi_R←I = " j∈ ¯Ci R∩NR ⎛ ⎝βj( ¯CRi)· " k∈F C(R,j) αk_R ⎞ ⎠ | ¯CR| " l=1 ⎛ ⎝ " j∈ ¯Cl R∩NR ⎛ ⎝βj( ¯CRl)· " k∈F C(R,j) αk_R ⎞ ⎠ ⎞ ⎠ . (3.43)

R Social Proximity ΨR←I I

ΨR←I =

"

i∈ ¯CR∩ ¯CI

Ψi_R←I. (3.44) (3.44) 0_{≤ Ψ}R←I ≤ 1

3.6.2

[8] Enca(P (x)) P (x) A Enca(P (n)) P (x) x = n P (n)

3.6.3

L1P

¯ CR={ ¯CR1, ¯CR2,· · · , ¯C| ¯ CR| R }, ¯CI ={ ¯CI1, ¯CI2,· · · , ¯C| ¯ CI| I } ¯ CR∩ ¯CI 1. I, R K I 2. I PI(x) R PI(x) = | ¯CI| ( k=1 ( ¯C_Ik_{− x).} (3.45) 3. R Horner EncI(P ( ¯CRi)) (i∈ {1, 2, · · · , | ¯CR|}) Ri I

EncI(P ( ¯CRi))· EncI(Ri) = EncI(P ( ¯CRi) + Ri). (3.46)

4. I K R 5. R P ( ¯Ci R) + Ri ? = Ri C¯R∩ ¯CI K I 6. I C¯R∩ ¯CI

3.6.4

L2P

¯ CR, ¯CI,{ΨiR←I}, ΨRτ ¯ CR∩ ¯CI/False 1. I, R K I, R

2. I PI(x) R

3. R DR, ρi, Ri (i∈ {1, 2, · · · , | ¯CR|}) 2

2 Ri I

EncI(ρi· P ( ¯CRi)) = EncI(P ( ¯CRi))ρi, (3.47)

EncI(P ( ¯CRi) + EncR(ΨiR←I · DR)) = EncI(P ( ¯CRi))· EncI(EncR(ΨiR←I · DR)).

(3.48) 4. I 1 ρi· P ( ¯CRi) = 0 J 2 J j _{∈ J} I EncR(Ψj_R←I· DR) R 5. R C¯R∩ ¯CI ¯ CR∩ ¯CI K I False " j∈J Ψj_R←I· DR! ΨRτ · DR. (3.49) 6. I EncK( ¯CR∩ ¯CI) C¯R∩ ¯CI False

3.6.5

L3P

¯ CR, ¯CI,{Ψi_R←I}, {Ψi_I←R}, ΨRτ, ΨIτ True/False 1. I, R 2. I DI R EncI(PI(x)), EncI(DI) 3. R DR I EncR(PR(x)), EncR(DR) 4. I ρ′ i 2 2 EncI(ΨIτ · DI) R EncR(ρ′i · PR( ¯CIi)) = EncR(PR( ¯CIi))ρ ′ i, (3.50)

EncR(ρ′i · PR( ¯CIi) + EncI(ΨiI←R· DI)) = EncR(ρ′i· PR( ¯CIi))· EncR(EncI(ΨiI←R· DI)).

5. R ρi 2 2

EncR(ΨRτ · DR) I

EncI(ρi· PI( ¯CRi )) = EncI(PI( ¯CRi))ρi, (3.52)

EncI(ρi· PI( ¯CRi ) + EncR(ΨiR←I · DR)) = EncI(ρi· PI( ¯CRi ))· EncI(EncR(ΨiR←I · DR)).

(3.53)

6. I L2P JI r1′, r2′

j _{∈ J}I

EncR(r′1· Ψ j

R←I · DR+ r2′) = EncR(ΨjR←I· DR)r

′ 1 · Enc R(r2′), (3.54) EncR(r′1· ΨRτ · DR+ r2′) = EncR(DR· ΨRτ) r′ 1· Enc R(r′2). (3.55) 7. R L2P _JR r1, r2 j ∈ JR I

EncI(r1· Ψj_I←R· DI + r2) = EncI(Ψj_R←I · DI)r1 · EncI(r2), (3.56)

EncI(r1· ΨIτ · DI + r2) = EncI(DI · ΨIτ) r1 _{· Enc} I(r2). (3.57) 8. I True False " j∈JI (r1· ΨjI←R· DI + r2)! r1· ΨIτ · DI + r2 (3.58) 9. R True False " j∈JR (r₁′ _{· Ψ}j_{R←I · D}R+ r2′)! r′1· ΨRτ · DR+ r2′ (3.59)

3.7

ZLJCL14 [32]

A A = (aij) j i l n ∀i ∈ N ∩ [1, l], ∀j ∈ N ∩ [1, n]. (3.60)

j = 2 ? ai2 1

0 i

B B = (bij)

{0, 1} n_{× l}

A Confusion Matrix Transformation(CMT) Algorithm 1

A A∗ −→_{K B Algorithm} 1 _{B B}∗ A B A∗ _{B Algorithm 2 A}∗ _{B D B} A D −→K T∗ _{W = (w} ij) T∗ _{H = (h} ij) τ =/ /hij wij = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ i (i = j), i− |i − j| (i − |i − j| > 1), 1 (i_{− |i − j| ≤ 1).} (3.61) A τ τA τ ≥ τA True τ < τA False B A D B (_A∗)−1_{× D = (A}∗)−1_{× A}∗_{× B = B.} (3.62) Algorithm 3 Algorithm 3 B W A _B

3.8

3.3: 2 1 2 FNP04 [8] _{× △} IO16 [12] ⃝ × LUB14 [18] × △ SX15 [25] _{× ×} TLSL15 [27] _{× △} ZDLG13 [31] ⃝ × ZLJCL14 [32] × △ 3.31 _{[8, 18, 27, 32]} [31] 2 1. 2. 2 semi-honest 1 ⃝ · · · △ · · · × · · ·

4

4.1 3 5 [31] BVT 4.1:

4.1

4.1 2 BVT 1 2 BVT

Setting A Pa Ia τa αa, βa, γa, ξa la 2 ηa:= [ηa(1), ηa(2),· · · , ηa(n)], η_a′ := [η′(1)_a , η′(2)_a ,· · · , η′(n)_a ] B Pb Ib τb αb, βb, γb, ξb lb 2 ηb := [ηb(1), η (2) b ,· · · , η (n) b ], ηb′ := [η′(1)b , η′(2)b ,· · · , η′(n)b ] A Enca(Pa) B Encb(Pb) Private Matching A Pa B Ib, lb, τb, ηb, ξb BVT A vˆb B vb vb τb ∆b(lb) ∆b(lb) B A vˆb |Pa∩ Ib| B Pb A Ia, la, τa, ηa, ξa BVT B vˆa A va va τa ∆a(la) ∆a(la) A B ˆva |Pb∩ Ia| Verification A va, ˆvb B vb, ˆva va≥ ˆ va∧ vb ≥ ˆvb A B True/False αa, βa, γa αb, βb, γb va ≥ ˆva∧ vb ≥ ˆvb A Deca(Pa′′)∩ Ib B ηb, ηb′, ξb B Pa∩ Ib B Decb(Pb′′)∩ Ia A ηa, ηa′, ξa A Pb∩ Ia

4.2:

4.2

BVT

4.2.1

BVT [31] BVT

4.2.2

4.1 ηb := [η_b(1), η(2)_b ,· · · , η(n)_b ], η(i)_b ̸= η(j)_b (i̸= j). (4.1)

4.1: No. 1 2 _{· · ·} n Pb p(1)_b p(2)_b · · · p(n)_b Ib i(1)b i (2) b · · · i (n) b ηb η(1)b η (2) b · · · η (n) b B Deca(Pa′′)∩ Ib′′ BVT P_a′′ I_b′′ 4.3: BVT

4.2.3

A A Enca(Pa) B Ib B lb B ηb η′ b B ξb vb |Pa∩ Ib| vˆb

1. A B A B B Enca(Pa) 2. A B (i) B Enca(Pa) rb ˆ Pa := Enca(ξb · (Pa+ rb) + ηb), (4.2) ) Ib := ξb· (Ib+ rb) + ηb. (4.3)

ξb ∈ ZN, r(i)b ∈ ZN, ηb(i) ∈ ZN, ηb(i) < ξb, )Ib(i) < N

(ii) lb ξb · yb + ηb′ yˆb := Enca(ξb · yb + ηb′) ξb· yb + η′b kb ZN ) yb ηb ηb′ η′ b (i) ∈ ZN, η′b (i) < ξb kb U ← {1, 2, · · · , lb} (iii) ˆPa, )Ib yˆb,y)b P_a′ := ˆPa⊕ ˆyb, Ib′ := )Ib⊕ )yb. (4.4) (iv) P′ a Ib′ P_a′′ := Shuffle [P_a′] , I_b′′:= Shuffle [I_b′] . (4.5) 3. A B P_a′′ I_b′′ A 4. B 2 B Pa Ib τb 2 (i)−(iv) vb := τb+ lb− kb. (4.6) 5. A A P_a′′ I_b′′ vˆb ˆ vb :=|Deca(Pa′′)∩ Ib′′|. (4.7)

4.3

N tN A, B αi, βi, γi (i = a, b) αi ∈ ZN, βi ∈ ZN, γi ∈ ZN, (4.8) αi· (n + li) + βi < N− 2tN−1, αi > βi > 0 (4.9)

BVT A (va, ˆvb) B (ˆva, vb) va ≤ ˆva ∧ vb ≤ ˆvb τa ≤ |Pb ∩ Ia| ∧ τb ≤ |Pa∩ Ib| A B va, vb, ˆva, ˆvb va≤ ˆva∧ vb ≤ ˆvb ZN (0, 2tN−1) [2tN−1, N ) tN va ≤ ˆva∧ vb ≤ ˆvb 4.4:

4.3.1

(va, ˆvb), (vb, ˆva) αa, αb, βa, βb, γa, γb va ≤ ˆva∧ vb ≤ ˆvb 1. A B , B A

A Enca(αa· ˆvb+ βa), Enca(αa) B B Encb(αb· ˆva+ βb), Encb(αb) A

2. A B

A γa, va Encb(αb· ˆva+ βb), Encb(αb) Encb(γa· (αb· (ˆva− va) + βb))

B $

Encb(αb · ˆva+ βb)· Encb(αb)−va

%γa

3. B A

B γb, vb Enca(αa· ˆvb+ βa), Enca(αa) Enca(γb· (αa· (ˆvb− vb) + βa))

A $ Enca(αa· ˆvb+ βa)· Enca(αa)−vb %γb = Enca(γb· (αa· (ˆvb− vb) + βa)). (4.11) 4. γi A [γa, γb· (αa· (ˆvb− vb) + βa)] B [γb, γa· (αb· (ˆva− va) + βb)] 5. tN αa· (ˆvb− vb) + βa, αb· (ˆva− va) + βb tN γb· (αa· (ˆvb− vb) + βa)· γb−1 = αa· (ˆvb− vb) + βa, (4.12) γa· (αb· (ˆva− va) + βb)· γa−1 = αb· (ˆva− va) + βb. (4.13) 6. tN A B False True

4.4

A B A B Deca(Pa′′)∩ Ib′′ B 2 ηb, ηb′ ξb B A B Pa∩ Ib Decb(Pb′′)∩ Ia′′ ηa, ηa′ ξa A B A Pb∩ Ia

4.4.1

Deca(Pa′′)∩ Ib′′ ηb BVT ξb Pa∩ Ib 1. B ξb A A

2. A ξb Ib′′∩ Deca(Pa′′) ˆ Ib := Ib′′∩ Deca(Pa′′) ˆ I_b(i) ≡ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ η(i)_b (mod ξb), η′(i) b (mod ξb), η (mod ξb). (4.14) η ηb, ηb′ 3. A B 4. B 5. B ηb 4.5: B A B Pa∩ Ib

5

3

5.1

6. BVT lb = kb proof. BVT [31]( 2) 7. (5.1) αi, βi αi ∈ ZN, βi ∈ ZN, γi ∈ ZN αi · (n + li) + βi < N − 2tN−1, αi > βi > 0. (5.1) proof. ZN (0, 2tN−1) [2tN−1, N ) ∀x ∈ ZN x tx ̸= tN x tx = tN 2 αi· (ˆvi− vi) + βi vˆi ! vi ! αi· (ˆvi− vi) + βi < 2tN−1, αi· (ˆvi− vi) + βi < N − 2tN−1. (5.2) 2tN−1 ≥ N − 2tN−1 αi· (ˆvi− vi) + βi < N− 2tN−1 ≤ 2tN−1. (5.3) αi, βi vˆi ! vi • ˆvi ≥ vi αi· (ˆvi− vi) + βi tN • ˆvi < vi αi· (ˆvi− vi) + βi tN αi· (ˆvi− vi) + βi tN

8. ηb ξb

I_b′′ ηb i̸= j

ξb ∈ ZN, η_b(i) ∈ ZN, 0 < η_b(i) < ξb, η_b(i) ̸= η_b(j), (5.4)

) I_b(j)= ξb· (i(j)b + r (j) b ) + η (j) b < N. (5.5) proof. I′′ b BVT ηb ξb Ib′′ I)b y)b ) Ib = ξb· (Ib+ rb) + ηb. (5.6) ) I_b(i) )

I_b(i) ≡ η(i)b (mod ξb). (5.7)

ηb 9. ξb Deca(Pa′′)∩ Ib′′ ηb Pa∩ Ib proof. 8 Deca(Pa′′)∩ Ib′′ ηb ηb Pa∩ Ib

5.2

10. BVT proof. A B • Paillier Paillier IND-CPA A Encb(Pb) Pb • BVT [31]( 4)

11. semi-honest

proof. A vˆb ≷ vb Enca(γb · (αa· (ˆvb − vb) + βa)) Enca(αa·

(ˆvb− vb) + βa) γb· (αa· (ˆvb− vb) + βa) αa· (ˆvb− vb) + βa A γb A vˆb ! vb Paillier Encb(αb· ˆva+ βb) vˆa A vˆa ! va 12. proof. A ηb ηb′ Ib′′ I)b = ξb· (Ib+ rb) + ηb Ib+ rb rb A Ib+ rb Ib B ηb

5.3

3

5.3.1

5.1: [31] BVT _{O(n + l}a+ lb) -BVT [31] O(n + la+ lb) -O(1) O(1) FACFM [31] _{O(1) O(1)}

O(ˆva+ ˆvb)

-5.1 BVT

[31] [31]

BVT n

5.3.2

5.2 5.3 5.4 BVT BVT BVT 3.1 FACFM 2 n 5.2: BVT [bit] A 2tN · (2n + lb) -2tN · (n + la) -O(n + la+ lb) -5.3: [bit] 8tN + 1 16tN 8tN 16tN + 2 O(1) O(1) 5.4: [bit] A 2tN · (ˆva+ 1) 2tN · (ˆva+ ˆvb+ 2) 2tN · (ˆvb+ 1) 2tN · (ˆva+ ˆvb+ 2) O(ˆva+ ˆvb) O(ˆva+ ˆvb)

5.4

5.4.1

PC 2GB RAM 3GB RAM BVT Android Studio 2.2

OS Android 6.0.1 CPU Qualcomm Snapdragon S4 2GB RAM Nexus 7

5.4.2

A, B A, B BVT 1 A B 1 n = 10, 20, 30,_{· · · , 90} BVT BVT A B [31] BVT BVT BVT BVT [31] Update - 1 Process 2 ,4 2 ,4 Decrypt 5 5

BVT i = a, b ri 108 bit n ηi 108 bit n η′_i 108 bit n ξi 36 bit li 10 ki 1 10 i = a, b αi 36 bit βi 108 bit γi 1024 bit

5.4.3

BVT

BVT 5.5 5.5: BVT [msec] (n + l) 20 30 40 50 60 70 80 90 100 Update 1449.6 2154.6 2891.1 3624.4 4345.5 5059.5 5812.9 6475.0 7197.46 Process 2229.2 3667.3 5079.3 6605.1 8002.2 9585.9 11104.3 12439.4 13966.7 [31] Process 1476.9 2215.9 2932.6 3671.0 4431.0 5126.0 5909.2 6635.5 7378.9 Decrypt 2848.0 4242.6 5655.8 7059.8 8472.7 9872.1 11316.4 12697.7 14105.6 0 2000 4000 6000 8000 10000 12000 14000 20 30 40 50 60 70 80 90 100

Time [msec]

Number of Attributes and Security parameter (n + l) Update

Refined BVT-Process BVT-Process[ZDLG13] BVT-Decrypt

5.1 BVT BVT [31] n

O(n + la+ lb) Update Decrypt 2

Process 1.5 n + li 2n + li n BVT O(n + la+ lb)

5.4.4

FACFM [31] 5.6 5.6: FACFM [31] [msec] (n + l) 20 30 40 50 60 70 80 90 100 Process 751.1 769.5 755.2 770.1 760.3 767.1 752.9 764.4 758.3 [31] Process 593.2 589.3 603.4 592.1 592.0 592.9 589.5 579.3 593.9 0 200 400 600 800 1000 10 20 30 40 50 60 70 80 90 100 Time [msec]

Number of Attributes and Security parameter (n + l)

FACFM[ZDLG’13] Judge Protocol

5.2 FACFM [31] n O(1) FACFM 180 ms 1 FACFM

5.4.5

[31]

A, B [31] ! A : Pa= [1, 0, 0, 0, 0], Ia= [1, 1, 0, 0, 0], B : Pb = [1, 1, 0, 0, 1], Ib = [1, 0, 0, 1, 1]. (5.8) |Pa∩ Ib| = 3, |Pb∩ Ia| = 4 5.7: FACFM (n = 5) ❍❍ ❍❍ ❍❍❍ A B 1 2 3 4 5

1 False False False False False 2 False False False False False 3 False False False False False 4 False False True False False 5 False False False False False

5.7 FACFM ( [31] ) A BVT B _|Pb∩ Ia| = 4 FACFM B |Pa∩ Ib| = 3

5.8: (n = 5) ❍❍ ❍❍ ❍❍❍ A B 1 2 3 4 5

1 True True True False False 2 True True True False False 3 True True True False False 4 True True True False False 5 False False False False False

5.8 ( ) |Pb∩ Ia| = 4 τa = 1, 2, 3, 4 A B |Pa∩ Ib| = 3 τa >|Pb∩ Ia| τa =|Pb∩ Ia| τb ≤ |Pa∩ Ia|

5.4.6

5.9 5.9: [msec] 10 20 30 40 50 60 70 2374.0 4506.5 6605.6 8781.3 11037.6 13092.4 15208.3 [31] N/A N/A N/A N/A N/A N/A N/A

0 2000 4000 6000 8000 10000 12000 14000 16000 0 10 20 30 40 50 60 70 Time [msec]

Number of Intersection including dummies

Solving Intersection 5.3: 5.3 |Dec (P′′_{)∩ I}′′_| n li

6

[31]

6.1

2 1. 2. 6.1: 1 2 ⃝ ⃝ FNP04 [8] _{× △} IO16 [12] _{⃝ ×} LUB14 [18] × △ SX15 [25] × × TLSL15 [27] _{× △} ZDLG13 [31] _{⃝ ×} ZLJCL14 [32] × △ 6.11 _{1 2} BVT 10 11 1 ⃝ · · · △ · · · × · · ·

6.1

6.2

ZDLG13 [31]

6.2: (1) BVT [31] BVT malicious semi-honest O(n + li) O(n + li) O(n + li) O(n + li) × ⃝ 6.2 [31] BVT BVT n + li 2n + li n BVT 6.3: (2) FACFM [31] malicious semi-honest O(1) O(1) O(1) O(1) × ⃝ 6.3 [31] FACFM FACFM

7

semi-honest

8

8.1

• SCIS2016 2C1-3 2016 • (2) SCIS2017 3B3-3 2017

[1] http://www.skout.com/. [2] http://www.tagged.com/. [3] http://www.hi5.com/. [4] https://www.badoo.com/. [5] http://www.pof.com/.

[6] L. Batina, J. Hermans, J. Hoepman, and A. Krasnova. High-Speed Dating Privacy-Preserving Attribute Matching for RFID. RFIDSec 2014, pages 19–35, 2014.

[7] J. Camenisch and G. M. Zaverucha. Private Intersection of Certified Sets. FC 2009, 5628:108–127, 2009.

[8] M. J. Freedman, K. Nissim, and B. Pinkas. Efficient Private Matching and Set Intersection. EUROCRYPT, 3027:1–19, 2004.

[9] P. Gasti and K. B. Rasmussen. Privacy-preserving User Matching. WPES 2015, pages 111–120, 2015.

[10] D. He, Z. Cao, X. Dong, and J. Shen. User Self-controllable Profile Matching for Privacy-preserving Mobile Social Networks. IEEE ICCS 2014, pages 248–252, 2014. [11] Y. He, F. Li, B. Niu, and J. Hua. Achieving Secure and Accurate Friend Discovery

Based on Friend-of-Friend’s Recommendations. IEEE ICC 2016, pages 1–6, 2016. [12] Y. Ishikuro and K. Omote. Privacy-preserving profile matching protocol considering

conditions. NSS 2016, pages 171–183, 2016.

[13] C. Clifton J. Vaidy. Secure set intersection cardinality with application to association rule mining. Journal of Computer Security, 13(4):593–622, 2005.

[14] S. Jiang, X. Zhu, L. Guo, J. Liu, R. Hao, and B. Yang. Efficient Private Matching based on Blind Signature for Proximity-based Mobile Social Networks. IEEE ICC 2015, pages 3246–3251, 2015.

[15] M. Kim, H.T. Lee, and J.H. Cheon. Mutual Private Set Intersection with Linear Complexity. WISA 2011, pages 219–231, 2011.

[16] M. Li, N. Cao, S. Yu, and W. Lou. FindU: Privacy-Preserving Personal Profile Matching in Mobile Social Networks. IEEE INFOCOM 2011, pages 2435–2443, 2011. [17] M. Li, S. Yu, N. Cao, and W. Lou. Privacy-Preserving Distributed Profile Matching in Proximity-Based Mobile Social Networks. IEEE Trans. on Wireless Communications, 12(5):2024–2033, 2013.

[18] X. Liao, S. Uluagac, and R. A. Beyah. S-MATCH: Verifiable Privacy-preserving Profile Matching for Mobile Social Services. 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 287–298, 2014.

[19] E. Luo, Q. Liu, and G. Wang. NMHP: A Privacy Preserving Profile Matching Proto-col in Multi-hop Proximity Mobile Social Networks. ICA3PP 2015, pages 463–474, 2015.

[20] B. Pinkas M. Naor. Oblivious Polynomial Evaluation. SIAM J. Comput., pages 1254–1287, 2006.

[21] K. Omote. . CSS 2014, pages

659–666, 2014.

[22] P. Paillier. Public-key Cryptosystems Based on Composite Degree Residuosity Classes. EUROCRYPT, pages 223–238, 1999.

[23] P. Paillier and D. Pointcheval. Efficient Public-key Cryptosystems Provably Secure Against Actirve Adversaries. ASIACRYPT, pages 165–179, 1999.

[24] F. Qi and W. Wang. Efficient Private Matching Scheme for Friend Information Exchange. ICA3PP 2015, pages 492–503, 2015.

[25] S. Sarpong and C. Xu. Privacy-preserving Attribute Matchmaking in Proximity-based Mobile Social Networks. International Journal of Security and Its Applications, 9(5):217–230, 2015.

[26] A. Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.

[27] A. Thapa, M. Li, S. Salinas, and P. Li. Asymmetric Social Proximity Based Pri-vate Matching Protocols for Online Social Networks. IEEE Trans. on Parallel and Distributed Systems 2015, 26(6):1547–1559, 2014.

[28] Y. Wang, X. Chen, Q. Jin, and J. Ma. LIP3: A Lightweighted Fine-Grained Privacy-Preserving Profile Matching Mechanism for Mobile Social Networks in Proximity. ICA3PP 2015, pages 166–176, 2015.

[29] Z. B. Chen Z. Some formal analysis of rocchio’s similarity-based relevance feedback algorithm. Algorithm and Computation, 19(69):108–119, 2000.

[30] R. Zhang, Y. Zhang, J.S. Sun, and G. Yan. Fine-grained Private Matching for Proximity-based Mobile Social Networking. IEEE INFOCOM 2012, pages 1969– 1977, 2012.

[31] H. Zhu, S. Du, M. Li, and Z. Gao. Fairness-Aware and Privacy-Preserving Friend Matching Protocol in Mobile Social Networks. IEEE Transactions on Emerging Topics in Computing, 1(1):192–200, 2013.

[32] X. Zhu, J. Liu, S. Jiang, Z. Chen, and H. Li. Efficient Weight-based Private Matching for Proximity-based Mobile Social Networks. IEEE ICC 2014, pages 4114–4119, 2014.