ทำไมเราถึงถือว่า f เป็นฟังก์ชันพหุนามหรือพหุนามในเวลา? สัญชาตญาณเบื้องหลังสิ่งนี้คืออะไร?
ฉันเชื่อว่าคุณคงทราบดีอยู่แล้วว่าทำไมเราจึงใช้เวลาพหุนามเป็นพื้นฐานสำหรับการเข้ารหัสทั้งหมด (ตรวจสอบความคิดเห็นของ Kelalaka) โดยสรุป มีเหตุผลนับไม่ถ้วนที่ทำให้เราเชื่อว่านี่เป็นแบบจำลองที่สมเหตุสมผลสำหรับสิ่งที่เราเรียกว่า "การคำนวณที่มีประสิทธิภาพ" โดยสัญชาตญาณที่นี่ ในบริบทของ MPC ก็ไม่ต่างกัน: เราต้องการที่จะสามารถมุ่งเน้นไปที่การคำนวณที่มีประสิทธิภาพในการดำเนินการ
นี่เป็นการจำกัดประเภทของฟังก์ชันที่เราสามารถทำซ้ำได้ด้วยความช่วยเหลือของโปรโตคอลใช่ไหม เหตุใดเราจึงคิดว่านี่เป็นกลุ่มฟังก์ชันเดียวที่โปรโตคอลสามารถเลียนแบบได้ ฟังก์ชันตระกูลนี้จำกัดปัญหาเฉพาะฟังก์ชันพหุนามด้วยหรือไม่ ข้อสันนิษฐานนี้ได้
ฉันไม่คุ้นเคยกับการใช้ถ้อยคำที่แน่นอนในเอกสารเหล่านี้ แต่โดยทั่วไปแล้วเมื่อใดก็ตามที่คุณอ้างถึงฟังก์ชันที่มีอินพุต/เอาต์พุตที่ไม่จำกัด คุณกำลังพิจารณาจริงๆ ว่าสิ่งเหล่านี้ยังคงสามารถคำนวณได้ในเวลาพหุนามตามความยาวอินพุต อีกครั้ง นี่เป็นเพราะเราจำลองผู้เข้าร่วมของโปรโตคอลเป็นเครื่องบอกเวลาแบบพหุนาม และเราต้องการให้พวกเขาสามารถคำนวณให้เสร็จสิ้นได้
นอกจากนี้มีแนวคิดเกี่ยวกับความปลอดภัยที่อาศัยข้อสันนิษฐานว่าฝ่ายตรงข้ามมีขอบเขตทางคอมพิวเตอร์ ตัวอย่างเช่น มีโปรโตคอลที่ความปลอดภัยขึ้นอยู่กับความสามารถของฝ่ายตรงข้ามในการแยกปัจจัยจำนวนมาก แน่นอนว่าสิ่งนี้เป็นไปได้หากมีเวลาคำนวณเพียงพอเพื่อลองปัจจัยหลักที่เป็นไปได้ทั้งหมด แต่ฝ่ายตรงข้ามที่มีเวลาพหุนามไม่สามารถทำได้
อย่างไรก็ตาม ยังมีแนวคิดอื่นๆ ในบริบทของการคำนวณแบบหลายฝ่ายที่ปลอดภัย ซึ่งเราสามารถทนต่อศัตรูที่ทำงานในเวลาซูเปอร์โพลิโนเมียลได้ โปรโตคอลด้วย สมบูรณ์แบบ และ ทางสถิติ ความปลอดภัย (ซึ่งได้รับระยะร่มของ ความปลอดภัยทางทฤษฎีข้อมูล) ได้รับการออกแบบมาในลักษณะที่ไม่มีศัตรู ไม่ว่าทรัพยากรการคำนวณหรือเวลาทำงานจะมีจำนวนเท่าใดก็ตาม ก็สามารถทำลายความปลอดภัยของโปรโตคอลได้
ตามหลักการแล้ว เราสามารถทำให้ทุกฝ่าย (ไม่เฉพาะฝ่ายตรงข้าม) ดำเนินการในเวลาซูเปอร์โพลิโนเมียล แต่จากนั้นคำถามก็กลายเป็นว่าได้อะไรจากการทำเช่นนี้ โดยพื้นฐานแล้ว ฉันไม่สามารถนึกถึงฟังก์ชันที่ไม่ใช่พหุนามที่มีความหมายที่เราต้องการคำนวณได้