ฉันคิดแผน FHE ที่ค่อนข้างเรียบง่ายซึ่งไม่น่าจะได้ผล แต่ฉันไม่สามารถเข้าใจได้ว่ามันแตกอย่างไร ความช่วยเหลือใด ๆ ที่ชื่นชมยินดี!

ส่วนหนึ่ง

อันดับแรก โปรดทราบว่าถ้าเรามีฟิลด์อะเบเลียนซึ่งการคำนวณอินเวอร์สการคูณเป็นเรื่องยาก เราก็สามารถสร้างโครงร่างโฮโมมอร์ฟิคสำหรับการบวกและการคูณเล็กน้อย สมมติว่าข้อความที่เราต้องการเข้ารหัสคือ $m$. จากนั้นเราจะสุ่มตัวอย่างองค์ประกอบแบบสุ่ม $e$ (อย่างที่เรารู้ $e^{-1}$) และข้อความรหัสของเราก็กลายเป็น $c=m\cdot e$. เราให้เซิร์ฟเวอร์ $m \cdot e$ และ $e$. โปรดทราบว่าเนื่องจากเป็นการยากที่จะหาตัวคูณผกผัน เซิร์ฟเวอร์จึงไม่สามารถคำนวณได้ง่ายๆ $e^{-1}$ แล้วคูณด้วย $m\cdot e$. อย่างไรก็ตาม สมมติว่าเซิร์ฟเวอร์ต้องการเพิ่มข้อความเข้ารหัสและค่าคงที่บางอย่าง $a$. พวกเขาก็จะคำนวณ $a \cdot e$แล้วเพิ่มสิ่งนี้ลงใน $m\cdot e$ ที่จะได้รับ $(a+m)\cdot e$. หากนี่ไม่ใช่ค่าคงที่ (ข้อความเข้ารหัสอื่นๆ) เราก็สามารถเพิ่มข้อความเข้าด้วยกันได้ การคูณค่อนข้างยุ่งยากกว่าเล็กน้อย ตอนนี้ เราจะต้องติดตามจำนวน âeâs ที่อยู่ในข้อความเข้ารหัสของเรา เมื่อไคลเอนต์ให้เซิร์ฟเวอร์เป็นครั้งแรก $ค$, เลขยกกำลังของ $e$ เป็นเพียง $1$ดังนั้นเราจึงสามารถจัดเก็บจุดข้อมูลนั้นเป็น $(ค,1)$. หากเรามีข้อความเข้ารหัสอื่น $câ = mâ e$และเราต้องการคูณสิ่งเหล่านี้เข้าด้วยกัน เราหาได้ $(c,1) \cdot (câ,1) = (c\cdot câ,2)$. โปรดทราบว่าสิ่งที่เซิร์ฟเวอร์มีอยู่จริงคือ $(m \cdot mâ)e^2$. เมื่อเซิร์ฟเวอร์ให้ค่านี้คืนแก่ไคลเอ็นต์ ก็จะคืนให้ $(c\cdot câ,2)$ซึ่งกำลังบอกลูกค้าว่ามีสองคน $e$ในผลิตภัณฑ์ ดังนั้นจึงสามารถคูณได้ $c\cdotcâ$ โดย $e^{-2}$ ที่จะได้รับ $m \cdot mâ$. แล้วถ้าการคำนวณไม่ได้จบแค่นั้นล่ะ จะเกิดอะไรขึ้นถ้าเซิร์ฟเวอร์มีไซเฟอร์เท็กซ์สามตัว $c_1,c_2,c_3$และมันต้องการคำนวณ $c_1\cdot c_2+c_3$. ก่อนอื่นก็จะคำนวณ $c_1 \cdot c_2 = (c_1c_2,2)$. ตอนนี้มันต้องการที่จะคำนวณ $(c_1c_2,2) + (c_3,1)$. ในการทำเช่นนี้จะต้องมีการคำนวณ $c_3\cdot e$ ที่จะได้รับ $(c_3,2)$แล้วมันก็ทำได้ $(c_1c_2,2) + (c_3,2)=(c_1c_2+c_3,2)$. เมื่อเซิร์ฟเวอร์ให้ค่านี้กลับมา ไคลเอนต์ก็สามารถคูณด้วย $e^{-2}$ และมี $m_1m_2+m_3$.

ส่วนที่สอง

การหาฟิลด์ที่เราไม่สามารถคำนวณค่าผกผันได้นั้นเป็นเรื่องยาก วิธีแก้ปัญหาที่ฉันพบ (ซึ่งฉันไม่มั่นใจนัก) คือการใช้ประโยชน์จากข้อเท็จจริงที่ว่าคุณสามารถคำนวณเฉพาะส่วนผกผันใน $\mathbb{F}_p$ หากคุณทราบลำดับของสนาม มิฉะนั้นจะเป็นไปไม่ได้ ดังนั้น ลูกค้าสามารถทำงานกับจำนวนเต็มได้ $\mod p$แต่มันจะไม่บอกสิ่งนี้กับเซิร์ฟเวอร์ จากนั้นมันก็จะเลือกแบบสุ่ม $e$,คำนวณ $m\cdot e \mod p$ให้กับเซิร์ฟเวอร์ และเซิร์ฟเวอร์สามารถทำการคำนวณทั้งหมดด้วยตัวเลข หากผลลัพธ์ของการคำนวณเป็น $R$เซิร์ฟเวอร์สามารถให้คืนได้ $(ร,น)$ ให้กับลูกค้า (โดยที่ $n$ เป็นจำนวนเงิน $e$s) จากนั้นไคลเอนต์ก็สามารถคำนวณได้ $R e^{-n} \mod p$ เพื่อรับคำตอบ เหตุผลที่ใช้งานได้เนื่องจาก modulo-ing เป็นแบบโฮโมมอร์ฟิคอย่างสมบูรณ์ คุณสามารถทำได้ระหว่างการคำนวณ ในแต่ละขั้นตอนของการคำนวณ หรือเพียงแค่ทำในตอนท้าย โดยพื้นฐานแล้ว ลูกค้าทำโมดูโลในตอนเริ่มต้น โดยปิดบัง $m$แล้วปล่อยให้เซิร์ฟเวอร์ทำการคำนวณบนนั้น เมื่อได้ผลลัพธ์กลับมา ก็แค่คำนวณโมดูโล สิ่งนี้จะเทียบเท่ากับเซิร์ฟเวอร์ที่ทำการคำนวณทั้งหมดในเลขคณิตโมดูลาร์ตลอดเวลา แต่เราทำสิ่งนี้โดยไม่บอกเซิร์ฟเวอร์ว่า $p$ เป็น. น่าเสียดายที่สิ่งนี้ไม่มีประสิทธิภาพเนื่องจากตัวเลขเหล่านี้อาจมีความยาวเพิ่มขึ้นตามอำเภอใจ เพื่อแก้ไขปัญหานี้ ลูกค้าสามารถคำนวณจำนวนเฉพาะอื่นๆ $คิว$ในระหว่างขั้นตอนการเตรียมใช้งาน จากนั้นทำการคำนวณ $N=pq$. ลูกค้าให้ $N$ ไปยังเซิร์ฟเวอร์ (โปรดทราบว่าจากการสันนิษฐานของ RSA สิ่งนี้ไม่ได้เปิดเผยอะไรเกี่ยวกับ $p$). จากนั้น เซิร์ฟเวอร์จะสามารถทำโมดูโลการคำนวณได้ทั้งหมด $N$และด้วยเหตุนี้ มันจึงไม่มีจำนวนเต็มที่จะเติบโตจนมีขนาดยาวตามอำเภอใจ เหตุผลที่ใช้งานได้คือตั้งแต่นั้นมา $N$ เป็นทวีคูณของ $p$, ถ้า $x \equiv a \mod N$, แล้ว $x \equiv a \mod p$ (ลองดูความเห็นบน โพสต์นี้ซึ่งเป็นแรงบันดาลใจให้ผมเกิดไอเดียนี้ขึ้น)

การคำนวณสิ่งที่ตรงกันข้าม $\bmod N$ น่าเสียดายที่ไม่ยากเป็นพิเศษ โดยเฉพาะอย่างยิ่ง, $x^{-1}\bmod N$ เป็นค่าใน $\mathbb{Z}_N$ ดังนั้น $xx^{-1}\equiv 1\bmod N$. โปรดทราบว่าถ้าเรารู้จำนวนเต็ม $a, b$ ดังนั้น

$$aN + bx = 1$$

แล้ว $x^{-1}\equiv b\bmod N$. ทั้งนี้เนื่องจากสมการข้างต้น $\bmod N$ เป็น $ bx\equiv 1\bmod N$, ดังนั้น $ข$ คือ "สิ่งที่ทวีคูณด้วย $x$ เพื่อให้ได้ 1 $\bmod N$", เช่น มันผกผัน

เราจะได้รับได้อย่างไร $a, b$ ดังนั้น $aN + bx = 1$? เดอะ อัลกอริทึมแบบยุคลิดแบบขยาย จะให้เรา $a, b$ ดังนั้น $aN+bx= \mathsf{gcd}(x, N)$. น่าเสียดาย, $x$ กลับด้าน $\bmod N$ เทียบเท่ากับ $\mathsf{gcd}(x, N) = 1$ดังนั้น อัลกอริทึมแบบยุคลิดแบบขยายจึงคำนวณค่าผกผัน $\bmod N$และทำลายระบบเข้ารหัสลับของคุณได้อย่างมีประสิทธิภาพ (เช่น $O((\logN)^3)$ ไออาร์ซี).