Score:0

พื้นที่สุ่มของฟังก์ชันการเข้ารหัส

ธง in

ฉันกำลังอ่านคำจำกัดความของการแปลง Fujisaki-Okamoto และฉันพบสิ่งนี้:

ป้อนคำอธิบายรูปภาพที่นี่

"พื้นที่สุ่ม" ของฟังก์ชันหมายความว่าอย่างไร รวม ในการตั้งค่า PKE?

Score:1
ธง ng

โดยทั่วไป หากคุณถามเกี่ยวกับคำจำกัดความเฉพาะ จะเป็นการดีที่จะใส่ลิงก์ไปยังคำจำกัดความภายใต้คำถาม

โดยทั่วไปเป็นที่ทราบกันดีว่า PKE ต้องใช้ การเข้ารหัสแบบสุ่ม (หรือ nonce ที่ไม่ซ้ำ ฉันจะเพิกเฉยต่อสิ่งนี้) กล่าวคือ (ยกเว้นในการตั้งค่าพิเศษ) ฟังก์ชัน:

$$\mathsf{Enc} : \mathcal{PK}\times\mathcal{M}\to\mathcal{C}$$

คือ สุ่ม อัลกอริทึม (ที่ไหน $\mathcal{PK}$ เป็นพื้นที่ของกุญแจสาธารณะทั้งหมด) คุณสามารถ [1] เขียนอัลกอริทึมแบบสุ่มเป็น a กำหนด อัลกอริทึมที่ใช้เป็นอินพุตสตริงสุ่ม เช่น เขียน:

$$\mathsf{Enc}^{det} : \mathcal{PK}\times\mathcal{M}\times\mathcal{R}\to\mathcal{C}$$

ที่ไหน $\mathsf{Enc}^{det}(pk, m;r)$ จำลองอัลกอริทึม $\mathsf{Enc}(pk,m)$และเมื่ออัลกอริทึมร้องขอบิตสุ่ม จะใช้สตริง (คงที่) $r$ เป็นแหล่งที่มาของบิต "สุ่ม"

สิ่งนี้เกี่ยวข้องกับการแปลง FO เนื่องจากสามารถ "แยกตัวประกอบ" ออกเป็นสองขั้นตอน (ไฟล์ $T$-แปลงร่างและ $U$-แปลงดู กระดาษแผ่นนี้). เดอะ $T$-transform แก้ไข $\mathsf{Enc}$ ในสองวิธี:

  1. สุ่ม: มากกว่าการใช้การสุ่ม $r$หนึ่งใช้ oracle สุ่ม $G$ เพื่อตั้งค่า $r := G(ม)$เช่น เลือก $\mathsf{Enc}^{det}(pk,m) := \mathsf{Enc}(pk,m; G(m))$

  2. เข้ารหัสซ้ำ: การถอดรหัสยังถูกแก้ไข กล่าวคือ การตรวจสอบนั้นสำหรับ $m'\gets\mathsf{ธ.ค.}(sk, c)$ ความสัมพันธ์ $c = \mathsf{Enc}^{det}(pk, m')$ ถือ เพื่อให้การตรวจสอบนี้สมเหตุสมผล การเข้ารหัสจะต้อง (แน่นอน) กำหนดขึ้นได้

ยังไงก็ตามที่จะสามารถทำขั้นตอนแรกของ $T$- การแปลงร่างจำเป็นต้องรู้ $\mathcal{R}$เนื่องจากคุณต้องสามารถเลือกออราเคิลแบบสุ่มได้ $G : \mathcal{M}\to\mathcal{R}$. โดยทั่วไป $\mathcal{R}$ สามารถเขียนแบบฟอร์ม $\{0,1\}^k$ สำหรับบางคน $k$ [2].


[1] อาจมีพยาธิสภาพบางอย่างที่นี่หากอัลกอริทึมแบบสุ่มมีเวลาทำงาน "คาดหมายพหุนาม" แทนที่จะยุติในเวลาทำงานพหุนามฉันจะเพิกเฉยต่อสิ่งนี้ ไม่เกี่ยวข้องกับการเข้ารหัส

[2] โปรดทราบว่ามีแผนการที่คุณอาจกังวล $\mathcal{R} \neq \{0,1\}^k$, หรือแม้กระทั่ง $\mathcal{R} = \{0,1\}^k$ แต่การกระจายเสียงนั้น $\mathsf{Enc}$ ความต้องการไม่สม่ำเสมอ $\{0,1\}^k$. โดยเฉพาะอย่างยิ่งฉันกำลังคิดถึงโครงร่างแบบตาข่ายซึ่งการสุ่มมักจะเป็น "แบบเกาส์เซียน" (หรือพูดว่าทวินามกึ่งกลาง) แม้ว่าสิ่งนี้จะเกิดขึ้นสำหรับโครงร่างแบบใช้รหัสซึ่งบ่อยครั้งการสุ่มได้แก้ไขน้ำหนักแฮมมิ่ง iirc โดยทั่วไปแล้ว oracle แบบสุ่มจะมีเอาต์พุต $ก(ม)$ นั่นคือการสุ่มอย่างสม่ำเสมอ $\{0,1\}$. นี่ไม่ใช่ปัญหาที่แท้จริง --- เราสามารถใช้อัลกอริธึมการสุ่มตัวอย่างได้ $\mathsf{Samp} : \{0,1\}^k \to \mathcal{R}$ เพื่อแปลงเอาต์พุตของ oracle แบบสุ่มเป็นการแจกแจงที่ต้องการ สิ่งนี้เกิดขึ้นได้แม้กับการเข้ารหัสแบบสุ่ม โดยที่แทนที่จะใช้ RO สำหรับการสุ่ม อัลกอริทึมจะใช้รูปแบบบางอย่างของการสุ่มของระบบ (ซึ่งถือว่าแยกไม่ออกจากการคำนวณจากบิตสุ่มแบบเดียวกัน)

โพสต์คำตอบ

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