ความสำคัญของการกระจายในการเข้ารหัส

ฉันได้ศึกษาเรื่องของการเข้ารหัสทางทฤษฎีและมีการอภิปรายเกี่ยวกับการสุ่มตัวอย่างและการกระจายอยู่เสมอ (ในขณะที่เรียนรู้แผนการใด ๆ ) ในชั้นเรียน คำถามเช่น การแจกแจงที่จะสุ่มตัวอย่างจากอินพุตคืออะไร นอกจากนี้ ฉันยังสับสนในคำถาม เช่น จะสร้างตัวอย่างได้อย่างไร

ฉันแค่ต้องการทำความเข้าใจเกี่ยวกับการสุ่มตัวอย่างและความสำคัญของการกระจายในขณะที่สุ่มตัวอย่างในการเข้ารหัส

ในการเข้ารหัส การแจกแจง (ความน่าจะเป็น) มักจะไม่ต่อเนื่อง นั่นคือฟังก์ชัน $F$ จากเซตจำกัด $\คณิตศาสตร์ S$ ถึงช่วงเวลา $[0,1]$ ของ $\mathbb R$ ดังนั้น $$1=\sum_{x\in\mathcal S}F(x)$$

$F(x)$ จะต้องเข้าใจว่าน่าจะเป็นที่ $x$ เกิดขึ้นได้ในบางสถานการณ์ ขึ้นอยู่กับสถานการณ์ ตั้งค่า $\คณิตศาสตร์ S$ ตัวอย่างเช่น สามารถเป็นชุดของคีย์ สัญลักษณ์ในตัวอักษรบางตัวหรือกลุ่มข้อมูล (เช่น ไบต์) ข้อความภาษาอังกฤษบางขนาด อินพุตหรือเอาต์พุตที่เป็นไปได้ของบางฟังก์ชัน

บ่อยครั้ง (และเว้นแต่จะชัดเจนหรือระบุไว้เป็นอย่างอื่น) การกระจายจะถือว่าสม่ำเสมอ นั่นคือค่าคงที่ทั่ว $\คณิตศาสตร์ S$. มันเป็นไปตาม $F(x)=1/\lvert\mathcal S\rvert$ โดยไม่คำนึงถึง $x$ ใน $\คณิตศาสตร์ S$.

บ่อยครั้ง (และเว้นแต่จะชัดเจนหรือระบุไว้เป็นอย่างอื่น) เมื่อหน่วยข้อมูลที่เป็นประโยชน์บางหน่วยประกอบด้วยหรือสัญลักษณ์สุ่มของชุดเดียวกัน (เช่น บิต ไบต์ อักขระของคีย์) จะถือว่าฟังก์ชันเดียวกัน $F$ ใช้กับสัญลักษณ์ทั้งหมด นั่นคือสัญลักษณ์สุ่มและไม่ขึ้นต่อกัน นั่นเป็นความคิดที่แตกต่าง (และมุมฉาก) จากเครื่องแบบ

ห่างไกลจากการแจกแจงทั้งหมดที่พิจารณาในการเข้ารหัสเป็นแบบเดียวกันหรือ/และเป็นอิสระ ตัวอย่างเช่น การกระจายตัวอักษรในข้อความธรรมดาภาษาอังกฤษยังห่างไกลจากรูปแบบเดียวกัน และสัญลักษณ์คู่ที่อยู่ติดกันยังห่างไกลจากความเป็นอิสระต่อกัน ในกรณีนั้น การพิจารณาการกระจายคำในภาษาอังกฤษหรือการแจกแจงตัวอักษรติดต่อกันสองหรือสามตัวในข้อความภาษาอังกฤษตัวอย่างขนาดใหญ่นั้นเหมาะสมกว่า

แนวคิดนี้มีความสำคัญในหลาย ๆ ด้านของการเข้ารหัสและการวิเคราะห์การเข้ารหัสตัวอย่างเช่น ความปลอดภัยของ One Time Pad ขึ้นอยู่กับแผ่นรองที่มีการกระจายสม่ำเสมอ และถ้าประกอบด้วยสัญลักษณ์แสดงว่าสัญลักษณ์นั้นไม่ขึ้นต่อกัน (คือใช้การแจกแจงแบบเดียวกันซึ่งต้องเหมือนกันด้วย) แต่ความปลอดภัยของ OTP ไม่ได้ขึ้นอยู่กับการกระจายของข้อความธรรมดา

การสร้างตัวอย่างตามการกระจายบางส่วน $F$ กำลังเลือกองค์ประกอบ $x_i$ จากชุด $\คณิตศาสตร์ S$ ตาม $F$สร้างทูเพิล (โดยทั่วไปสั่ง) เว้นแต่จะระบุไว้เป็นอย่างอื่น ตัวอย่าง (ถ้ามีมากกว่า 1) จะถูกเลือกโดยอิสระ และแต่ละตัวอย่างจะถูกเลือกด้วยวิธีนั้น $x_i$ มีความน่าจะเป็น $F(x)$ เป็น $x$. หรือบางที (ขึ้นอยู่กับบริบท) ตัวเลือกอาจมาจากกระบวนการที่กำหนดขึ้นเอง (แทนที่จะสุ่ม) เช่น การแจกแจงจริงนั้น (หรือสันนิษฐาน) แยกไม่ออกจากการแจกแจงแบบสุ่มต่อ $F$.