อาจารย์ของคุณกำลังพูดถึงการเพิ่มประสิทธิภาพที่ค่อนข้างบ่อยดังต่อไปนี้
อนุญาต $\คณิตศาสตร์แคล{K}$ เป็นชุดและให้ $\mathsf{Sample} : \{0,1\}^r\to\mathcal{K}$ เป็นอัลกอริทึมที่เมื่อป้อนข้อมูล $r$ บิตสุ่มที่สม่ำเสมอ ส่งออกองค์ประกอบ $k\in \mathcal{K}$.
ถ้า $\mathsf{PRG} : \{0,1\}^s\to\{0,1\}^r$ เป็น PRG แล้วสำหรับ $s\leftarrow\{0,1\}^s, r\leftarrow\{0,1\}^r$, การกระจายของ
$$\mathsf{Sample}(\mathsf{PRG}(s))\ประมาณ_c \mathsf{Sample}(r)$$
ไม่สามารถแยกความแตกต่างทางการคำนวณได้
การพิสูจน์เรื่องนี้เป็นเรื่องเล็กน้อย โดยการรักษาความปลอดภัยของ PRG $\mathsf{PRG}(s) \ประมาณ_c r$. การใช้อัลกอริทึม (ที่มีประสิทธิภาพ) $\mathsf{ตัวอย่าง}$ คงความสามารถในการแยกแยะความแตกต่างทางคอมพิวเตอร์ (เช่น อื่น ๆ $\mathsf{ตัวอย่าง}$ จะเป็นศัตรูที่มีประสิทธิภาพในการต่อต้าน PRG)
โดยพื้นฐานแล้ว หากการก่อสร้างขั้นสุดท้ายของคุณต้องการ $s$-บิตคีย์ มักจะพอเพียงที่จะให้คีย์เป็น a $r$- บิตเมล็ด PRG แล้วยืดสิ่งนี้ไปที่ $s$ บิตกับ PRG
มีรายละเอียดเฉพาะหลายประการที่จะชี้ให้เห็นในข้างต้น:
คีย์สุดท้ายที่สร้างจาก $\mathsf{Sample}(r)$ ไม่จำเป็นต้องสุ่มแบบสม่ำเสมอ (แม้ว่านี่จะเป็นกรณีที่พบบ่อยที่สุด)
เราสามารถทำให้ข้อสันนิษฐานของผลลัพธ์ข้างต้นอ่อนแอลงได้โดยการดึงดูดผู้ป้อนข้อมูลแบบสุ่ม $r$ ตัวมันเองไม่จำเป็นต้องเหมือนกัน แต่ต้องการ "ค่าเอนโทรปีต่ำสุดที่เพียงพอ" แทน ในแบบที่จะทำให้แม่นยำได้
คุณยังต้องการการแลกเปลี่ยนคีย์. เกมการรักษาความปลอดภัยของ PRG กำหนดให้เก็บเมล็ดพันธุ์ของ PRG ไว้เป็นความลับเพื่อความปลอดภัย ดังนั้นคุณยังคงต้องแน่ใจว่าอีฟไม่สามารถเข้าถึงเมล็ดพันธุ์ได้ (ตามที่คุณพูดถึง)
การเพิ่มประสิทธิภาพทั้งหมดนี้กำลังบอกว่า "เพย์โหลด" ของการแลกเปลี่ยนคีย์สามารถทำให้เล็กลงได้โดยใช้ PRG (โดยเฉพาะอย่างยิ่ง มันสามารถ $r$ บิตมากกว่า $s$ บิต)
มีการเพิ่มประสิทธิภาพที่เกี่ยวข้อง (ซึ่งแตกต่างกันเล็กน้อย) ที่อาจคุ้มค่าที่จะพูดคุยเช่นกัน
บ่อยครั้งในการเข้ารหัส (โดยเฉพาะอย่างยิ่ง ในตาข่ายและการเข้ารหัสตามการเข้ารหัส) เราต้องส่งองค์ประกอบสุ่มขนาดใหญ่ที่สม่ำเสมอ
โดยเฉพาะอย่างยิ่ง สมมติฐานการเรียนรู้ด้วยข้อผิดพลาดเกี่ยวกับ "ตัวอย่าง" ของ LWE:
$$ (A, As+e)$$
ฉันจะไม่กำหนดทุกอย่างในตัวอย่างนี้ แต่จะพูดอย่างนั้นแทน $A$ โดยทั่วไปจะเป็นเมทริกซ์สุ่มที่มีขนาดเท่ากัน $\ประมาณ 1-10kb$ขึ้นอยู่กับรูปแบบเฉพาะ
คุณอาจถูกล่อลวงให้แทนที่วัตถุสุ่มแบบเดียวกันนี้ด้วยเมล็ดพันธุ์ PRG $s$ซึ่งสามารถขยายเป็นค่าสุ่มตามกำหนดได้ $A$ ภายหลัง. เนื่องจากเมล็ดพันธุ์ PRG เป็นไปตามคำสั่งของ $\ประมาณ 128$ บิต นี่คือกำไร (ศักยภาพ) ที่สำคัญ
นี่ไม่ใช่การปรับให้เหมาะสมที่ถูกต้อง เนื่องจากจุดที่ 3 ด้านบน --- คุณไม่สามารถใช้ PRG เพื่อ "บีบอัด" ค่าสุ่มแบบสม่ำเสมอให้กับเมล็ดแบบสั้นด้วยวิธีนี้ หากโครงร่างของคุณทำให้ค่าสุ่มแบบสม่ำเสมอนี้เป็นแบบสาธารณะในภายหลัง หรือคุณสามารถทำได้ แต่สำหรับ PRG บางอย่าง สิ่งนี้อาจทำลายความปลอดภัยโดยสิ้นเชิง
ยังมีสิ่งที่คล้ายกันที่คุณสามารถทำได้กับสิ่งที่เรียกว่าฟังก์ชันเอาต์พุตที่ขยายได้ (ไม่ว่าจะด้วยเหตุผลใดก็ตาม ตัวย่อคือ XOF) สิ่งเหล่านี้เป็นแบบดั้งเดิมที่ใช้การแฮชซึ่ง (คร่าวๆ) มีไว้เพื่อใช้เมื่อต้องการคุณสมบัติที่เหมือน PRG แต่มีเมล็ดพันธุ์สาธารณะ
อย่างไรก็ตาม การใช้ XOF เพื่อบีบอัดค่าสุ่มที่สม่ำเสมอขนาดใหญ่นั้นเป็นการปรับให้เหมาะสมที่ธรรมดาอย่างไม่น่าเชื่อ ฉันค่อนข้างแน่ใจว่าผู้เข้ารอบสุดท้ายของ NIST PQC ที่ใช้ LPR (Saber/Kyber) ที่ใช้ LPR ทั้งสองใช้การปรับให้เหมาะสมนี้ แม้ว่าการใช้งานเฉพาะใดๆ อาจเบี่ยงเบนไปจากข้อกำหนดเล็กน้อยและรวม/ล้มเหลวในการรวมการปรับให้เหมาะสม