ข้อความ

การเปรียบเทียบความเป็นส่วนตัวหมายถึงการได้รับความสัมพันธ์ระหว่างสองฝ่ายโดยไม่เปิดเผยค่าเฉพาะของทั้งสองฝ่าย ปัญหาของเศรษฐีเริ่มต้นจากเหยา จื่อจื้อ: มีเศรษฐีสองคนที่ต้องการเปรียบเทียบว่าใครรวยกว่ากันแต่พวกเขาไม่ต้องการเปิดเผยว่าพวกเขามีเงินเท่าไร พวกเขาจะสามารถเปรียบเทียบได้อย่างไรหากปราศจากบุคคลที่สามที่เชื่อถือได้? คำถามนี้ถูกตั้งขึ้นในทศวรรษที่ 1980 โดย Yao Qizhi ผู้ชนะรางวัล Turing Award คนแรกและคนเดียวในจีน เขาเป็นคนแรกในวิทยาการคอมพิวเตอร์และการศึกษาในจีน และเปิดประตูใหม่สำหรับการเข้ารหัสสมัยใหม่

ในบทความก่อนหน้านี้ "Elegant Job Hunting—ตัวอย่างอัลกอริทึมการเปรียบเทียบความเป็นส่วนตัว" ได้มีการแนะนำสถานการณ์การใช้งานของการเปรียบเทียบความเป็นส่วนตัวและวิธีนำไปใช้ผ่านกรณีการหางาน บทความนี้แนะนำโปรโตคอลการเปรียบเทียบความเป็นส่วนตัวที่มีประสิทธิภาพค่อนข้างสูงในปัจจุบันเป็นหลัก

โปรโตคอลนี้เป็นโปรโตคอลย่อยที่เสนอใน [1] CrypTFlow2: Practical 2-Party SecureInference และตามโปรโตคอลนี้ ฟังก์ชันการเปิดใช้งาน DRelu จะถูกนำไปใช้กับโครงข่ายประสาทเทียม

--เทคโนโลยีที่เกี่ยวข้อง--

โปรโตคอลส่วนใหญ่สร้างขึ้นโดยใช้สองเทคโนโลยีของการแชร์ความลับแบบบูลีนและการส่งผ่านแบบลืมเลือน:

▲ การส่งโดยไม่ได้ตั้งใจ

การถ่ายโอนแบบลืมเลือน (OT, Oblivious Transfer) หมายถึง ผู้ส่งข้อมูลมีข้อมูล n ข้อมูล ผู้รับข้อมูลได้รับข้อมูลอย่างใดอย่างหนึ่ง และผู้รับข้อมูลไม่สามารถรับข้อมูลอื่นได้ และผู้ส่งข้อมูลไม่ทราบรายละเอียดของข้อมูลที่ผู้รับ เลือกรับแบบไหนดี โครงร่างการใช้งานได้รับการแนะนำในบทความก่อนหน้านี้ "เทคโนโลยีคอมพิวเตอร์ส่วนบุคคลตาม Secure Multi-Party Computation (MPC) (1)" ดังนั้นบทความนี้จะไม่ทำซ้ำ

▲ การแชร์ความลับแบบบูลีน

ในการประมวลผลแบบหลายฝ่ายที่ปลอดภัย การแชร์แบบลับจะใช้เพื่อแยกข้อมูลและแชร์ออก แต่ละฝ่ายจะได้รับแฟรกเมนต์ที่สอดคล้องกันของแต่ละข้อมูล และตรรกะการคำนวณสำหรับข้อมูลต้นฉบับจะถูกแปลงเป็นการคำนวณของแฟรกเมนต์ หลังจากนั้น ตรรกะการคำนวณทั้งหมดเสร็จสมบูรณ์ จากนั้นรวมและกู้คืนผลการคำนวณของแฟรกเมนต์เพื่อให้ได้ผลลัพธ์การคำนวณของข้อมูลต้นฉบับ

การแชร์ข้อมูลลับแบบบูลีนหมายถึงการแบ่งค่าบูลีน b ออกเป็นสองส่วน b0 และ b1 และนำทั้งสองส่วนมารวมกันเพื่อกู้คืนข้อมูลต้นฉบับ b

การสร้างแฟรกเมนต์: สุ่มสร้างค่าบูลีน b0 และดำเนินการ XOR ด้วย b เพื่อคำนวณ b1=b0⊕b

 b=b0⊕b1

Shard Restore: ดำเนินการ XOR บนสองส่วนย่อย

      a=a0⊕a1，b=b0⊕b1

      a⊕b=(a0⊕b0)⊕(a1⊕b1)

การดำเนินการ XOR: การแบ่งปันความลับแบบบูลีนเป็นไปตามคุณสมบัติโฮโมมอร์ฟิกในการดำเนินการ XOR และดำเนินการ XOR กับแฟรกเมนต์ในเครื่อง จากนั้นกู้คืนจะเทียบเท่ากับการดำเนินการ XOR กับข้อมูลต้นฉบับ

และการดำเนินการ: การแบ่งปันความลับแบบบูลีนไม่เป็นไปตามคุณสมบัติโฮโมมอร์ฟิกสำหรับการดำเนินการ AND และใช้เทคโนโลยีการถ่ายโอนที่ลืมเลือนเพื่อให้ได้การดำเนินการและความปลอดภัย:

Alice เก็บเศษส่วน a0 และ b0, Bob เก็บเศษส่วน a1 และ b1, ผ่านการดำเนินการ AND, Alice ได้รับ c0, Bob ได้รับ c1, c0⊕c1=(a0⊕a1)∧(b0⊕b1) และความปลอดภัยของทั้งสองส่วนคือ รับประกัน ;

*Alice ในฐานะผู้ส่งการส่งผ่านที่ถูกลบเลือน สุ่มสร้างค่าบูลีน r เป็น c0 และสร้างอินพุตของการส่งสัญญาณที่หลงลืมดังที่แสดงด้านล่าง:

*Bob ในฐานะผู้รับการส่งข้อมูลโดยไม่ตั้งใจ ประกบชิ้นส่วน a1 และ b1 ของเขาเข้ากับ a1||b1 เพื่อเป็นทางเลือกสำหรับการส่งข้อมูลโดยไม่ตั้งใจเพื่อรับข้อมูล r⊕((a0⊕a1)∧(b0⊕b1)) เป็น c1;

ตรวจสอบได้ว่า c0⊕c1= r⊕r⊕((a0⊕a1)∧(b0⊕b1))=(a0⊕a1)∧(b0⊕b1);

สาระสำคัญคือการแสดงรายการความเป็นไปได้ทั้งหมดของการดำเนินการ AND และหลังจากเพิ่มรายการสุ่ม อีกฝ่ายเลือกผลการคำนวณที่สับสนตามข้อมูลของตนเอง

--แนวคิดการดำเนินการ--

▲ การเปรียบเทียบข้อความล้วน

ประการแรก โดยไม่คำนึงถึงความเป็นส่วนตัวของการดำเนินการเปรียบเทียบ ตัวเลขสองตัวจะเปรียบเทียบในสถานการณ์ปกติได้อย่างไร:

a=123，b=5879，a=>[0,1,2,3]，b=>[5,8,7,9]

*จัดตัวเลขทั้งสองให้อยู่ในอาร์เรย์ดิจิทัลที่มีความยาวเท่ากัน หากความยาวไม่เพียงพอ ให้เติม 0 ข้างหน้า

*เปรียบเทียบตัวเลขในสองอาร์เรย์ตามลำดับ หากตัวเลขในหลักที่ตรงกันเท่ากัน ให้เปรียบเทียบตัวเลขถัดไปต่อไปจนกว่าตัวเลขหนึ่งจะไม่เท่ากัน ผลการเปรียบเทียบของตัวเลขแรกสุดที่ไม่เท่ากันคือผลการเปรียบเทียบของข้อมูลทั้งสอง ถ้า ถ้าทุกหลักเท่ากัน แสดงว่าสองจำนวนนั้นเท่ากัน สรุปกระบวนการทั้งหมดได้เป็นสูตรดังนี้

ทั้ง X และ Y เป็นข้อมูลที่มีความยาว n, 1{X

X=x0||x1||x2||...||x(n-1), Y=y0||y1||y2||...||y(n-1), xi, yi หมายถึง ข้อมูล i-th หลังจากแยก

1{X

1{X1

     ...

1{X(n-1)

Xi=xi||...||x(n-1), Yi=yi||...||y(n-1) ใช้เพื่อแสดงข้อมูลหลังจากลบบิต i-1 แรก

▲ การเปรียบเทียบความเป็นส่วนตัวที่ไม่ปลอดภัย

หากคุณต้องการแปลงรูปแบบการเปรียบเทียบข้างต้นเป็นการเปรียบเทียบแบบส่วนตัว วิธีคิดที่ง่ายที่สุดคือการเปรียบเทียบหน่วยเปรียบเทียบที่เล็กที่สุดสองหน่วยเป็นแบบส่วนตัว ซึ่งได้แนะนำไปแล้วในบทความก่อนหน้านี้ "การหางานที่สง่างาม—อัลกอริทึมการเปรียบเทียบความเป็นส่วนตัว ตัวอย่าง": การเปรียบเทียบหน่วยเปรียบเทียบที่เล็กที่สุดสองหน่วยสามารถทำได้ผ่านโปรโตคอลการถ่ายโอนที่ลืมเลือน สิ่งนี้รับประกันความปลอดภัยของหน่วยเปรียบเทียบขั้นต่ำหน่วยเดียว แต่ในบางกรณี ข้อมูลบางสถานการณ์จะถูกเปิดเผย:

a=1230 b=1231 สำหรับการเปรียบเทียบตัวเลขสองตัวนี้ ถ้า b เป็นผู้รับของ ot ซึ่งก็คือผู้ได้รับผลการเปรียบเทียบข้อมูลของหน่วยเปรียบเทียบที่เล็กที่สุด และทำการเปรียบเทียบตามรูปแบบข้างต้น ข้อมูลเพิ่มเติมสองรายการจะรั่วไหลออกมา:

1) เมื่อเลขสองสามตัวแรกเหมือนกัน: b จะรู้ว่าสามตัวแรกของ a คือ 123;

2) ข้อมูลของหน่วยที่เล็กที่สุดสองหน่วยคือข้อมูลที่ปลายทั้งสองของช่วงหน่วยที่เล็กที่สุด: b จะรู้ว่าหลักสุดท้ายของ a คือ 0;

▲ ขจัดความไม่ปลอดภัย

ข้อความ

ในโปรโตคอลการเปรียบเทียบความเป็นส่วนตัวในเอกสารนี้ แนวคิดการเปรียบเทียบทั้งหมดสอดคล้องกับการเปรียบเทียบความเป็นส่วนตัวที่ไม่ปลอดภัยด้านบน แต่โปรโตคอลนี้แนะนำเทคโนโลยีการแบ่งปันความลับ และผู้ส่งสับสนกับข้อมูลก่อนหน้าสำหรับแต่ละข้อมูลเมื่อได้รับผลการเปรียบเทียบผ่านการถ่ายโอนโดยไม่ตั้งใจ protocol.random items เพื่อไม่ให้ฝ่ายใดฝ่ายหนึ่งได้ผลลัพธ์การเปรียบเทียบของข้อมูลหน่วยการเปรียบเทียบขั้นต่ำแต่เป็นแฟรกเมนต์ของผลการเปรียบเทียบ และใช้แฟรกเมนต์ในการเปรียบเทียบแบบเรียกซ้ำตามกระบวนการเปรียบเทียบแบบข้อความธรรมดา หลังจากหน่วยเปรียบเทียบขั้นต่ำทั้งหมดคือ เมื่อเปรียบเทียบแล้ว การเปรียบเทียบ ส่วนที่เป็นผลลัพธ์จะถูกกู้คืนเพื่อให้ได้ผลลัพธ์การเปรียบเทียบสำหรับข้อมูลทั้งหมด

เนื่องจากผลการเปรียบเทียบของหน่วยที่เล็กที่สุดเป็นเศษส่วนทั้งหมด ผลการคำนวณแบบเรียกซ้ำจะไม่ถูกเรียกคืนจนกว่าการเปรียบเทียบจะเสร็จสิ้น ดังนั้นจึงเป็นการหลีกเลี่ยงการรั่วไหลของข้อมูลที่เกิดจากการได้รับผลการเปรียบเทียบของหน่วยเปรียบเทียบที่เล็กที่สุด

--ขั้นตอนการตกลง--

อลิซมีข้อมูล x บ๊อบมีข้อมูล y ความยาวไบนารีของข้อมูลคือ l ความยาวไบนารีของหน่วยการเปรียบเทียบขั้นต่ำคือ m จำนวนหน่วยการเปรียบเทียบขั้นต่ำที่หารด้วย q=l/m และค่าสูงสุดที่เป็นทศนิยม ของหน่วยเปรียบเทียบขั้นต่ำคือ M= 2^m-1

1) ทั้งสองฝ่ายแบ่งข้อมูลแยกกัน: x=x0||...||x(q-1), y=y0||...||y(q-1)

2) สำหรับหน่วยเปรียบเทียบที่เล็กที่สุดทั้งหมด xi(0<=i_0，*Alice เตรียมข้อมูลเป็นผู้ส่งของการถ่ายโอนที่หลงลืม: การสร้างบูลีนแบบสุ่ม

sij=_0 ⊕ 1{xi

      tij=_0 ⊕ 1{xi=j}

_0 เนื่องจากส่วนการแชร์แบบบูลีนว่า xi น้อยกว่าหรือเท่ากับ yi ตามลำดับ สำหรับ 0<=j<=M อินพุตของอินสแตนซ์การถ่ายโอนโดยไม่ตั้งใจสองตัวจะถูกตั้งค่าตามลำดับดังนี้:

*Bob ใช้ yi เป็นอินพุตเพื่อดำเนินการถ่ายโอนโดยไม่ตั้งใจสองกรณีตามลำดับ และได้รับส่วนย่อยของผลการเปรียบเทียบสองรายการ:1

1 และ_0，ตัวอย่างเช่น เมื่อ m เป็น 2 หน่วยเปรียบเทียบขั้นต่ำหน่วยแรกของอลิซ x0=2 หน่วยเปรียบเทียบขั้นต่ำหน่วยแรกของบ๊อบ y0=1 อลิซจะสร้างแบบสุ่ม

_0 และสร้างอินพุตที่หลงลืมสองรายการดังนี้:

_1=0⊕_0，_1=0⊕_0

Bob ใช้ y0 เป็นตัวเลือกสำหรับการถ่ายโอนที่หลงลืม การรับ:

3) หลังจากการเปรียบเทียบหน่วยการเปรียบเทียบขั้นต่ำทั้งหมดเสร็จสิ้น ทั้งสองฝ่ายได้รับแฟรกเมนต์ที่ใช้ร่วมกันแบบบูลีนว่าหน่วยการเปรียบเทียบขั้นต่ำที่สอดคล้องกันนั้นน้อยกว่าหรือเท่ากันหรือไม่ จากนั้นสามารถทำตามขั้นตอนการเปรียบเทียบข้อความธรรมดาและใช้การเรียกซ้ำแฟรกเมนต์ เพื่อคำนวณเศษของผลการเปรียบเทียบขั้นสุดท้าย

สำหรับการดำเนินการ XOR ของแฟรกเมนต์ จำเป็นต้องดำเนินการ XOR ของแฟรกเมนต์ในเครื่องเท่านั้น สำหรับการดำเนินการ AND ของแฟรกเมนต์ จำเป็นต้องถ่ายโอนแฟรกเมนต์ของผลลัพธ์ที่คำนวณได้โดยไม่ตั้งใจตามโครงร่างที่แนะนำด้านบน

ในกระบวนการเรียกซ้ำ มีสองส่วนหลักที่ต้องดำเนินการ AND:

1{x0||x1 = y0||y1 } ∧ 1{x2 < y2 }

เมื่อหน่วยเปรียบเทียบก่อนหน้าทั้งหมดเท่ากันและจำเป็นต้องเปรียบเทียบหน่วยถัดไป:

1{x0||x1 = y0||y1} = 1{x0 = y0 } ∧ 1{x1 = y1 }

เมื่อคำนวณว่าหน่วยเปรียบเทียบก่อนหน้าทั้งหมดเท่ากันหรือไม่:

--สรุป--

สำหรับการเปรียบเทียบองค์ประกอบเดียว อินสแตนซ์ OT ของการดำเนินการไม่สามารถปรับให้เหมาะสมผ่านการขยาย OT ได้ เนื่องจากจำเป็นต้องมีการคำนวณแบบเรียกซ้ำ และมีการขึ้นต่อกันก่อนและหลัง สำหรับการเปรียบเทียบองค์ประกอบแบทช์ สามารถเพิ่มประสิทธิภาพผ่านการขยาย OT ในทิศทางแนวตั้งสำหรับอินสแตนซ์ OT ที่มีตำแหน่งและการทำงานเดียวกัน

เกี่ยวกับผู้เขียน

เกี่ยวกับผู้เขียน

ข้อความ

อ้างอิง

อ้างอิง