โปรโตคอลการตัดกันชุดส่วนตัวที่มีประสิทธิภาพสำหรับชุดขนาดเล็ก

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

• ใน Diffie-Hellman ตาม โปรโตคอล (มีต้นกำเนิดใน ฮูเบอร์แมน-แฟรงคลิน-ฮอกก์) คู่สัญญาต้องคำนวณเลขชี้กำลังเล็กน้อยสำหรับแต่ละรายการในชุดของตน

• ใน ลบเลือนตามการถ่ายโอน โปรโตคอล (ตัวนำในกรณีนี้คือ เคเคอาร์ที และ เชส-แม้ว) ฝ่ายแรกดำเนินการ OT ฐานสองสามร้อยครั้ง (แต่ละครั้งต้องการการยกกำลังสองสามครั้ง) โดยไม่คำนึงถึงขนาดของชุด PSI ทุกอย่างที่ตามมาในโปรโตคอลจะใช้เฉพาะการดำเนินการคีย์สมมาตรที่มีประสิทธิภาพมากกว่าเท่านั้น เช่น การเรียกไปยัง AES/SHA

วิธี Diffie-Hellman มีต้นทุนการสื่อสารที่ต่ำกว่าเสมอ ไม่ว่าชุด PSI จะใหญ่แค่ไหนก็ตาม และเมื่อชุด PSI มีขนาดเล็ก เวลาในการดำเนินการยกกำลังเล็กน้อยต่อรายการจะน้อยกว่าเวลาในการดำเนินการ "ฐาน OT" ของโปรโตคอลอื่นๆ โดยทั่วไป Diffie-Hellman PSI สำหรับชุดเล็ก เป็นกฎง่ายๆ

แต่เล็กแค่ไหน? คุณพูดถึงชุดที่มี ~1,000 รายการ ด้วยชุดข้อมูลขนาดนี้ จึงไม่ชัดเจนว่าโปรโตคอลใดดีที่สุดอีกต่อไป ในการทดลองที่เราดำเนินการในกลุ่มวิจัยของเรา จุดตัด (ซึ่งโปรโตคอลที่ใช้ OT จะเร็วขึ้น) อยู่ที่ต่ำกว่า 500 รายการบนเครือข่ายที่เร็วมาก และสูงกว่า 1,000 รายการบนเครือข่ายที่ช้ามากแต่แม้ในเครือข่ายที่รวดเร็ว ความแตกต่างของประสิทธิภาพก็ไม่มีอะไรต้องกังวลสำหรับแอปพลิเคชันนี้: เรากำลังพูดถึง 0.35 เทียบกับ 0.25 วินาทีในการดำเนินการ PSI

สรุป, ฉันอยากจะแนะนำให้ใช้โปรโตคอล Diffie-Hellman PSI ของ Huberman-Franklin-Hogg เนื่องจาก (1) เวลาทำงานใกล้เคียงกับค่าต่ำสุดมากพอ (2) การสื่อสารต่ำที่สุด; (3) ความเรียบง่ายของโปรโตคอลทำให้ง่ายต่อการนำไปใช้

แก้ไขธันวาคม 2564: เราเพิ่งเผยแพร่ ปรับปรุงโปรโตคอล Huberman-Franklin-Hogg สำหรับ PSI ในชุดเล็ก เร็วกว่า ใช้การสื่อสารน้อยกว่า และมีความปลอดภัย (ที่เป็นอันตราย) ที่แข็งแกร่งกว่า นี่จะเป็นคำแนะนำล่าสุดของฉัน

เพื่อตอบคำถามของคุณเกี่ยวกับ PSI แบบหลายฝ่าย: ตอนนี้ค่อนข้างง่ายที่จะแปลงโปรโตคอล PSI แบบ 2 ฝ่ายเป็นหลายฝ่าย

โปรโตคอล PSI ส่วนใหญ่สร้างขึ้นจาก PRF ที่หลงลืม (ใน Diffie-Hellman PSI นั้น PRF ที่หลงลืมคือ $x \mapsto H(x)^k$ ที่ไหน $H$ เป็นออราเคิลแบบสุ่ม) ใน กมธ เราได้แสดงวิธีสร้าง PSI แบบหลายฝ่ายจาก OPRF แบบ 2 ฝ่าย สิ่งก่อสร้างหนึ่งมีความปลอดภัยต่อศัตรูกึ่งซื่อตรง และอีกสิ่งหนึ่งมีคุณสมบัติการรักษาความปลอดภัยพร้อมการพิมพ์ที่ละเอียดยิ่งขึ้น ใน กระดาษ ซึ่งจะปรากฏใน Crypto 2021 เราแสดงให้เห็นว่าการก่อสร้างครั้งที่สองนี้ปลอดภัยจากศัตรูที่เป็นอันตราย

โดยรวมแล้ว PSI แบบหลายฝ่ายเกี่ยวข้องกับแต่ละฝ่ายที่ทำการแก้ไข PSI แบบ 2 ฝ่ายโดยมีฝ่ายกลางฝ่ายเดียว (ฝ่ายที่ได้รับเอาต์พุต)