ในการแก้ไขคำตอบโดย ป่าผู้ใช้มีการกล่าวถึงว่ามีการโจมตีใหม่ที่พัฒนาขึ้นสำหรับการเข้ารหัสแบบตาข่ายฉันคิดว่าการเข้ารหัสแบบใช้แลตทิซเป็นวิธีที่ค่อนข้างดีในการให้การรักษาความปลอดภัยที่พิสูจน์ด้วยคอมพิวเตอร์ควอนตัม และสิ่งเดียวที่ต้องทำคือพัฒนาระบบมาตรฐานที่ NIST
แต่การโจมตีในปัจจุบันทำให้ฉันมีคำถาม: มีมติเป็นเอกฉันท์ในปัจจุบันว่าการเข้ารหัสแบบใช้ตาข่ายมีความปลอดภัยเพียงใด? นั่นคือเรามั่นใจแค่ไหนว่านี่เป็นทางเลือกที่สมเหตุสมผลสำหรับระบบ RSA ทั่วไปทั้งในวิธีการโจมตีแบบควอนตัมและแบบคลาสสิก
การโจมตีที่อ้างสิทธิ์นั้นไม่ได้ "ทำลาย" การเข้ารหัสแบบ lattice แต่เพียงปรับปรุงการโจมตีที่รู้จักให้ดียิ่งขึ้นเท่านั้น ฉันจะพยายามอธิบายสถานการณ์โดยย่อ
ซีมโทติค:
บ่งชี้ที่ดีที่สุดของเราคือ LWE ต้องใช้เวลา $2^{cn}$ เพื่อแก้ปัญหาค่าคงที่ $ค$. สิ่งนี้จะต้องตรงกันข้ามกับ RSA $2^{(\log N)^{1/3}}$ (สิ่งนี้ไม่ชัดเจนมากและควรใช้อย่างเหมาะสม L-สัญกรณ์) และ DLog เส้นโค้งวงรี $2^{\frac{1}{2}\log_2|\mathbb{G}|}$. กล่าวคือ แม้ว่าจะมีการปรับปรุงเพื่อโจมตีรูปแบบต่างๆ ของ LWE แต่เราเชื่อว่าจะมี "การปรับขนาดที่ดีกว่า" กว่าสมมติฐานเช่น RSA (ซึ่งคุณกล่าวถึงโดยเฉพาะ) แม้ว่าจะคล้ายกับ ECDlog ก็ตาม
ประมาณการปัจจุบันของ $ค$ อาจแตกต่างกันไป แต่ก็เป็น $< 1/2$ (ฉันเชื่อว่าบางที $\ประมาณ 0.28$ เป็นปัจจุบัน แต่ยังไม่ได้ตรวจสอบ) ดังนั้น ECDlog จึงดีที่สุดสำหรับเมตริกนี้ จากนั้น LWE และจากนั้น (ไกลออกไป) RSA/เขตข้อมูลจำกัด DH ยังไม่ชัดเจนว่าแนวคิดนี้มีประโยชน์อย่างไรในทางปฏิบัติ --- มันพูดอย่างนั้น บาง ชุดพารามิเตอร์อาจปลอดภัย แต่ไม่ได้ช่วยเลือกชุดใด
อย่างเป็นรูปธรรม:
แม้ว่า LWE ทำ เอา $2^{cn}$ เวลาจะแก้ปัญหานี้ไม่ได้ช่วยเราถ้าเราไม่รู้ $ค$. การโจมตีที่ได้รับการปรับปรุงมีการปรับปรุง (ในทางทฤษฎี) $ค$ ล่วงเวลา. สิ่งนี้สามารถนำไปสู่ชุดพารามิเตอร์ต่างๆ ที่ "เสียหาย" (แม้ว่าจะไม่ใช่ในแง่ที่ว่าเราสามารถโจมตีพวกมันในเชิงปฏิบัติได้ --- ในแง่ที่ว่าพวกมันไม่ตรงตามมาตรฐานขั้นต่ำของ NIST ที่จะอยู่ใน "ระดับความปลอดภัย" ที่แน่นอน)
สถานการณ์นี้เป็นเนื้อหา ดีกว่า กว่าสถานการณ์ที่แฟคเตอริงประสบกับการพัฒนาเทคนิค "แคลคูลัสดัชนี" สำหรับ ECDlog การโจมตีที่ดีที่สุดยังคงเป็น (รูปแบบต่างๆ ของ) อัลกอริทึม Pollard Rho และเป็นเช่นนี้สำหรับ ยาว เวลา.
ทั้งหมดนี้เป็นการบอกว่า ECDlog มีความปลอดภัยที่เข้าใจได้ดีที่สุด แม้ว่าฉันจะบอกว่า LWE ยังคงเอาชนะ RSA/สิ่งอื่นๆ ที่เสี่ยงต่อเทคนิคแคลคูลัสดัชนี แม้ว่า NFS ถูกสร้างขึ้นเมื่อประมาณ 30 ปีที่แล้ว แต่ก็ยังมีความเป็นไปได้ที่จะมีการปรับปรุง ตัวอย่างเช่น เส้นทางของ DLog ฟิลด์จำกัด (ลักษณะเฉพาะขนาดเล็ก) มาจากความซับซ้อนโดยประมาณเช่นเดียวกับ RSA ไปจนถึง (คร่าวๆ) $2^{(\log p^n)^{1/4}}$แล้วจึงเป็นเวลากึ่งพหุนาม (cf นาเดีย เฮนนิงเกอร์ โดย Matthew Green). นี่ไม่ได้หมายความว่าสิ่งที่คล้ายกันจะเกิดขึ้นกับแฟคเตอริง (ไม่ใช่เป็นเวลาประมาณ 30 ปี) แต่อาจยังมีความเป็นไปได้ที่ไม่สบายใจ
ในทางปฏิบัติ:
วิธีสุดท้ายในการทำความเข้าใจความปลอดภัยของสมมติฐานความแข็งคือการแก้อินสแตนซ์ที่ใหญ่มากของมัน สิ่งนี้นำไปสู่คำถาม
สำหรับ RSA สิ่งต่าง ๆ เช่น RSA-240 (เซมิไพรม์ 768 บิต) ถูกทำลายใน 1,000 ปีแกนหลัก (หรือ 6 เดือนผนัง iirc) ในแง่นี้ RSA (และ DH เขตข้อมูลจำกัดสำหรับคุณลักษณะที่ไม่ใช่ขนาดเล็ก) คือสมมติฐานความแข็งที่ผ่านการทดสอบที่ดีที่สุดของเรา (และอาจเข้าใจได้ดีที่สุด) เส้นโค้งวงรีมีการคำนวณที่ยาวนานเช่นกัน เดอะ หน้าบันทึก แสดงรายการตัวแบ่งจำนวนหนึ่งในช่วงของกลุ่มขนาด $2^{110}$ ถึง $2^{120}$, และเวลานาฬิกาแขวนอยู่ที่สูงสุด 6 เดือนอีกครั้งในระดับไฮเอนด์
ในตัวชี้วัดนี้ LWE ล้าหลังจริงๆ มี "ความท้าทายขัดแตะ" ที่รู้จักกันดี (ลา ความท้าทายของ RSA) ตัวอย่างเช่น ความท้าทายของ TU Darmstadt. สิ่งเหล่านี้มีไว้สำหรับ LWE ธรรมดา (Peikert สร้างขึ้นสำหรับ ร.ลแต่ฉันไม่เห็นลีดเดอร์บอร์ดสาธารณะสำหรับพวกเขา) อย่างไรก็ตาม สำหรับการท้าทาย LWE ธรรมดา มิติสูงสุดที่ทุกคนเคยไขได้คือ 85 ในขณะที่มิติ 500+ (แม้ว่า 700+ จะธรรมดากว่า) จะใช้ในรูปแบบเชิงปฏิบัติ บันทึกทั้งหมดที่ฉันดูใช้เวลาน้อยกว่า 200 ชั่วโมง (โดยปกติจะใช้โปรเซสเซอร์จำนวนหนึ่ง) ดังนั้นการคำนวณจึงเป็นจริง มาก สเกลเล็กกว่าการคำนวณ RSA/ECDlog
กล่าวได้ว่า "การโจมตีครั้งใหญ่" ต่อ LWE นั้นมีขนาดเล็กกว่าการโจมตี RSA/ECDlog ที่คล้ายคลึงกันเป็นอย่างน้อย แม้ว่าสิ่งนี้จะลดขนาดการโจมตีทางวิชาการสมัยใหม่ต่อ RSA ลงอย่างมาก ดังนั้นทั้งตัวอย่างที่ใหญ่ที่สุดของ LWE ที่ถูกทำลายจึงมีขนาดเล็ก (ซึ่งเป็นตัวบ่งชี้ความปลอดภัยที่ดี) และยังไม่มี "การโจมตีครั้งใหญ่อย่างแท้จริง" ติดตั้งอยู่ (ซึ่งเป็นสิ่งที่ไม่ดี)
ข้างต้นไม่สนใจรายละเอียดปลีกย่อยมากมายเกี่ยวกับสมมติฐานความแข็ง เช่น
LWE ทำงานได้ดีกับเมตริกเหล่านี้ทั้งหมด (ตราบใดที่คุณไม่ได้ทำลายเซ็น) ดีกว่า RSA อย่างแน่นอน ฉันไม่รู้จัก ECDlog เป็นการส่วนตัว
จากที่กล่าวมาทั้งหมด ฉันมองว่า LWE เป็นการส่วนตัว
แน่นอนว่าหากคอมพิวเตอร์ควอนตัมไม่เสี่ยง ก็ไม่มีเหตุผลใดที่จะต้องเลิกใช้ ECDlog (ยกเว้นสำหรับแอปพลิเคชันพิเศษอย่าง FHE) แต่พวกเขาเป็นดังนั้นเราต้อง
จากมุมมองนี้ การเปรียบเทียบไม่ควรเป็นระหว่าง LWE และ RSA/ECDlog เนื่องจากน่าเสียดายที่โลกของพวกเขาสมเหตุสมผลกำลังจากเราไปอย่างรวดเร็ว การเปรียบเทียบควรเป็นสมมติฐานหลังควอนตัมอื่นแทน แต่จากสมมติฐานหลังควอนตัม LWE อยู่ในจุดสูงสุดจริงๆ มีสมมติฐานที่มีการรักษาความปลอดภัยที่ดีกว่า (เช่น McEliece) แต่ประสิทธิภาพไม่ดีเกินกว่าจะใช้งานได้ ยกเว้นกรณีพิเศษ สมมติฐานหลักที่เป็นไปได้อื่นๆ ได้แก่
SIDH เองยังคงเป็นลำดับความสำคัญที่ช้ากว่าโครงสร้างแบบขัดแตะ iirc (แม้ว่าจะมีขนาดกะทัดรัดกว่าก็ตาม) มีเหตุผลบางประการที่จะโต้แย้งว่าความปลอดภัยนั้น "ยืนหยัดในการทดสอบของเวลาได้ดีกว่า" มากกว่าสมมติฐานที่อิงตามโครงตาข่าย (cf กรณีสำหรับ SIKE) แต่ก็มี iirc เพียง ~ 10 ปี ดังนั้นตัวมันเองยังคงเป็นข้อสันนิษฐานใหม่ (และยิ่งกว่านั้นในปี 2559 เมื่อ NIST เริ่มกระบวนการคัดเลือก) นอกจากนี้ยังค่อนข้างซับซ้อนทางคณิตศาสตร์ ซึ่งอาจทำให้การใช้งานยาก (แต่ฉันยังไม่ได้ลอง)
เรื่องนี้ค่อนข้างยาว (และไม่สนใจหัวข้อทางเทคนิคมากมาย เช่น ความแข็งของ LWR "โมดูลาขนาดเล็ก" หรือการอ้างสิทธิ์เกี่ยวกับผลกระทบของขนาดกลุ่ม galois ต่อความแข็ง RLWE ซึ่งไม่ได้รับการแก้ไขมานานหลายปี นี่เป็นหัวข้อที่ดูเหมือนว่าเป็นไปได้มากที่สุดสำหรับ "ช่วงพักใหญ่" แต่ก็ยังไม่มีอะไรเกิดขึ้น) แต่ฉันหวังว่าจะเริ่มตอบคำถามของคุณอย่างน้อย
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
