หมายเหตุบรรณาธิการ: บทความนี้มาจากAmbi Labs (รหัส: secbitlabs)พิมพ์ซ้ำโดย Odaily โดยได้รับอนุญาต

หมายเหตุบรรณาธิการ: บทความนี้มาจาก

Ambi Labs (รหัส: secbitlabs)

พิมพ์ซ้ำโดย Odaily โดยได้รับอนุญาต

เมื่อไม่นานมานี้ ฉันเรียนหลักสูตร CS355 (การเข้ารหัสขั้นสูง) ที่มหาวิทยาลัยสแตนฟอร์ด เราได้รับการสอนโดยนักศึกษาปริญญาเอกของ Dan สามคน ได้แก่ Dima Kogan, Florian Tramer และ Saba Eskandarian อาจารย์ระดับปริญญาเอกทั้งสามคนมีลักษณะเฉพาะของตนเอง และแนวทางการวิจัยของพวกเขาก็แตกต่างกันมากเช่นกัน Dima มุ่งเน้นไปที่เทคโนโลยีการปกป้องความเป็นส่วนตัว PIR (การดึงข้อมูลส่วนตัว) Florian มุ่งเน้นไปที่การวิจัย ML และ blockchain และ Saba มุ่งเน้นไปที่การพิสูจน์ความรู้เป็นศูนย์

CS355 หลักสูตรนี้ครอบคลุมเกือบทุกอย่างในด้านการเข้ารหัสตั้งแต่สมัยโบราณจนถึงปัจจุบัน ตั้งแต่ฟังก์ชันแบบทางเดียว (One-way Function) ไปจนถึงสมการวงรี (ECC) และการจับคู่ (Pairing) และสุดท้ายคือ MPC ยอดนิยม ความรู้เป็นศูนย์ การดึงข้อมูลส่วนตัว (PIR) อัลกอริทึมโฮโมมอร์ฟิกแบบสมบูรณ์ และอื่นๆ ในช่วงไม่กี่ปีที่ผ่านมา . เนื่องจากชั้นเรียนเพิ่งจบไปเมื่อสองวันก่อน ฉันจึงจัดบันทึกเป็นระลอกในขณะที่เนื้อหาความรู้ยังคงอยู่ในความทรงจำอันตื้นเขิน เนื้อหาของหลักสูตรน่าสนใจมากและเนื้อหาที่เหลือจะแบ่งปันกับคุณเมื่อฉันมีเวลา~

ในฉบับนี้ เราจะพูดถึง Fully Homomorphic Encryption (FHE) ที่ได้รับความนิยมเมื่อเร็วๆ นี้ และเทคโนโลยีการเข้ารหัสแบบ Lattice-based

ชื่อเรื่องรอง

การเข้ารหัสแบบโฮโมมอร์ฟิคโดยสมบูรณ์คืออะไร

เชื่อว่าเพื่อนๆหลายคนคงเคยได้ยินชื่อ Fully Homomorphic Encryption (FHE) กันมาบ้างแล้ว ในช่วงไม่กี่ปีที่ผ่านมา มีหัวข้อเกี่ยวกับการคุ้มครองข้อมูลส่วนบุคคลมากขึ้นเรื่อย ๆ และเทคโนโลยีแอปพลิเคชันเข้ารหัสหลายชุดรวมถึงการเข้ารหัสแบบโฮโมมอร์ฟิคก็ได้รับความนิยมอย่างกว้างขวางเช่นกัน

เพื่อให้เข้าใจหัวข้อนี้ได้ดีขึ้น ฉันอยากจะแนะนำคำจำกัดความของการเข้ารหัสแบบโฮโมมอร์ฟิคโดยสมบูรณ์โดยสังเขป

• รีวิวระบบเข้ารหัส

• ก่อนที่เราจะเริ่ม เรามาทบทวนระบบการเข้ารหัสแบบดั้งเดิมกัน

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

ภาพประกอบด้านบนแสดงภาพรวมของระบบการเข้ารหัสทั่วไปทั้งหมด ระบบการเข้ารหัสทั้งหมด หากอธิบายอย่างเป็นทางการมากขึ้น จะทำสามสิ่งอย่างไม่ต้องสงสัย:

ประการแรก คู่ของคีย์สำหรับการเข้ารหัสและถอดรหัสจะถูกสร้างแบบสุ่มโดยอัลกอริทึมการสร้าง

ฝ่ายเข้ารหัสจะเข้ารหัสข้อความต้นฉบับผ่านคีย์เข้ารหัสและอัลกอริทึมการเข้ารหัส และสุดท้ายจะได้รับข้อความเข้ารหัส

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

เพื่อนๆ ที่รู้เกี่ยวกับอัลกอริทึมการเข้ารหัสจะต้องรู้จักอัลกอริธึมการเข้ารหัสทั่วไป เช่น AES, RSA เป็นต้น ทุกคนจะรู้ว่าระบบการเข้ารหัสโดยทั่วไปแบ่งออกเป็นสองประเภท: ระบบเข้ารหัสแบบสมมาตรและระบบเข้ารหัสแบบอสมมาตร สามขั้นตอนที่เราอธิบายในที่นี้ใช้ได้กับระบบการเข้ารหัสใดๆ หากเป็นแบบสมมาตร คีย์ที่ใช้สำหรับการเข้ารหัสและถอดรหัสจะเหมือนกัน หากเป็นระบบอสมมาตร การเข้ารหัสจะใช้คีย์สาธารณะ (Public Key) จากนั้นการถอดรหัสจะใช้คีย์ส่วนตัวอื่น (Private Key)

ในการวิจัยวิทยาการเข้ารหัสลับ เมื่อใดก็ตามที่เราเห็นคำจำกัดความของระบบใหม่ เรามักจะต้องระบุคุณสมบัติ (Properties) ที่ระบบนี้ควรมี

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

สมการข้างต้นแสดงให้เห็นว่าหากเรามีคีย์ที่ถูกต้อง ความน่าจะเป็นที่อัลกอริทึมการถอดรหัสสามารถกู้คืนข้อความรหัสที่สร้างโดยอัลกอริทึมการเข้ารหัสคือ 100%

คุณสมบัติที่สองที่เราต้องการบรรลุคือ Semantic Security

สำหรับคำจำกัดความของ semantic security เราจะไม่อธิบายในที่นี้ แต่เราสามารถเข้าใจได้ว่าหากเรามีข้อความรหัสสองตัวที่สอดคล้องกับข้อความต้นฉบับที่แตกต่างกัน เราจะไม่สามารถแยกได้ว่าข้อความรหัสใดสอดคล้องกับข้อความต้นฉบับใด:

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

หลังจากผ่านคุณสมบัติสองประการข้างต้นแล้ว ระบบการเข้ารหัสก็จะกลายเป็นระบบเสียง

การเข้ารหัสแบบโฮโมมอร์ฟิก: คุณสมบัติพิเศษโดยไม่ได้ตั้งใจ

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

เราทุกคนรู้คำตอบ: ไม่จริง

แต่ในบรรดาอัลกอริธึมการเข้ารหัสจำนวนมาก ข้อความไซเฟอร์เท็กซ์ที่สร้างโดยคลาสของอัลกอริทึมมีคุณสมบัติพิเศษแบบโฮโมมอร์ฟิก: หากเราใช้อัลกอริทึมการเข้ารหัสเพื่อรับข้อความเข้ารหัสของหมายเลข 1 เราก็จะได้ข้อความเข้ารหัสของหมายเลข 2 ในเวลานี้ หากเราเพิ่มไซเฟอร์เท็กซ์ มันก็เป็นไซเฟอร์เท็กซ์!

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

ตัวอย่าง: ระบบลงคะแนนนิรนาม

ต่อไป เราจะยกตัวอย่างเพื่ออธิบายการใช้งานจริงของการเข้ารหัสแบบโฮโมมอร์ฟิคอย่างชัดเจน

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

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

หากเราสามารถใช้อัลกอริทึมการเข้ารหัสแบบโฮโมมอร์ฟิกแบบเสริมได้ ปัญหานี้ก็สามารถแก้ไขได้อย่างง่ายดาย

ประการแรก ฝ่ายไอทีสามารถใช้อัลกอริทึม KeyGen เพื่อสร้างคู่ของคีย์เข้ารหัสและถอดรหัส pk, sk แล้วแจกจ่ายคีย์สาธารณะให้กับพนักงานแต่ละคน

ต่อจากนั้น พนักงานแต่ละคนจะเข้ารหัสตัวเลือกของตน (1 หรือ 0) เป็นข้อความเข้ารหัสผ่านอัลกอริทึมการเข้ารหัส จากนั้นจึงส่งข้อความเข้ารหัสไปยังเซิร์ฟเวอร์ไอที:

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

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

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

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

การจำแนกประเภทของระบบเข้ารหัสแบบโฮโมมอร์ฟิค

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

ต่อไป เรามาดูคำจำกัดความเฉพาะของแต่ละหมวดหมู่กัน

การเข้ารหัสแบบโฮโมมอร์ฟิกบางส่วน

ขั้นตอนเริ่มต้นของการเข้ารหัสแบบโฮโมมอร์ฟิกเรียกว่าการเข้ารหัสแบบโฮโมมอร์ฟิกบางส่วน คำนิยามคือ ไซเฟอร์เท็กซ์มีลักษณะโฮโมมอร์ฟิกเพียงลักษณะเดียว ขั้นตอนนี้รวมถึงสองโหมดของโฮโมมอร์ฟิซึ่มแบบบวกและแบบโฮโมมอร์ฟิซึ่มแบบทวีคูณที่เราอธิบายไว้ข้างต้น

หากเราใส่เข้าไปในสถานการณ์ของการประมวลผลพร็อกซีที่ปลอดภัยที่กล่าวถึงก่อนหน้านี้ หากเรามีอินพุตส่วนตัว และเราหวังว่าคลาวด์จะช่วยเราคำนวณได้ (x1, x2,...) เราก็สามารถใช้คลาวด์เพื่อคำนวณสิ่งเหล่านี้ได้ อินพุต ฟังก์ชันเพื่อแสดง

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

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

อัลกอริธึมการเข้ารหัสแบบเพิ่มเนื้อซ้ำแบบโฮโมมอร์ฟิกทั่วไปคืออัลกอริทึมการเข้ารหัส ElGamal ตามกลุ่มวงจร

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

ตัวสร้างนี้สามารถยกกำลังได้ วิธีการใช้งานการเข้ารหัส ElGamal มีดังนี้:

ตอนแรกเรา

เราจะไม่พิสูจน์ความถูกต้องและความปลอดภัยของ ElGamal แต่หลังจากได้เห็นวิธีการเข้ารหัสของระบบเข้ารหัสนี้แล้ว เราสามารถพบลักษณะพิเศษแบบโฮโมมอร์ฟิกเพิ่มเติมที่เป็นไปได้ของ ElGamal เนื่องจากเป็นการดำเนินการด้วยพลังงานทั้งหมด

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

วิธีการใช้งานการเข้ารหัส RSA มีดังนี้:

เราได้รับข้อความรหัสที่สอดคล้องกับการคูณของข้อความทั้งสองนี้! นี่คือธรรมชาติของการคูณแบบโฮโมมอร์ฟิก เราสามารถวาง ciphertexts ใหม่ทับข้อความไซเฟอร์ต่อไปได้

การเข้ารหัสที่ค่อนข้างโฮโมมอร์ฟิก

ดังที่เรากล่าวไว้ในย่อหน้าก่อนหน้า หากเราต้องการคูณอินพุตส่วนตัวและรับชุดค่าผสมเชิงเส้นระหว่างพวกเขา อัลกอริทึมการเข้ารหัสแบบโฮโมมอร์ฟิคบางส่วนอย่างง่าย (RSA, ElGamal) ไม่สามารถทำได้ ดังนั้นเราต้องไปที่ขั้นตอนต่อไป

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

มีตัวอย่างทั่วไปไม่มากนักในขั้นตอนนี้ของการเข้ารหัสแบบโฮโมมอร์ฟิกโดยประมาณ หากเราพูดถึงตัวอย่างที่เข้าใจได้ดีที่สุด มันควรจะขึ้นอยู่กับการจับคู่ (การจับคู่) อัลกอริทึมการเข้ารหัสกลุ่มแบบวนรอบ

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

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

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

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

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

การเข้ารหัสแบบ Homomorphic ระดับสมบูรณ์

หลังจากไปถึงขั้นตอนต่อไปแล้ว เราก็เข้าใกล้เป้าหมายของโฮโมมอร์ฟิซึมเต็มรูปแบบไปอีกก้าวหนึ่ง

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

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

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

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

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

การเข้ารหัสแบบ Homomorphic อย่างสมบูรณ์ (FHE)

หลังจากการเรียกร้องหลายครั้ง ในที่สุดเราก็มาถึงการเข้ารหัสแบบโฮโมมอร์ฟิคเต็มรูปแบบ (FHE) ที่เรารอคอย

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

ชื่อเรื่องรอง

ความหมายของระบบการเข้ารหัสแบบ Homomorphic อย่างสมบูรณ์

ก่อนที่จะเริ่มการอภิปรายเกี่ยวกับประวัติของระบบโฮโมมอร์ฟิคแบบเต็มด้านล่าง เราสามารถกำหนดคำจำกัดความอย่างเป็นทางการของระบบโฮโมมอร์ฟิคเต็มรูปแบบได้อย่างเป็นระบบ ระบบการเข้ารหัสแบบโฮโมมอร์ฟิกเต็มรูปแบบมีทั้งหมดสี่อัลกอริทึม:

ชื่อเรื่องรอง

คุณสมบัติของระบบเข้ารหัส Homomorphic อย่างสมบูรณ์

ทีนี้มาดูคุณสมบัติของระบบนี้กัน (Properties) อันดับแรก ระบบต้องถูกต้อง

นั่นคือถ้าเราเลือกวงจร F โดยพลการ และเลือกชุดข้อความต้นฉบับโดยพลการ m1,m2,.... หากเรามีคีย์ที่สร้างโดยอัลกอริทึม KeyGen ในตอนเริ่มต้น ดังนั้น:

ประการที่สอง ระบบจะต้องมีความปลอดภัยทางความหมาย เราได้อธิบายคำจำกัดความข้างต้นนี้แล้ว

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

ทำไมเราต้องเพิ่มฟีเจอร์สั้นๆ นี้ เนื่องจากไม่มีข้อกำหนดนี้ เราสามารถสร้างระบบโฮโมมอร์ฟิคที่ไร้ความหมาย (การโกง) อย่างสมบูรณ์ได้อย่างง่ายดาย:

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

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

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

ชื่อเรื่องรอง

การทบทวนประวัติศาสตร์ของการเข้ารหัสแบบ Homomorphic อย่างสมบูรณ์

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

แนวคิดของ FHE (โฮโมมอร์ฟิซึมเต็มรูปแบบ) ถูกเสนอขึ้นในช่วงปลายทศวรรษ 1970 ในปี 1978 ในเอกสารของพวกเขาเรื่อง Data Banks and Privacy Homomorphisms, Rivest, Adleman และ Dertouzos ชื่อใหญ่หลายคนในสาขาวิทยาการเข้ารหัสลับ ได้กล่าวถึงแนวคิดของระบบที่สามารถดำเนินการคำนวณบางอย่างบน ciphertext และดำเนินการทางอ้อมบน ข้อความต้นฉบับ ต่อมา แนวคิดนี้ได้รับการสรุปใหม่และตั้งชื่อการเข้ารหัสแบบโฮโมมอร์ฟิคทั้งหมด

จะเห็นได้ว่ามีการเสนอแนวคิดของการเข้ารหัสแบบโฮโมมอร์ฟิกอย่างสมบูรณ์มานานแล้ว น่าแปลกที่ในปี 1976 สองปีก่อนที่กระดาษจะตีพิมพ์ โปรโตคอลการแลกเปลี่ยนคีย์ Diffle-Hellman เพิ่งได้รับการเสนอ! จะเห็นได้ว่าจินตนาการของช่องเข้ารหัสยังคงสมบูรณ์อยู่มาก

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

จนกระทั่งปี 2009 PhD Craig Gentry ซึ่งกำลังศึกษาอยู่ที่ Stanford จู่ๆ ก็ได้รับแรงบันดาลใจและฝ่าฟันความยุ่งยากของอัลกอริธึม FHE ในวิทยานิพนธ์ระดับปริญญาเอกของเขา เขาได้มอบระบบการเข้ารหัสแบบโฮโมมอร์ฟิกเต็มรูปแบบที่สมเหตุสมผลและปลอดภัยเป็นครั้งแรก! ระบบนี้ตั้งอยู่บนสมมติฐานของโครงตาข่ายในอุดมคติ ระบบโฮโมมอร์ฟิคเต็มรูปแบบที่เสนอโดย Gentry09 มักเรียกว่าระบบเข้ารหัสโฮโมมอร์ฟิคเต็มรูปแบบรุ่นแรก

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

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

ในปี 2554 ทั้งสองบริษัทใหญ่อย่าง Brakerski และ Vaikuntanathan ได้เสนอระบบการเข้ารหัสแบบโฮโมมอร์ฟิกเต็มรูปแบบใหม่ ซึ่งอิงจาก Learning With Errors (LWE) ซึ่งเป็นอีกสมมติฐานหนึ่งของการเข้ารหัสแบบแลตทิซ ในปีเดียวกันนั้น Brakerski, Gentry และ Vaikuntanathan สร้างระบบร่วมกันจนเสร็จและเผยแพร่อย่างเป็นทางการ ระบบโฮโมมอร์ฟิกเต็มรูปแบบที่พวกเขาคิดค้นเรียกว่าระบบ BGV ในระยะสั้น ระบบ BGV เป็นระบบเข้ารหัสแบบโฮโมมอร์ฟิคที่มีซีรีส์จำกัด แต่สามารถเปลี่ยนเป็นระบบโฮโมมอร์ฟิกโดยสมบูรณ์ผ่าน Bootstrapping ระบบ BGV ใช้สมมติฐาน LWE ที่เป็นจริงมากกว่าระบบที่เสนอโดย Gentry09 โดยทั่วไป เราเรียกระบบ BGV ว่าเป็นระบบเข้ารหัสแบบโฮโมมอร์ฟิคเต็มรูปแบบรุ่นที่สอง

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

นอกเหนือจากการพัฒนาไลบรารี่โฮโมมอร์ฟิคเต็มรูปแบบแบบดั้งเดิมแล้ว หลายทีมยังค้นคว้าวิธีเร่งการคำนวณอัลกอริทึมการเข้ารหัสโฮโมมอร์ฟิคเต็มรูปแบบให้ดีขึ้นผ่านฮาร์ดแวร์ที่แตกต่างกัน เช่น GPU, FPGA และ ASIC ตัวอย่างเช่น cuFHE เป็นระบบการเข้ารหัสแบบโฮโมมอร์ฟิกเต็มรูปแบบที่เร่งด้วย GPU ที่ใช้ CUDA ที่รู้จักกันดี

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

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

ชื่อเรื่องรอง

ความสัมพันธ์ระหว่าง FHE และ MPC

MPC เป็นสาขาที่มีชื่อเสียงและมีการศึกษามาเป็นเวลานาน เนื่องจากนักวิทยาการเข้ารหัสลับ Yao Zhizhi ได้เปิดตัว Garbled Circuits ของเขาในศตวรรษที่ผ่านมา สาขาของ MPC จึงได้รับการยอมรับอย่างกว้างขวางและมีความก้าวหน้ามากมาย ตอนนี้เรามีไลบรารี MPC จำนวนมากที่สามารถใช้ได้ และยังมีประสิทธิภาพการทำงานในระดับหนึ่งอีกด้วย

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

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

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

ชื่อเรื่องรอง