เมื่อคำนึงถึงวรรณกรรมมากมายเกี่ยวกับการคำนวณหลายฝ่ายที่ปลอดภัยและการแบ่งปันข้อมูลลับ จึงมีสมมติฐานเฉพาะสำหรับการคำนวณฟังก์ชันกฎ ฟังก์ชันหลังใช้เป็นอินพุตความลับส่วนบุคคลของเอเจนต์และให้เป็นเอาต์พุตของคำสั่งแต่ละตัวตามกฎที่เอเจนต์ต้องการเลียนแบบ จำไว้อีกครั้งว่าผู้เล่นทุกคน $i$, ของ $N<+\infty$ ผู้เล่นถือความลับพูด $x_i$. พวกเขาทั้งหมดต้องการแบ่งปันข้อมูลในลักษณะที่กฎทำงาน $f(x_1,x_2,\cdots,x_N)=(a_1,a_2,...a_N)$ มีรูปร่างในลักษณะที่แน่นอน และผู้เล่นทุกคนเมื่อสิ้นสุดโปรโตคอลจะรู้เฉพาะองค์ประกอบของตนเอง $a_i=f(x_i)$ และไม่มีข้อมูลอื่นๆ
ทำไมเราถึงถือว่า f เป็นฟังก์ชันพหุนามหรือพหุนามในเวลา? สัญชาตญาณเบื้องหลังสิ่งนี้คืออะไร?
ฉันเชื่อว่าคุณคงทราบดีอยู่แล้วว่าทำไมเราจึงใช้เวลาพหุนามเป็นพื้นฐานสำหรับการเข้ารหัสทั้งหมด (ตรวจสอบความคิดเห็นของ Kelalaka) โดยสรุป มีเหตุผลนับไม่ถ้วนที่ทำให้เราเชื่อว่านี่เป็นแบบจำลองที่สมเหตุสมผลสำหรับสิ่งที่เราเรียกว่า "การคำนวณที่มีประสิทธิภาพ" โดยสัญชาตญาณที่นี่ ในบริบทของ MPC ก็ไม่ต่างกัน: เราต้องการที่จะสามารถมุ่งเน้นไปที่การคำนวณที่มีประสิทธิภาพในการดำเนินการ
นี่เป็นการจำกัดประเภทของฟังก์ชันที่เราสามารถทำซ้ำได้ด้วยความช่วยเหลือของโปรโตคอลใช่ไหม เหตุใดเราจึงคิดว่านี่เป็นกลุ่มฟังก์ชันเดียวที่โปรโตคอลสามารถเลียนแบบได้ ฟังก์ชันตระกูลนี้จำกัดปัญหาเฉพาะฟังก์ชันพหุนามด้วยหรือไม่ ข้อสันนิษฐานนี้ได้
ฉันไม่คุ้นเคยกับการใช้ถ้อยคำที่แน่นอนในเอกสารเหล่านี้ แต่โดยทั่วไปแล้วเมื่อใดก็ตามที่คุณอ้างถึงฟังก์ชันที่มีอินพุต/เอาต์พุตที่ไม่จำกัด คุณกำลังพิจารณาจริงๆ ว่าสิ่งเหล่านี้ยังคงสามารถคำนวณได้ในเวลาพหุนามตามความยาวอินพุต อีกครั้ง นี่เป็นเพราะเราจำลองผู้เข้าร่วมของโปรโตคอลเป็นเครื่องบอกเวลาแบบพหุนาม และเราต้องการให้พวกเขาสามารถคำนวณให้เสร็จสิ้นได้
นอกจากนี้มีแนวคิดเกี่ยวกับความปลอดภัยที่อาศัยข้อสันนิษฐานว่าฝ่ายตรงข้ามมีขอบเขตทางคอมพิวเตอร์ ตัวอย่างเช่น มีโปรโตคอลที่ความปลอดภัยขึ้นอยู่กับความสามารถของฝ่ายตรงข้ามในการแยกปัจจัยจำนวนมาก แน่นอนว่าสิ่งนี้เป็นไปได้หากมีเวลาคำนวณเพียงพอเพื่อลองปัจจัยหลักที่เป็นไปได้ทั้งหมด แต่ฝ่ายตรงข้ามที่มีเวลาพหุนามไม่สามารถทำได้
อย่างไรก็ตาม ยังมีแนวคิดอื่นๆ ในบริบทของการคำนวณแบบหลายฝ่ายที่ปลอดภัย ซึ่งเราสามารถทนต่อศัตรูที่ทำงานในเวลาซูเปอร์โพลิโนเมียลได้ โปรโตคอลด้วย สมบูรณ์แบบ และ ทางสถิติ ความปลอดภัย (ซึ่งได้รับระยะร่มของ ความปลอดภัยทางทฤษฎีข้อมูล) ได้รับการออกแบบมาในลักษณะที่ไม่มีศัตรู ไม่ว่าทรัพยากรการคำนวณหรือเวลาทำงานจะมีจำนวนเท่าใดก็ตาม ก็สามารถทำลายความปลอดภัยของโปรโตคอลได้
ตามหลักการแล้ว เราสามารถทำให้ทุกฝ่าย (ไม่เฉพาะฝ่ายตรงข้าม) ดำเนินการในเวลาซูเปอร์โพลิโนเมียล แต่จากนั้นคำถามก็กลายเป็นว่าได้อะไรจากการทำเช่นนี้ โดยพื้นฐานแล้ว ฉันไม่สามารถนึกถึงฟังก์ชันที่ไม่ใช่พหุนามที่มีความหมายที่เราต้องการคำนวณได้
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
