Score:1

การดำเนินการช่องเดียวบน SIMD พหุนามโฮโมมอร์ฟิกอย่างเต็มที่

ธง cn

ตาม https://eprint.iacr.org/2011/133.pdf และเอกสารอื่นๆ อีกมากมาย มีไอโซมอร์ฟซิมระหว่างสเปซของพหุนามกับค่าสัมประสิทธิ์ของมัน อย่างน้อยในโครงการ BFV เราสามารถทำได้:

$$p(x) = [a_1, a_2, ..., a_3]$$ $$\phi(p(x)) = [\phi(a_1), \phi(a_2), ..., \phi(a_3)]$$

ดังนั้นการใช้การดำเนินการเดียวกับพหุนามจึงเหมือนกับการใช้กับองค์ประกอบทั้งหมด เช่นเดียวกับ SIMD ที่ทำงานบน CPU นี่ก็เรียกว่า Galois automorphism ในบางโครงร่าง

ตอนนี้ สมมติว่าฉันต้องการใช้งานองค์ประกอบที่สอง ดังนั้นฉันจึงหาวิธีแยกมันด้วยบิตมาสก์ ดังนั้นฉันจึงได้รับ:

$$p_2(x) = [0, \phi(a_2), ..., 0]$$

ตอนนี้ฉันสามารถดำเนินการ $p_2(x)$ ในการปรับเปลี่ยน $\phi(a_2)$ อย่างไรก็ตามฉันต้องการ มีวิธีใส่กลับเข้าไปใน $p(x)$ ด้วยการปรับเปลี่ยนของฉัน? ฉันคิดว่าการดำเนินการบางอย่างที่ฉันทำอยู่ p_2(x) อาจทำให้องค์ประกอบอื่นๆ ไม่เป็นศูนย์ ซึ่งเป็นความท้าทายเช่นกัน

Score:0
ธง ng

มีวิธีง่ายๆในการทำเช่นนี้ โดยเฉพาะอย่างยิ่ง คุณได้กล่าวไปแล้วว่าคุณมีขั้นตอนการแยกบิตมาสก์ จึงกำหนดให้ $p(x)$, $p_2(x)$, และ $p_2'(x)$ (การดำเนินการแบบโฮโมมอร์ฟิคของคุณใช้กับ $p_2$), อนุญาต $p_3(x)$ เป็นผลมาจากการใช้บิตมาสก์เดียวกันกับ $p_2'$. จากนั้นตรวจสอบได้ง่าย

$$p(x) - p_2(x) + p_3(x)$$

ให้ผลลัพธ์ที่คุณต้องการ

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

  • การสกัด bitmask หนึ่งรายการเพียงพอหรือไม่
  • เราจะใช้การสกัด bitmask อย่างมีประสิทธิภาพได้อย่างไร

หากสล็อตที่คุณต้องการคำนวณคือ สาธารณะก็เพียงพอแล้วที่จะคูณด้วยค่าคงที่ที่เหมาะสม (ด้วยค่าสัมประสิทธิ์ 0/1) พหุนาม โดยให้ค่าโสหุ้ยการคูณเป็น 1 สำหรับการสกัดบิตมาสก์แต่ละครั้ง บิตมาสก์ส่วนตัวดูเหมือนจะมีประสิทธิภาพน้อยลง --- ฉันนึกถึงบางสิ่งที่ใช้ได้ $O(n)$ การคูณ (แต่อย่างน้อยก็มีความลึก 1) โดยพื้นฐานแล้วโดยการคำนวณการคูณบูลีน 0/1 (เข้ารหัส) สำหรับแต่ละดัชนีเพื่อ "เลือก" ดัชนีที่ถูกต้อง จากนั้นเพิ่มทุกอย่างในตอนท้าย

ฉันไม่รู้ว่าสิ่งที่กล่าวมาข้างต้นเปรียบเทียบกับความล้ำสมัยได้อย่างไร

นอกจากนี้ยังเป็นมูลค่าการกล่าวขวัญว่าหากการดำเนินการของคุณเปิดอยู่ $p_2(x)$ ทำ ไม่ ขึ้นอยู่กับพิกัดอื่นๆ $\phi(a_i)$ (แต่อาจเพียงแค่ "เขียนทับ" พวกมัน) เราสามารถลบหนึ่งในการดำเนินการแยกบิตมาสก์ (คือตัวแรก) ขึ้นอยู่กับฟังก์ชั่นเฉพาะที่คุณกำลังประเมิน

โพสต์คำตอบ

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