การค้นหามูลค่าที่ปลอดภัยด้วยการเข้ารหัสในชุด

ฉันกำลังมองหาวิธีแก้ไขที่สวยงามสำหรับปัญหาที่อาจดูเล็กน้อยในการค้นหาค่าเฉพาะในชุดค่าที่รู้จักโดยไม่เปิดเผยว่าค่าใดที่เรามองหา ให้ฉันอธิบายด้วยวิธีคลาสสิก:

อลิซจะฉลองวันเกิดของเธอในเร็วๆ นี้ และเธอต้องการทราบว่ามีใครในชั้นเรียนของเธอที่มีวันเกิดวันเดียวกับเธอบ้าง น่าเสียดาย คนเดียวที่รู้วันเกิดของทุกคนในชั้นเรียน (ยกเว้นคนเดียวของอลิซ) คือมาลอรี อลิซจะถาม Malory ได้อย่างไรว่าใครเกิดวันเดียวกันโดยไม่บอกวันที่ของเธอเอง?

สมมติฐาน:

1. Malory พร้อมที่จะช่วยเหลืออลิซและเธอจะตอบคำถามใด ๆ อย่างถูกต้องตามกฎหมาย แต่เธอตอบได้เพียงใช่หรือไม่เท่านั้น
2. อลิซจะถามมาลอรีเพียงครั้งเดียว มาลอรีไม่สามารถโน้มน้าวให้อลิซถามคำถามเดิมซ้ำได้แม้ว่าในอนาคต อลิซอาจจะถามเกี่ยวกับวันที่ต่างๆ ด้วยตัวเอง (เช่น วันเกิดของบ็อบ)
3. อลิซไม่ต้องการและไม่ต้องการรู้วันเกิดของทุกคนในชั้นเรียน เธออยากได้คำตอบจากมาโลรีที่ถามคำถามเดียว

วิธีที่ค่อนข้างตรงไปตรงมาในการแก้ไขปัญหานี้คือการใช้แฮช อลิซแฮชวันเกิดของเธอและส่งต่อข้อมูลนี้ให้กับมาลอรี ในขณะเดียวกันก็ขอให้เธอแฮชวันเกิดของทุกคนที่เธอรู้จักและบอกเธอว่าตรงกันหรือไม่ ปัญหาคือ Malory ที่ต้องการทราบวันเกิดของ Alice สามารถระบุวันที่ที่เป็นไปได้ทั้งหมด (เนื่องจากเอนโทรปีของการป้อนข้อมูลต่ำ) และตรวจสอบทีละรายการหากตรงกับสิ่งที่ Alice ถาม ฉันอยากจะกำจัดภัยคุกคามนั้น

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

ฉันหวังว่าฉันจะไม่ทำให้สับสนมากเกินไป และฉันจะขอบคุณสำหรับความช่วยเหลือ การอ้างอิง การกล่าวถึงอัลกอริทึม หรือปัญหาที่คล้ายกัน! ฉันจะขอบคุณความคิดเห็นของคุณหากคุณคิดว่าปัญหานี้ไม่สามารถแก้ไขได้ด้วยสมมติฐานที่กำหนด! หากบางส่วนไม่ชัดเจน โปรดแจ้งให้เราทราบ เราจะทำให้ดีที่สุดเพื่อชี้แจงเจตนา

คุณกำลังอธิบายปัญหาของ 1 จาก $n$ การถ่ายโอนที่หลงลืม กับ $n=366$ หากจำเป็นต้องให้อลิซไม่ได้รับข้อมูลที่ไม่เกี่ยวข้อง วิธีการของ Kolesnikov และคณะในบทความของพวกเขา âชุด PRF ที่หลงลืมอย่างมีประสิทธิภาพพร้อมแอปพลิเคชันไปยังจุดตัดส่วนตัวâ ให้ความรู้สึกถึงสิ่งที่เป็นไปได้

หากอลิซรับข้อมูลเพิ่มเติมได้แสดงว่าปัญหาคือหนึ่งในนั้น การดึงข้อมูลส่วนตัว. เอกสารการสำรวจของ Ostrovsky และ Skeith âการสำรวจการดึงข้อมูลส่วนตัวฐานข้อมูลเดียว: เทคนิคและแอปพลิเคชัน â ให้ภาพรวมที่ดี

วิธีที่สอง ง่ายกว่า ขอบคุณความคิดเห็นจาก @Mikero:

อลิซเลือกคีย์ส่วนตัวแบบสุ่มอย่างสม่ำเสมอ $ข$. วันเกิดของอลิซคือวันที่ $k$วันที่ของปี อลิซมาส่ง $A = bH_p(k)$ ไปที่ Malory ซึ่งทำหน้าที่ $H_p()$ หมายถึงแฮชอินพุตและตีความผลลัพธ์เป็นจุด EC

Malory เลือกคีย์ส่วนตัวแบบสุ่มอย่างสม่ำเสมอ $e$. มาลอรีมีหน้าที่ $F_e(i)$ ซึ่งเอาต์พุต $eH_p(i)$ หากมีบุคคลอย่างน้อยหนึ่งคนเกิดในวันนั้นของปี และมิฉะนั้นจะแสดงผลจุด EC ที่เลือกแบบสุ่ม

สำหรับแต่ละค่าของ $i$ ดังนั้น $0\leq ฉัน \leq 365$, มาลอรีส่ง $F_e(i)$ ถึงอลิซ นอกจากนี้ยังส่งมาลอรี $Q = eA$ ถึงอลิซ

อลิซคำนวณ $Z = b^{-1}Q == b^{-1}eA == b^{-1}ebH_p(k) == eH_p(k)$.

อลิซก็ตรวจสอบว่า $Z$ ตรงกับผลลัพธ์ใด ๆ จาก 366 ของ $F_e(i)$ ที่มาลอรีส่งมาให้อลิซ หากมีการจับคู่อลิซจะแบ่งปันวันเกิดกับคนอื่น

คำอธิบาย: เราได้สร้าง "1-OPRF" ซึ่งหมายถึงฟังก์ชันสุ่มหลอกที่หลงลืม ซึ่ง Alice สามารถสืบค้นได้เพียงครั้งเดียวโดยมี Malory คอยช่วยเหลือ แต่ Malory สามารถสืบค้นได้หลายครั้ง

PRF เป็นเพียง Malory ที่ทำให้จุด EC ทำให้ไม่เห็น $H_p(i)$ (ที่ไหน $H_p(i)$ หมายถึงวันใดวันหนึ่ง $i$ ของปีเป็นจุด EC) ด้วยรหัสส่วนตัวของเขา $e$โดยการคำนวณ $eH_p(i)$. เนื่องจากปัญหาล็อกไม่ต่อเนื่องของเส้นโค้งวงรี ไม่มีผู้สังเกตคนใด (รวมถึงอลิซ) สามารถทำนายผลลัพธ์ของ $eH_p(i)$ สำหรับใดๆ $i$ โดยไม่รู้ความลับ $e$. ซึ่งหมายความว่าเมื่อไม่มีใครเกิดในวันใดวันหนึ่ง อลิซไม่สามารถบอกได้ว่า Malory ได้ส่งจุด EC แบบสุ่มแทนเอาต์พุตจริงของ PRF เนื่องจากผลลัพธ์ของ PRF นั้นคาดเดาไม่ได้สำหรับอลิซ

อลิซปิดบังข้อมูลของเธอต่อ PRF โดยเลือกปัจจัยที่ทำให้ไม่เห็น $ข$ และส่ง $bH_p(k)$ ถึง Malory แทนที่จะส่ง (และเปิดเผย) $k$. อลิซไม่ปิดบังการตอบสนองโดยการย้อนกลับการคูณด้วย $ข$และด้วยเหตุนี้จึงสามารถค้นหา PRF ได้โดยที่ Malory ไม่มีความรู้เกี่ยวกับการป้อนข้อมูลที่ Alice กำลังใช้อยู่

ผลที่ตามมาคือ Malory ได้ส่งรายการคะแนน EC ให้กับ Alice ซึ่งรวมเฉพาะผลลัพธ์ที่แท้จริงของ PRF สำหรับวันนั้นๆ ของปีที่มีบุคคลอื่นอย่างน้อยหนึ่งคนเกิดในวันที่ นอกจากนี้ อลิซยังสามารถค้นหา PRF สุ่มสี่สุ่มห้าสำหรับผลลัพธ์ของวันเกิดเฉพาะของเธอ และสามารถดูว่าผลลัพธ์นั้นปรากฏในรายการผลลัพธ์ PRF ที่เป็นไปได้ที่ Malory ส่งถึงเธอหรือไม่

Malory ไม่ได้เรียนรู้ $k$และอลิซไม่สามารถเรียนรู้อะไรได้อีกนอกจากว่าเธอมีวันเกิดร่วมกับคนอื่นอย่างน้อยหนึ่งคนหรือไม่

แนวทางหนึ่งที่จะทำ การถ่ายโอนแบบลืมเลือน 1-out-of-n. Malory จะส่งรายการบูลีนเข้ารหัส 366 รายการให้อลิซ (เพื่อให้วันเกิดวันที่ 29 ก.พ.) โดยที่บูลีนแต่ละตัวจะบ่งบอกว่าใครมีวันเกิดในวันนั้นของปีอลิซจะสามารถถอดรหัสบูลีนตัวใดตัวหนึ่งจาก 366 ตัวเท่านั้น และจะสามารถรู้ได้ก็ต่อเมื่อมีใครเกิดในวันดังกล่าวของปีเท่านั้น

บทความวิกิพีเดียที่ฉันเชื่อมโยงในย่อหน้าด้านบนอ้างอิงถึงแนวทางการนำไปใช้หลายๆ วิธีเพื่อให้ได้การถ่ายโอนแบบ 1-out-of-n ที่ลืมเลือน นี่คือแนวทางหนึ่งที่ฉันคิดขึ้นในตอนนี้ (โดยให้เครดิตแก่ @IlmariKaronen สำหรับการปรับปรุงที่หรูหรามาก):

อลิซเกิดวันที่ $k$ แห่งปีที่ไหน $0\leq k\leq 365$. อลิซส่งรหัสสาธารณะ $P = xG-kH$ ไป Malory ที่ไหน $x$ เป็นคีย์ส่วนตัวสเกลาร์แบบสุ่มอย่างสม่ำเสมอ $H$ คำนวณเป็น $H = H_p(G)$โดยที่ฟังก์ชัน $H_p()$ หมายถึงการแฮชค่าและตีความผลลัพธ์เป็นจุด EC การเลือก $H$ ในลักษณะนี้หมายถึงบันทึกที่ไม่ต่อเนื่องของ $H$ w.r.t. $G$ เป็นสิ่งที่ไม่สามารถรู้ได้ เช่น $h$ ไม่สามารถรู้ได้เช่นนั้น $H==hG$.

Malory คำนวณ 366 กุญแจสาธารณะ $\{Q\}$ ของแบบฟอร์ม $Q_i=P+iH$ สำหรับค่าทั้งหมดของ $i$ ที่ไหน $0\leq ฉัน\leq 365$.

คีย์ส่วนตัวที่สอดคล้องกับคีย์สาธารณะแต่ละคีย์ $Q_i$ จะ $q_i == x - kh + ih == x+(i-k)h$.

เนื่องจากเราได้แสดงให้เห็นแล้วว่า $h$ เป็นสิ่งที่ไม่สามารถรู้ได้ หมายความว่า $q_i$ อลิซจะรู้ได้ก็ต่อเมื่อ $i=k$ซึ่งในกรณีนี้ $q_k$ จะเท่ากับ $x$.

ดังนั้น Malory จะคำนวณคีย์สาธารณะ 366 อัน ซึ่ง Malory สามารถมั่นใจได้ว่า Alice สามารถรู้คีย์ส่วนตัวที่เกี่ยวข้องกับหนึ่งในนั้นเท่านั้น

สำหรับแต่ละวันของปี $i$Malory ใช้รูปแบบ El Gamal ดังนี้: Malory เลือกสเกลาร์แบบสุ่มที่สม่ำเสมอ $e_i$และให้ทั้งคู่กับอลิซ $(อี_ไอ, ฟ_ไอ)$ ที่ไหน $E_i = e_iG$, $F_i = e_iQ_i + H_p(v_i)$ และที่ไหน $v_i$ จะระบุเป็น $0$ ถ้าไม่มีใครมีวันเกิดในวันนั้นของปีหรือเป็น $1$ ถ้าอย่างน้อยหนึ่งคนมีวันเกิดในวันนั้นของปี

เพื่อถอดรหัส $v_k$อลิซคำนวณ $V_k = F_k - xE_k$. จากนั้นอลิซจะตรวจสอบว่า $V_k\overset{?}{=}H_p(0)$ หรือ $V_k\overset{?}{=}H_p(1)$และทำให้รู้ว่าถ้า $v_k$ เป็น $0$ หรือ $1$. สิ่งนี้ใช้ได้เพราะ $q_k==x$ และ $Q_k==xG$และอื่น ๆ $xE_k==x\cdot e_kG==e_k\cdot xG==e_kQ_k$.

อลิซจะสามารถระบุได้ว่าคนอื่นเกิดวันไหนเท่านั้น $k$ ของปี และ Malory จะไม่สามารถระบุได้ $k$.

มีการดึงข้อมูลส่วนตัวที่แปลกใหม่พร้อมระบบ Homomorphic เต็มรูปแบบ

• 2014 แบนด์วิดท์ที่มีประสิทธิภาพ PIR จาก NTRU ยาร์กิน ดอเรซ, บี. ซูนาร์, เกธ ฮัมมูรี

นี่คือรูปแบบการเข้ารหัสส่วนตัวที่สามารถค่าที่ดัชนี $i$ จากอาร์เรย์บนเซิร์ฟเวอร์กึ่งซื่อสัตย์ เซิร์ฟเวอร์ไม่ได้เรียนรู้อะไรเลยและส่งคืนค่าที่ดัชนีเท่านั้น $i$. เราสามารถแก้ไขได้ดังนี้

1. Mallory เข้ารหัสวันเกิดที่มีอยู่ทั้งหมด $b_i$, $0 \leq ฉัน \leq 366 $ ด้วยรหัสสาธารณะ FHE ของอลิซ (การเข้ารหัสของ $366\cdot 8$ บิตไม่จำเป็นต้องทุกวัน วันเกิดที่มีอยู่เพียงพอและช่วยประหยัดพื้นที่ในชุดใหญ่

   $$c_i = \operatorname{FHE-Enc}(A_{ผับ}, b_i)$$

   ถ้าเราใช้ bit-based (HLibe, TFHE) ละก็ $c_i$ เป็นอาร์เรย์ขนาด 8

2. อลิซส่งวันเกิดของเธอ $A$ เข้ารหัสด้วยรหัสสาธารณะของเธอไปยัง Mallory (การเข้ารหัส 8 บิต)

   $$a = \operatorname{FHE-Enc}(A_{pub}, A)$$

3. Mallory ประหารชีวิต FHE วงจรความเท่าเทียมกัน ในแต่ละวันเกิดที่เข้ารหัส

   $$t_i = \operatorname{FHE-เปรียบเทียบ}(A_{pub}, c_i,a)$$

4. มัลลอรี่ หรือ ผลลัพธ์กับ FHE โดยใช้วิธีไบนารีทรีเพื่อลดความลึกของวงจร (เป็นไปได้ด้วยการรวมแทน หรือ) และส่งผลลัพธ์กลับไปยังอลิซ

   $$o = \operatorname{FHE-OrAll}(A_{ผับ}, [t_0,\ldots,t_n])$$

5. อลิซถอดรหัสผลลัพธ์ นิดหน่อย ด้วยรหัสส่วนตัวของพวกเขา

   $$ b = \operatorname{FHE-ธ.ค}(A_{priv})$$

   • ถ้า $b=1$ จากนั้นมีนักเรียนอย่างน้อยหนึ่งคนที่มีวันที่ $A$
   • ถ้า $b=0$ จากนั้นไม่มีนักเรียนที่มีวันที่ $A$.

รับประกันอะไร

1. Mallory ไม่สามารถเรียนรู้ว่าข้อมูลที่สืบค้นคืออะไร $A$ เนื่องจากมันถูกเข้ารหัสด้วย FHE - จึงมีความปลอดภัยเชิงความหมาย
2. Mallory ไม่สามารถชักนำข้อมูลที่สืบค้นจากผลลัพธ์ได้ด้วยเหตุผลเดียวกับข้างต้น จาก $(อ,o)$.
3. วงจรไม่เปิดเผยอะไรเกี่ยวกับข้อมูลภายในนอกเหนือจากฟังก์ชันที่คำนวณ - วงจรจะคำนวณการมีอยู่ของข้อมูลโดยไม่เปิดเผยผลลัพธ์
4. อลิซเรียนรู้การมีอยู่ของวันเกิดเท่านั้น! อลิซได้รับเพียงเล็กน้อย $ข$, มีอยู่หรือไม่. การดำเนินการนี้จะไม่ส่งคืนการนับวันเกิดที่เท่ากัน
5. อลิซสอบถามเพียงครั้งเดียว
6. Mallory ส่งการเข้ารหัสเพียงหนึ่งบิตเท่านั้น $ข$! ดังนั้นจึงเป็นโครงการที่ค่อนข้างมีประสิทธิภาพ

1. Mallory เตรียมบิตอาร์เรย์ขนาด 366 ที่เริ่มต้นเป็นศูนย์ $$B = [b_0,b_1,\ldots,b_{366}] = 0$$

2. Mallory ตั้งวันเกิดที่มีอยู่เป็น 1. ชอบ; $$B = [0,0,1,\ldots,0] $$

3. Mallory เข้ารหัสอาร์เรย์บิตด้วยคีย์สาธารณะของอลิซ (คีย์สาธารณะ FHE) และรับอาร์เรย์ขนาด 366 อีกชุดหนึ่ง

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, B[i]) \;\; \text{สำหรับ }\; 0\leq ฉัน \leq 366 $$

4. อลิซเตรียมบิตอาร์เรย์ขนาด 366 อีกชุดโดยตั้งค่าเฉพาะวันเกิดของเธอเป็น 1 ส่วนที่เหลือตั้งค่าเป็น 0 $$A = [0,0,0,\ldots,1,\ldots,0] $$

5. เช่นเดียวกับมัลลอรี่ อลิซใช้อาร์เรย์ด้วยคีย์สาธารณะของเธอ และส่งอาร์เรย์ที่เป็นผลลัพธ์ไปยังมัลลอรี่

   $$a_i = \operatorname{FHE-Enc}(A_{pub}, A[i]) \;\; \text{สำหรับ }\; 0\leq ฉัน \leq 366 $$

6. Mallory ดำเนินการส่วนประกอบการดำเนินการ FHE-AND อย่างชาญฉลาดบนอาร์เรย์ที่เข้ารหัส $$c_i = \operatorname{FHE-และ}(A_{pub}, A[i], B[i])$$

7. มัลลอรี่ หรือ บิตของอาร์เรย์ที่เป็นผลลัพธ์และส่งผลลัพธ์กลับไปยังอลิซ

   $$b = \operatorname{FHE-OrAll}(A_{ผับ}, [c_0,\ldots,c_{366}])$$

8. อลิซถอดรหัสผลลัพธ์ นิดหน่อย ด้วยรหัสส่วนตัวของพวกเขา

   $$ b = \operatorname{FHE-ธ.ค}(A_{priv})$$

   • ถ้า $b=1$ จากนั้นมีนักเรียนอย่างน้อยหนึ่งคนที่มีวันที่ $A$
   • ถ้า $b=0$ จากนั้นไม่มีนักเรียนที่มีวันที่ $A$.

รับประกันอะไร

1. เช่นเดียวกับโครงร่างพื้นฐาน
2. ครั้งนี้แทนที่จะเข้ารหัส 9 บิต Alice เข้ารหัส 366 บิต (เพิ่มขึ้นประมาณ 40 เท่าของต้นทุนการส่งเริ่มต้น/ครั้ง)
3. ในทางกลับกัน Mallory ได้รับการปรับปรุงอย่างมากในด้านเวลาและหน่วยความจำ
   1. ไม่จำเป็นต้องมีการดำเนินการความเท่าเทียมกันของ FHE ที่หนักหน่วง
   2. ขนาดของไซเฟอร์เท็กซ์ที่เก็บไว้ลดลง ~40
4. ในทางกลับกันผลลัพธ์ยังคงเป็นการเข้ารหัสแบบ 1 บิต
5. โครงร่างนี้ช่วยประหยัดเวลาในกระบวนการได้มาก