Score:1

อัลกอริทึมของ Shor สามารถพิจารณาฟิลด์ / วงแหวน / กลุ่มที่ จำกัด ได้หรือไม่?

ธง dz

อัลกอริทึมของ Shor สามารถแก้สมการของแบบฟอร์มได้อย่างมีประสิทธิภาพ:

$$n = pq$$

และ

$$n = x^{2} + y^{2}$$

คำถามนี้ง่าย: อัลกอริทึมของ Shor สามารถแก้สมการเหล่านี้ในเวลาพหุนามได้หรือไม่ เมื่อดำเนินการด้วยเลขคณิตจำกัดแทนจำนวนเต็ม เช่น.

$$n = pq \bmod k$$

และ

$$n = x^{2} + y^{2} \bmod k$$

ขนาดของข้อกำหนด

อย่างน้อยก็ในกรณีการแยกตัวประกอบถ้า $\log_{2}(p) = \log_{2}(q) = \log_{2}(k)$ ดังนั้นการแก้สมการจึงเป็นไปไม่ได้ในทางทฤษฎีด้วยข้อมูล เนื่องจากโดยพื้นฐานแล้วเป็นการแก้สมการเพียงครั้งเดียวดังนั้นสำหรับจุดประสงค์ของคำถามนี้ สมมติว่า $\log_{2}(p) <= \log_{2}(q) < \log_{2}(k)$. ฉันไม่ชัดเจนในทันทีว่าปัญหานี้ใช้กับผลรวมของสองกรณีกำลังสองด้วยหรือไม่ ข้อจำกัดที่คล้ายกันนี้อาจถูกวางไว้บนเงื่อนไขหากจำเป็น เพื่อป้องกันความเป็นไปไม่ได้เล็กน้อยในการแก้ปัญหา

ลักษณะของข้อกำหนด

แฟคตอริ่งแบบดั้งเดิมจะสันนิษฐานว่าเกี่ยวกับเซมิไพรม์ ไม่ลักษณะของ $p, q$ (และ/หรือ $x, y$) สร้างความแตกต่างในบริบทนี้หรือไม่ เช่นเดียวกับใน, มันสำคัญถ้า $p, q, x, y$ เป็นจำนวนเฉพาะหรือหากเป็นไปตามความสอดคล้องกันบางอย่าง (เช่น $x = 1 \bmod 4$)? เงื่อนไขเหล่านี้มีความสำคัญต่อจำนวนเต็ม เงื่อนไขเหล่านั้นยังมีความสำคัญกับเลขคณิตจำกัดหรือไม่

poncho avatar
my flag
มันง่ายที่จะหาทางออก โดยกำหนด $n, p$, ถึง $n \equiv xy \pmod p$ - เลือก $x$ r.p ตามอำเภอใจ เป็น $p$ และคำนวณ $y = x^{-1} \bmod p$ - นั่นคือวิธีแก้ปัญหา - ไม่จำเป็นต้องใช้ Quantum Computer...
dz flag
@poncho ในขณะที่ฉันเห็น แต่ก็ไม่ชัดเจนว่าความสามารถในการเลือกวิธีแก้ปัญหาใด ๆ จะช่วยแก้ปัญหาการเข้ารหัสได้จริง: เช่น สำหรับแป้นแบบครั้งเดียว เราสามารถเลือกคู่คำศัพท์ใดก็ได้และนับเป็นวิธีแก้ปัญหาที่ถูกต้อง แต่นั่นไม่ได้ช่วยให้ใครบางคนเรียนรู้ข้อความของคุณจริงหรือ โดยพื้นฐานแล้วดูเหมือนว่าฟีเจอร์นั้นจะไม่ *จำเป็น* เป็นบั๊กใช่ไหม เว้นแต่ฉันจะพลาดอะไรไป?
poncho avatar
my flag
โดยปกติแล้วใน crypto จะมีข้อมูลเพียงพอในการตรวจสอบโซลูชัน (ข้อยกเว้นคือ OTP เช่นเดียวกับการแชร์แบบลับ) ถ้า $n \equiv xy \pmod p$ ให้ข้อมูลไม่เพียงพอที่จะได้คำตอบที่ถูกต้อง แสดงว่าน่าจะมีข้อมูลอื่นอยู่...
dz flag
น่าเสียดายเนื่องจากเงื่อนไขการใช้งานของไซต์นี้ ฉันจำเป็นต้องถามคำถามของฉันในลักษณะที่อ้อมค้อมและทั่วๆ ไป แทนที่จะนำเสนอสิ่งที่ฉันมีและคำถามเฉพาะเจาะจงใดๆ เกี่ยวกับไซต์นี้ ฉันไม่รู้ว่าจะเรียบเรียงคำถามของฉันในลักษณะที่ยอมรับได้อย่างไรที่จะไม่ถูกปิดโหวต
Score:0
ธง ng

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

เป็นหมายเหตุด่วนเกี่ยวกับความคิดเห็น

อย่างน้อยก็ในกรณีการแยกตัวประกอบถ้า $\log_2(p)=\log_2(q)=\log_2(k)$ ดังนั้นการแก้สมการจึงเป็นไปไม่ได้ในทางทฤษฎีด้วยข้อมูล เนื่องจากโดยพื้นฐานแล้วเป็นการแก้สมการเพียงครั้งเดียว

โดยทั่วไป วิธีการจัดการคือการบอกว่าฝ่ายตรงข้ามชนะหากพวกเขาฟื้นตัว ใดๆ วิธีการแก้ปัญหา $x^2+y^2\bmod k$แทนที่จะเป็นโซลูชันเฉพาะบางอย่าง สิ่งนี้สามารถเห็นได้ในสิ่งต่าง ๆ เช่น

  1. เกมกู้คืนคีย์ที่สอดคล้องกัน (ไม่ใช่เกมกู้คืนคีย์เป้าหมาย) และ
  2. ฟังก์ชันแบบทางเดียวจำเป็นต้องกู้คืนภาพล่วงหน้าใด ๆ ของ $y$, เช่น. ใดๆ $x$ ดังนั้น $f(x) = y$แทนที่จะ "แน่นอน" บางอย่าง $x'$ ที่เลือกไว้ภายในระหว่างเกม

ฉันจะอธิบายสิ่งต่าง ๆ ในเงื่อนไขเหล่านี้เนื่องจากเป็นมาตรฐาน หากไม่เหมาะกับใบสมัครของคุณ คุณอาจลองอธิบายใบสมัครของคุณเพิ่มเติม

คำถามนี้ง่าย: อัลกอริทึมของ Shor สามารถแก้สมการเหล่านี้ในเวลาพหุนามได้หรือไม่ เมื่อดำเนินการด้วยเลขคณิตจำกัดแทนจำนวนเต็ม

ความเข้าใจของฉันคืออัลกอริทึมของ Shor ถูกอธิบายไปแล้ว $\mathbb{Z}$ ค่อนข้างมากกว่า $\mathbb{Z}_n$ ไม่ใช่ปัญหาร้ายแรงในการใช้งาน "ในโลกแห่งความเป็นจริง" โดยเฉพาะอย่างยิ่ง ในขณะที่เราต้องระวังว่าการแทนค่าที่มีความแม่นยำจำกัดนั้นไม่ "สูญเสีย" เกินไป แต่ความเข้าใจของฉันคือรายละเอียดเหล่านี้หาได้ง่ายกว่าการสร้างคอมพิวเตอร์ควอนตัม

หากความเข้าใจนี้ถูกต้อง คำตอบของคำถามทั้งสองนี้เป็นเรื่องเล็กน้อย --- แก้สมการต่างๆ $\mathbb{Z}$แล้วลดคำตอบลง $\bmod k$ เพื่อรับแนวทางแก้ไข $\mathbb{Z}_k$. ดังที่ปอนโชชี้ให้เห็นในความคิดเห็น ปัญหาในการแก้ไข $n = xy\bmod k$ สำหรับ $x, y$ เท่ากัน คลาสสิก ง่าย ดังนั้น คุณธรรมของเรื่องราวก็คือ การกำหนดข้อจำกัดแบบโมดูลาร์จะทำให้ปัญหา (อาจจะ) ง่ายขึ้นอย่างมาก แต่สำหรับปัญหาเหล่านี้ มันไม่ได้ทำให้ปัญหายากขึ้น

มีการขยายเล็กน้อยของการแก้ปัญหาสำหรับ $n = xy \bmod k$ ซึ่งคิดว่าเป็นควอนตัมยาก การแก้ความสอดคล้องนี้อาจมองได้ว่าเป็นการแก้สมการเชิงเส้นตัวแปรเดียว (แบบแน่นอน) มีสองวิธีตามธรรมชาติในการสรุปสิ่งนี้

  1. มากกว่าหนึ่งตัวแปร และ
  2. มากกว่าหนึ่งสมการ

เช่น เปลี่ยนโจทย์ให้เป็นที่กำหนด $\vec b = A\vec s\bmod k$ ที่ไหน $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$. นี่ยังคงเป็นเรื่องเล็กน้อยที่จะ "แก้ไข" แม้ว่า --- หากคุณเลือก $A$ ให้เป็นเมทริกซ์เอกลักษณ์แล้ว $\vec s = \vec b$ ทำงาน โดยทั่วไปถ้าคุณเลือก $A$ กลับด้านได้ $\mathbb{Z}_k$, แล้ว $\vec s = \vec A^{-1}\vec b$ ทำงาน ถึงแม้ว่า $\vec A$ ไม่สามารถกลับด้านได้ (บอกว่ามันไม่เป็นรูปสี่เหลี่ยมจัตุรัส) มีหลายสิ่งที่คุณสามารถทำได้โดยใช้เทคนิคพีชคณิตเชิงเส้นทั่วไป ทั้งหมดนี้มีทั้งประสิทธิภาพและคลาสสิก เช่น Shor's ยังคง overkill

โดยทั่วไปวิธีการหยุดการโจมตีข้างต้นนั้นมีสองเท่า

  1. ระบุเมทริกซ์บางอย่าง $A$ ต้องใช้ (จึงไม่สามารถตั้งค่าได้ $A$ เป็นตัวตนหรือเมทริกซ์กลับด้านแบบสุ่ม) และ

  2. ใส่เสียงรบกวนเข้าไปในปัญหา

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

การเรียนรู้ด้วยข้อผิดพลาด: อนุญาต $A\in\mathbb{Z}_k^{n\times n}$ สุ่มอย่างสม่ำเสมอและปล่อยให้ $\vec s\in\mathbb{Z}_k^n$ เป็นเวกเตอร์ "ความลับ" สำหรับการกระจายแบบคงที่ $\chi$ รองรับบน $\mathbb{Z}_k$เราว่า ค้นหาการเรียนรู้ด้วยข้อผิดพลาด ปัญหาคือการกู้คืน $\vec s$, ที่ให้ไว้ $(ก, ก\vec s + \vec e)$, ที่ไหน $\vec e \gets \chi^n$.

ขึ้นอยู่กับการกำหนดพารามิเตอร์ ปัญหา LWE เป็นหนึ่งในตัวเลือกชั้นนำสำหรับการสันนิษฐานความแข็งที่ปลอดภัยต่อคอมพิวเตอร์ควอนตัม กล่าวคือ เพื่อการสรุปผลทั่วไปที่เหมาะสม $n \equiv xy\bmod k$ก็คิดว่าเป็นอัลกอริทึมของชอร์ ไม่ได้ แก้ปัญหา. ดังที่ได้กล่าวไปแล้ว การสรุปเป็นขั้นตอนหลายขั้นตอนที่ลบออกจากปัญหาเริ่มต้นของคุณ

มีความคล้ายคลึงกันอื่น ๆ ในทิศทางนี้ (ปัญหาความเท่าเทียมกันของการเรียนรู้กับปัญหาเสียงรบกวนหรือปัญหา GCD โดยประมาณ) --- ความคล้ายคลึงกันพื้นฐานกับสิ่งเหล่านี้ทั้งหมดคือคุณมีตัวแปร "ที่มีเสียงดัง" ของปัญหาเชิงเส้น


นอกจากนี้ยังมีลักษณะทั่วไปของ $x^2+y^2\bmod k$ ปัญหาที่คิดว่าจะปลอดภัยควอนตัม แต่ฉันไม่ทราบรายละเอียดมากดังนั้นจะเขียนน้อยลง ประมาณหนึ่งแทนที่พหุนามกำลังสอง $f(x, y) = x^2+y^2\bmod k$ ด้วย ตามอำเภอใจ พหุนามกำลังสอง (หรือชุดของพหุนาม) ใน $n$ ตัวแปร จากนั้นปัญหาของการฟื้นตัว $(x_1,\จุด, x_n)$ นั่นคือศูนย์ (พร้อมกัน) ของพหุนามกำลังสองหลายตัวแปร $p_0, \จุด,p_m$ เกี่ยวข้องกับการทำลาย "ระบบเข้ารหัสลับหลายตัวแปร" (โดยประมาณ) โปรดทราบว่าการยืนกรานที่จะกู้คืนศูนย์ของพหุนาม (แทนที่จะเป็น $p(x_0,\dots,x_n) = N$ตามที่คุณขอ) มาพร้อมกับลักษณะทั่วไปที่ไม่สูญเสียไป เนื่องจากเราสามารถกู้คืนสิ่งนี้ได้โดยดูที่ศูนย์ของ $p(x_0,\dots,x_n) - N$.

นี่คือทั้งหมดที่จะบอกว่า

  1. Shor's คิดที่จะทำลายปัญหาของคุณทั้งคู่ แต่
  2. มีภาพรวมของปัญหาทั้งสองของคุณที่คิดว่าปลอดภัยควอนตัม ในความเป็นจริง สมมติฐานที่ปลอดภัยเกี่ยวกับควอนตัม "ชั้นนำ" จำนวนมาก (ทุกอย่างที่ฉันรู้ยกเว้นสิ่งที่เป็นไอโซจีนีและการเข้ารหัสอันดับเมตริก) สามารถมองได้ว่าเป็นภาพรวมของปัญหาของคุณ
dz flag
ขอบคุณอีกครั้ง - ระบบยังคงไม่อนุญาตให้ฉันลงคะแนน (แต่จะให้ฉันใช้การแชท แปลกพอ) ฉันไม่คิดว่าจะมีจุดกึ่งกลางระหว่างคำถามที่โพสต์ที่นี่และคำอธิบายของระบบที่เป็นปัญหา ฉันสามารถส่งอีเมลสำเนาของระบบที่เป็นปัญหาได้ หากคุณต้องการ แต่ฉันเข้าใจว่านั่นเกินหน้าที่สำหรับ crypto.se และหากคุณไม่มีเวลา/ความสนใจ
dz flag
หากคุณ (หรือใครก็ตาม) ต้องการดูเฉพาะเจาะจง ฉันสามารถแบ่งปันที่อยู่อีเมลในแชทได้

โพสต์คำตอบ

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