ฉันกำลังศึกษาโปรโตคอลที่ใช้ OT และทันใดนั้นฉันก็รู้ว่าฉันนึกไม่ถึงว่าโปรโตคอลที่ใช้ OT จะเป็นอันตรายได้อย่างไร
สมมติว่าเรามีโปรโตคอล P ที่ใช้ OT เป็นโปรโตคอลย่อย สมมุติว่าใช้โอที $N$ ครั้ง. แต่ละโอทีมีอินพุต $x_{0,i}$, $x_{1,i}$, ที่ไหน $i$ หมายถึง $i-$ค่าล่วงเวลาตั้งแต่ 1 ถึง $N$. มีเหตุผลที่จะสมมติว่าผู้รับเลือกบิตทุกครั้ง $0$ หรือ $1$ ตามอินพุต (ตัวอย่างเช่น ในกรณีของโปรโตคอล Yao ซึ่งสำหรับแต่ละเกต ผู้รับจะถามหา 0 หากอินพุตเป็น 0 หรือ 1 อย่างอื่น)
ตอนนี้ สมมติว่าผู้ส่งใน OT เป็นอันตรายและตัดสินใจที่จะเปลี่ยนแปลง $x_{0,N}$ ด้วยสิ่งอื่น อาจเป็นค่าสุ่มก็ได้ ค่า $x_{1,N}$ หรืออะไรก็ตาม เรามีความเป็นไปได้สามประการ
หากลักษณะการทำงานเป็นหนึ่งในสามข้อแรก ผู้ส่งสามารถเปลี่ยน OT ทุกรายการได้ด้วยวิธีนี้ $\frac{1}{2^N}$ ความน่าจะเป็นที่จะเรียนรู้คำขอทั้งหมดโดยไม่ตรวจพบว่าตั้งแต่นั้นมา $N$ เป็นพารามิเตอร์คงที่ไม่สำคัญ (ยิ่งถ้า $N$ เล็ก). ในกรณีอื่น ๆ ผู้รับจะเรียนรู้ว่าผู้ส่งเป็นอันตราย แต่สิ่งนี้ไม่ได้ป้องกันผู้รับเพื่อเรียนรู้บางสิ่ง
หากพฤติกรรมเป็นครั้งสุดท้าย ฉันไม่เข้าใจว่าโปรโตคอลดังกล่าวได้รับการพิจารณาว่า "ปลอดภัย" ได้อย่างไร เนื่องจากผู้โจมตีสามารถทำการโจมตีแบบ "DoS" ได้ง่ายมาก โดยที่ทุกเอาต์พุตไม่มีความหมาย
ในกรณีของโปรโตคอล Yao สมมติว่าผู้ส่งตั้งค่า OT ล่าสุด $X_{0,N}, X_{0,N}$. เราจะป้องกันได้อย่างไร? หากโปรโตคอล "ผิดพลาด" ผู้ส่งจะรู้ว่าบิตสุดท้ายของ Bob คือ 0 มันใหญ่มากใช่ไหม
และฉันไม่ได้พิจารณากรณีสมมาตร: จะเกิดอะไรขึ้นหากผู้รับแทนที่จะถามตามกฎ กลับถามแบบสุ่ม เท่าที่ฉันเข้าใจพฤติกรรมนี้ไม่ได้รับการพิจารณาในระหว่างการพิสูจน์ความปลอดภัย ฉันผิดหรือไม่?
ฉันพลาดอะไรไปรึเปล่า? การพิจารณาเหล่านี้อยู่นอกขอบเขตและเราอนุญาตให้มีพฤติกรรมแบบนี้หรือไม่ บางทีเราคิดว่าผู้ส่งตั้งค่าเสมอ $x_0$ และ $x_1$ ในทางที่ถูกต้อง?
มีคำถามมากมายที่รวบรวมไว้ที่นี่ -- การตอบคำถามทั้งหมดทั้งหมดจะต้องมีบทช่วยสอนฉบับสมบูรณ์เกี่ยวกับ MPC ที่ปลอดภัยที่เป็นอันตราย ฉันจะพยายามมุ่งเน้นไปที่ภาพใหญ่
โดยทั่วไป หากมี "ค่าที่ถูกต้อง" ที่ผู้ส่ง OT "ควรจะ" ใช้เป็นอินพุต OT แสดงว่าใช่ โปรโตคอลจะต้องระมัดระวังอย่างมาก โดยปกติจะมี "ค่าที่ถูกต้อง" เพราะค่าอื่น ๆ จะทำให้ผู้รับยกเลิก ดังนั้นค่าที่ "ไม่ถูกต้อง" ใน OT จะทำให้เกิดการยกเลิกตามอินพุต OT ของผู้รับ - ข้อมูลรั่วไหลเกี่ยวกับอินพุต OT เหล่านั้น!
มีสองสามวิธีในการจัดการกับสิ่งนี้ นี่คือวิธีที่ง่ายที่สุดในการทำความเข้าใจ:
โปรโตคอล 2PC แบบวงจรอ่านไม่ออกแบบคลาสสิกของ ลินเดลล์-ปินกาส 2550 ทำดังต่อไปนี้ สมมติว่าเราต้องการทำ OT เพื่อเลือกหนึ่งในสองป้ายลวด $x_0, x_1$ ขึ้นอยู่กับอินพุตวงจรของเครื่องรับ $ข$. สมมติว่าเครื่องรับสามารถตรวจสอบได้ว่าฉลากสายไฟถูกต้องหรือไม่ เมื่อเครื่องรับยกเลิกเนื่องจากเห็นฉลากสายไฟที่ไม่ถูกต้อง แสดงว่าวงจรอินพุตรั่วไหล! Lindell & Pinkas แก้ไขปัญหานี้โดยแก้ไขวงจรที่อ่านไม่ออกเพื่อให้ผู้รับควรป้อนข้อมูลการแบ่งปันที่เป็นความลับ $b = b_1 \oplus \cdots \oplus b_\lambda$ ของอินพุตที่แท้จริง $ข$. วงจรที่อ่านไม่ออกจะ XOR หุ้นเหล่านี้เพื่อกู้คืน $ข$ แล้วดำเนินการตามปกติ ดังนั้นตอนนี้แทนที่จะเป็นหนึ่ง OT สำหรับสายอินพุตของวงจรนี้มี $\แลมบ์ดา$ OT เนื่องจากเราได้เพิ่มจำนวนอินพุตของวงจรเทียม สมมติว่าผู้ส่งโอทีโกงในตอนแรก $k < \แลมบ์ดา$ OT การรับอินพุตเหล่านี้ก่อน $k$ OTs เป็นชุดของหุ้นลับ แต่มีจำนวนหุ้นน้อยกว่าเกณฑ์ดังนั้นจึงมีการแจกจ่าย เป็นอิสระจากอินพุตส่วนตัว $ข$! ในกรณีนี้ผู้รับจะยกเลิกด้วยความน่าจะเป็น $1 - 2^{-k}$โดยไม่ขึ้นกับการป้อนข้อมูลของพวกเขา หากผู้ส่งโอทีโกงทั้งหมด $\แลมบ์ดา$ OTs จากนั้นผู้รับจะยกเลิกด้วยความน่าจะเป็น 1 หรือ $1-2^{-\แลมบ์ดา}$ด้วยความน่าจะเป็นขึ้นอยู่กับการป้อนข้อมูลส่วนตัว! -- แต่เนื่องจากสิ่งเหล่านี้มีความใกล้ชิดกันโดยไม่ได้ตั้งใจ จึงไม่ถือเป็นการรั่วไหลของข้อมูลอย่างแท้จริง
โปรโตคอล ZK ของ จาวูเร็ก, เคิร์ชบอม, ออร์ลันดี ยังขึ้นอยู่กับวงจรที่อ่านไม่ออก พวกเขาทำ OT ทั่วไปของป้ายลวด โดยที่อินพุตของเครื่องรับ OT เป็นพยาน ZK ส่วนตัวของพวกเขา พวกเขาจัดโครงสร้างโปรโตคอลอย่างระมัดระวังเพื่อให้ผู้ส่ง OT สามารถเปิดเผยต่อสาธารณะได้ ทั้งสอง ของอินพุต OT ในภายหลัง --- ซึ่งต้องใช้ตัวแปรของ OT ที่เรียกว่า "commit OT" โดยพื้นฐานแล้ว ผู้ตรวจสอบจะคำนวณ "คำตอบสุดท้าย" บางอย่างเกี่ยวกับวงจรที่อ่านไม่ออก ซึ่งจะรั่วไหลข้อมูลเกี่ยวกับอินพุตส่วนตัวหากมีการโกงใน OT ดังนั้นแทนที่จะส่งคำตอบสุดท้ายนี้ไป กระทำ ไปมัน จากนั้นผู้ส่ง OT จะเปิดเผยอินพุต OT ทั้งหมดของตนเพื่อพิสูจน์ว่าไม่มีการโกง หากผู้รับ OT เชื่อมั่น ก็สามารถเปิดข้อผูกมัดของตนต่อ "คำตอบสุดท้าย" ได้
บางครั้งคุณสามารถออกแบบโปรโตคอลเพื่อให้ไม่มีสิ่งที่เรียกว่าอินพุต OT ที่ไม่ถูกต้อง ต่อไปนี้เป็นวิธีง่ายๆ ในการตรวจสอบว่ามีสตริงส่วนตัว 2 สตริงหรือไม่ $x = x_1 \cdots x_n$ และ $y = y_1 \cdots y_n$ เท่ากัน (ได้รับแรงบันดาลใจจากโปรโตคอล PSI ของ พิงกาส-ชไนเดอร์-โซห์เนอร์). วิ่ง $n$ OTS ของค่าสุ่มดังนั้น $i$อปท.มีปัจจัยการผลิต $r_{i,0}$ และ $r_{i,1}$. เครื่องรับ OT ใช้บิตของอินพุต $x$ เป็นบิตตัวเลือก OT และเรียนรู้ค่าของแบบฟอร์ม $r_{i, x_i}$. สามารถคำนวณมูลค่าได้ $R_x = H(x, r_{1,x_1}, r_{2,x_2}, \ldots, r_{n,x_n} )$, ที่ไหน $H$ เป็นออราเคิลแบบสุ่ม ผู้ส่ง OT มีอินพุตส่วนตัวของตนเอง $y$และรู้เรื่องทั้งหมด $r_{i,b}$ ค่า จึงจะคำนวณค่าได้ $R_y = H( y, r_{1,y_1}, r_{2,y_2}, \ldots, r_{n,y_n} )$ และส่งไปยังเครื่องรับโอที ถ้า $R_x = R_y$ แล้ว $x$ และ $y$ เท่ากัน; มิฉะนั้น $x$ และ $y$ แตกต่างกัน (และ $R_y$ ดูสุ่มไปยังผู้รับ) ผู้ส่ง OT ที่เสียหายจะโกงได้อย่างไร พวกเขาสามารถส่ง $H$ ของบางคน อื่นๆ สิ่งของ (เช่น รวมสิ่งที่ไม่เท่ากับใดๆ $r_{i,b}$ เป็นข้อมูลเข้า $H$). แต่นั่นจะเป็นเพียงแค่ รับประกัน ที่ผู้รับจะสรุปว่า "สตริงไม่ตรงกัน" ไม่ว่าจะเกิดอะไรขึ้น $x$ พวกเขาถือ นี่เป็นเรื่องง่ายสำหรับตัวจำลองในการจัดการ
ดังนั้นเราจึงมีแนวทางระดับสูงที่แตกต่างกันสามแนวทางสำหรับปัญหาที่คุณถาม:
โปรโตคอลนี้จัดให้บิตตัวเลือก OT ของผู้รับเป็นอิสระจากข้อมูลส่วนตัวอย่างมีประสิทธิภาพ --- ดังนั้นหากการโกงนำไปสู่การยกเลิก ความน่าจะเป็นของการยกเลิกนั้นไม่ได้ขึ้นอยู่กับอินพุตส่วนตัวของผู้รับ OT
เครื่องรับ OT จะได้รับวิธีการตรวจจับการโกงเพื่อให้สามารถหยุดโปรโตคอลก่อนที่จะเห็นผลเสียของการโกง
ส่วนอื่นๆ ของโปรโตคอลจะไม่มีผลเสียใดๆ หากผู้ส่ง OT เลือกที่จะดำเนินการที่ไม่สอดคล้องกับอินพุต OT ของตน
มีวิธีการที่ชาญฉลาดอื่น ๆ เช่นกัน แต่นี่เป็นวิธีแรกที่นึกถึง
จะเกิดอะไรขึ้นถ้าคนรับแทนที่จะถามตามกฎกลับสุ่มถาม? เท่าที่ฉันเข้าใจพฤติกรรมนี้ไม่ได้รับการพิจารณาในระหว่างการพิสูจน์ความปลอดภัย ฉันผิดหรือไม่?
ในโปรโตคอลที่ใช้ OT ส่วนใหญ่ บิตตัวเลือก OT ของผู้รับจะเป็นการเข้ารหัสโดยตรงของอินพุตไปยังโปรโตคอลหลัก เป็นเช่นนั้นแน่นอนใน 3 ตัวอย่างข้างต้น การใช้บิตตัวเลือก OT "ผิด" นั้นเทียบเท่ากับการเลือกอินพุตอื่นสำหรับโปรโตคอลหลัก และไม่ถือว่าเป็นการโจมตีเพื่อความปลอดภัยที่เป็นอันตราย
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
