ใน อัลกอริทึมควอนตัมที่มีประสิทธิภาพสำหรับปัญหาแลตทิซเพื่อให้ได้ปัจจัยการประมาณแบบซับเอ็กซ์โพเนนเชียลผู้เขียนอ้างว่าพวกเขาให้อัลกอริธึมควอนตัมพหุนาม-เวลาสำหรับการแก้ปัญหาการถอดรหัสระยะทางที่มีขอบเขตด้วยปัจจัยการประมาณแบบเลขชี้กำลังย่อยในคลาสของจำนวนเต็ม ผลลัพธ์นี้หมายความว่าอย่างไร มันจะบ่งบอกถึงความไม่ปลอดภัยของการเข้ารหัสขัดแตะหรือไม่? มันสำคัญเท่ากับ อัลกอริทึมควอนตัมสำหรับการแยกตัวประกอบ โดย ปีเตอร์ ชอร์?
ยังไม่มีกระดาษสาธารณะให้บริการ ดังนั้นคำตอบนี้เป็นข้อมูลเบื้องต้นและขึ้นอยู่กับสิ่งที่นำเสนอในการพูดคุยและการอภิปรายติดตามผล ไม่สามารถเข้าถึงความเข้าใจทั้งหมดได้จนกว่าจะมีเอกสารเพื่อตรวจสอบ ประเมิน และเปรียบเทียบกับงานก่อนหน้าและผลลัพธ์ที่ทราบ อย่างไรก็ตาม ความเข้าใจที่ดีเกี่ยวกับสถานการณ์ดูเหมือนจะเกิดขึ้นแล้ว
tl;dr คือ: ปัญหาพิเศษที่ผู้เขียนกล่าวถึงคือ คลาสสิก ง่ายต่อการแก้ไขโดยใช้อัลกอริธึมขัดแตะมาตรฐาน (ไม่จำเป็นต้องใช้ควอนตัม) ดังที่แสดง ในบันทึกนี้. ยิ่งไปกว่านั้น ขั้นตอนควอนตัมแกนใหม่สามารถนำไปใช้แบบคลาสสิกแทนได้ (และง่ายกว่าและมีประสิทธิภาพมาก) เช่นกัน ดังนั้น งานจึงไม่ได้แสดงให้เห็นถึงความได้เปรียบเชิงควอนตัมเมื่อเทียบกับสิ่งที่เรารู้อยู่แล้วว่าต้องทำอย่างไรในแบบคลาสสิก หรือไม่มีอะไรใหม่เกี่ยวกับสิ่งที่เราสามารถทำได้แบบคลาสสิก รายละเอียดตามนี้
ประโยค âในคลาสของจำนวนเต็ม latticesâ เป็นตัวระบุที่สำคัญมาก ปัญหา BDD ที่ผู้เขียนกล่าวถึงคือปัญหาที่โครงตาข่ายคือ â$คิว$-aryâ และสร้างโดยคนเดียว $n$-มิติ mod-$คิว$ เวกเตอร์ (หรือจำนวนเล็กน้อย), โมดูลัส $q \gg 2^{\sqrt{n}}$และเวกเตอร์เป้าหมายอยู่ภายใน a $\ll 2^{-\sqrt{n}}$ ปัจจัยระยะทางขั้นต่ำของตาข่าย การตั้งค่านี้ห่างไกลจากสิ่งที่เคยใช้ในการเข้ารหัสแบบแลตทิซ (ตามความรู้ของฉัน) ดังนั้นผลลัพธ์จะไม่ส่งผลโดยตรงต่อระบบแลตทิซที่เสนอ แน่นอนว่าคำถามที่กว้างกว่านั้นก็คือว่าเทคนิคดังกล่าวสามารถนำไปสู่ผลลัพธ์ที่ดีกว่าซึ่งส่งผลต่อ lattice crypto หรือไม่
จากคำอธิบายที่ให้ไว้ในการพูดคุย ผู้เข้าร่วมผู้เชี่ยวชาญหลายคนเชื่อว่าเป็นไปได้มากที่ปัญหาโครงตาข่ายพิเศษที่ผู้เขียนกล่าวถึงนั้นสามารถแก้ไขได้อย่างง่ายดายโดยใช้ที่รู้จัก คลาสสิก เทคนิค (ไม่จำเป็นต้องใช้ควอนตัม) อัปเดต: สิ่งนี้กลายเป็นกรณีและได้รับการพิสูจน์ใน บันทึกนี้. กล่าวอีกนัยหนึ่ง รูปแบบเฉพาะของปัญหา BDD ทำให้ง่ายต่อการแก้ไขด้วยวิธีที่เป็นที่รู้จักและไม่น่าแปลกใจ อัลกอริทึมเป็นเพียงลำดับมาตรฐานของการลดพื้นฐาน LLL ตามด้วยการถอดรหัสระนาบที่ใกล้ที่สุดของ Babai แต่แสดงให้เห็นว่าสิ่งนี้ใช้งานได้จริงโดยอาศัยคุณสมบัติของ LLL ที่ลึกกว่า (แต่เคยรู้จักมาก่อน) มากกว่าคุณสมบัติที่มักจะเรียกใช้
แล้วคำถามที่กว้างขึ้น: เทคนิคหลักสามารถนำไปสู่ผลลัพธ์ที่ดีกว่าที่เราไม่สามารถได้รับในปัจจุบันได้หรือไม่ ปรากฎว่าสิ่งที่ขั้นตอนควอนตัมแกนกลางทำได้สำเร็จ การแปลง "ตัวพิมพ์เล็ก-ตัวพิมพ์ใหญ่ที่สุดเป็นตัวพิมพ์ใหญ่-เล็ก" สามารถทำได้ คลาสสิก (และเรียบง่ายและมีประสิทธิภาพมากขึ้น) โดยใช้เทคนิคการสุ่มที่รู้จักกันเป็นอย่างดีซึ่งเรียกว่า âLWE self reductionâ หรือ â($คิว$-ary) การลด BDD เป็น LWEâ ดูส่วนที่ 5 และทฤษฎีบท 5.3 ของ กระดาษแผ่นนี้ และงานก่อนหน้านี้ที่อ้างถึงในรายละเอียด
อย่างแม่นยำมากขึ้น, $n$มิติ $คิว$-ary BDD สำหรับระยะทางสัมพัทธ์ $\alpha$ (ปัญหาที่ผู้เขียนพิจารณา) ลดระดับเป็น LWE แบบคลาสสิกด้วยอัตราข้อผิดพลาด $\alpha \cdot O(\sqrt{n})$. แม้ว่าการลดลงนี้จะดูไม่จำเป็นในการแก้ปัญหา BDD ดั้งเดิมที่เป็นปัญหา แต่ก็แสดงให้เห็นว่าขั้นตอนควอนตัมแกนใหม่สามารถถูกแทนที่ด้วยบางสิ่งแบบดั้งเดิมที่มีประสิทธิภาพอย่างน้อยเช่นกัน (และน่าจะดีกว่าในแง่ของพารามิเตอร์) สิ่งนี้บ่งชี้ว่าเทคนิคควอนตัมหลักอาจไม่มีความแปลกใหม่หรือพลังที่น่าประหลาดใจในบริบทนี้
ฉันสร้างเว็บไซต์เพื่อรวบรวมสิ่งที่ทราบเกี่ยวกับอัลกอริทึมสำหรับปัญหาขัดแตะใน NP ตัดกัน ConNP:
กระดาษของเราหมด:
https://arxiv.org/abs/2201.13450
สำหรับบันทึก นี่คือไทม์ไลน์ที่เราติดตาม:
จนถึงวันที่ 17/8/21 เราได้ศึกษาวรรณกรรมคลาสสิกอย่างถี่ถ้วน อัลกอริทึมแบบคลาสสิกก็ใช้ได้เหมือนกัน เพื่อที่เราจะป้อนกลับเข้าไปในอัลกอริทึมควอนตัมได้ แต่เนื่องจากกรณีฐานเป็นประเภทกรณีที่เลวร้ายที่สุดของปัญหาจำนวนที่ซ่อนอยู่ซึ่งได้รับการศึกษาเป็นอย่างดี จึงดูสมเหตุสมผลที่ไม่มีอะไรเป็นที่รู้จัก
17/8/21-9/21/21: เราสอบถามผู้เชี่ยวชาญ 5 คนตามลำดับเกี่ยวกับปัญหาที่ทราบ ในกรณีหนึ่ง เราได้ระบุแนวทางดั้งเดิมที่ดีที่สุดเท่าที่เราจะหาได้ เราไม่ได้รับคำตอบเกี่ยวกับข้อมูลใหม่
21/9/21: มีการตัดสินใจเลือกกรณีฐานพิเศษที่มีเวกเตอร์ 1 ตัวในการพูดคุย เพราะ (1) จะช่วยผู้คนในการแก้ปัญหา และ (2) เป็นการพูดคุยแบบ colloquium ในการสัมมนาควอนตัม ดังนั้นจึงจำเป็นต้อง เพื่อให้เข้าถึงคนในวงกว้างได้ การพูดคุยโดยใช้เพียงแลตทิซหรือควอนตัมอย่างเดียวก็เป็นเรื่องที่ท้าทายแล้ว และลองรวมทั้งสองอย่างเข้าด้วยกัน! 21/9/21: การอภิปรายที่มีชีวิตชีวาเกี่ยวกับความเป็นไปได้ระหว่างการอภิปราย แต่ไม่มีอัลกอริทึม
22/9/22: เราได้รับการติดต่อเกี่ยวกับอัลกอริทึมแบบคลาสสิกใหม่สำหรับกรณีพิเศษ และหลังจากที่เราชี้แจงอย่างชัดเจนว่าอัลกอริทึมของเราสามารถทำอะไรได้บ้าง การแก้ไขจะสรุปวิธีการรับกรณีทั่วไปมากขึ้นโดยการวิเคราะห์ LLL
1/31/22: ยังไม่ได้รับคำตอบคลาสสิกสำหรับขอบเขต Schnorr ของเรา
ฌอน
อาจให้คำตอบที่ยาวกว่านี้มากสำหรับคำถามนี้ (และฉันค่อนข้างสนใจที่จะเห็นคนอย่างมุมมองของคริส) แต่สองประเด็นต่อไปนี้อาจเพียงพอสำหรับผู้ที่ไม่ใช่ผู้เชี่ยวชาญ
ปัจจัยประมาณ: แนวทางหลักที่การโจมตีนี้ควรถูกมองว่า (อาจ) คุกคามต่อการเข้ารหัสแบบตาข่ายคือผ่านความเป็นไปได้ของการปรับปรุงในอนาคต ปัจจัยการประมาณเป้าหมายนี้ (ซึ่งฉันเชื่อว่าเป็น $2^{n^{1/2}}$) มีขนาดใหญ่พอที่แม้ว่า LWE จะเป็นก็ตาม คลาสสิก อ่อนแอในช่วงนี้ เรายังคงสามารถสร้างสิ่งต่าง ๆ เช่น:
เช่น. สิ่งที่คุณอาจสนใจส่วนใหญ่จะยังคงอยู่ ดังนั้นการโจมตีในปัจจุบันจึงไม่ส่งผลกระทบต่อเนื้อหาหลักของการเข้ารหัสแบบตาข่าย "เชิงปฏิบัติ" แม้ว่าการปรับปรุงการโจมตีในอนาคตจะเป็นไปได้ก็ตาม
ความเป็นไปได้ของการลดจำนวน: การโจมตีมีสองส่วน:
ผู้คนจำนวนหนึ่งเสนอแนะความเป็นไปได้ในการลดปริมาณขั้นตอนแรก โดยทำสิ่งต่าง ๆ เช่น การผสมเชิงเส้นแบบสุ่ม (พูดโดยใช้ค่าสัมประสิทธิ์เกาส์เซียน) ของเวกเตอร์พื้นฐาน หากการลดขนาดนี้ได้ผล ผู้ใช้จะได้รับ BDD พร้อมค่าประมาณ $2^{n^{1/2}}$ ในเวลาพหุนาม (ฉันเชื่อ)
ขณะนี้จะทำให้อัลกอริทึมของตัวเอง แข็งแกร่งขึ้นมันจะทำให้ความกังวลน้อยลงในแง่หนึ่ง นี่เป็นเพราะเรา (แบบคลาสสิก) มีความคิดที่ดีพอสมควรว่าปัญหาขัดแตะยากแค่ไหน ด้วยเหตุนี้ ฉันจึงนึกถึงสิ่งต่างๆ เช่น:
แน่นอนว่าสิ่งเหล่านี้ไม่ได้ตัดทอนการโจมตีที่เป็นไปได้ทั้งหมด แต่ควรได้รับการกล่าวถึงในฐานะหลักฐานอย่างเป็นทางการที่เพิ่มขึ้นสำหรับความแข็งแบบคลาสสิกของปัญหาขัดแตะ นี่คือการบอกว่าสิ่งสำคัญที่เกี่ยวข้องกับการพูดคุยที่เชื่อมโยงคือการมีอยู่ของ การเร่งความเร็วควอนตัมที่ไม่สำคัญ --- หากเป็น dequantized เราจะกลับมาสู่การตั้งค่าของการคำนวณแบบคลาสสิก ซึ่งความเข้าใจของเราเกี่ยวกับความแข็งของปัญหาแลตทิซจะดีกว่า
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
