นักเข้ารหัสที่รับรองว่าเราไว้ใจคอมพิวเตอร์ของเราได้ | นิตยสารควอนตั้ม

Yael Tauman Kalai เป็นนักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีรุ่นบุกเบิกที่ได้รับรางวัลอันน่าประทับใจและเปลี่ยนวิธีคิดของผู้คนเกี่ยวกับอินเทอร์เน็ต แต่ตอนเป็นเด็กเธอไม่ได้เป็นนักเรียนตัวอย่าง

“ฉันเป็นคนสร้างปัญหา” เธอกล่าว “โดยพื้นฐานแล้วฉัน – ไม่มาก แต่โดยพื้นฐานแล้ว – ถูกไล่ออกจากโรงเรียนมัธยม”

กลัย เกิดและเติบโตในเมืองเทลอาวีฟ ประเทศอิสราเอล ในครอบครัวนักวิชาการ พ่อของเธอ Yair Tauman เป็นนักเศรษฐศาสตร์และนักทฤษฎีเกม ชั้นเรียนไฮสคูลของเธอทำให้เธอเบื่อ โดยการ์ดรายงานหนึ่งฉบับบันทึกบางอย่าง เช่น การขาดเรียน 150 ครั้ง เธอจำได้ เนื่องจากเธอชอบใช้เวลาเล่นสกีน้ำและเข้าสังคม แต่ทักษะการวิเคราะห์ของเธออยู่ที่นั่นเสมอ

“เมื่อพ่อแม่ไม่ให้ฉันออกไปไหน วิธีเดียวที่จะทำให้พ่อเห็นด้วยคือบอกเขาว่า 'เอาล่ะ ขอปริศนาคณิตศาสตร์ให้ฉันหน่อย ยากแค่ไหนก็ได้ แต่ถ้าฉันแก้ ฉันจะไป'” เธอมักจะไป

ในที่สุดความรักในวิชาคณิตศาสตร์ของเธอก็ถูกปลุกให้ตื่นขึ้นในวิทยาลัย เมื่อเธอเริ่มรับรู้ถึงความสวยงามของมัน ในที่สุด เธอก็ค้นพบว่าเธอสามารถนำคณิตศาสตร์นี้ไปใช้กับคอมพิวเตอร์ได้ และโดยเฉพาะอย่างยิ่ง การรักษาความปลอดภัยข้อมูล ปัจจุบัน งานของเธอครอบคลุมสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ และแนวคิดของเธอเป็นพื้นฐานในการปกป้องและตรวจสอบการคำนวณในยุคดิจิทัล ตลอดสองทศวรรษที่ผ่านมา เธอทำงานเพื่อให้แน่ใจว่าสมาร์ทโฟน การเชื่อมต่อบนคลาวด์ และแม้แต่สกุลเงินดิจิทัลของเรามีความสมบูรณ์ ปัจจุบันเป็นนักวิจัยที่ Microsoft และผู้ช่วยศาสตราจารย์ที่ Massachusetts Institute of Technology เธอเพิ่งได้รับรางวัล ACM Prize อันทรงเกียรติด้านคอมพิวเตอร์ของ Association for Computer Machinery สำหรับ "ความก้าวหน้าในการมอบหมายการคำนวณที่ตรวจสอบได้และการสนับสนุนพื้นฐานในการเข้ารหัส" งานล่าสุดของเธอยังเป็นการมองไปยังอนาคตด้วย ขณะที่เธอพิจารณาว่าคอมพิวเตอร์ควอนตัมอาจส่งผลต่อภูมิทัศน์ด้านความปลอดภัยอย่างไร

ควอนตั้ม พูดคุยกับ Kalai เกี่ยวกับการรั่วไหลของความลับ การตรวจสอบคลาวด์ และความขี้ขลาดของควอนตัมคอมพิวเตอร์ บทสัมภาษณ์ได้รับการย่อและแก้ไขเพื่อความชัดเจน

คุณเปลี่ยนจากตัวแสบในโรงเรียนมัธยมมาเป็นนักวิชาการได้อย่างไร?

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

อะไรเกี่ยวกับคณิตศาสตร์ที่ทำให้คุณหลงใหล?

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

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

คุณทำงานเกี่ยวกับปัญหาการเข้ารหัสแบบใด

วิทยานิพนธ์ปริญญาโทของฉันมีชื่อว่า “How to Leak a Secret.” นี่คือปัญหา: เรารู้วิธีเซ็นชื่อแบบดิจิทัล - เพื่อพูดว่า "นี่คือฉันที่เขียนข้อความนี้" แต่พูดว่าฉันต้องการเซ็นชื่อในฐานะศาสตราจารย์ MIT แต่ฉันไม่ต้องการให้คนอื่นรู้ว่าเป็นฉัน? ด้วยวิธีนี้ความลับจะเก็บน้ำไว้ได้เพราะคุณรู้ว่าศาสตราจารย์ของ MIT ลงนาม แต่คุณไม่รู้ว่าใคร

เราแก้ไขปัญหานี้ด้วยสิ่งที่เราเรียกว่าลายเซ็นแบบวงแหวน ซึ่งได้รับแรงบันดาลใจจากแนวความคิดในวิทยาการคอมพิวเตอร์ที่เรียกว่าการพิสูจน์ที่แยกจากพยานไม่ได้ สมมติว่ามีข้อความและวิธีพิสูจน์สองวิธีที่แตกต่างกัน เราบอกว่ามี "พยาน" สองคนที่ยืนยันว่าข้อความนั้นถูกต้อง — แต่ละข้อพิสูจน์ หลักฐานที่แยกไม่ออกของพยานมีลักษณะเหมือนกันไม่ว่าคุณจะใช้แบบใด: เป็นการซ่อนพยานที่คุณเริ่มด้วย

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

สถาบันจะใช้ระบบนี้จริงหรือ?

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

งานของคุณพัฒนาไปสู่การวิเคราะห์ความปลอดภัยของอุปกรณ์ของเราได้อย่างไร

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

แต่โดยทั่วไปแล้วการพิสูจน์จะใช้เวลานานมาก และอุปกรณ์ที่อ่อนแอไม่สามารถตรวจสอบการพิสูจน์ที่ยาวนานได้ แม้แต่อุปกรณ์ที่ทำได้ก็มีราคาแพงมาก มีวิธีที่เราสามารถลดการพิสูจน์ได้หรือไม่? ข้อมูลในทางทฤษฎีไม่มี แต่กลับกลายเป็นว่าการใช้เครื่องมือเข้ารหัสทำให้เราสามารถสร้างใบรับรองที่รวบรัดซึ่งปลอมแปลงได้ยากมากแทน สิ่งเหล่านี้เรียกว่าอาร์กิวเมนต์แบบไม่โต้ตอบรวบรัดหรือ SNARG มันไม่ใช่ข้อพิสูจน์จริงๆ แต่ตราบใดที่คุณไม่สามารถแก้ปัญหาบางอย่างที่เรานักเข้ารหัสลับเชื่อว่าเป็นเรื่องยากมาก เช่น การแยกตัวประกอบจำนวนมาก คุณก็ไม่สามารถปลอมหลักฐานที่รวบรัดได้

หลักฐานเหล่านี้เกิดขึ้นได้อย่างไร?

เริ่มต้นในปี 1985 โดย Shafi Goldwasser, Silvio Micali และ Charles Rackoff ซึ่งร่วมกันแนะนำแนวคิดของการพิสูจน์แบบโต้ตอบ ก่อนหน้านี้ เมื่อผู้คนนึกถึงการพิสูจน์ พวกเขานึกถึงการเขียนบรรทัดข้อมูล และคุณสามารถอ่านและตรวจสอบว่าถูกต้องหรือไม่ Goldwasser, Micali และ Rackoff นำเสนอวิธีที่แตกต่างอย่างสิ้นเชิงในการพิสูจน์บางอย่าง นั่นคือการใช้ปฏิสัมพันธ์ มีผู้พิสูจน์และมีผู้ตรวจสอบ และพวกเขาแลกเปลี่ยนข้อความไปมา จากนั้นผู้ตรวจสอบจะตัดสินว่าพวกเขาเชื่อหรือไม่

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

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

แต่ข้อเสียของการพิสูจน์แบบโต้ตอบคือไม่สามารถถ่ายโอนได้ สมมติว่าคุณให้เงิน 100 ดอลลาร์แก่ฉัน และพิสูจน์ผ่านการโต้ตอบว่ามีมูลค่า XNUMX ดอลลาร์จริงๆ ฉันต้องการที่จะสามารถผ่านมันไปได้ ฉันต้องการมอบให้กับผู้อื่นซึ่งมอบให้กับผู้อื่น แต่ถ้าฉันมีหลักฐานเชิงโต้ตอบเท่านั้น ก็ไม่มีความหมายอะไร ฉันไม่สามารถมอบให้คนอื่นได้ ข้อดีเกี่ยวกับ SNARGs ก็คือคุณสามารถมอบให้คนอื่นได้

เช่นใบรับรองความถูกต้อง?

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

คุณจะลบการโต้ตอบเพื่อสร้างใบรับรองที่ถ่ายโอนได้อย่างไร

ด้วยการเข้ารหัส ให้ฉันลองให้สัญชาตญาณแก่คุณเกี่ยวกับวิธีการทำงานนี้ ในการพิสูจน์แบบอินเทอร์แอกทีฟของเรา ผู้ตรวจสอบมักจะส่งการสุ่มไปยังผู้พิสูจน์ — คุณอาจคิดว่านี่คือผู้ตรวจสอบที่สุ่มตรวจสอบหลักฐาน จากนั้น Amos Fiat และ Adi Shamir ก็มีความคิด: ทำไมคุณถึงต้องการตัวตรวจสอบนี้ ถ้าสิ่งที่เขาทำคือส่งแบบสุ่ม บางทีเราอาจแทนที่ตัวตรวจสอบนี้ด้วยฟังก์ชันบางอย่าง เช่น ฟังก์ชันแฮช ซึ่งเป็นฟังก์ชันที่มีลักษณะสุ่มและเป็นองค์ประกอบหลักที่สำคัญมากในการเข้ารหัส

และปรากฎว่าใช่เราทำได้ วันนี้ทำอย่างนี้ตลอด หากคุณมี iPhone หรือ Android แสดงว่าคุณกำลังใช้กระบวนทัศน์ Fiat-Shamir เมื่อโทรศัพท์ของคุณเชื่อมต่อกับเซิร์ฟเวอร์ระยะไกล ซึ่งอาจเกิดขึ้นบ่อยครั้งตลอดทั้งวัน และนี่คือกระบวนทัศน์ที่เราใช้เพื่อสร้างหลักฐานที่รวบรัดซึ่งรับรองว่าการคำนวณระยะไกลนั้นถูกต้อง

คุณได้พูดคุยเกี่ยวกับเครื่องจักรที่ต้อง "ปลอดภัยหลังควอนตัม" นั่นหมายความว่าอย่างไร?

คอมพิวเตอร์ควอนตัมหากมีอยู่จริงในขนาดใหญ่จะมีประสิทธิภาพมากกว่าคอมพิวเตอร์แบบคลาสสิก คอมพิวเตอร์แบบคลาสสิกทำงานในบิต ซึ่งเป็น 0 หรือ 1 ในคอมพิวเตอร์ควอนตัม คุณมีควอนตัมบิต ซึ่งอยู่ในตำแหน่งซ้อนระหว่าง 0 และ 1 และคิวบิตเหล่านี้จะพันกัน ซึ่งหมายความว่าพวกมันมีอิทธิพลต่อกันและกัน นั่นคือสิ่งที่ทำให้คอมพิวเตอร์ควอนตัมมีพลัง

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

ในปี 2018 ได้มีการเปิดตัว ผล โดยนักเรียนของ Berkeley Urmila Mahadev เธอเป็นคนแรกที่แสดงหลักฐานคลาสสิกที่มีความปลอดภัยในการคำนวณสำหรับการตรวจสอบการคำนวณควอนตัม

คุณสามารถใช้คอมพิวเตอร์แบบคลาสสิกเพื่อตรวจสอบการคำนวณควอนตัมได้หรือไม่? ฟังดูเป็นไปไม่ได้!

ไม่ว่าที่น่าตื่นตาตื่นใจ? ฉันอยู่ในคณะกรรมการโครงการเมื่อ Urmila ตีพิมพ์บทความของเธอ และฉันใช้เวลาทั้งคืนดูปริมาณคาเฟอีนที่ฉันดื่ม! ฉันรู้สึกทึ่ง ณ จุดนั้น ฉันเป็นหุ่นควอนตัมที่สมบูรณ์ ฉันเข้าใจส่วน crypto แต่ต้องใช้เวลาสักพักกว่าจะเข้าใจว่ามันเข้ากันได้อย่างไรกับส่วนควอนตัม และมันก็สวยงาม

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

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