วิธีการ/กระบวนการทั่วไปในการสร้างระบบเข้ารหัสตามปัญหาการตัดสินใจ

สมมติว่าฉันได้รับปัญหาการตัดสินใจ (DP) ซึ่งพิสูจน์แล้วว่าเป็น NP-hard มีวิธีการ/กระบวนการทั่วไปในการสร้างระบบเข้ารหัสตาม DP หรือไม่

ขอบคุณ.

ไม่ ไม่ใช่แค่ไม่มี ทั่วไป วิธีสร้างระบบเข้ารหัสตามปัญหาการตัดสินใจ ไม่มีปัญหาการตัดสินใจเดียวที่ทราบ:

1. เป็น NP-Complete และ
2. เราสามารถสร้างการเข้ารหัสได้จาก

"การเข้ารหัสใด ๆ " อาจดูค่อนข้างคลุมเครือ แต่สามารถระบุได้ค่อนข้างง่าย --- คีย์พื้นฐานแบบสมมาตรส่วนใหญ่ (ฟังก์ชันทางเดียว ฟังก์ชันหลอก/เครื่องกำเนิด และฟังก์ชันที่คาดเดาไม่ได้) เป็นที่รู้กัน เทียบเท่าในแง่ที่ว่าถ้าคุณมีหนึ่ง (เช่น OWF) คุณสามารถสร้างสิ่งอื่นได้อย่างง่ายดาย และในทางกลับกัน

เหตุใดจึงไม่มีการสร้างการเข้ารหัสจากสมมติฐานนี้ เหตุผลพื้นฐานคือ "ทฤษฎีบทเล็กน้อย" ที่:

หากมีความปลอดภัย (OWF/PRG/PRF/UF) อยู่แล้ว $P\neq NP$

นี่เป็นเพราะสำหรับความคิดที่สมเหตุสมผลเกี่ยวกับ "ความปลอดภัย" ปัญหาของการทำลาย OWF/PRG/PRF/UF คือ:

• ได้อย่างง่ายดายใน NP ("เดา" รหัสลับ จากนั้นอะไรก็ตามที่แนวคิดด้านความปลอดภัยเป็นเรื่องเล็กน้อย)
• ไม่อยู่ใน P (ไม่เช่นนั้น ศัตรูที่เก่งสามารถทำลายมันได้ ดังนั้นมันจะไม่ "ปลอดภัย")

นอกจากนั้นยังมีคำถาม (ที่เกี่ยวข้อง) ของ

ฉันจะใช้ความรู้เรื่องปัญหาหนักๆ เพื่อสร้างการเข้ารหัสได้อย่างไร

คำตอบค่อนข้างซับซ้อน หากคุณสามารถสร้างมาตรฐานการเข้ารหัสแบบดั้งเดิม (a PRG/PRF/OWF/UF หรือ OWF ประตูกล) สิ่งต่างๆ จะกลายเป็นเรื่องง่ายอย่างรวดเร็ว ยิ่งไปกว่านั้น ฉันจะชี้ให้เห็นว่าถ้าคุณสามารถสร้าง "สิ่งดั้งเดิมมาตรฐาน" ที่เป็น "โฮโมมอร์ฟิก" สิ่งต่าง ๆ ก็ค่อนข้างตรงไปตรงมาเช่นกัน. แต่เรื่องราวทั่วไปยังคงดำเนินต่อไป --- การเข้ารหัสแบบใช้ตาข่ายได้รับการเสนอครั้งแรกเมื่อประมาณ 25 ปีที่แล้ว แต่ใช้เวลาประมาณหนึ่งทศวรรษที่ผ่านมาในการพัฒนาลายเซ็นแบบใช้ตาข่าย นี่คือการบอกว่าการรู้วิธีพัฒนาการเข้ารหัส (คีย์สาธารณะ) ไม่ได้นำไปสู่การสร้างลายเซ็น "ฟรี" (แม้ว่า PKE จะเป็น "การสร้างแบบดั้งเดิมที่ยากกว่า" ในความหมายที่เป็นทางการบางอย่าง)

มีความคืบหน้าบางอย่างในการทำความเข้าใจว่าสิ่งก่อสร้างทั่วไปได้รับจากการสร้างสิ่งดั้งเดิมบางอย่าง (นี่คือสิ่งที่บทความที่ฉันเชื่อมโยงทำ) แต่ทั้งหมดนี้ค่อนข้างใหม่