Score:14

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

ธง cn
vnd

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

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

สมมติฐาน:

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

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

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

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

cn flag
vnd
การโกหกเป็นสิ่งที่ไม่พึงปรารถนา แต่ก็ไม่ใช่เป้าหมายของฉันที่จะป้องกันไม่ให้มันเกิดขึ้น เป้าหมายหลักของฉันคือป้องกันไม่ให้ Malory เปิดเผยวันเดือนปีเกิดของ Alice โดยถือว่า Malory ไม่สนใจที่จะให้คำตอบผิดๆ
Mark avatar
ng flag
อาจช่วยได้ถ้าคุณชี้แจงว่า "อลิซไม่ต้องการและไม่ต้องการรู้วันเกิดของทุกคนในชั้นเรียน เธอต้องการได้รับคำตอบจากมาลอรีที่ถามคำถามเดียว" สิ่งนี้สามารถอ่านได้ว่า "คุณไม่จำเป็นต้องส่งผ่านฐานข้อมูลทั้งหมด (แต่สามารถทำได้ถ้าคุณต้องการ)" หรือ "โปรโตคอลควรมีคุณสมบัติเป็นศูนย์" (ซึ่งการส่งฐานข้อมูลจะเป็นการละเมิด) คำตอบจนถึงตอนนี้ถือว่าเป็นคำตอบที่สอง แต่ถ้าคำตอบแรกใช้ได้ แสดงว่ามีประสิทธิภาพ *มาก* กว่า ในขณะที่ยังคงตอบสนองคุณสมบัติด้านความปลอดภัยทั้งหมดที่คุณต้องการ
Score:13
ธง ru

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

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

kelalaka avatar
in flag
แบบสำรวจเกี่ยวกับ PIR นี้เก่าแล้ว และมีแบบสำรวจเกี่ยวกับการวัดค่า PIR (ชื่อ UNY แต่จำชื่อผู้เขียนไม่ได้ว่า Gene Tsudik หรือเปล่า) ซึ่งถ้าไคลเอนต์ดาวน์โหลดข้อมูลทั้งหมดและกระบวนการในเครื่องจะเร็วกว่าแบบแผนที่มีอยู่ทั้งหมด PIR ฉบับใหม่อ้างอิงจาก [FHE](https://pdfs.semanticscholar.org/bfde/352ba1bdb70bf850b18a08c9da092489b698.pdf) แม้ว่าเซิร์ฟเวอร์จะคำนวณการดำเนินการของ FHE...
Score:5
ธง es

วิธีที่สอง ง่ายกว่า ขอบคุณความคิดเห็นจาก @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$และอลิซไม่สามารถเรียนรู้อะไรได้อีกนอกจากว่าเธอมีวันเกิดร่วมกับคนอื่นอย่างน้อยหนึ่งคนหรือไม่

Matthieu M. avatar
ru flag
ทำไมอลิซเดา `e` ในโครงร่างนี้ไม่ได้ พวกเขารู้จัก `A` และ `Q = eA` พวกเขาไม่สามารถ "แบ่ง" `Q` ด้วย `A` เพื่อเข้าถึง `e` ได้ไหม
knaccc avatar
es flag
@MatthieuM ปัญหาบันทึกไม่ต่อเนื่องของเส้นโค้งวงรีหมายความว่าคุณไม่สามารถ "แบ่ง" จุดหนึ่งไปยังอีกจุดหนึ่งได้ ถ้าทำได้ คุณสามารถดูพับลิกคีย์และกำหนดไพรเวตคีย์ได้อย่างง่ายดาย
Score:4
ธง es

แนวทางหนึ่งที่จะทำ การถ่ายโอนแบบลืมเลือน 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$.

ar flag
ฉันไม่แน่ใจว่าฉันเข้าใจแผนการของคุณทั้งหมด แต่เกิดขึ้นกับฉันว่า แทนที่จะยุ่งกับลายเซ็นแหวน อลิซไม่สามารถปล่อยให้ $C_i = (i-k)H_p(G) + c_kG$ ได้ไหม ด้วยวิธีนี้ Mallory สามารถตรวจสอบได้ว่า $C_{i+1} = H_p(G) + C_i$ ถือ $C_i$ ทั้งหมด และด้วยเหตุนี้จึงมั่นใจได้ว่า Alice ไม่สามารถทราบบันทึกแยกสำหรับมากกว่าหนึ่งรายการ (อลิซไม่จำเป็นต้องส่งคะแนนทั้งหมดให้มัลลอรี่ด้วยซ้ำ เพราะมัลลอรี่สามารถคำนวณคะแนนทั้งหมดจาก $C_0$ ด้วยการบวกคะแนนซ้ำๆ) หรือบางทีฉันอาจทำบางอย่างผิดพลาด เป็นไปได้เสมอ เนื่องจากฉันไม่คุ้นเคยกับ ECC มากนัก
knaccc avatar
es flag
@IlmariKaronen สง่างามมาก คุณพูดถูก ฉันหวังว่าฉันจะคิดแบบนั้น! ฉันจะแก้ไขคำตอบของฉัน
us flag
ฉันเชื่อว่าคำตอบนี้กำลังมุ่งสู่ Oblivious PRF Alice & Mallory ใช้โปรโตคอล OPRF โดยที่ Alice เรียนรู้ฟังก์ชันสุ่ม $F : \{1,\ldots,365\} \to \{0,1\}^\lambda$ และ Mallory เรียนรู้ $F(i)$ โดยที่ $ i$ คือวันเกิดของเธอ เนื่องจากเป็น PRF ผลลัพธ์อื่นๆ ทั้งหมดของ $F$ จึงดูสุ่มสำหรับเธอ อลิซสามารถส่ง $\{ F(j) \mid j \in \mbox{Birthdays}\}$ และมัลลอรี่สามารถดูว่าตรงกันหรือไม่ [เป็นไปได้จริงๆ](https://ia.cr/2020/1043) ที่จะทำ OPRF แบบนี้ด้วยการสื่อสารอย่างต่อเนื่อง ลิงก์นั้นมีโปรโตคอลที่ปลอดภัยสำหรับ UC; ฉันสงสัยว่าหนึ่งในคำถามนี้คือ UC ปลอดภัย
knaccc avatar
es flag
@Mikero ขอบคุณ นั่นเป็นบทความที่น่าสนใจ ฉันไม่ได้ทำตามที่คุณพูดทั้งหมด แต่ฉันได้เพิ่มคำตอบที่สองสำหรับคำถามนี้ซึ่งรวมแนวทาง 1-OPRF จากบทความนี้ มีการปรับปรุงวิธีการของฉันหรือไม่?
knaccc avatar
es flag
@Mikero คุณอาจหมายถึงการบอกว่าจะเป็น Malory ที่จะส่ง $\{F(j)\}$ ให้ Alice แทนที่จะเป็นอย่างอื่น?
us flag
ใช่ ฉันเชื่อว่าฉันสลับชื่อของทั้งสองฝ่ายโดยไม่ได้ตั้งใจ (สายเกินไปที่จะแก้ไขความคิดเห็นในตอนนี้)
Score:4
ธง cn
Mac

ยินดีต้อนรับสู่ฟอรัม @vnd !

คำถามของคุณอาจแก้ไขได้โดยใช้ ตามแฮช เค- ไม่เปิดเผยชื่อ? ตามที่ฉันเข้าใจ วิธีการนี้จะ:

  • ป้องกันไม่ให้มัลลอรี่ค้นพบวันเกิดของอลิซ
  • ป้องกันไม่ให้อลิซรู้วันเกิดของเพื่อนร่วมชั้น; และ
  • อนุญาตให้อลิซค้นพบว่ามีเพื่อนร่วมชั้นคนใดของเธอที่มีวันเกิดร่วมกับเธอเท่านั้น

สมมติว่าอลิซมีเพื่อนร่วมชั้น 12 คนซึ่งมีตารางนี้แสดงข้อมูล:

                    ()                            
บ๊อบ 11 ม.ค. 2544 a40b69b979ef6af5e9f13a49cfc568d8b942d5c2 a40b6
โจ 23 มี.ค. 2532 4fde4b6b8e077d5b51eed716ab3d94a6ac04c45e 4fde4
เบ็น 9 มิถุนายน 2545 46885da4ffaa4c3d1b31413f96c38f2cb7e895ea 46885    
ศิลปะ 4 ธันวาคม 2548 a40b6425e2a7a93a9ac95ee275a5398397c46dd2 a40b6
ทอม 17 พ.ย. 2520 a49e374c34333b86ccf08bc10d6e04312e772c41 a49e3    
ทิม 3 ก.ค. 2532 39e95ac6c6286e6f036822f3fa31131a2e892b08 39e95
เอมี่ 12 ก.พ. 2545 92dac31b3d3a0793fd2845081c93024d0ea8ac8c 92dac
อีวา 24 เมษายน 2533 a0ed580e3df29f9a8f22276092ac9f58117401ec a0ed5
ฟ้อง 10 ก.ค. 2546 a93703839d02a539c12841f5de2ec8790107925b a9370
Zoe 5 ม.ค. 2549 a40b6232f910b358e971e4c5f91e273c07499ab0 a40b6
เลีย 18 ธ.ค. 2521 addc1fc5fbe7dea93e3bd1d421521f005ba89c8e addc1
เคย์ 4 ส.ค. 2533 a4e15e622b89d302f2b0357c2b2efc0d38fba7a0 a4e15

อลิซ 11 ม.ค. 2544 a40b69b979ef6af5e9f13a49cfc568d8b942d5c2 a40b6

ข้อมูลตาราง
ตารางนี้มีชื่อที่กำหนด วันเดือนปีเกิด (ในรูปแบบทหาร ด้วยเหตุผลด้านความงาม); ค่าแฮชของวันเกิดโดยใช้แฮช (MUH) ที่ไม่มีอยู่จริงและกราฟ 5 กราฟแรกของแฮช (แฟรกเมนต์)

ขั้นตอน
. อลิซคำนวณข้อความย่อยของวันเกิดของเธอโดยใช้แฮชที่สร้างขึ้น (สามารถใช้แฮชใดก็ได้ แม้แต่ SHA1 ที่อ่อนแอ)

. แทนที่จะสื่อสารค่าแฮชทั้งหมดให้กับมัลลอรีซึ่งจะถูกมองว่าเป็นภัยคุกคาม อลิซให้แฮชเพียงส่วนย่อยๆ ของเธอแก่มัลลอรี: ห้ากราฟแรก (ปรับได้)

. มัลลอรี่รู้วันเกิดของทุกคนในชั้นเรียน ยกเว้นอลิซ Mallory คำนวณแฮชของวันเกิดของเพื่อนร่วมชั้นแต่ละคน และส่งคืนข้อมูลนั้นให้กับอลิซ แต่เฉพาะเมื่อส่วนของอลิซตรงกับแฟรกเมนต์เดียวกันของแฮชแบบเต็มเท่านั้นข้อมูลที่ส่งกลับไม่รวมแฟรกเมนต์ เนื่องจากจะเป็นการซ้ำซ้อน
อย่ า ย า ย . ใช้แฟรกเมนต์ 5 กราฟ a40b6มัลลอรี่จะให้ข้อมูลต่อไปนี้กับอลิซ

9b979ef6af5e9f13a49cfc568d8b942d5c2
425e2a7a93a9ac95ee275a5398397c46dd2
232f910b358e971e4c5f91e273c07499ab0

   และอลิซจะดูว่าส่วนของเธอและการตอบสนองตรงกับแฮชทั้งหมดของเธอหรือไม่ ในกรณีนี้ ข้อแรกคือการจับคู่และอลิซมีคำตอบ ตอนนี้เธอรู้แล้วว่ามีใครบางคนในชั้นเรียนมีวันเกิดร่วมกับเธอ แม้ว่าเธอจะไม่รู้จักตัวตนของพวกเขาก็ตาม

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

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

นอกจากนี้ การใช้ข้อมูลที่มัลลอรี่ให้มา อลิซไม่สามารถอนุมานวันเกิดของเพื่อนร่วมชั้นคนใดคนหนึ่งได้ ยกเว้นวันเกิดที่ตรงกับแฮชของเธอ การแข่งขันบางส่วนไม่สามารถหาข้อสรุปได้

จำนวนข้อมูลที่ส่งคืนสามารถปรับได้ตามขนาดของแฟรกเมนต์:

อย่ า ย า ย . การใช้แฟรกเมนต์อักขระตัวเดียว มัลลอรี่จะให้ข้อมูลต่อไปนี้แก่อลิซ:

40b69b979ef6af5e9f13a49cfc568d8b942d5c2
40b6425e2a7a93a9ac95ee275a5398397c46dd2
f9e374c34333b86ccf08bc10d6e04312e772c41
0ed580e3df29f9a8f22276092ac9f58117401ec
93703839d02a539c12841f5de2ec8790107925b
40b6232f910b358e971e4c5f91e273c07499ab0
4e15e622b89d302f2b0357c2b2efc0d38fba7a0

หมายเหตุ: วิธีการนี้ไม่ต้องการให้เรารู้ว่ามีวันเกิดกี่วันเกิด (365) จะสามร้อยสี่ล้านก็ไม่สำคัญ

Score:3
ธง in

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

นี่คือรูปแบบการเข้ารหัสส่วนตัวที่สามารถค่าที่ดัชนี $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. โครงร่างนี้ช่วยประหยัดเวลาในกระบวนการได้มาก

โพสต์คำตอบ

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