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

จนถึงปัจจุบัน การเข้ารหัสแบบแฮชถูกนำมาใช้ในการสร้าง รูปแบบ ลายเซ็นดิจิทัลเช่นรูปแบบลายเซ็น Merkle , ความรู้เป็นศูนย์ และการพิสูจน์ความสมบูรณ์เชิงคำนวณ เช่น ระบบการพิสูจน์ zk-STARK ^{[ 1 ]}และการพิสูจน์ช่วงเหนือข้อมูลประจำตัวที่ออกผ่านโปรโตคอล HashWires ^{[ 2 ]}รูปแบบลายเซ็นแบบแฮชรวมรูปแบบลายเซ็นแบบใช้ครั้งเดียว เช่นลายเซ็น Lamportเข้ากับ โครงสร้าง ต้นไม้ Merkleเนื่องจากคีย์รูปแบบลายเซ็นแบบใช้ครั้งเดียวสามารถลงนามข้อความเดียวได้อย่างปลอดภัย จึงเป็นเรื่องที่ปฏิบัติได้จริงที่จะรวมคีย์ดังกล่าวจำนวนมากไว้ในโครงสร้างขนาดใหญ่เพียงโครงสร้างเดียว โครงสร้างต้นไม้ Merkle ถูกนำมาใช้เพื่อจุดประสงค์นี้ ในโครงสร้างข้อมูลแบบลำดับชั้นนี้ ฟังก์ชันแฮชและการเชื่อมต่อจะถูกใช้ซ้ำ ๆ เพื่อคำนวณโหนดต้นไม้

ข้อควรพิจารณาประการหนึ่งเกี่ยวกับรูปแบบลายเซ็นแบบแฮชคือ สามารถลงนามข้อความได้อย่างปลอดภัยเพียงจำนวนจำกัดเท่านั้น เนื่องจากใช้รูปแบบลายเซ็นแบบใช้ครั้งเดียวสถาบันมาตรฐานและเทคโนโลยีแห่งชาติ ของสหรัฐอเมริกา (NIST) ระบุว่าอัลกอริทึมใน การแข่งขัน การเข้ารหัสลับหลังควอนตัมต้องรองรับลายเซ็นอย่างน้อย 2 ⁶⁴รายการได้อย่างปลอดภัย^{[ 3 ]}

NIST ได้กำหนดมาตรฐานการเข้ารหัสแบบแฮชที่มีสถานะตามแบบแผนลายเซ็น Merkle ที่ขยาย (XMSS) และลายเซ็น Leighton–Micali (LMS) ^{[ 4 ]}ซึ่งสามารถนำไปใช้ได้ในสถานการณ์ที่แตกต่างกันในปี 2020 แต่ตั้งข้อสังเกตว่าข้อกำหนดในการรักษาสถานะเมื่อใช้งานทำให้ยากต่อการนำไปใช้ในลักษณะที่หลีกเลี่ยงการใช้งานในทางที่ผิด^{[ 5 ] [ 6 ] [ 7 ]}

ในปี 2022 NIST ประกาศSPHINCS+เป็นหนึ่งในสามอัลกอริธึมที่จะได้รับการกำหนดมาตรฐานสำหรับลายเซ็นดิจิทัล^{[ 8 ]}และในปี 2024 NIST ประกาศมาตรฐานลายเซ็นดิจิทัลแบบแฮชไร้สถานะ (SLH-DSA) ^{[ 9 ]}ซึ่งอิงตาม SPHINCS+

Leslie Lamportคิดค้นลายเซ็นแบบแฮชในปี 1979 XMSS (eXtended Merkle Signature Scheme) ^{[ 10 ]}และ SPHINCS ^{[ 11 ] [ 12 ]}ซึ่งเป็นรูปแบบลายเซ็นแบบแฮช ได้รับการแนะนำในปี 2010 และ 2015 ตามลำดับ XMSS ได้รับการพัฒนาโดยทีมวิจัยภายใต้การกำกับดูแลของJohannes Buchmannและมีพื้นฐานมาจากทั้งรูปแบบลายเซ็น Merkle ดั้งเดิมและรูปแบบลายเซ็น Merkle ทั่วไป (GMSS) ปี 2007 ^{[ 13 ]} XMSS ^MT ซึ่งเป็นรูปแบบหลายต้นไม้ของ XMSS ได้รับการอธิบายในปี 2013 ^{[ 14 ]}

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

รูปแบบลายเซ็นแบบใช้ครั้งเดียวที่ใช้กันทั่วไป ได้แก่รูปแบบ Lamport–Diffie , รูปแบบ Winternitz ^{[ 15 ]}และการปรับปรุงต่างๆ เช่นรูปแบบ W-OTS ^{+ [ 16 ]}ซึ่งแตกต่างจากรูปแบบ Lamport–Diffie ดั้งเดิม รูปแบบ Winternitz และรูปแบบต่างๆ สามารถลงนามหลายบิตพร้อมกันได้ จำนวนบิตที่จะลงนามพร้อมกันจะถูกกำหนดโดยค่า: พารามิเตอร์ Winternitz การมีอยู่ของพารามิเตอร์นี้ทำให้เกิดความสมดุลระหว่างขนาดและความเร็ว ค่าพารามิเตอร์ Winternitz ที่สูงจะทำให้ลายเซ็นและคีย์สั้นลง แต่ต้องแลกมาด้วยการลงนามและการตรวจสอบที่ช้าลง ในทางปฏิบัติ ค่าทั่วไปสำหรับพารามิเตอร์นี้คือ 16

ในกรณีของลายเซ็นแบบแฮชที่ไม่ขึ้นกับสถานะ จะมีการใช้รูปแบบลายเซ็นแบบใช้ครั้งเดียวจำนวนน้อย (few-time signature schemes) รูปแบบดังกล่าวจะช่วยลดระดับความปลอดภัยลงทีละน้อยหากมีการใช้คีย์แบบใช้ครั้งเดียวจำนวนน้อยมากกว่าหนึ่งครั้ง HORST เป็นตัวอย่างหนึ่งของรูปแบบลายเซ็นแบบใช้ครั้งเดียวจำนวนน้อย

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

โดยทั่วไปแล้ว คีย์ส่วนตัวส่วนกลางจะถูกจัดการโดยใช้ตัวสร้างเลขสุ่มเทียม จากนั้นจึงเพียงพอที่จะจัดเก็บค่าเริ่มต้น (seed value) คีย์ลับแบบใช้ครั้งเดียวจะถูกสร้างขึ้นตามลำดับจากค่าเริ่มต้นโดยใช้ตัวสร้างเลขสุ่มเทียม ด้วยวิธีการนี้ คีย์ส่วนตัวส่วนกลางจึงมีขนาดเล็กมาก เช่น โดยทั่วไปจะมีขนาดเพียง 32 ไบต์

ปัญหาการท่องไปในโครงสร้างต้นไม้เป็นปัญหาสำคัญที่ส่งผลต่อประสิทธิภาพในการลงนาม มีการนำวิธีการที่มีประสิทธิภาพมากขึ้นมาใช้ ซึ่งช่วยลดเวลาในการลงนามได้อย่างมาก

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

งานของ Naor–Yung ^{[ 17 ]}แสดงรูปแบบในการถ่ายโอนลายเซ็นเวลาจำกัดของตระกูลประเภท Merkle ไปยังรูปแบบลายเซ็นไม่จำกัด (ปกติ)

ระบบลายเซ็นแบบใช้แฮชอาศัยข้อสมมติฐานด้านความปลอดภัยเกี่ยวกับฟังก์ชันแฮชพื้นฐาน แต่ฟังก์ชันแฮชใดๆ ที่ตรงตามข้อสมมติฐานเหล่านี้ก็สามารถนำมาใช้ได้ ดังนั้น ฟังก์ชันแฮชที่เหมาะสมแต่ละฟังก์ชันจึงให้ระบบลายเซ็นแบบใช้แฮชที่แตกต่างกัน แม้ว่าฟังก์ชันแฮชที่กำหนดจะไม่ปลอดภัย ก็เพียงพอที่จะแทนที่ด้วยฟังก์ชันแฮชที่ปลอดภัยกว่าเพื่อสร้างระบบลายเซ็นแบบใช้แฮชที่ปลอดภัยได้ ระบบลายเซ็นแบบใช้แฮชบางระบบ (เช่น XMSS ที่ใช้การสร้างคีย์แบบสุ่มเทียม) มีความปลอดภัยแบบส่งต่อ (forward secure) หมายความว่าลายเซ็นก่อนหน้ายังคงใช้ได้หากคีย์ลับถูกบุกรุก

ลักษณะเด่นอีกประการหนึ่งของระบบลายเซ็นดิจิทัลแบบใช้แฮชคือ การตั้งสมมติฐานด้านความปลอดภัยให้น้อยที่สุด โดยทั่วไปแล้ว ระบบเหล่านี้ต้องการเพียงฟังก์ชันแฮชเข้ารหัสลับที่ปลอดภัย (เช่น ในแง่ของความต้านทานต่อการหาค่าก่อนหน้าลำดับที่สอง ) เพื่อรับประกันความปลอดภัยโดยรวมของระบบ สมมติฐานประเภทนี้จำเป็นสำหรับระบบลายเซ็นดิจิทัลทุกระบบ อย่างไรก็ตาม ระบบลายเซ็นดิจิทัลอื่นๆ อาจต้องการสมมติฐานด้านความปลอดภัย เพิ่มเติม ซึ่งไม่ใช่กรณีของระบบนี้

เนื่องจากระบบลายเซ็นแบบแฮชอาศัยกลไกการลงลายเซ็นแบบใช้ครั้งเดียวเป็นพื้นฐาน จึงสามารถลงลายเซ็นข้อความได้อย่างปลอดภัยเพียงจำนวนจำกัดเท่านั้น ในกรณีของระบบ Merkle และ XMSS จำนวนข้อความสูงสุดที่สามารถลงลายเซ็นได้อย่างปลอดภัยนั้น จะขึ้นอยู่กับความสูงรวมของโครงสร้าง Merkle tree ${\displaystyle 2^{h}}$${\displaystyle h}$

นับตั้งแต่แผนการเริ่มต้นของ Merkle ได้มีการนำเสนอแผนการลงลายมือชื่อแบบแฮชจำนวนมากที่มีการปรับปรุงประสิทธิภาพ แผนการล่าสุดได้แก่ XMSS, Leighton–Micali (LMS), SPHINCS และ BPQS แผนการลงลายมือชื่อแบบแฮชส่วนใหญ่เป็นแบบมีสถานะ หมายความว่าการลงลายมือชื่อต้องมีการอัปเดตคีย์ลับ ซึ่งแตกต่างจากแผนการลงลายมือชื่อดิจิทัลทั่วไป สำหรับแผนการลงลายมือชื่อแบบแฮชที่มีสถานะ การลงลายมือชื่อต้องเก็บสถานะของคีย์แบบใช้ครั้งเดียวที่ใช้แล้วและตรวจสอบให้แน่ใจว่าจะไม่นำกลับมาใช้ใหม่ แผนการ XMSS, LMS และ BPQS ^{[ 18 ]}เป็นแบบมีสถานะ ในขณะที่แผนการ SPHINCS เป็นแบบไม่มีสถานะ ลายมือชื่อ SPHINCS มีขนาดใหญ่กว่าลายมือชื่อ XMSS และ LMS BPQS ได้รับการออกแบบมาโดยเฉพาะสำหรับระบบบล็อกเชน นอกจากแผนการลงลายมือชื่อแบบใช้ครั้งเดียว WOTS+ ^{[ 16 ]} แล้ว SPHINCS ยังใช้แผนการลงลายมือชื่อแบบใช้ไม่กี่ครั้ง (แบบแฮช) ที่เรียกว่า HORST อีกด้วย HORST เป็นการปรับปรุงรูปแบบลายเซ็นแบบไม่กี่ครั้งแบบเก่า HORS (Hash to Obtain Random Subset) ^{[ 19 ]}

^{XMSS และ XMSS MT} ซึ่ง เป็นรูปแบบแฮชที่มีสถานะ ได้รับการกำหนดไว้ในRFC 8391 (XMSS: eXtended Merkle Signature Scheme) ^{[ 20 ]}ลายเซ็นแบบแฮชของ Leighton–Micali ได้รับการกำหนดไว้ในRFC 8554 ^{[ 4 ]} มีการเสนอการปรับปรุงในทางปฏิบัติในเอกสารทางวิชาการที่ ช่วย บรรเทาความกังวลที่เกิดจากรูปแบบที่มีสถานะ^{[ 21 ]}ฟังก์ชันแฮชที่เหมาะสมสำหรับรูปแบบเหล่านี้ ได้แก่SHA-2 , SHA-3และBLAKE

SLH-DSA ซึ่งเป็นรูปแบบการเข้ารหัสแบบแฮชไร้สถานะ ได้รับการกำหนดไว้ในมาตรฐาน FIPS- 205

รูปแบบการเข้ารหัส XMSS, GMSS และ SPHINCS มีให้บริการในAPI การเข้ารหัส ของ Java Bouncy Castle ^{[ 22 ]} รูปแบบการเข้ารหัส LMS ^{[ 23 ]}และ XMSS มีให้บริการในAPI การเข้ารหัสของ wolfSSL ^{[ 24 ]} SPHINCS ถูกนำไปใช้ในชุดเครื่องมือการวัดประสิทธิภาพ SUPERCOP ^{[ 25 ]} มีการใช้งานอ้างอิง ที่ปรับให้เหมาะสม^{[ 26 ]}และไม่ได้ปรับให้เหมาะสม^{[ 27 ]}ของ RFC XMSS รูปแบบการเข้ารหัส LMS ได้รับการนำไปใช้ใน Python ^{[ 28 ]}และใน C ^{[ 29 ]}ตามร่างอินเทอร์เน็ต

• [10]รายการเอกสารที่มีคำอธิบายเกี่ยวกับรูปแบบลายเซ็นแบบแฮช
• [11]รายการอ้างอิงอื่น (ไม่ได้แสดงความคิดเห็น)