อ่าน 3 นาที
เงื่อนไขสุดขั้ว
ใน การเข้ารหัสลับ เงื่อนไข หลัก (hard-core predicate ) ของ ฟังก์ชันทางเดียว f คือ เงื่อนไข b (กล่าวคือ ฟังก์ชันที่มีเอาต์พุตเป็นบิตเดียว) ซึ่งคำนวณได้ง่าย (เป็นฟังก์ชันของ x )...
เงื่อนไขสุดขั้ว
ในการเข้ารหัสลับ เงื่อนไข หลัก(hard-core predicate ) ของฟังก์ชันทางเดียวfคือเงื่อนไขb (กล่าวคือ ฟังก์ชันที่มีเอาต์พุตเป็นบิตเดียว) ซึ่งคำนวณได้ง่าย (เป็นฟังก์ชันของx ) แต่คำนวณได้ยากเมื่อกำหนดf(x)ในทางทฤษฎีแล้ว ไม่มีอัลกอริธึมแบบพหุนามเวลา (PPT)ใดที่คำนวณb(x)จากf(x)ด้วยความน่าจะเป็นที่มากกว่าครึ่งหนึ่งอย่างมีนัยสำคัญเมื่อเทียบกับการเลือกx แบบ สุ่ม[ 1 ] : 34 กล่าวอีกนัยหนึ่ง หากxถูกสุ่มอย่างสม่ำเสมอ เมื่อกำหนดf(x) แล้ว ฝ่ายตรงข้าม PPT ใดๆ ก็สามารถแยกแยะบิตหลักb(x)และบิตสุ่มอย่างสม่ำเสมอได้โดยมีข้อได้เปรียบ เพียงเล็กน้อย เมื่อเทียบกับความยาวของx [ 2 ]
ฟังก์ชันแกนแข็งสามารถกำหนดได้ในทำนองเดียวกัน นั่นคือ ถ้าxถูกเลือกแบบสุ่มอย่างสม่ำเสมอ เมื่อกำหนดf(x) แล้ว อัลกอริทึม PPT ใดๆ ก็สามารถแยกแยะค่าฟังก์ชันแกนแข็งh(x)และบิตสุ่มอย่างสม่ำเสมอที่มีความยาว|h(x)|ได้โดยมีข้อได้เปรียบเล็กน้อยเหนือความยาวของx [ 3 ] [ 4 ]
คำกริยาแสดงความ หมาย เข้มข้นจะสื่อถึงความยากลำบากในการกลับด้านฟังก์ชันf
แม้ว่าฟังก์ชันทางเดียวจะยากต่อการผกผัน แต่ก็ไม่มีการรับประกันเกี่ยวกับความเป็นไปได้ในการคำนวณข้อมูลบางส่วนเกี่ยวกับภาพก่อนหน้าcจากภาพf(x)ตัวอย่างเช่น แม้ว่าRSAจะถูกสันนิษฐานว่าเป็นฟังก์ชันทางเดียว แต่สัญลักษณ์ Jacobiของภาพก่อนหน้าสามารถคำนวณได้ง่ายจากสัญลักษณ์ Jacobi ของภาพ[ 1 ] : 121
เป็นที่ชัดเจนว่าหากฟังก์ชันแบบหนึ่งต่อหนึ่งมีเงื่อนไขแกนแข็ง ฟังก์ชันนั้นจะต้องเป็นฟังก์ชันทางเดียว Oded GoldreichและLeonid Levin (1989) แสดงให้เห็นว่าฟังก์ชันทางเดียวทุกฟังก์ชันสามารถปรับเปลี่ยนได้อย่างง่ายดายเพื่อให้ได้ฟังก์ชันทางเดียวที่มีเงื่อนไขแกนแข็งเฉพาะ[ 5 ] ให้fเป็นฟังก์ชันทางเดียว กำหนดg(x,r) = (f(x), r)โดยที่ความยาวของrเท่ากับความยาว ของ xให้x jแทน บิต ที่jของxและ r jแทน บิต ที่jของrจากนั้น
เป็นเงื่อนไขหลักของgโปรดทราบว่าb(x, r) = < x, r > โดยที่ <·, ·> หมายถึงผลคูณภายใน มาตรฐาน บนปริภูมิเวกเตอร์ ( Z 2 ) nเงื่อนไขนี้เป็นเงื่อนไขหลักเนื่องจากปัญหาในการคำนวณ กล่าวคือ ไม่ได้ยากต่อการคำนวณเพราะg(x, r)มี การสูญเสีย ข้อมูลในเชิงทฤษฎีแต่ถ้ามีอัลกอริทึมที่คำนวณเงื่อนไขนี้ได้อย่างมีประสิทธิภาพ ก็จะมีอัลกอริทึมอื่นที่สามารถผกผันfได้อย่างมีประสิทธิภาพเช่นกัน
โครงสร้างที่คล้ายกันนี้ทำให้ได้ฟังก์ชันแกนแข็งที่มีบิตเอาต์พุตO(log |x|) สมมติว่า fเป็นฟังก์ชันทางเดียวที่แข็งแกร่ง กำหนดg(x, r) = (f(x), r)โดยที่ | r | = 2| x | เลือกฟังก์ชันความยาวl(n) = O(log n)โดยที่l(n) ≤ nให้
จากนั้นh(x, r) := b 1 (x, r) b 2 (x, r) ... b l(|x|) (x, r)เป็นฟังก์ชันแกนแข็งที่มีความยาวเอาต์พุตl(|x| ) [ 6 ]
บางครั้งบิตจริงของอินพุตx นั้นเป็นแกนหลัก ตัวอย่างเช่น บิตทุกบิตของอินพุตไปยังฟังก์ชัน RSA เป็นตัวบ่งชี้แกนหลักของ RSA และบล็อกของบิตO(log |x|) ของ x นั้นไม่สามารถแยกแยะได้จากสตริงบิตสุ่มในเวลาพหุนาม (ภายใต้สมมติฐานว่าฟังก์ชัน RSA นั้นยากต่อการผกผัน) [ 7 ]
เงื่อนไขหลัก (Hard-core predicate) เป็นวิธีหนึ่งในการสร้างตัวสร้างเลขสุ่มเทียมจากลำดับการเรียงสับเปลี่ยนทางเดียว ใดๆ ก็ได้ ถ้าbเป็นเงื่อนไขหลักของลำดับการเรียงสับเปลี่ยนทางเดียวfและsเป็นค่าเริ่มต้นของเลขสุ่มแล้ว
เป็นลำดับบิตสุ่มเทียม โดยที่f nหมายถึงการวนซ้ำครั้งที่ n ของการใช้fบนsและbคือบิตแกนแข็งที่สร้างขึ้นโดยแต่ละรอบn [ 1 ] : 132
เงื่อนไขหลักที่เข้มงวดของการเรียงสับเปลี่ยนทางเดียวของกับดัก (เรียกว่าเงื่อนไขกับดัก ) สามารถใช้ในการสร้างแผนการเข้ารหัสกุญแจสาธารณะที่ปลอดภัยทางความหมายได้[ 1 ] : 129
ดูเพิ่มเติม
- การถอดรหัสแบบลิสต์ (อธิบายการถอดรหัสแบบลิสต์ แก่นของการสร้างพรีดิเคตแบบฮาร์ดคอร์ของโกลด์ไรช์-เลวินจากฟังก์ชันทางเดียวสามารถมองได้ว่าเป็นอัลกอริธึมสำหรับการถอดรหัสแบบลิสต์ของรหัสฮาดามาร์ด )
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ เงื่อนไขสุดขั้ว
ใน การเข้ารหัสลับ เงื่อนไข หลัก (hard-core predicate ) ของ ฟังก์ชันทางเดียว f คือ เงื่อนไข b (กล่าวคือ ฟังก์ชันที่มีเอาต์พุตเป็นบิตเดียว) ซึ่งคำนวณได้ง่าย (เป็นฟังก์ชันของ x )...
ดูเพิ่มเติม
การถอดรหัสแบบลิสต์ (อธิบายการถอดรหัสแบบลิสต์ แก่นของการสร้างพรีดิเคตแบบฮาร์ดคอร์ของโกลด์ไรช์-เลวินจากฟังก์ชันทางเดียวสามารถมองได้ว่าเป็นอัลกอริธึมสำหรับการถอดรหัสแบบลิสต์ของ รหัสฮาดามาร์ด ) ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?