ฉันได้ใช้งาน Paillier Cryptosystem สมมติว่าฉันมีอาร์เรย์ที่เข้ารหัส E(x) = [2,4,5,10,0,20] และฉันต้องการค้นหาว่าถ้ามี 0 อยู่ในอาร์เรย์นั้น เนื่องจากข้อจำกัดของระบบเข้ารหัส Paillier ฉันจึงไม่สามารถคูณข้อความรหัสสองตัวได้ มีวิธีอื่นในการค้นหาหรือไม่?
Paillier เป็นการเข้ารหัสที่ปลอดภัยของ CPA ดังนั้นทุกสิ่งที่เราสามารถอนุมานได้จากข้อความเข้ารหัสต้องใช้คีย์ส่วนตัว ดังนั้น "ฉันต้องการค้นหา" กำหนดให้ "ฉัน" มีรหัสส่วนตัว จากนั้น "ฉันมีอาร์เรย์ที่เข้ารหัส" หมายความว่า "ฉัน" สามารถถอดรหัสข้อความเข้ารหัสแต่ละรายการได้ ซึ่งทำให้คำถามเป็นไปตามที่ระบุไว้
ดังนั้น เราจะเปลี่ยนคำชี้แจงปัญหาเป็น: เรามีมากที่สุด $k$ จำนวนเต็มขนาดเล็ก $m_i\in[0,\ell)$ (ในโจทย์ที่เราอยากได้ $k\ge6$, และ $\ell>20$); และเราต้องการวิธีการสาธารณะในการแสดงสิ่งเหล่านี้ $m_i$ เข้ารหัสเป็น $c_i$ โดยใช้ Paillier Cryptosystem และรวมไฟล์ $c_i$ เป็นหนึ่งเดียว $ค$ เช่นเดียวกับที่เราทำใน Paillier นั่นคือการสร้างโมดูโลผลิตภัณฑ์ $n$ ของ $c_i$และเลือกที่จะคูณโมดูโล $n$ โดยข้อความเข้ารหัสสำหรับ $0$ เพื่อปกปิดผลลัพธ์ต่อไป เราต้องการสิ่งต่าง ๆ เพื่อให้บุคคลที่ถือคีย์ส่วนตัวสามารถระบุได้ $ค$ ถ้า $0$ มีอยู่ในชุดข้อมูลเริ่มต้นของ $m_i$. การเปลี่ยนแปลงที่สำคัญสองประการในคำชี้แจงปัญหาเริ่มต้น:
นี่คือสิ่งที่เราจะไม่เพียงรู้ว่า $0$ มีอยู่ใน $m_i$เราจะทราบด้วยว่าแต่ละจำนวนเต็มมีกี่จำนวน $[0,\เอล)$ มีอยู่ในอาร์เรย์เดิม
เพื่อสิ่งนี้ เราเข้ารหัส $m_i$ เข้าไปข้างใน $m'_i=(k+1)^{m_i}$ ก่อนใช้การเข้ารหัส Paillier Paillier จะให้เรารวมข้อความไซเฟอร์ $c_i$ จากนั้นถอดรหัสชุดค่าผสม $ค$ เข้าไปข้างใน $m'=(\sum m'_i)\bmod n$. จาก $m'$ เราสามารถอนุมานได้ว่าแต่ละจำนวนเต็มมีกี่เวลา $[0,\เอล)$ มีอยู่ใน $m_i$, ตราบเท่าที $k(k+1)^{\ell-1}<n$โดยแสดงออก $m'$ ในฐาน $k+1$ และดูที่ตัวเลข/แขนขา ฉันจะข้ามพีชคณิตสำหรับวิธีการ และใช้ตัวอย่างเป็นทศนิยม (ดังนั้น $k=9$). $m_0=2$, $m_1=4$, $m_2=5$, $m_3=10$, $m_4=0$, $m_5=20$ เข้ารหัสเป็น $m'_0=100$, $m'_1=10,000$, $m'_2=100,000$, $m'_3=10000000000$, $m'_4=1$, $m'_5=0$, $m'_6=100000000000000000000$ เป็นทศนิยม เราจะได้รับ $m'=1000000000010000110101$ซึ่งเราสามารถบอกได้ว่ามีอยู่อย่างละหนึ่งอย่าง $0$, $2$, $4$, $5$, $10$, $20$ ในอาร์เรย์เดิมของ $m_i$โดยดูที่ตำแหน่งของตัวเลขที่ไม่ใช่ศูนย์และเห็นว่าเป็น $1$. ถ้า $20$ ถูกเปลี่ยนเป็น $0$, ผลลัพธ์จะเป็นอย่างไร $m'=10000110102$ และเราจะรู้ว่ามีสอง $m_i=0$เนื่องจากหลักขวาสุดคือ $2$.
คำถามไม่ได้บอกสิ่งที่เรา อย่า ต้องการให้เจ้าของคีย์ส่วนตัวสามารถตรวจสอบได้จาก $ค$. บางทีเราต้องการจำกัดสิ่งนั้นเพื่อพิจารณาว่ามี $0$กับการรั่วไหลเล็กน้อยประมาณกี่ $0$ เป็นไปได้.
ในการทำเช่นนี้ เราสามารถเข้ารหัสแต่ละรายการได้ $m_i\ne0$ ถึง $m'_i=0$, และแต่ละ $m_i=0$ เป็นจำนวนเต็ม $m'_i$ ใน $[1,\ชั้นn/k\rชั้น)$ เลือกโดยการสุ่มโดยมีการแจกแจงที่มีอคติอย่างมากต่อค่าที่ต่ำ เมื่อการถอดรหัสของชุดค่าผสมเป็นศูนย์ เป็นที่ทราบกันดีว่าไม่มีศูนย์ใน $m_i$และไม่มีอะไรอื่น มิฉะนั้น เป็นที่ทราบกันว่ามีค่าเป็นศูนย์ และมีการรั่วไหลของข้อมูลเล็กน้อยเกี่ยวกับจำนวน การกระจายสามารถปรับให้เหมาะสมเพื่อลดการรั่วไหลให้เหลือน้อยที่สุด นี่เป็นแบบฝึกหัดสำหรับผู้อ่าน
เป็นไปได้ที่จะปรับแต่งสิ่งต่าง ๆ ด้วยคีย์ส่วนตัวและ $c_i$ สามารถหาได้ $m_i$แต่ (ตามด้านบน) อันหนึ่งที่มีคีย์ส่วนตัวและ $ค$ สามารถรับข้อมูลเล็กน้อยเกี่ยวกับ $m_i$นอกเหนือจากนั้นก็คือ $0$. ฉันจะไม่ลงรายละเอียดเพราะไม่ได้อยู่ในคำสั่งปัญหา
เช่นเดียวกับการเข้ารหัสแบบโฮโมมอร์ฟิกหลายๆ อย่าง ระบบเหล่านี้เป็นระบบทางทฤษฎีที่ดีโดยมีปัญหาเล็กน้อยที่ตรงกันในชีวิตจริง
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
