Score:2

ความได้เปรียบของศัตรูต่อฟังก์ชั่นง่ายๆ?

ธง ng

ผู้โจมตีต้องชนะเกมต่อไปนี้โดยแยกแยะว่าผลลัพธ์นั้นได้รับการอัปเดตโดยฟังก์ชันบางอย่างหรือไม่?

  1. ผู้โจมตีสอบถามออราเคิลสำหรับผลลัพธ์

  2. Oracle สร้าง 4 ไบต์แบบสุ่มใหม่ $a$, $ข$, $ค$, และ $d$ และหนึ่งบิตสุ่ม $x$.

  3. ถ้า $x=0$, Oracle ส่งออกค่าของ $a$, $ข$, $ค$, และ $d$.

  4. ถ้า $x=1$อันดับแรกจะอัปเดตค่าโดยใช้สมการต่อไปนี้ (ใช้ตามลำดับ) จากนั้นจึงส่งออกค่าที่อัปเดตของ $a$, $ข$, $ค$, และ $d$. $$\begin{จัด} ก &= (a + dc) \bmod 256;\ b &= (b + โฆษณา) \bmod 256;\ ค &= (ค + บา) \bmod 256;\ d &= (d + cb) \bmod 256;\ \end{align}$$

  5. เป้าหมายของผู้โจมตีคือค้นหาผลลัพธ์ที่เป็นผลมาจากขั้นตอนที่ 3 หรือ 4?

*ผู้โจมตีสามารถสอบถามได้อย่างไม่จำกัด

ตัวอย่าง: ถ้า a=0, b=0, c=1, d=1 และ x=1 ที่ขั้นตอนที่ 2 จากนั้น Oracle จะแสดงผล 1,1,2,3.

ShAr avatar
cn flag
เป้าหมายของผู้โจมตีคืออะไร กำไร/กำไร หรือยูทิลิตี้ fn คืออะไร
elonnoe avatar
ng flag
@ShAr อัปเดตคำถาม
ShAr avatar
cn flag
ฉันตอบ แต่ฉันคิดว่าคำถามนี้เหมาะกว่าในวิทยาการคอมพิวเตอร์หรือทฤษฎีเกม/number thorey สำหรับการดำเนินการ mod ถ้ามี อย่างไรก็ตามนี่เป็นเพียงความคิดเห็นเท่านั้นไม่ได้ลงคะแนนอะไร
fgrieu avatar
ng flag
ข้อความระบุปัญหาที่ 4 ไม่ชัดเจนว่าสมการถูกนำไปใช้ตามลำดับหรือเป็นกลุ่ม เช่น ถ้าในขั้นตอนที่ 2 a=0, b=0, c=1, d=1, x=1 oracle เอาต์พุต 1,1,2,3 หรือ 1,0,1,1 ? การอ่านครั้งแรกทำให้ปัญหาง่ายขึ้น: การเปลี่ยนแปลงแต่ละครั้งทำให้การกระจายของสิ่งที่เปลี่ยนแปลงเป็นอย่างไร การอ่านครั้งที่สองน่าสนใจยิ่งขึ้น คำแนะนำ: สำรวจว่าเกิดอะไรขึ้นกับบิตลำดับต่ำ จากนั้นจึงเกิดบิตที่สอง เพียงพอที่จะชนะเกม แต่ไม่ได้รับประโยชน์สูงสุด พิจารณา: $(\mathbb Z_{2^k},+,\cdot)$ เป็นฟิลด์ก็ต่อเมื่อ $k=0$ หากคุณต้องการความช่วยเหลือ บอกเราว่าคุณทำอะไร ติดขัดตรงไหน!
elonnoe avatar
ng flag
@fgrieu ฉันอัปเดตคำถามเพื่อตอบคำถามของคุณ ฉันคำนวณความถี่ของแต่ละค่าที่เป็นไปได้สำหรับแต่ละเอาต์พุตไบต์และบิตที่มีนัยสำคัญน้อยที่สุดของแต่ละเอาต์พุตไบต์ แต่ไม่พบรูปแบบใดๆ ในนั้น เนื่องจากผู้โจมตีไม่สามารถควบคุมอินพุตไบต์ได้ และ Oracle จะสร้างไบต์สุ่มใหม่ทุกครั้งที่มีการสืบค้น ผลลัพธ์ของขั้นตอนที่ 4 จึงปรากฏขึ้นแบบสุ่ม!!!
fgrieu avatar
ng flag
สิ่งนี้ถูกต้อง: เมื่อใช้สมการตามลำดับ ไม่มีทางแยกความแตกต่างของ 3 จาก 4 ได้ นั่นเป็นเพราะการเปลี่ยนแปลงทั้งสี่รายการทำให้การกระจายของ $(a,b,c,d)$ เหมือนกัน (อาร์กิวเมนต์: ในกลุ่มใดๆ ที่มี กฎหมาย $\boxplus$ ก็เพียงพอแล้วที่ $u$ จะสุ่มแบบสม่ำเสมอและไม่ขึ้นกับ $v$ เพื่อให้ $u\boxplus v$ สุ่มแบบสม่ำเสมอ) ไม่เป็นเช่นนั้นสำหรับ `(a,b,c,d)=((a+d*c)%256,(b+a*d)%256,(c+b*a)%256,(d+c* b)%256)` ในความหมายที่มีใน Python ซึ่งเป็นจุดที่ฉันแนะนำให้ตรวจสอบว่าเกิดอะไรขึ้นกับบิตต่ำ จากนั้นจึงให้บิตลำดับต่ำสองตัว
elonnoe avatar
ng flag
@fgrieu ขอบคุณสำหรับความช่วยเหลือ ฉันติดอยู่ แต่ตอนนี้ฉันเข้าใจเหตุผลพื้นฐานนั้นแล้ว
Score:3
ธง us

อนุญาต $f(ก,ข,ค,ง)$ แสดงถึงการเปลี่ยนแปลงของคุณในขั้นตอนที่ 4 ซึ่งเป็นองค์ประกอบตามลำดับของขั้นตอนทั้ง 4 นี้:

  1. $(a,b,c,d) \mapsto (a+dc \bmod 256,b,c,d)$
  2. $(a,b,c,d) \mapsto (a,b+ad \bmod 256,c,d)$
  3. $(a,b,c,d) \mapsto (a,b,c+ba \bmod 256,d)$
  4. $(a,b,c,d) \mapsto (a,b,c,d+cb \bmod 256)$

โปรดทราบว่าแต่ละขั้นตอนจะกลับด้านได้ ตัวอย่างเช่น ขั้นตอนแรกกลับเป็น $(a',b,c,d) \mapsto (a'-dc \bmod 256,b,c,d)$. ดังนั้นการเปลี่ยนแปลงทั้งหมด $f(ก,ข,ค,ง)$ กลับด้านได้

ตั้งแต่การจัดจำหน่ายไป $(ก,ข,ค,ง)$ เป็นเครื่องแบบในขั้นต้นและ $f$ กลับด้านการกระจายบน $f(ก,ข,ค,ง)$ เป็นเครื่องแบบด้วย นั่นหมายความว่า: โดยไม่คำนึงถึง $x=0$ หรือ $x=1$เอาต์พุตจะเหมือนกัน ดังนั้นตัวแยกความแตกต่างจึงไม่มีข้อได้เปรียบในการคาดเดา $x$.

fgrieu avatar
ng flag
ใช่. กรณีที่การแปลงคือ $a'=(a+dc)\bmod256$, $b'=(b+ad)\bmod256$, $c'=(c+ba)\bmod256$, $d'=( d+cb)\bmod256$ ตามด้วย $a=a'$, $b=b'$, $c=c'$, $d=d'$ ยาก/น่าสนใจกว่า ขณะนี้มีข้อได้เปรียบที่ไม่จำเป็นในการคำนวณ
crypt avatar
cn flag
นั่นถือเป็นจริงสำหรับ f ที่กลับค่าได้?
Score:0
ธง cn
  • ความน่าจะเป็นที่จะชนะจากการทดลองครั้งที่ 1 = 0.5 (การเดาล้วนๆ สมมติว่าค่า X สุ่มสม่ำเสมอ 0 หรือ 1)

  • ความน่าจะเป็นที่จะชนะในการทดลองครั้งที่ 2 เนื่องจากเขารู้ผลลัพธ์ของการทดลองครั้งที่ 1 = 1 - โพรบ[((a=a+dc)mod256) และ ((b=b+ad) mod256) และ ((c=c+ba) mod256) และ ((d=d+cb) mod256)]

ในการเริ่มต้นสูตรเหล่านี้จะมีค่า €256 (เข้าถึงค่าเดียวกันผ่านการดำเนินการ mod) อย่างน้อย 3 ใน 4 ค่าต้องเป็น €128

ในความเป็นจริง พวกมันต้องมี (ไม่ใช่แค่มากกว่าหรือเท่ากัน) กำลังเพียงพอของ 2 (dc=nâ 256, ad=mâ 256, ab=kâ 256, cb=lâ 256)

.... และอื่น ๆ อย่างไรก็ตามฉันคิดว่าจะไปตรวจสอบเพิ่มเติมว่าต้องเก็บค่าไว้ในหนึ่งไบต์หรือไม่ เช่นโดยค่าเริ่มต้น a,b,c,d < 256?

»»» ในกรณีของขั้นตอนที่ 2 ซ้ำทุกการทดลอง ฉันเดาว่าวิธีเดียวที่ฝ่ายตรงข้ามจะได้รับจากการรู้ฟังก์ชัน (เปลี่ยนความน่าจะเป็นที่จะชนะของเขาเป็นมากกว่า 0.5 การเดาล้วนๆ) คือถ้าสูตรที่กำหนด r ไม่สุ่มแบบเดียวกัน เช่น ถ้าคุณสามารถพิสูจน์ได้ว่าค่า a,b,c,d ที่แก้ไขแล้วมีความเบ้ไปทาง 1 วินาทีหรือมากกว่า 9 วินาที บางทีความน่าจะเป็นที่จะชนะควรเพิ่มขึ้นโดยการลดลงของ ระดับของความสุ่ม.

fgrieu avatar
ng flag
ความน่าจะเป็นที่จะชนะขึ้นอยู่กับวิธีที่เราอ่านคำชี้แจงปัญหาสำหรับขั้นตอนที่ 4 และกลยุทธ์ที่ฝ่ายตรงข้ามใช้ (รอการพิจารณา) ด้วยสองสิ่งนี้ที่คงที่ เนื่องจากการทดลองเป็นอิสระต่อกัน ความน่าจะเป็นที่จะชนะจึงไม่ได้ขึ้นอยู่กับหมายเลขการทดลอง ดังที่ระบุไว้ในคำตอบปัจจุบัน
ShAr avatar
cn flag
แน่นอน หากคุณทำการทดลองติดต่อกัน 2 ครั้งและพบว่าผลลัพธ์แตกต่างกัน คุณสามารถชนะได้ 100% โดยพูดว่า X=1 หมายความว่าฝ่ายตรงข้ามมีความได้เปรียบอย่างน้อยในกรณีนี้โดยรู้ว่าเกมนั้นอยู่ภายใต้ fn
fgrieu avatar
ng flag
ดำเนินการขั้นตอนที่ 2 และสร้าง a, b, c, d, x ใหม่ก่อนขั้นตอนที่ 3 หรือขั้นตอนที่ 4 ทุกครั้งที่ถึงขั้นตอนเหล่านี้ ดังนั้น การรู้ว่าสองเอาต์พุตแตกต่างกันนั้นไม่เพียงพอที่จะสรุปบน x ในเอาต์พุตแรกหรือเอาต์พุตที่สอง โดยทั่วไปแล้ว ไม่มีประเด็นใดในการเปรียบเทียบผลลัพธ์ของการทดลองต่างๆ เนื่องจากเป็นการทดลองที่เป็นอิสระต่อกัน คำถามเกี่ยวกับการวางแผนกลยุทธ์ที่ก่อให้เกิดความได้เปรียบ ซึ่งจะอยู่ในการทดสอบแต่ละครั้งโดยอิสระ อย่างที่ฉันอธิบายไว้ในความคิดเห็นของคำถามนั้น จะเป็นไปได้หรือไม่นั้นขึ้นอยู่กับว่าเราอ่านขั้นตอนที่ 4 อย่างไร และมีสองวิธี
ShAr avatar
cn flag
Aha ตกลง ขอโทษ ฉันคิดว่า (แก้ไขบนพื้นฐานที่ว่า) ขั้นตอนที่ 2 จะทำเพียงครั้งเดียวเหมือนเมล็ดสำหรับเครื่องกำเนิดตัวเลขสุ่ม
elonnoe avatar
ng flag
@ShAr ไม่ ขั้นตอนที่ 2 จะดำเนินการอีกครั้งสำหรับแต่ละแบบสอบถามใหม่

โพสต์คำตอบ

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