Score:0

การแก้ไขบันทึกแยกด้วย BsGs

ธง jo

ถ้าเราพิจารณากลุ่ม G ที่มีโมดูลัส p ให้สั่ง q ด้วย $p=2*q+1$และเครื่องกำเนิดไฟฟ้า $g=2$ ($p$, $คิว$ จำนวนเฉพาะมาก) มีวิธีแก้ปัญหาบันทึกแยกหรือไม่ $ g^ x = y $ สำหรับ y ที่กำหนดโดยใช้อัลกอริทึมขั้นตอนยักษ์ของ baby step และข้อเท็จจริงที่ว่า $x$ เป็นรูปแบบ: $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ โดยไม่ต้องเก็บขั้นตอนเล็กๆ ทั้งหมดใน hashtable ซึ่งเป็นไปไม่ได้ด้วยขนาดของตัวเลข $p$ และ $คิว$.

แก้ไข: เดอะ $ \alpha_i $ ผู้โจมตีไม่ทราบค่า

แก้ไข 2: $\alpha_i \in [0,\infty] $

poncho avatar
my flag
ผู้โจมตีรู้ค่า $\alpha_i$ หรือไม่
kelalaka avatar
in flag
จริง ๆ แล้ว $\alpha_i \in \{0,1\}$ หรือไม่ หาก $\mathbb{N} = \mathbb{Z}^+$ หรือ $\mathbb{N} = \mathbb{Z}^+ \cup \{0\}$ ไม่มีข้อตกลงร่วมกันในเรื่องนี้
Score:0
ธง my

มีวิธีแก้ปัญหาบันทึกแยกหรือไม่ $g^x=y$ สำหรับ $y$ ให้โดยใช้อัลกอริธึมขั้นตอนยักษ์ขั้นตอนทารก

ไม่มีทางปฏิบัติถ้า $p, q$ มีขนาดใหญ่

ถึงแม้ว่า $x$ เป็นที่ทราบกันดีว่าอยู่ในรูป $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ ?

ทุกศักยภาพ $x$ สามารถแสดงในรูปแบบนั้น พิจารณา $\alpha_1 = \alpha_2 = ... = \alpha_{10} = 0$ และ $\alpha_{0} = x$. จึงรู้ว่า $x$ แสดงในรูปแบบนั้นไม่ได้ให้ข้อมูลเพิ่มเติมใดๆ BsGs ใช้งานได้ก็ต่อเมื่อโมดูลัสมีขนาดเล็กพอ (และคำถามถือว่าไม่เป็นเช่นนั้น)

Ievgeni avatar
cn flag
ไม่มี $x
poncho avatar
my flag
@levgeni: หากเรากำลังพูดถึงค่าที่ **สามารถ** แสดงในรูปแบบนั้น เราก็มี $x \ge 2047$ (และนั่นคือข้อตกลงที่ว่า $0 \not\in \mathbb{N}$; ไม่เช่นนั้น , ค่า $x$ ทั้งหมดสามารถแสดงในรูปแบบนั้นได้)
poncho avatar
my flag
@levgeni: และถ้า $x
kelalaka avatar
in flag
@poncho ฉันคิดว่า levgeni ให้เหตุผลว่าแม้ว่า $x>2046$ ก็ไม่ได้หมายความว่า $x$ นั้นไม่เล็กเลย ขนาดใหญ่มีความชัดเจน แต่ขนาดเล็กต้องมีเมตริก
poncho avatar
my flag
@kelalaka: ฉันไม่เข้าใจข้อโต้แย้งของคุณ หากเราตีความคำถามว่า "DLog สามารถแก้ไขได้หรือไม่หากเราถือว่าเลขยกกำลังสุ่มโดยกำหนดเงื่อนไขโดยแสดงออกในรูปแบบที่กำหนด" ด้วยความเข้าใจนั้น คำตอบของฉันถูกต้อง - คุณตีความคำถามอย่างไร
kelalaka avatar
in flag
@poncho ถ้า $x$ มีขนาดเล็ก ( ไม่มีเมตริกที่นี่ ) แต่เรารู้ขอบเขต BsGs สามารถเป็นพารามิเตอร์เพื่อแก้ไขได้เร็วขึ้นใช่ไหม และอีกครั้ง ถ้า $x$ น้อย จริงๆแล้วเราไม่ต้องการ BsGs เราสามารถบังคับเดรัจฉานได้เหมือนที่เราบังคับเดรัจฉานตั้งแต่ 1 ถึง $2^{48}$ สำหรับ $x$' ที่เป็นไปได้ หรือคุณสมมติว่าสุ่ม $x$ เครื่องแบบโดยปริยาย?
Ievgeni avatar
cn flag
@poncho ตกลงฉันคิดว่า $\alpha$'s เป็นบิต ฉันหลงทางเล็กน้อยกับการแก้ไขทั้งหมด ฉันยังไม่เข้าใจว่าทำไมคุณถึงพูดถึง $2046$ ฉันต้องการลบ $-1$ ของฉัน แต่ฉันทำได้ก็ต่อเมื่อคุณแก้ไขข้อความของคุณเท่านั้น
poncho avatar
my flag
@levgeni: ถ้า $0 \not\in \mathbb{N}$ ดังนั้น $\sum_1^{10} 2^i\alpha_i$ ขั้นต่ำสามารถเป็น 2046 คำจำกัดความบางอย่างของ $\mathbb{N}$ ไม่รวม 0 คนอื่นทำ
Ievgeni avatar
cn flag
แต่ผลรวมในคำถามเริ่มเป็นศูนย์ ดังนั้นควรเป็น $2047$?
poncho avatar
my flag
@levgeni: ฉันใช้ $\alpha_0$ เป็นค่าที่เปลี่ยนแปลง ดังนั้นเราจึงมี $x = \alpha_0 + 2046$ - $\alpha_0 = 0$ ไม่ได้รับอนุญาต ดังนั้นเรามี $x > 2046$
Ievgeni avatar
cn flag
@Ievgeni : โอเค ขอบคุณสำหรับคำอธิบาย ฉันเข้าใจแล้ว. แต่ดูเหมือนว่า $alpha$'s จะเท่ากับศูนย์ในที่สุด

โพสต์คำตอบ

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