Semantic Security อาจถูกกำหนดโดยใช้การทดสอบ/เกมแยกแยะความแตกต่าง ซึ่งเราจำได้ดังนี้:
อนุญาต $(จ,ด)$ เป็นแบบแผนการเข้ารหัส หลังจากผู้ท้าชิงเลือกพารามิเตอร์ความปลอดภัย $n$ และคีย์สุ่ม $k$, ศัตรู (ความปลอดภัยเชิงความหมาย) เลือกสองข้อความ $m_0, m_1$ ที่ขึ้นอยู่กับ $n$. ผู้ท้าชิงสุ่มเลือกหน่อย $b \ใน \{0,1\}$, จัดเตรียมให้ $E_k(m_b)$ ต่อฝ่ายตรงข้ามซึ่งจะต้องตัดสินใจว่า $ข$ เป็น $0$ หรือ $1$.
คำถาม: ข้อความ $m_0$ และ $m_1$ มีความยาวพหุนามในหน่วย $n$แต่เป็นฟังก์ชันที่คำนวณได้จริงของ $n$? นั่นคือฝ่ายตรงข้ามคำนวณหรือไม่ $m_0$ และ $m_1$ ใช้เครื่องทัวริงที่ทำงานในเวลาพหุนาม?
ฉันสงสัยว่าคำตอบคือไม่ ไม่สามารถคำนวณได้ (แต่ยังคงมีความยาวพหุนาม) ฉันตั้งฐานนี้จากการพยายามพิสูจน์คุณสมบัติของความปลอดภัยทางความหมาย เช่น ความเป็นไปไม่ได้ของการเดาบิตและการกู้คืนข้อความ เป็นต้น ฉันยังคิดว่าสิ่งนี้ระบุไว้อย่างชัดเจนในหนังสือของ Goldreich ที่ไม่มีการสร้างข้อความและระบุเฉพาะความยาวพหุนามเท่านั้น (แต่เขา ใช้ตระกูลวงจรแทนซึ่งฉันไม่คุ้นเคย) แต่ใน Katz-Lindell ดูเหมือนว่าจะมีความคลุมเครือในคำจำกัดความนี้