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

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

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

การเข้ารหัสแบบโฮโมมอร์ฟิกบางส่วนรองรับการดำเนินการชนิดหนึ่งได้ไม่จำกัด RSA (แบบตำรา) มีคุณสมบัติโฮโมมอร์ฟิกเชิงการคูณ: Enc(m1)*Enc(m2) = Enc(m1*m2) ส่วน Paillier มีคุณสมบัติโฮโมมอร์ฟิกเชิงการบวก: Enc(m1)*Enc(m2) = Enc(m1+m2) ใช้ในการลงคะแนนอิเล็กทรอนิกส์และการเรียกคืนข้อมูลส่วนตัว

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

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

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

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

รูปแบบ HE ส่วนใหญ่มีพื้นฐานจากปัญหายากอย่างการเรียนรู้ที่มีข้อผิดพลาด (LWE) หรือ LWE บนวงแหวน (RLWE) ซึ่งเชื่อกันว่าทนทานต่อควอนตัม การทำลาย HE จำเป็นต้องแก้ปัญหา RLWE — ยังไม่มีอัลกอริทึมควอนตัมที่ทราบว่าสามารถเร่งความเร็วกับปัญหานี้ได้อย่างมีนัยสำคัญ

SEAL (Microsoft รองรับ BFV/CKKS), HEAAN (มหาวิทยาลัยแห่งชาติโซล, CKKS), OpenFHE (โอเพนซอร์ส, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV) ทั้งหมดอยู่ในระดับงานวิจัย การนำไปใช้งานจริงยังพบได้น้อยและขึ้นอยู่กับสาขาเฉพาะ

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

HE: ฝ่ายหนึ่งคำนวณข้อมูลที่อีกฝ่ายเข้ารหัสไว้ MPC: หลายฝ่ายร่วมกันคำนวณโดยไม่เปิดเผยข้อมูลนำเข้าของตนแก่กันและกัน แบบผสม: ใช้ HE สำหรับการประมวลผลล่วงหน้าแบบไม่โต้ตอบ และใช้ MPC สำหรับโพรโทคอลแบบโต้ตอบ ข้อแลกเปลี่ยน: HE = เวลาแฝงสูง; MPC = ค่าใช้จ่ายด้านการสื่อสาร

ข้อจำกัดสำคัญของการเข้ารหัสแบบโฮโมมอร์ฟิกบางส่วน (SHE) คืออะไร

การเข้ารหัสแบบโฮโมมอร์ฟิกช่วยให้คำนวณบนข้อความเข้ารหัสได้ PHE รองรับการดำเนินการหนึ่งชนิด SHE รองรับความลึกที่จำกัด และ FHE รองรับวงจรโดยพลการผ่านการบูตสแตรป มีพื้นฐานจากปัญหายาก LWE/RLWE ถัดไป: พื้นฐานทางคณิตศาสตร์ของ LWE