การใช้งานจริงของสมาชิกชุดส่วนตัว

คำชี้แจงปัญหา

จินตนาการว่าคุณมีชุด (ไม่มีองค์ประกอบที่ซ้ำกัน) เช่น S1 = {'a', 'b', 'c'}.

คุณต้องการแบ่งปันการเป็นตัวแทนส่วนตัว (และควรมีขนาดเล็กและปกป้องความสมบูรณ์) ของชุดนี้กับบุคคลอื่น (ซึ่งอาจมีคีย์ที่แบ่งปันล่วงหน้ากับคุณ) ซึ่งพวกเขาสามารถตรวจสอบได้ (ใช่หรือไม่) หากมีองค์ประกอบบางอย่างที่พวกเขาเลือก เช่น. 'ข' เป็นส่วนหนึ่งของชุด S1.

ชุดค่าผสมดั้งเดิมของการเข้ารหัสที่ง่ายที่สุดที่คุณสามารถใช้เพื่อแก้ปัญหานี้คืออะไร

ทิศทางจนถึงปัจจุบัน

ดูเหมือนว่าการแฮชชุดจะเหมาะ (ตรงข้ามกับการเข้ารหัสเพียงอย่างเดียว) เนื่องจากข้อจำกัดด้านขนาด

หากเราต้องการทำการเป็นสมาชิกแบบทึบ ให้ตรวจสอบว่าจำเป็นต้องมีการเข้ารหัสแบบโฮโมมอร์ฟิคบางประเภท

ฉันได้อ่านเกี่ยวกับ Private-Set-Intersection และ Private-Set-Membership แล้ว อย่างไรก็ตาม การใช้งานที่ฉันพบนั้นไม่น้อยเลย และมีฟังก์ชัน "อ่างล้างจาน" อื่นๆ ที่ไม่เป็นที่ต้องการ

บางคนอ่านจนถึงตอนนี้

• https://engineering.fb.com/2019/03/01/security/homomorphic-hashing/ (https://eprint.iacr.org/2019/227.pdf)
• https://github.com/google/private-membership
• ทางแยกส่วนตัวที่เร็วขึ้นขึ้นอยู่กับ ขยายโอที (pdf)
• การจับคู่ส่วนตัวอย่างมีประสิทธิภาพและตั้งค่าทางแยก (pdf)
• ทางแยกชุดที่ไม่สมดุลที่เร็วขึ้น (pdf)

คุณเพียงแค่ต้องการ PRF ที่หลงลืม อลิซคำนวณและส่ง $F_k(x)$ สำหรับทุกอย่าง $x \ใน S$, ที่ไหน $F$ เป็น PRF อลิซและบ็อบใช้โปรโตคอล OPRF เพื่อให้บ็อบเรียนรู้ $F_k(y)$ สำหรับค่า $y$ ทางเลือกของเขา ถ้า $y \ใน S$ จากนั้นบ๊อบจะเห็นการจับคู่กับค่าที่อลิซส่งมา ถ้า $y \ไม่\ใน S$ แล้วความสุ่มเสี่ยงของ $F$ เป็นนัยว่า $\{ F_k(x) \กลาง x \ใน S \}$ ทั้งหมดดูสุ่มแม้กระทั่งให้ $F_k(y)$. กล่าวอีกนัยหนึ่ง ค่าเหล่านี้ไม่รั่วไหลเกี่ยวกับค่าเฉพาะของ $x$ ใน $S$.

มีโปรโตคอล OPRF แบบกึ่งซื่อสัตย์ที่เรียบง่ายสำหรับ PRF $F_k(x) = H(x)^k$, ที่ไหน $H$ เป็นออราเคิลแบบสุ่ม มันทำงานดังนี้:

• บ๊อบสุ่มเลือก $r$ และส่ง $Y = H(y)^r$ ถึงอลิซ
• อลิซมาส่ง $Z = Y^k = H(y)^{rk}$ ถึงบ๊อบ
• Bob คำนวณผลลัพธ์ $Z^{1/r} = H(y)^k = F_k(y)$.

OPRFs ที่ปลอดภัยที่เป็นอันตรายไม่ได้มีราคาแพงกว่ามากนัก คุณสามารถหาได้ไม่กี่ ที่นี่ และ ที่นี่.

นี่คือสิ่งที่ฉันกำลังดำเนินการอยู่

ฉันต้องการ "เล็ก" ด้านล่างให้เล็กกว่าสิ่งต่อไปนี้มาก แต่สิ่งนี้จะใช้ได้กับจุดประสงค์ของคุณสำหรับชุดของสตริงไบนารี $S$, แฮชการเข้ารหัสลับ $H(x)$และคีย์ที่แบ่งปันล่วงหน้า $k$.

$H(S)=\text{sort} \{H(x) | x \ใน S\}$. เรียกสิ่งนี้ว่าพยานสาธารณะสำหรับ $S$. คุณสามารถซ่อนขนาดของชุดได้โดยการรวมแฮชแบบสุ่มเข้ากับโมดูลัสความยาวที่กำหนด นี่อาจเป็นพยานสาธารณะที่ไม่มีความซื่อสัตย์ แต่ให้แนวคิดพื้นฐาน

สมมติขนาดของ $x$ โดยทั่วไปจะมีขนาดใหญ่กว่า $H(x)$, การเป็นตัวแทนของพยาน $H(S)$ สำหรับ $S$ มีขนาดเล็กเมื่อเทียบกับตัวแทนสำหรับ $S$.

หากคุณต้องการจำกัดสิ่งนี้ให้กับผู้ที่มีคีย์สมมาตรแบบแบ่งล่วงหน้า k: (ฉันใช้ $+$ สำหรับต่อท้ายเพื่อแยกความแตกต่างจากชุด "so that")

$H^2(k+S)=\text{sort} \{H(k+H(k+x)) | x \ใน S\}$. ผนวกการตรวจสอบความถูกต้องของคีย์สำหรับการตรวจสอบความสมบูรณ์

$\text{พยานสำหรับ S}: H^2(k+S) + H(k+H^2(k+S))$

อีกครั้งเพื่อซ่อนขนาดของ $S$ คุณสามารถเพิ่มแฮชแบบสุ่มเป็นขนาดสูงสุดหรือ (ไม่สมบูรณ์) ให้กับโมดูลัสขนาด

ตรวจสอบการเป็นสมาชิก: ส่ง $(n,H(k+n) \bigoplus H(k+x))$ ที่ไหน $n$ เป็นตัวเลขที่เพิ่มขึ้น (อาจบอกโดยนัย เช่น การประทับเวลา) ผู้รับสามารถเปิดเผย $H(k+x)$ แล้วคำนวณ $H(k+H(k+x))$ เพื่อดูว่าอยู่ในชุดพยานหรือไม่