Score:0

จะพิสูจน์ความรู้ความลับและให้ผู้รับสามารถลบข้อมูลที่ซ้ำกันได้อย่างไร?

ธง ug

พิจารณาสถานการณ์ต่อไปนี้:

เรามีตัวแทนสองคน และ .

ต้องพิสูจน์ว่าพวกเขารู้ความลับ โดยไม่เปิดเผยความลับที่แท้จริง

เช่น.: ต้องการวิธีขจัดความลับที่ได้รับซ้ำซ้อน แต่พวกเขาไม่จำเป็นต้องรู้ความลับที่แท้จริง (และ ไม่อยากให้รู้)

คิดว่ามันเหมือนกับการแบ่งปันแฮชของความลับนั้น ยกเว้น: เป็นแหล่งเอนโทรปีต่ำที่มีขนาดเล็กมาก (มีค่าที่เป็นไปได้ประมาณ 1 พันล้านค่า) ซึ่งหมายความว่าแฮชธรรมดาจะเสี่ยงต่อการถูกโจมตีจากพจนานุกรม

ตอนนี้, อาจเพิ่ม "เกลือ" ที่ซ่อนอยู่ในความลับแต่ละข้อที่พวกเขาแบ่งปันแล้วแฮช ซึ่งจะทำให้ยากขึ้น เพื่อทำการโจมตีพจนานุกรม เท่าที่ฉันสามารถบอกได้ นี่จะเป็นการ "แก้ปัญหา" สำหรับกรณี 1-1

อย่างไรก็ตาม ขอแนะนำตัวแทนคนที่สาม . กำลังส่งความลับประเภทเดียวกันไปให้ . และ ไม่สามารถแบ่งปันความลับระหว่างกันได้

สามารถจบลงด้วยการส่ง "สำเนา" ของความลับที่ มีแม้ว่าพวกเขาจะไม่รู้ว่าอะไร มีที่สิ้นสุดของพวกเขา

แน่นอนว่าตอนนี้จำเป็นต้องยกเลิกการทำซ้ำไม่เพียง แต่ความลับเท่านั้น แต่ยังมาจาก .

เกลือที่ซ่อนอยู่จะไม่ทำงานอีกต่อไปเพราะตอนนี้ จะต้องรู้เกลือจึงจะสามารถสร้างแฮชเดียวกันได้ มิฉะนั้น จะไม่สามารถยกเลิกการทำซ้ำระหว่างคีย์จาก และ . การมีเกลือร่วมกันหมายความว่าอย่างนั้น สามารถโจมตีพจนานุกรมได้ หรือในทางกลับกัน

สามารถ , และ บรรลุข้อตกลงที่ และ สามารถแบ่งปัน "หลักฐาน" ของพวกเขากับ ในทางที่ ลบซ้ำกันได้ แต่ไม่มีใครเปิดเผยความลับของกันและกันได้?

หากเป็นเช่นนั้น สามารถสรุปเป็นภาพรวมกับผู้บริโภค/ผู้ผลิตจำนวนเท่าใดก็ได้

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

(เพื่อให้ชัดเจนหากยังไม่ได้ทำ: , และ ไม่ไว้ใจกัน)

(วางแผน) ตัวอย่าง

อลิซและบ็อบต้องการขายแสตมป์ให้กับนักสะสมแสตมป์ ให้คิดว่าแสตมป์เป็นสตริง 7 อักขระที่มีเฉพาะอักขระตัวพิมพ์เล็ก และนักสะสมแสตมป์จะประดิษฐ์เองไม่ได้

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

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

knaccc avatar
es flag
B และ C จะต้องเชื่อใจ A เพราะ A จะสามารถเปิดเผยต่อ B หรือ C ได้หาก B และ C แบ่งปันสิ่งที่ซ้ำกัน ถ้า B แชร์ค่าหนึ่งกับ A ทีละค่า B อาจได้รับแจ้งจาก A ทันทีที่ A สังเกตเห็นว่า C แชร์ค่าเฉพาะ บางทีถ้าคุณอธิบายปัญหาที่เป็นรูปธรรม มันอาจจะง่ายกว่าที่จะเข้าใจข้อจำกัดด้านความน่าเชื่อถือทั้งหมด
Cássio Renan avatar
ug flag
B หรือ C ไม่สามารถไว้วางใจ A ได้เลยหรือเชื่อใจซึ่งกันและกัน ฉันไม่แน่ใจว่าปัญหาที่เป็นรูปธรรม (ครั้งหนึ่ง) จะเพิ่มอะไร TBH อย่างที่ฉันพูด มันกระตุ้นให้เกิดคำถาม แต่จริงๆ แล้วมันไม่ใช่ปัญหาที่ฉันกำลังพยายามแก้ไขหรือคิดอยู่
knaccc avatar
es flag
คุณกำลังบอกว่าข้อกำหนดคือ A จะไม่สามารถสมรู้ร่วมคิดกับ B เพื่อแจ้งให้ B ทราบว่าค่าที่มองไม่เห็นของ B ใดที่ B มีเหมือนกันกับ C? ดังนั้นจึงเป็นไปไม่ได้ที่ B จะส่งค่าที่มองไม่เห็นไปให้ A ทีละค่า เพื่อที่ A จะได้แจ้ง B ทันทีที่สังเกตเห็นค่าที่ซ้ำกัน คุณกำลังบอกด้วยว่า "ตัวแทน" ต่อไปไม่ควรเข้าร่วมโดยไม่ได้รับอนุญาตจากตัวแทนที่มีอยู่ทั้งหมด เพื่อป้องกันการสมรู้ร่วมคิดดังกล่าว
kelalaka avatar
in flag
คุณกำลังมองหา[การเข้ารหัสแบบบรรจบกัน](https://crypto.stackexchange.com/q/729/18298)หรือไม่
Cássio Renan avatar
ug flag
@knaccc ไม่นั่นไม่ใช่ข้อกำหนด ในทางทฤษฎี B และ C ไม่รู้จักกันและกันด้วยซ้ำ (พวกเขาสื่อสารกับ A เท่านั้นและไม่มีใครอื่น)
Cássio Renan avatar
ug flag
@kelalaka จากคำตอบที่ยอมรับดูเหมือนว่าหนึ่งในข้อกำหนดคือ "ไฟล์" ที่จะเข้ารหัสนั้นยาวเพียงพอ ข้อ จำกัด ของคำถามนี้คือความลับมีขนาดเล็ก (ไม่เช่นนั้นแฮชของความลับที่ดีก็เพียงพอแล้ว เนื่องจากการโจมตีพจนานุกรมจะไม่เป็นปัญหาอีกต่อไป)
Cássio Renan avatar
ug flag
จากความคิดเห็นล่าสุดของฉัน ฉันเดาว่า "การพิสูจน์" ไม่ใช่คำอธิบายที่ดี - เนื่องจากฉันไม่สนใจจริงๆ หาก "ตัวแทน" ส่งแฮช "ปลอม" ไปยัง A ดังนั้นฉันจึงไม่สนใจการพิสูจน์ แต่บางอย่าง แบบฟอร์มถ้าเอกลักษณ์/โทเค็น ฉันจะพยายามหาคำที่ดีกว่าและปรับปรุงคำถาม
Cássio Renan avatar
ug flag
@knaccc ฉันเพิ่มตัวอย่าง ฉันคิดว่ามันสรุปข้อ จำกัด ได้ดี แจ้งให้เราทราบหากใช้งานได้!
knaccc avatar
es flag
หากตัวแทนแบบไม่จำกัดสามารถติดต่อ A โดยไม่ได้รับการอนุมัติจากตัวแทนที่มีอยู่ A สามารถเข้าร่วมเป็นตัวแทนและตรวจสอบทุกชุดที่เป็นไปได้เพื่อดูว่ามีตัวแทนอื่นเสนอความลับนั้นหรือไม่ ดังนั้นคุณต้องมีกลไกในการจำกัดจำนวนของรายการที่ตัวแทนสามารถเสนอให้กับ A ซึ่งตัวแทนแต่ละคนจะยอมรับและเต็มใจที่จะประกาศรายการที่มองไม่เห็นของพวกเขาในเวลาเดียวกับที่ตัวแทนรายอื่นมีจำนวนจำกัด เสนอข้อเสนอจำนวน จำกัด ที่พิสูจน์ได้ เนื่องจากคุณไม่ได้ระบุกรณีการใช้งานจริง ฉันจึงไม่รู้ว่าสิ่งนี้จะยอมรับได้หรือไม่
Cássio Renan avatar
ug flag
ไม่ ฉันคิดว่าคุณให้ประเด็นที่ดีมากที่นี่ ความคิดแรกเริ่มของฉันคือ "ทำไม A ถึงต้องการตรวจสอบสิ่งนั้นกับตัวเอง ในทางทฤษฎีแล้ว พวกเขารู้อยู่แล้วว่าตัวแทนอื่นๆ เสนออะไร แม้ว่าพวกเขาจะไม่รู้ความลับก็ตาม" แต่แล้วมันก็กระทบใจฉัน - การจัดการดังกล่าวจะต้องยอมให้ A ดำเนินการ เพียงแค่กำลังดุร้ายในแบบที่คุณอธิบายและมีความลับอยู่แล้ว
Cássio Renan avatar
ug flag
ในตัวอย่างแสตมป์ นักสะสมสามารถ "ขาย" แสตมป์ที่เป็นไปได้ทั้งหมดให้กับตัวมันเอง จากนั้นนักสะสมจะรู้จักแสตมป์ทุกดวงของผู้ขายรายอื่นโดยใช้กลไกการทำซ้ำในทางที่ผิด ฉันเดาว่านั่นคือคำตอบของฉัน
knaccc avatar
es flag
มีวิธีที่ A สามารถตรวจสอบกับตัวแทนแต่ละคนเพื่อดูว่าตัวแทนแต่ละคนมีสิ่งที่ A ยังไม่มีหรือไม่ สิ่งนี้สามารถทำได้โดยที่เจ้าหน้าที่ไม่ค้นพบว่าความลับใดที่ A มี และไม่มีเจ้าหน้าที่เปิดเผยความลับใด ๆ ที่พวกเขามี (นอกเหนือจากที่ A มีอยู่แล้ว) ตัวแทนสามารถจำกัดจำนวนรายการที่ A ตรวจสอบเพื่อหลีกเลี่ยงการถูกบังคับอย่างดุร้ายน่าเสียดายที่วิธีนี้ไม่อนุญาตให้ A ดูว่าตัวแทนมากกว่าหนึ่งรายมีความลับแบบเดียวกับที่ A ไม่มีหรือไม่
Cássio Renan avatar
ug flag
ไม่นั่นจะไม่ทำงานในสถานการณ์ที่ฉันคิด ลองนึกถึง "A" หรือตัวสะสมแสตมป์ ราวกับว่ามันเป็น API ที่คนอื่นใช้ มันไม่สามารถเกิดขึ้นในทางกลับกัน ไม่ว่าในกรณีใด หลังจากความคิดเห็นล่าสุดของคุณ ฉันค่อนข้างมั่นใจว่าโดยธรรมชาติแล้ว ข้อตกลงนี้ไม่สามารถรับประกันความลับของ "ตราประทับ" รวมถึงกลไกการขจัดข้อมูลซ้ำซ้อนได้ ขอบคุณมาก ๆ ท่าน!
Cássio Renan avatar
ug flag
หรืออีกนัยหนึ่ง "การเก็บแสตมป์ไว้เป็นความลับ" และ "ความสามารถในการลอกเลียนแบบแสตมป์จากแหล่งต่างๆ" เป็นข้อกำหนดที่ขัดแย้งกัน เมื่อจำนวนของแสตมป์ที่เป็นไปได้มีน้อยพอที่จะบังคับได้

โพสต์คำตอบ

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