ฉันไม่เห็นที่ใดในหน้านั้นที่อธิบายการถ่ายโอนที่ถูกลืมในแบบที่คุณอธิบาย
การถ่ายโอนที่ลืมเลือน:
- อลิซถือเชือกสองเส้น $x_0, x_1$
- บ๊อบถือเล็กน้อย $ข$
- บ๊อบเรียนรู้ $x_b$ แต่เรียนไม่รู้เรื่อง $x_{1-b}$
- อลิซเรียนรู้อะไรเกี่ยวกับ $ข$
วงจรที่อ่านไม่ออก:
- เมื่ออลิซ อ่านไม่ออก วงจรบูลีน $f$เธอได้รับไซเฟอร์เท็กซ์ชุดใหญ่ $F$ ("วงจรที่อ่านไม่ออก") และเธอยังเรียนรู้ปุ่มสองปุ่ม (ฉลาก) บนสายแต่ละเส้นของวงจร บนสาย #$i$ เธอเรียนรู้ $W_i^0$ ซึ่งแทนค่าเท็จบนเส้นลวดนั้น และ $W_i^1$ ซึ่งแทนค่าจริงบนเส้นลวดนั้น
- ถ้าบ๊อบรู้วงจรที่อ่านไม่ออก $F$ และสำหรับแต่ละคน ป้อนข้อมูล ลวด $i$ ของวงจรที่เขารู้จักอย่างใดอย่างหนึ่ง $\{ W_i^0, W_i^1\}$ จากนั้นเขาก็สามารถ ประเมิน วงจรที่อ่านไม่ออกเพื่อเรียนรู้ฉลากเดียวบนแต่ละสายของวงจร (ไม่ใช่แค่สายอินพุต) เขาเรียนรู้ฉลากลวดที่ "ถูกต้อง" (เช่น ฉลากที่สอดคล้องกับพฤติกรรมของ $f$) ในแต่ละสายตามป้ายกำกับอินพุตที่เขาเริ่มต้นด้วย
- ขณะที่บ็อบประเมินวงจรที่อ่านไม่ออก เขาไม่รู้ว่าเขากำลังถืออยู่หรือไม่ $W_i^0$ หรือ $W_i^1$ สำหรับสายใด ๆ $i$. กล่าวอีกนัยหนึ่งเขาไม่รู้ว่าสายใดในวงจรมีค่าจริงหรือเท็จ เขาประเมินวงจร "สุ่มสี่สุ่มห้า"
หากอลิซและบ็อบต้องการประเมินฟังก์ชันโดยใช้วงจรที่อ่านไม่ออก จากนั้นอลิซก็จะอ่านวงจรและส่งวงจรที่อ่านไม่ออก $F$ ถึงบ๊อบ
แต่บ๊อบจำเป็นต้องเรียนรู้สำหรับแต่ละคนด้วย ป้อนข้อมูล ลวด $i$ ในวงจรอย่างใดอย่างหนึ่ง $\{ W_i^0, W_i^1\}$.
ทั้งอลิซและบ็อบมีอินพุตสำหรับการคำนวณนี้
ถ้าลวด #$i$ เป็นหนึ่งในสายอินพุตของอลิซ จากนั้นเธอก็สามารถส่งสายที่ "ถูกต้อง" จาก $\{W_i^0, W_i^1\}$เนื่องจากเธอรู้ทั้งสองสิ่งนี้และเธอรู้บิตอินพุตของเธอบนสายนั้น
ถ้าลวด #$i$ เป็นหนึ่งในสายอินพุตของ Bob ต้องมีทางสำหรับ Bob เลือก เพื่อเรียนรู้ว่าหนึ่งในนั้น $\{W_i^0, W_i^1\}$.
เนื่องจาก Bob เลือกระหว่างค่าเหล่านี้ตามข้อมูลส่วนตัวของเขา Alice จึงไม่ควรเรียนรู้ว่าเขาเลือกค่าใด
การถ่ายโอนที่ไม่ชัดเจนใช้สำหรับขั้นตอนนี้
สำหรับสายเข้า #$i$ อลิซเป็นผู้ให้ข้อมูลของบ็อบ $W_i^0$ และ $W_i^1$ ถึงตัวอย่างการถ่ายโอนที่ถูกลืมเลือน และบ็อบเลือกว่าจะเรียนรู้เรื่องใดในสิ่งเหล่านี้
มีรูปแบบต่างๆ ของการถ่ายโอนที่ถูกลืมซึ่งอลิซมี $N$ สตริงและบ็อบเลือกหนึ่งในนั้นเพื่อเรียนรู้
ถ้า Alice & Bob ต้องการคำนวณฟังก์ชันง่ายๆ $f(ก,ข)$ที่ที่มีแต่ $N$ อินพุตที่เป็นไปได้สำหรับ Bob ($b \in \{1, \ldots, N\}$) ใช่แล้ว พวกเขาสามารถใช้ oblivious transfer เพื่อคำนวณฟังก์ชันได้โดยตรงตามที่คุณแนะนำ โดยไม่มีวงจรที่อ่านไม่ออก
อลิซใช้ $f(a,1), f(a,2), \ldots, f(a,N)$ เป็นอินพุตสำหรับการถ่ายโอนที่หลงลืม
บ๊อบเลือกที่จะเรียนรู้ $ข$เหล่านี้ซึ่งก็คือ $f(ก,ข)$.
ใช้งานได้เฉพาะเมื่อ $N$ มีขนาดเล็กมากเนื่องจากต้องใช้การสื่อสารและการคำนวณตามสัดส่วน $N$.
จำไว้ $N$ คือจำนวนอินพุตที่เป็นไปได้สำหรับ Bob
หากมีวงจรที่บ๊อบมี $k$ สายเข้าเขาก็มี $N=2^k$ อินพุตที่เป็นไปได้
ดังนั้น โดยปกติแล้ว Bob จะมีอินพุตมากเกินไปที่จะใช้แนวทางนี้
ตอบกลับโพสต์ที่แก้ไขแล้ว:
แนวทางของคุณสำหรับปัญหาของเศรษฐีนั้นไม่ชัดเจน ดังนั้นฉันจึงต้องคาดเดาบางอย่าง
การเปิดเผยข้อมูลบางส่วนเกี่ยวกับอินพุตระหว่างโปรโตคอลไม่ได้ผล
ถ้าอลิซมีอินพุต 1 เธอไม่ควรแยกความแตกต่างระหว่าง Bob ที่มีอินพุต 2 กับอินพุต $2^{20}$ -- แต่อินพุตทั้งสองนี้จะดูแตกต่างกันมากหากผลลัพธ์ของการเปรียบเทียบถูกเปิดเผยอย่างชัดเจน
ด้วยเหตุนี้ คุณจึงแนะนำให้เข้ารหัสสิ่งต่างๆ แต่คุณกำลังเสนอการค้นหาแบบไบนารีเป็นหลัก การค้นหาแบบไบนารีกำหนดให้คุณต้องทราบผลลัพธ์ของการเปรียบเทียบครั้งก่อนเพื่อตัดสินใจว่าจะทำการเปรียบเทียบแบบใดต่อไป หากคุณกำลังเข้ารหัสผลลัพธ์ของการเปรียบเทียบ คุณจะไม่ชัดเจนว่าจะดำเนินการอย่างไรในรอบต่อไป
ปัญหาใหญ่ของข้อเสนอของคุณคือข้อเสนอนั้นเป็นไปตามลำดับโดยเนื้อแท้ ฝ่ายต่างๆ ไม่สามารถทราบข้อมูลของตนในรอบถัดไปได้จนกว่าจะได้รับผลจากรอบที่แล้ว
ดังนั้นสำหรับ $k$ การเปรียบเทียบที่คุณต้องการ $\เธต้า(k)$ รอบของการสื่อสาร
เปรียบเทียบวิธีนี้กับแนวทางแบบ GC ซึ่งใช้จำนวนรอบการสื่อสารคงที่เสมอ
ฉันคิดว่าคุณมีความเชื่อมโยงทางความคิดที่ดี
ลองนึกภาพฟังก์ชั่น $f$ มีขนาดเล็กมาก จนสามารถจดตารางความจริงทั้งหมดของ $f$.
สมมติว่า $f : \{1,2,3,4\}^2 \ถึง \{0,1\}$.
อลิซเลือกคีย์เข้ารหัสแบบสุ่ม $A_1, \ldots, A_4$ และ $B_1, \ldots, B_4$.
เธอยังเข้ารหัสตารางความจริงของ $f$ เช่น
$$\textsf{Enc}( A_1 \| B_1, f(1,1)), ~~
\textsf{Enc}( A_1 \| B_2, f(1,2)), ~~\ldots,
\textsf{Enc}( A_i \| B_j, f(i,j)), ~~\ldots$$
เพื่อประเมิน $f$ ในอินพุตส่วนตัว อลิซสามารถส่งไซเฟอร์เท็กซ์ทั้งหมดเหล่านี้ให้บ็อบได้
เธอสามารถส่งที่ถูกต้อง $A_i$ คุ้มค่า และพวกเขาสามารถใช้โอที 1 ใน 4 เพื่อให้บ็อบเรียนรู้สิ่งที่ถูกต้อง $B_j$ ค่า.
ตอนนี้ Bob สามารถถอดรหัสหนึ่งในข้อความเข้ารหัสเหล่านี้ได้ ซึ่งจะมีเอาต์พุตที่ถูกต้องของ $f$.
วงจรที่อ่านไม่ออกเป็นเพียงสิ่งที่คุณได้รับเมื่อคุณสร้างแบบง่ายๆ นี้ แต่แทนที่จะเข้ารหัสเอาต์พุตฟังก์ชันสุดท้าย คุณจะเข้ารหัสคีย์ไปยังแกดเจ็ตอื่นที่เป็นประเภทเดียวกัน