เราจะวัดระดับความปลอดภัยของอัลกอริทึมการเข้ารหัสหลังควอนตัมได้อย่างไร มีวิธีมาตรฐานในการวัดนี้หรือไม่?

เราจะวัดระดับความปลอดภัยของอัลกอริธึมการเข้ารหัสแบบโพสต์ควอนตัม เช่น: NTRU Prime, Saber, Kyber,... ที่ส่งไปยัง NIST PQC Standardization Process (Competition) โดยทั่วไปได้อย่างไร

ฉันอ่านเอกสารในแพ็คเกจการส่ง NIST ของ NTRU Prime แต่การทำความเข้าใจระดับความปลอดภัยนั้นดูซับซ้อนมากสำหรับอัลกอริทึม PQC ซึ่งแตกต่างจากที่ไม่ใช่ PQC ซึ่งเราสามารถเปรียบเทียบวิธีการง่ายๆ กับ AES-256 ได้ พวกเขาพูดคุยเกี่ยวกับการแปลงและ CCA, ระดับความปลอดภัย CPA ขึ้นอยู่กับพารามิเตอร์บางตัว แต่ดูเหมือนว่าจะซับซ้อนสำหรับฉัน

ใครสามารถอธิบายการวัดความปลอดภัยสำหรับอัลกอริทึม PQC โดยทั่วไปได้บ้าง

คำถามนี้ เกี่ยวข้องกับ. โปรดทราบว่าคำถามนี้ ทำ บอกว่าความปลอดภัยได้รับการวิเคราะห์โดยเปรียบเทียบกับ AES/SHA3 อย่างที่คุณสงสัย

บางทีวิธีที่ให้ข้อมูลมากที่สุดในการเรียนรู้เพิ่มเติมเกี่ยวกับเรื่องนี้คือการ "ลงมือทำ" และอ่านส่วนการวิเคราะห์ความปลอดภัยของผู้สมัคร NIST PQC รอบ 3 ต่างๆ สิ่งเหล่านี้ควรใกล้เคียงกับฉันทามติของชุมชนเกี่ยวกับวิธีวิเคราะห์โครงร่าง (แม้ว่าจะยังมีความขัดแย้งซึ่งมักจะกล่าวถึงในกลุ่ม Google NIST PQC) ตัวอย่างของความขัดแย้งบางอย่างเช่น:

• การปัดเศษ (เพื่อวัตถุประสงค์ในการบีบอัด) ปรับปรุงความปลอดภัยของ KEM แบบใช้ตาข่ายหรือไม่ ถ้าเป็นเช่นนั้นได้กี่บิต? (หรือโดยสิ่งที่ "CoreSVP นับ" ซึ่งเป็นเมตริกเฉพาะสำหรับการวิเคราะห์โครงร่างแบบตาข่าย)
• การนับ "CoreSVP" หมายความว่าอย่างไร
• การประมาณค่ามีความแม่นยำเพียงใด (จากการวิเคราะห์การเข้ารหัสของ "สัญญาณรบกวน" แบบพื้นฐานขัดแตะ) เมื่อนำไปใช้กับแบบดั้งเดิมแบบขัดแตะที่มีสัญญาณรบกวน "กำหนดขึ้น" เพียงอย่างเดียว (เกิดจากการปัดเศษ)
• วิธีจัดการกับการวิเคราะห์ต้นทุนหน่วยความจำของการโจมตีอย่างเหมาะสม เรื่องใหญ่ที่นี่คือความแตกต่างระหว่างหน่วยความจำควอนตัม (หมายถึงต้องใช้ qubits) กับหน่วยความจำคลาสสิกที่เข้าถึงควอนตัมได้ ซึ่งควรจะมีมากกว่านั้นมาก (ตัวอย่างเช่น $2^{30}$ หน่วยความจำแบบคลาสสิกในปัจจุบันค่อนข้างเป็นไปได้ แต่ฉันไม่เคยได้ยินเกี่ยวกับการประมาณการที่มั่นใจว่าเราควรคาดหวังเมื่อใด $2^{30}$ qubits แบบลอจิคัล --- ฉันไม่เชื่อว่าเราจะโดน หนึ่ง qubit เชิงตรรกะยัง!)
• วิธีจัดการการลดแบบไม่รัดกุมอย่างเหมาะสม? บ่อยครั้งที่การลด QROM นั้นเข้มงวดน้อยกว่าการลด ROMควรตั้งค่าพารามิเตอร์ให้หลวมกว่านี้เพื่อชดเชย หรือนี่เป็นสิ่งประดิษฐ์ของโมเดลที่ค่อนข้างใหม่

โดยทั่วไปแล้ว แม้ว่าจะมีความขัดแย้งอยู่บ้าง การวัดความปลอดภัยจะใกล้เคียงกับการวัดความปลอดภัยแบบดั้งเดิม (หมายถึงการเปรียบเทียบกับความปลอดภัยของ AES/SHA3) และสามารถพบได้ในข้อกำหนดต่างๆ ของการส่ง หากคุณอ่านมามากพอ คุณควรเข้าใจว่าชุมชนมี (ส่วนใหญ่) อย่างไรในการวิเคราะห์ความปลอดภัยของแผนการต่างๆ

คุณสามารถอ่าน google group ได้เช่นกัน แต่มันเป็นรูปแบบฟรีมากกว่าการส่ง ดังนั้นจึงอาจไม่ใช่แหล่งข้อมูลที่รวบรัดที่สุด เป็นมูลค่าการกล่าวขวัญว่าสามารถอ่านได้อย่างสนุกสนานโดยไม่คำนึงว่า เนื่องจากการโต้วาทีสามารถเคลื่อนไหวได้ค่อนข้างน้อย (ซึ่งอาจทำให้มีความหนาแน่นของข้อมูลน้อยกว่าการส่ง)

บ่อยครั้ง รูปแบบการเข้ารหัส (แบบอสมมาตร) สามารถพูดถึงในแง่ของความปลอดภัยที่พิสูจน์ได้ - เราสามารถแสดงได้ว่าโครงร่างมีความปลอดภัยภายใต้การโจมตีบางอย่าง หากรูปแบบการเข้ารหัสพื้นฐานนั้นยาก กล่าวอีกนัยหนึ่ง ความปลอดภัยที่พิสูจน์ได้นั้นขึ้นอยู่กับการลดปัญหาของเราให้เหลือเพียงปัญหาดั้งเดิม ตัวอย่างเช่น ปัญหา RSA สามารถลดลงได้เป็นปัญหาแฟคตอริ่ง

โดยทั่วไปจะกล่าวถึงคุณสมบัติสี่ประการต่อไปนี้ IND, CPA, CCA และ CCA2:

ดัชนี (แยกแยะไม่ได้): ฝ่ายตรงข้ามไม่สามารถแยกแยะการเข้ารหัสของข้อความสองข้อความที่มีความยาวเท่ากันได้ เช่น หากได้รับข้อความเข้ารหัสที่ท้าทาย $ค$พวกเขาไม่สามารถบอกได้ว่า $ค$ มาจาก $m_1$ หรือ $m_2$.

IND-CPA (แยกแยะไม่ออกภายใต้การโจมตีข้อความธรรมดาที่เลือก): ฝ่ายตรงข้ามไม่สามารถแยกได้ว่าข้อความใดถูกใช้เพื่อสร้างข้อความเข้ารหัสที่ท้าทายหากได้รับสิทธิ์เข้าถึงคีย์สาธารณะ (กล่าวคือ พวกเขาสามารถสร้างข้อความเข้ารหัสจากข้อความที่เลือก)

IND-CCA (แยกไม่ออกภายใต้การโจมตีแบบไซเฟอร์เท็กซ์ที่เลือก): ตั้งค่าเหมือนครั้งก่อน แต่คราวนี้ ศัตรูมีออราเคิลถอดรหัสที่พวกเขาสามารถสืบค้นได้จนกว่าจะได้รับโจทย์ไซเฟอร์เท็กซ์

IND-CCA2 (แยกแยะไม่ได้ภายใต้การโจมตีแบบเข้ารหัสที่เลือกปรับได้): เช่นเดียวกับตัวอย่างก่อนหน้านี้ อย่างไรก็ตาม ขณะนี้ฝ่ายตรงข้ามได้รับอนุญาตให้สอบถามการถอดรหัสออราเคิลแม้ว่าจะได้รับความท้าทายแล้วก็ตาม (มีข้อแม้ พวกเขาไม่ได้รับอนุญาตให้ป้อนข้อความเข้ารหัสท้าทายไปยังออราเคิล)

สิ่งเหล่านี้ถูกเลือกให้อภิปรายราวกับว่าเราสามารถพิสูจน์ได้ว่า (สมมติว่ามีการพิสูจน์ในบริบทที่เหมาะสม) เราเพียงแค่ต้องกังวลเกี่ยวกับความแข็งของปัญหาที่เป็นรากฐาน

คำจำกัดความของคุณสมบัติเหล่านี้อาจแตกต่างกันเล็กน้อยสำหรับโครงร่างสมมาตร (ไม่อิงจากปัญหาทางคณิตศาสตร์) แต่เราสามารถพิสูจน์ผลลัพธ์ที่คล้ายคลึงกันได้อีกครั้งภายใต้เงื่อนไขบางประการ (ลองนึกถึงความยาวของคีย์)

สิ่งนี้ช่วยให้เราสามารถประเมิน 'ระดับความปลอดภัย' สำหรับพารามิเตอร์เหล่านี้ในลักษณะที่สามารถแปลและเปรียบเทียบกับ AES ได้