นักเข้ารหัสลับคิดค้นแนวทางเพื่อความเป็นส่วนตัวในการค้นหาโดยรวม | นิตยสารควอนต้า

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

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

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

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

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

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

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

ในช่วงต้นทศวรรษ 2000 นักวิจัยเริ่มสงสัยว่าพวกเขาสามารถหลบเลี่ยงอุปสรรคในการสแกนแบบเต็มได้โดยการ "ประมวลผลล่วงหน้า" ฐานข้อมูล โดยคร่าวๆ นี่จะหมายถึงการเข้ารหัสฐานข้อมูลทั้งหมดเป็นโครงสร้างพิเศษ ดังนั้นเซิร์ฟเวอร์จึงสามารถตอบคำถามโดยการอ่านเพียงส่วนเล็กๆ ของโครงสร้างนั้น ตามทฤษฎีแล้ว การประมวลผลล่วงหน้าอย่างระมัดระวังเพียงพออาจหมายความว่าเซิร์ฟเวอร์เดียวที่โฮสต์ข้อมูลจะต้องผ่านกระบวนการเพียงครั้งเดียวเท่านั้น ทำให้ผู้ใช้ในอนาคตทั้งหมดสามารถดึงข้อมูลแบบส่วนตัวโดยไม่ต้องใช้ความพยายามอีกต่อไป

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

แต่ในปี 2017 มีนักวิจัยสองกลุ่ม การตีพิมพ์ ผล นั่นเปลี่ยนใจของเขา พวกเขาสร้างโปรแกรมแรกๆ ที่สามารถดึงข้อมูลส่วนตัวประเภทนี้ได้ แต่ไม่สามารถแสดงให้เห็นว่าโปรแกรมเหล่านั้นมีความปลอดภัย (นักวิทยาการเข้ารหัสลับแสดงให้เห็นถึงความปลอดภัยของระบบโดยแสดงให้เห็นว่าการทำลายระบบนั้นยากพอ ๆ กับการแก้ปัญหายาก ๆ นักวิจัยไม่สามารถเปรียบเทียบกับปัญหายาก ๆ ตามรูปแบบบัญญัติได้)

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

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

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

ในตอนแรกผู้เขียนไม่เชื่อ “เรามาดูกันว่าเกิดอะไรขึ้นกับเรื่องนี้” วิชส์นึกถึงขณะกำลังคิดอยู่ “เราพยายามค้นหาต่อไปว่ามันพังตรงไหน”

แต่วิธีแก้ปัญหาก็มีอยู่: พวกเขาค้นพบวิธีที่ปลอดภัยในการประมวลผลฐานข้อมูลเซิร์ฟเวอร์เดียวล่วงหน้า เพื่อให้ใครก็ตามสามารถดึงข้อมูลเป็นความลับได้ “มันเกินกว่าทุกสิ่งที่เราคาดหวังไว้จริงๆ” กล่าว ยูวัล อิซายนักเขียนวิทยาการเข้ารหัสลับที่ Technion ในอิสราเอลซึ่งไม่ได้เกี่ยวข้องกับงานนี้ ผลลัพธ์ก็คือ “เราไม่กล้าแม้แต่จะขอ” เขากล่าว

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

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

แม้ว่าการเข้ารหัสแบบโฮโมมอร์ฟิกจะเป็นส่วนขยายที่มีประโยชน์ของโครงการค้นหาส่วนตัว แต่ Ishai กล่าวว่าเขามองว่าการดึงข้อมูลส่วนตัวเป็นปัญหาพื้นฐานมากกว่า วิธีแก้ปัญหาของผู้เขียนคือ "โครงสร้างมหัศจรรย์" และกลยุทธ์การเข้ารหัสแบบโฮโมมอร์ฟิกของพวกเขาก็เป็นการติดตามผลอย่างเป็นธรรมชาติ

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

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

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