Score:1

ฉันจะพิสูจน์พรีอิมเมจของแฮชที่มีจำนวนมากกว่า x ได้อย่างไร

ธง ht

ดังนั้นฉันต้องการสร้างระบบพิสูจน์ตัวเลขที่ไม่มีความรู้ (คิดว่าสินเชื่อและบัญชีธนาคาร ฉันต้องการพิสูจน์ว่าเช็คเงินเดือนของฉันมากกว่า x ดอลลาร์ต่อเดือน)

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

แต่นั่นก็ไม่มีประโยชน์มากนักเพราะฉันไม่ต้องการเปิดเผยแฮชของเช็คเงินเดือนของฉัน เพราะมันไม่ยากที่จะแฮชจำนวนเงินทั้งหมดที่เป็นไปได้ (สมมติว่า 500.00-5000.00 นั่นเป็นเพียง 450k ตัวเลือก) และตรวจสอบว่าเท่ากันหรือไม่

ดังนั้นสิ่งที่ฉันคิดจะทำคือเพิ่มสตริงสุ่มต่อจำนวนและแฮช มีวิธีที่ฉันสามารถพิสูจน์ได้หรือไม่ว่าแฮชของสตริงที่มีตัวเลขมากกว่าจำนวนหนึ่ง หรือฉันคิดเรื่องนี้ผิดไป?

Sam Jaques avatar
us flag
คุณได้ดูการพิสูจน์ระยะ: https://arxiv.org/abs/1907.06381?
knaccc avatar
es flag
คำตอบของฉันที่นี่ https://crypto.stackexchange.com/questions/96232/zkp-prove-that-18- while-hiding-age/97836#97836 แสดงวิธีใช้ Pedersen Commitment แทนแฮช และวิธีสร้าง การพิสูจน์ช่วงตามลายเซ็นของ Schnorr-ring ที่พิสูจน์ว่าความมุ่งมั่นนั้นมากกว่าหรือเท่ากับค่าหนึ่งๆ
Score:-1
ธง kr

หนึ่งในเกณฑ์ของฟังก์ชันแฮชที่ดีคือไม่เปิดเผยข้อมูลใดๆ เกี่ยวกับพรีอิมเมจ นั่นเป็นเหตุผลที่คำตอบคือ: ไม่ สำหรับฟังก์ชันแฮชที่ดี คุณจะไม่สามารถพูดอะไรเกี่ยวกับพรีอิมเมจได้

เอาเป็นว่าน่าจะได้ สมมติว่าฟังก์ชันแฮชบางตัวจะตอบจริงๆ ถ้าตัวเลขแฮชมากกว่าค่าที่กำหนดจากนั้นจะหาหมายเลขนั้นได้ง่าย

  1. ใช้แฮชเพื่อตรวจสอบว่าหมายเลขแฮชนั้นมากกว่า 1,000,000 หรือไม่
  2. ถ้าไม่ใหญ่กว่า ให้ใช้ค่ามัธยฐาน 500,000 ใช้แฮชเพื่อตรวจสอบว่าตัวเลขที่แฮชนั้นมากกว่า 500,000
  3. หากใหญ่กว่านี้ ให้ใช้ค่ามัธยฐานจากครึ่งบนคือ 750,000 หากไม่ใหญ่กว่า ให้ใช้ค่ามัธยฐานจากครึ่งล่างคือ 250,000 เป็นต้น สำหรับ 1,000,000 คุณจะได้รับหมายเลขที่แฮชหลังจากผ่านไปเพียง 20 ขั้นตอน ด้วยความแม่นยำ +-1 ถ้าทำอีก 7 ขั้นตอน ก็จะทราบตัวเลขที่มีความแม่นยำ 0.01
ht flag
โอเค แต่ฉันต้องการให้ใครสักคนพิสูจน์ให้คนอื่นเห็นว่าเงินเดือนของพวกเขามีค่ามากกว่ามูลค่าบางอย่าง พวกเขาสามารถนำความรู้เกี่ยวกับสิ่งที่อยู่ในแฮชและใช้ข้อมูลนั้นเพื่อสร้างหลักฐาน การพิสูจน์เหล่านั้นจะไม่ถูกสร้างขึ้นโดยอัตโนมัติ ผู้ใช้จำเป็นต้องลงนามด้วยค่าที่พวกเขารู้ว่าอยู่ในแฮชเท่านั้น ฉันควรใช้อะไรสำหรับแอปพลิเคชันนี้
Manish Adhikari avatar
us flag
คำตอบนี้ผิด @vrwim ใช่ คุณพูดถูกที่สามารถทำได้ มันควรจะเป็นไปได้ที่จะสร้างการพิสูจน์ความรู้เป็นศูนย์ว่าค่า v ที่เข้ารหัสมีค่ามากกว่า x สำหรับค่า x ที่รู้จักบางส่วนโดยไม่เปิดเผยสิ่งอื่นใดเกี่ยวกับ x คุณไม่สามารถค้นหาค่าแบบไบนารีด้วยข้อมูลนั้นเพียงอย่างเดียวได้ เพราะคนอื่นไม่สามารถตรวจสอบได้ว่ามีค่ามากกว่าค่า y อื่นๆ หรือไม่ เว้นแต่ผู้พิสูจน์จะตัดสินใจพิสูจน์เช่นกัน เห็นได้ชัดว่าปัญหาอยู่ใน NP และทุกปัญหาใน NP นั้นไม่มีหลักฐานความรู้
Manish Adhikari avatar
us flag
สิ่งที่ดีที่สุดที่ฉันรู้สำหรับการพิสูจน์ดังกล่าวคือ ZK SNARK บนวงจรบูลีนสำหรับการคำนวณแฮช ซึ่งดีมากสำหรับการตรวจสอบ (การพิสูจน์สั้นและมีเวลาตรวจสอบเชิงเส้นย่อยที่มีขนาดพยาน) การสร้างการพิสูจน์ต้องใช้เวลาพอสมควรเนื่องจากจำเป็นต้องคอมไพล์โปรแกรมแฮชและการดำเนินการเส้นโค้งวงรี
kelalaka avatar
in flag
ดู https://www.wisdom.weizmann.ac.il/~oded/gmw1.html
kr flag
@Manish Adhikari: ความคิดเห็นของคุณผิด ฉันคิดว่าคุณยังไม่เข้าใจคำถาม คำถามคือ **ไม่** หากสามารถพิสูจน์ ZP ได้ คำถามคือว่าแฮช **คงที่** ที่คำนวณโดยผู้พิสูจน์ **ล่วงหน้า** (โดยไม่มีการโต้ตอบใดๆ กับตัวตรวจสอบ) สามารถใช้สำหรับการพิสูจน์ ZK ได้หรือไม่ เป็นไปไม่ได้เนื่องจากเหตุผลที่ฉันได้อธิบายไว้ในคำตอบ
Manish Adhikari avatar
us flag
ตกลง แต่ฉันยังไม่เห็นว่าคำถามใช้คำอย่างไรเพื่อสื่อความหมายที่คุณพูด อย่างไรก็ตาม ฉันยอมรับว่ามีบางส่วนที่ฉันไม่เข้าใจว่านายจ้างเข้ามาในสมการได้อย่างไร
kr flag
@ManishAdhikari: OP กำลังมองหาวิธีคำนวณแฮช **single** และทำ **ล่วงหน้า** การพิสูจน์ ZK ไม่ทำงานในลักษณะนี้

โพสต์คำตอบ

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