Phép biến đổi Fiat–Shamir

Phép biến đổi Fiat–Shamir là gì?

Phép biến đổi Fiat–Shamir là kỹ thuật mật mã chuyển một số giao thức chứng minh tương tác thành bằng chứng không tương tác hoặc chữ ký số.

Kỹ thuật này loại bỏ nhu cầu để bên xác minh trực tiếp gửi một thử thách ngẫu nhiên mới cho bên chứng minh.

Thay vào đó, bên chứng minh tính thử thách bằng cách băm bản ghi giao thức, mệnh đề công khai, cam kết, thông điệp và ngữ cảnh cần thiết khác.

Bằng chứng tạo ra có thể được lập một lần và được bất kỳ ai có cùng thông tin công khai xác minh về sau.

Kỹ thuật này còn được gọi là heuristic Fiat–Shamir vì tính bảo mật thường dựa trên việc mô hình hóa hàm băm mật mã như một oracle ngẫu nhiên.

Amos Fiat và Adi Shamir giới thiệu phương pháp này trong công trình năm 1986, How to Prove Yourself: Practical Solutions to Identification and Signature Problems.

Phép biến đổi này có ý nghĩa trong tiền mã hóa vì hệ thống blockchain không phải lúc nào cũng hỗ trợ liên lạc riêng tư nhiều lần giữa mọi bên chứng minh và bên xác minh.

Bằng chứng không tương tác có thể được đưa vào giao dịch, block, lệnh gọi hợp đồng thông minh, bằng chứng rollup, chữ ký và thông điệp cross-chain.

Phép biến đổi Fiat–Shamir giải quyết vấn đề gì?

Nhiều giao thức chứng minh tri thức ban đầu được thiết kế như cuộc trao đổi giữa bên chứng minh và bên xác minh.

Trước tiên, bên chứng minh cam kết với thông tin ngẫu nhiên ẩn hoặc thông tin liên quan đến bí mật.

Sau đó, bên xác minh gửi một thử thách ngẫu nhiên mà bên chứng minh không thể đoán trước khi đưa ra cam kết.

Bên chứng minh phản hồi bằng cách sử dụng nhân chứng bí mật và thử thách.

Bên xác minh kiểm tra xem cam kết, thử thách, phản hồi và mệnh đề công khai có thỏa mãn các phương trình của giao thức hay không.

Tương tác này có thể gây bất tiện trong mạng phi tập trung vì bên chứng minh và bên xác minh phải trực tuyến đồng thời và trao đổi nhiều thông điệp.

Một giao dịch blockchain có thể được hàng nghìn node không tham gia lúc tạo bằng chứng kiểm tra độc lập vào thời điểm sau đó.

Phép biến đổi Fiat–Shamir thay thử thách ngẫu nhiên trực tiếp của bên xác minh bằng thử thách tất định từ hàm băm mà mọi bên xác minh đều có thể tính lại.

Nhờ đó, bản ghi bằng chứng có thể được lưu trữ, truyền đi và xác minh mà không cần liên hệ với bên chứng minh ban đầu.

Bằng chứng tương tác hoạt động như thế nào?

Một giao thức tương tác ba thông điệp phổ biến gồm cam kết, thử thách và phản hồi.

Bên chứng minh biết một giá trị bí mật gọi là nhân chứng.

Mệnh đề công khai nêu điều mà bên chứng minh tuyên bố mình biết hoặc phép tính mà bên chứng minh khẳng định đã hoàn tất chính xác.

Ở bước đầu, bên chứng minh lấy ngẫu nhiên một giá trị riêng tư và tạo cam kết.

Ở bước thứ hai, bên xác minh tạo một thử thách ngẫu nhiên không thể dự đoán.

Ở bước thứ ba, bên chứng minh kết hợp nhân chứng, giá trị ngẫu nhiên riêng tư và thử thách để tính phản hồi.

Bên xác minh chỉ chấp nhận khi phản hồi phù hợp với cam kết, thử thách và mệnh đề công khai.

Thử thách phải không thể dự đoán tại thời điểm tạo cam kết.

Nếu không, bên chứng minh gian lận có thể tạo cam kết chỉ hoạt động với thử thách đã được chọn trước.

Phép biến đổi Fiat–Shamir hoạt động như thế nào?

Phép biến đổi loại bỏ thông điệp thứ hai của bên xác minh và thay bằng phép tính hàm băm mật mã.

Trước tiên, bên chứng minh tạo cùng loại cam kết sẽ được dùng trong giao thức tương tác.

Sau đó, bên chứng minh băm mệnh đề công khai, cam kết, thông điệp, mã định danh giao thức và dữ liệu bản ghi bắt buộc khác.

Đầu ra hàm băm được chuyển thành một thử thách thuộc không gian thử thách hợp lệ của giao thức.

Bên chứng minh dùng thử thách đó và nhân chứng bí mật để tính phản hồi.

Bằng chứng không tương tác cuối cùng thường chứa cam kết và phản hồi; bên xác minh có thể tính lại thử thách.

Bên xác minh dựng lại bản ghi, tính cùng thử thách hàm băm rồi áp dụng phương trình xác minh ban đầu.

Có thể biểu diễn phép biến đổi đơn giản như sau:

Các đầu vào và quy tắc mã hóa chính xác đóng vai trò quan trọng đối với bảo mật.

Ví dụ về giao thức Schnorr

Giao thức nhận dạng Schnorr là ví dụ rõ ràng về phép biến đổi Fiat–Shamir.

Giả sử một nhóm cyclic có phần tử sinh

và cấp .

Bên chứng minh có khóa riêng tư

và khóa công khai .

Bên chứng minh muốn chứng minh mình biết

mà không tiết lộ giá trị này.

Trong giao thức tương tác, bên chứng minh chọn giá trị ngẫu nhiên

và gửi cam kết .

Bên xác minh phản hồi bằng thử thách ngẫu nhiên

.

Bên chứng minh tính

.

Bên xác minh kiểm tra

.

Phản hồi hợp lệ cho thấy bên chứng minh có thể thỏa mãn phương trình với thử thách không thể dự đoán.

Áp dụng Fiat–Shamir cho giao thức Schnorr

Phiên bản không tương tác thay thử thách do bên xác minh tạo bằng giá trị băm.

Bên chứng minh tính thử thách, chẳng hạn

.

Sau đó, bên chứng minh tính

.

Bằng chứng hoặc chữ ký chứa cam kết

và phản hồi .

Bên xác minh tính lại thử thách từ cùng khóa công khai, cam kết, ngữ cảnh và thông điệp.

Bên xác minh chấp nhận khi phương trình xác minh Schnorr được thỏa mãn.

RFC 8235 quy định bằng chứng zero-knowledge không tương tác Schnorr được tạo từ lược đồ nhận dạng Schnorr ba lượt thông qua phép biến đổi Fiat–Shamir.

Phép biến đổi tạo chữ ký số như thế nào?

Bằng chứng nhận dạng cho thấy bên chứng minh biết bí mật gắn với một danh tính công khai.

Để tạo chữ ký số, thử thách cũng phải gắn bằng chứng với một thông điệp cụ thể.

Thay đổi thông điệp sẽ làm thay đổi đầu ra hàm băm và do đó làm thay đổi thử thách.

Thông thường, không thể sử dụng lại một bằng chứng tạo cho giao dịch này làm chữ ký hợp lệ cho giao dịch khác.

Phản hồi của người ký chứng minh họ biết khóa riêng tư và gắn kiến thức đó với thông điệp được ký.

Mô hình chuyển đổi từ nhận dạng sang chữ ký này là một trong những ứng dụng quan trọng nhất của phép biến đổi Fiat–Shamir.

Fiat–Shamir và chữ ký Schnorr của Bitcoin

BIP 340 của Bitcoin quy định chữ ký Schnorr cho đường cong elliptic secp256k1.

Thử thách chữ ký được tạo bằng cách băm cam kết nonce, khóa công khai và thông điệp.

Đây là mô hình chữ ký Schnorr không tương tác gắn với phép biến đổi Fiat–Shamir.

BIP 340 cũng sử dụng hàm băm có gắn nhãn để tách biệt phép tính hàm băm của giao thức với các mục đích sử dụng khác.

Hàm băm có gắn nhãn thêm vào đầu vào một giá trị được tạo từ nhãn riêng của giao thức.

Điều này giảm rủi ro cùng một hàm băm và định dạng đầu vào bị diễn giải như hai phép toán mật mã khác nhau.

Chữ ký BIP 340 được sử dụng trong quy tắc giao dịch Taproot của Bitcoin.

Phép biến đổi này có phạm vi rộng hơn Bitcoin và có thể dùng với nhiều hệ thống chứng minh, nhóm đại số và giả định mật mã.

Fiat–Shamir trong hệ thống bằng chứng zero-knowledge

Các hệ thống bằng chứng zero-knowledge hiện đại thường bắt đầu bằng một giao thức dễ mô tả dưới dạng tương tác giữa bên chứng minh và bên xác minh.

Bên chứng minh gửi cam kết đa thức, Merkle root, phần tử nhóm hoặc thông điệp khác.

Bên xác minh phản hồi bằng các phần tử trường ngẫu nhiên hoặc vị trí truy vấn.

Fiat–Shamir tạo các thử thách đó từ bản ghi thay vì yêu cầu bên xác minh trực tuyến.

Nhờ đó, bằng chứng có thể được tạo off-chain rồi xác minh về sau bởi node blockchain hoặc hợp đồng thông minh.

Phép biến đổi được dùng trong các hệ thống hỗ trợ giao dịch riêng tư, bằng chứng hợp lệ, rollup mở rộng quy mô, tính toán có thể xác minh và khả năng tương tác blockchain.

Fiat–Shamir trong Halo2

Halo2 mô tả giao thức chứng minh dưới dạng tương tác để phân tích, nhưng triển khai theo cách không tương tác thông qua phép biến đổi Fiat–Shamir.

Bản ghi gồm các cam kết và thông điệp khác của bên chứng minh.

Đầu ra hàm băm mật mã được chuyển thành thử thách của bên xác minh dùng cho phép tính đa thức và kiểm tra bằng chứng.

Tài liệu giao thức Halo2 giải thích rằng lập luận tương tác public-coin trở thành không tương tác khi thay bên xác minh bằng hàm băm mạnh về mật mã.

Halo2 cũng phân tích các thuộc tính bảo mật có tính đến khả năng bên chứng minh tạo và xem lại trạng thái bản ghi.

Điều này cho thấy áp dụng Fiat–Shamir an toàn không chỉ đơn giản là thay bộ tạo số ngẫu nhiên bằng một lần gọi hàm băm.

Fiat–Shamir trong bằng chứng STARK

Hệ thống chứng minh STARK sử dụng nhiều vòng cam kết và thử thách của bên xác minh.

Các thử thách có thể quyết định hệ số ngẫu nhiên, điểm đánh giá đa thức và truy vấn kiểm tra bậc thấp.

Kênh Fiat–Shamir tạo tính ngẫu nhiên không tương tác này từ bản ghi bằng chứng đang được cập nhật.

Bên chứng minh đưa các cam kết vào kênh trước khi yêu cầu thử thách tiếp theo.

Bên xác minh lặp lại các thao tác trên bản ghi và nhận được cùng các thử thách.

Tài liệu về bên chứng minh STARK mô tả kênh Fiat–Shamir dùng để tạo tính ngẫu nhiên không tương tác trong suốt quá trình xây dựng bằng chứng.

Nếu cam kết hoặc đầu vào công khai thay đổi, các thử thách tiếp theo cũng phải thay đổi.

Mô hình oracle ngẫu nhiên là gì?

Mô hình oracle ngẫu nhiên là mô hình bảo mật xem hàm băm như một hàm ngẫu nhiên công khai lý tưởng.

Mỗi đầu vào duy nhất nhận được một đầu ra ngẫu nhiên độc lập.

Việc sử dụng lại cùng đầu vào luôn trả về cùng đầu ra.

Bất kỳ ai cũng có thể truy vấn oracle, nhưng không ai có thể dự đoán đầu ra mới nếu chưa gửi truy vấn tương ứng.

Hàm băm thực tế là thuật toán tất định, không phải oracle ngẫu nhiên lý tưởng.

Chứng minh bảo mật Fiat–Shamir trong mô hình oracle ngẫu nhiên cho thấy tính bảo mật dựa trên giả định lý tưởng hóa này.

Sau đó, bên triển khai sử dụng hàm băm mật mã thực được cho là hoạt động đủ giống mô hình để đáp ứng giao thức.

Mô hình oracle ngẫu nhiên hữu ích, nhưng chứng minh trong mô hình đó không phải chứng minh vô điều kiện cho mọi cách triển khai hàm băm.

Vì sao hàm băm phải bao gồm toàn bộ bản ghi?

Mỗi thử thách phải gắn với tất cả thông tin giao thức trước đó có ảnh hưởng đến ý nghĩa của nó.

Thông tin này có thể gồm tham số công khai, khóa công khai, mệnh đề, cam kết, thông điệp, thử thách trước đó, mã định danh chain và phiên bản giao thức.

Bỏ sót một giá trị quan trọng có thể cho phép chuyển bằng chứng sang ngữ cảnh khác.

Bằng chứng có thể hợp lệ cho hai khóa công khai, hai ứng dụng, hai mạng blockchain hoặc hai giai đoạn giao thức trong khi lẽ ra chỉ hợp lệ cho một đối tượng.

Trong bằng chứng nhiều vòng, mỗi thử thách phải phụ thuộc vào bản ghi được tích lũy trước thời điểm tạo thử thách đó.

Bên chứng minh phải cam kết với dữ liệu trước đó trước khi biết thử thách được suy ra.

Chỉ băm thông điệp cuối cùng có thể phá hỏng các bảo đảm về thứ tự mà giao thức tương tác cần có.

Phân tách miền là gì?

Phân tách miền bảo đảm một phép băm không thể bị nhầm lẫn với phép băm khác dùng cùng hàm nền tảng.

Giao thức có thể thêm tiền tố là nhãn duy nhất như tên, phiên bản, mạng, giai đoạn bằng chứng hoặc loại thao tác.

Nhãn làm thay đổi đầu vào hàm băm ngay cả khi dữ liệu còn lại giống nhau.

Nếu không phân tách miền, một giá trị được tạo làm thử thách trong giao thức này có thể bị diễn giải thành nonce, cam kết hoặc thử thách của giao thức khác.

Phân tách miền đặc biệt quan trọng trong phần mềm tiền mã hóa, nơi một hàm băm có thể được dùng lại cho mã giao dịch, chữ ký, cây Merkle, dẫn xuất khóa và bản ghi bằng chứng.

Hàm băm có gắn nhãn riêng cho giao thức trong BIP 340 là ví dụ thực tế về biện pháp bảo vệ này.

Vì sao mã hóa chính tắc quan trọng?

Bên chứng minh và bên xác minh phải băm chính xác cùng một chuỗi byte.

Đôi khi một giá trị toán học có thể có nhiều biểu diễn byte hợp lệ.

Số nguyên có thể được mã hóa với độ dài, thứ tự byte hoặc số 0 đứng đầu khác nhau.

Điểm trên đường cong elliptic có thể có dạng mã hóa nén, không nén hoặc dạng thay thế không hợp lệ.

Danh sách có thể trở nên mơ hồ nếu độ dài phần tử và ranh giới không được mã hóa rõ ràng.

Tuần tự hóa chính tắc quy định một biểu diễn được chấp nhận duy nhất cho mỗi giá trị bản ghi hợp lệ.

Tiền tố độ dài, nhãn kiểu dữ liệu, trường độ rộng cố định và quy tắc giải mã nghiêm ngặt có thể ngăn sự mơ hồ.

Phần mềm nên từ chối giá trị không chính tắc thay vì chuẩn hóa chúng theo cách khác với bên xác minh khác.

Độ dài thử thách và tính đúng đắn

Không gian thử thách ảnh hưởng đến xác suất bên chứng minh gian lận có thể thành công mà không biết nhân chứng hợp lệ.

Thử thách một bit tạo cho bên chứng minh gian lận xác suất đoán đúng tương đối cao trong một vòng.

Lặp lại giao thức hoặc dùng thử thách lớn hơn sẽ giảm sai số về tính đúng đắn.

Đầu ra hàm băm phải được chuyển thành thử thách có độ lớn đủ để đáp ứng mức bảo mật yêu cầu.

Cắt ngắn thử thách quá mức có thể làm suy yếu bằng chứng.

Việc ánh xạ đầu ra hàm băm vào một trường hoặc cấp nhóm cũng phải tránh sai lệch thống kê không thể chấp nhận.

Giao thức có thể dùng lấy mẫu từ chối, phép rút gọn rộng hoặc phương pháp được tài liệu hóa khác để tạo thử thách chính xác.

Fiat–Shamir grinding là gì?

Grinding xảy ra khi bên chứng minh liên tục thay đổi tính ngẫu nhiên của cam kết trong phạm vi cho phép rồi băm từng bản ghi cho đến khi có thử thách thuận lợi.

Bên chứng minh có thể tìm kiếm như vậy vì thử thách được tạo cục bộ thay vì do một bên xác minh trực tuyến độc lập tạo ra.

Phân tích bảo mật phải tính đến số lượng truy vấn hàm băm và kích thước không gian thử thách.

Không gian thử thách đủ lớn khiến việc grinding hữu ích trở nên bất khả thi về mặt tính toán theo các giả định của giao thức.

Ứng dụng không nên thêm các giá trị do bên chứng minh tùy ý kiểm soát nếu chúng khiến việc grinding rẻ hơn hoặc tạo ra sai lệch.

Hệ thống bằng chứng dùng Fiat–Shamir phải phân tích hành vi này, thay vì cho rằng bên chứng minh chỉ gửi một truy vấn hàm băm trung thực.

Rủi ro phát lại và gắn kết ngữ cảnh

Bằng chứng không tương tác có thể bị sao chép vì đây là dữ liệu công khai.

Việc sao chép không gây hại nếu bằng chứng chỉ chứng minh một mệnh đề công khai không phụ thuộc thời gian.

Việc này trở nên nguy hiểm khi ứng dụng nhầm lẫn việc sở hữu bằng chứng với bằng chứng về một hành động mới hoặc quyền cấp phép mới.

Bản ghi có thể chứa mã định danh giao dịch, người nhận, mạng, giá trị phiên, địa chỉ hợp đồng, thời hạn hoặc nonce riêng của ứng dụng.

Điều này gắn bằng chứng với ngữ cảnh dự định.

Việc thêm giá trị ngữ cảnh không hữu ích nếu bên xác minh không đối chiếu giá trị đó với yêu cầu hiện tại.

Yêu cầu về tính mới thuộc về toàn bộ giao thức ứng dụng, không chỉ phương trình bằng chứng.

Fiat–Shamir có tự động tạo ra zero-knowledge không?

Không, phép biến đổi này không tự động khiến mọi giao thức trở thành zero-knowledge.

Giao thức tương tác ban đầu phải có các thuộc tính zero-knowledge hoặc zero-knowledge với bên xác minh trung thực phù hợp.

Giao thức sau biến đổi cũng phải được phân tích theo mô hình bảo mật được chọn.

Cam kết có thể cần tính ngẫu nhiên che giấu để tránh làm lộ nhân chứng.

Thử thách trong bản ghi có thể cần giới hạn nhằm tránh giá trị đặc biệt làm lộ thông tin riêng tư.

Bằng chứng có thể không tương tác mà không có tính chất zero-knowledge.

Không tương tác chỉ có nghĩa bên chứng minh có thể tạo bằng chứng mà không cần nhận thông điệp trực tiếp từ bên xác minh.

Fiat–Shamir có tự động bảo đảm tính đúng đắn không?

Không, biến đổi an toàn một giao thức không chứng minh rằng mọi giao thức tương tự đều an toàn.

Giao thức tương tác ban đầu phải có tính đúng đắn, tính đúng đắn đặc biệt hoặc thuộc tính chứng minh tri thức cần thiết.

Đầu vào hàm băm và cách ánh xạ thử thách phải giữ nguyên thứ tự dự kiến: cam kết trước, thử thách sau.

Một số giao thức cần giả định mạnh hơn hoặc chứng minh chuyên biệt sau khi biến đổi.

Một cấu trúc có thể an toàn trong mô hình oracle ngẫu nhiên cổ điển nhưng không có chứng minh đầy đủ trước đối thủ lượng tử.

Nhà phát triển nên dựa vào cấu trúc đã được thẩm định và có chứng minh bảo mật, thay vì áp dụng Fiat–Shamir một cách không chính thức cho giao thức mới.

Fiat–Shamir và mật mã hậu lượng tử

Mô hình thiết kế Fiat–Shamir cũng xuất hiện trong nghiên cứu chữ ký hậu lượng tử.

Các lược đồ nhận dạng dựa trên lattice, mã và tính toán đa bên có thể dùng thử thách tạo từ hàm băm để lập chữ ký.

Một số chữ ký lattice dùng biến thể gọi là Fiat–Shamir có cơ chế hủy bỏ.

Người ký có thể khởi động lại một phần quy trình ký khi phản hồi trung gian có thể làm lộ thông tin hoặc nằm ngoài phân phối được chấp nhận.

NIST FIPS 204 tiêu chuẩn hóa ML-DSA, thuật toán chữ ký dựa trên module-lattice được phát triển từ thiết kế Dilithium.

Việc có các tiêu chuẩn chữ ký hậu lượng tử không có nghĩa mọi bằng chứng Fiat–Shamir cổ điển vẫn an toàn trước máy tính lượng tử.

Fiat–Shamir trong mô hình oracle ngẫu nhiên lượng tử

Đối thủ lượng tử có thể truy vấn oracle ngẫu nhiên được mô hình hóa trên trạng thái chồng chập của nhiều đầu vào.

Điều này khác với đối thủ cổ điển gửi từng truy vấn thông thường một.

Chứng minh oracle ngẫu nhiên cổ điển không tự động còn hiệu lực trong mô hình oracle ngẫu nhiên lượng tử, thường viết tắt là QROM.

Các nhà nghiên cứu mật mã đã phát triển thêm kỹ thuật chứng minh và điều kiện giao thức để phân tích cấu trúc Fiat–Shamir trước đối thủ lượng tử.

Vì vậy, tuyên bố bảo mật hậu lượng tử cần được hỗ trợ bằng phân tích bao quát QROM hoặc một mô hình bảo mật lượng tử phù hợp khác.

Chỉ thay nhóm cổ điển bằng bài toán lattice là chưa đủ.

Fiat–Shamir và chữ ký ngưỡng

Chữ ký ngưỡng chia quyền ký cho nhiều người tham gia.

Một số lượng người tham gia theo yêu cầu phối hợp tạo một chữ ký hợp lệ mà không cần khôi phục khóa riêng tư đầy đủ tại một nơi.

Giao thức Schnorr ngưỡng phải phối hợp cẩn thận các cam kết nonce và phép tính thử thách.

Thử thách phải gắn với khóa công khai tổng hợp, cam kết nonce tổng hợp, thông điệp, ngữ cảnh người tham gia và quy tắc giao thức.

Dựng bản ghi không chính xác có thể tạo điều kiện cho thao túng nonce, tấn công khóa giả mạo hoặc tấn công xuyên phiên.

RFC 9591 quy định giao thức ký Schnorr ngưỡng FROST và các phép toán bộ mật mã dựa trên hàm băm.

Ưu điểm của phép biến đổi Fiat–Shamir

Phép biến đổi loại bỏ tương tác trực tiếp với bên xác minh khỏi các hệ thống bằng chứng tương thích.

Bằng chứng có thể được tạo một lần và nhiều node blockchain xác minh độc lập.

Phép biến đổi giảm số vòng liên lạc và đơn giản hóa việc xác minh bất đồng bộ.

Bằng chứng có thể được đưa vào giao dịch, block, hợp đồng thông minh và bộ nhớ phân tán.

Cùng một bằng chứng có thể được kiểm tra mà không cần cung cấp cho bên xác minh tính ngẫu nhiên riêng tư hoặc duy trì phiên tương tác.

Phép biến đổi cũng tạo lộ trình thực tế để chuyển giao thức nhận dạng thành lược đồ chữ ký số.

Những đặc tính này khiến kỹ thuật hữu ích trong mạng phi tập trung, nơi các bên có thể không bao giờ liên lạc trực tiếp.

Hạn chế của phép biến đổi Fiat–Shamir

Phép biến đổi thường phụ thuộc vào mô hình oracle ngẫu nhiên.

Không thể biến đổi an toàn mọi bằng chứng tương tác có thể có.

Bỏ sót dữ liệu trong bản ghi và không nhất quán trong mã hóa có thể tạo lỗ hổng nghiêm trọng.

Bên chứng minh có thể tính hàm băm nhiều lần, vì vậy phải đưa hành vi grinding vào phân tích bảo mật.

Bằng chứng không tương tác có thể bị phát lại nếu ứng dụng không gắn chúng với ngữ cảnh phù hợp.

Bảo mật lượng tử cần được phân tích riêng.

Phép biến đổi không bảo vệ phần mềm khỏi rò rỉ kênh bên, tính ngẫu nhiên yếu, lỗi bộ nhớ hoặc khóa riêng tư bị đánh cắp.

Việc tạo bằng chứng cũng có thể vẫn tốn nhiều tài nguyên tính toán dù đã loại bỏ tương tác.

Phép biến đổi Fiat–Shamir và bằng chứng tương tác

Bằng chứng tương tác yêu cầu trao đổi thông điệp giữa bên chứng minh và bên xác minh.

Bên xác minh cung cấp các thử thách ngẫu nhiên mới trong quá trình tương tác.

Bằng chứng Fiat–Shamir suy ra các thử thách đó từ hàm băm của bản ghi.

Bằng chứng không tương tác dễ phân phối và xác minh bất đồng bộ hơn.

Giao thức tương tác có thể dựa vào tính ngẫu nhiên thực sự của bên xác minh, còn giao thức sau biến đổi dựa vào hành vi kiểu oracle ngẫu nhiên của hàm băm.

Phép biến đổi Fiat–Shamir và bằng chứng zero-knowledge không tương tác

Phép biến đổi Fiat–Shamir là một phương pháp tạo bằng chứng không tương tác.

Bằng chứng zero-knowledge không tương tác (NIZK) là phạm trù rộng hơn, gồm bằng chứng không cần tương tác trực tiếp với bên xác minh và không tiết lộ thông tin nhân chứng được bảo vệ.

Một số NIZK dùng Fiat–Shamir, trong khi số khác dùng chuỗi tham chiếu chung, thiết lập tin cậy, thiết lập minh bạch hoặc kỹ thuật mật mã khác.

Gọi một bằng chứng là không tương tác không cho biết phương pháp tạo ra nó.

Phép biến đổi Fiat–Shamir và chữ ký số

Chữ ký số xác thực thông điệp bằng khóa riêng tư và khóa công khai dùng để xác minh.

Phép biến đổi Fiat–Shamir là kỹ thuật cấu trúc có thể chuyển một số giao thức nhận dạng thành lược đồ chữ ký.

Không phải chữ ký số nào cũng được tạo bằng Fiat–Shamir.

Không phải bằng chứng Fiat–Shamir nào cũng được thiết kế để hoạt động như chữ ký số.

Bằng chứng có thể chứng minh người dùng biết một nhân chứng hoặc phép tính đã được thực hiện chính xác mà không xác thực một người hay ví cụ thể.

Phép biến đổi Fiat–Shamir và hash-to-curve

Hash-to-curve chuyển dữ liệu đầu vào tùy ý thành một điểm hợp lệ trên đường cong elliptic.

Fiat–Shamir chuyển dữ liệu bản ghi thành thử thách của bên xác minh.

Một hệ thống chứng minh có thể dùng cả hai phép toán.

Thử thách có thể là scalar, trong khi một thành phần giao thức khác cần điểm đường cong được tạo từ hàm băm.

Hai quy trình này cần quy tắc mã hóa và phân tách miền riêng.

Phép biến đổi Fiat–Shamir và commit-reveal

Giao thức commit-reveal yêu cầu người tham gia công bố cam kết rồi tiết lộ giá trị ẩn sau đó.

Giao thức này có thể giúp giảm khả năng biết trước hoặc thao túng tính ngẫu nhiên được chia sẻ.

Fiat–Shamir không chờ tiết lộ tính ngẫu nhiên công khai vào thời điểm sau.

Kỹ thuật này tạo thử thách tất định từ bản ghi hiện có.

Commit-reveal và Fiat–Shamir giải quyết các vấn đề phối hợp khác nhau, dù cả hai đều dùng cam kết mật mã và hàm băm.

Thực tiễn triển khai tốt nhất

Nhà phát triển nên dùng hệ thống bằng chứng có phân tích bảo mật Fiat–Shamir được công bố và thẩm định.

Bản ghi phải bao gồm mọi giá trị công khai xác định mệnh đề và ngữ cảnh.

Mỗi giao thức và giai đoạn bằng chứng phải có phân tách miền riêng.

Mọi giá trị phải dùng tuần tự hóa chính tắc, có ranh giới kiểu dữ liệu và độ dài rõ ràng.

Phải đưa các cam kết vào bản ghi trước khi tạo những thử thách phụ thuộc vào chúng.

Đầu ra thử thách cần được ánh xạ vào trường hoặc nhóm bằng phương pháp không sai lệch đã được tài liệu hóa.

Phải từ chối điểm không hợp lệ, scalar không chính tắc, giá trị trường bị cấm và bản ghi sai định dạng.

Tính ngẫu nhiên của bên chứng minh và nonce ký phải được tạo an toàn hoặc dẫn xuất bằng phương pháp tất định đã được phê duyệt.

Phần mềm cần kiểm tra rằng thay đổi bất kỳ mệnh đề, cam kết, thông điệp, mã mạng hoặc phiên bản giao thức nào đều làm thay đổi thử thách được suy ra.

Bộ vector kiểm tra nên bao gồm thứ tự bản ghi, mã hóa, nhãn miền, giá trị rỗng, giá trị biên và bằng chứng sai định dạng.

Các lỗi triển khai Fiat–Shamir thường gặp

Một lỗi là chỉ băm cam kết mà không băm mệnh đề công khai.

Một lỗi khác là bỏ sót thông điệp khi bằng chứng được dùng làm chữ ký.

Nối dữ liệu mơ hồ có thể khiến hai bản ghi khác nhau tạo ra cùng một chuỗi byte.

Dùng cùng nhãn miền cho các giao thức không liên quan có thể gây nhầm lẫn giữa các giao thức.

Tạo thử thách tiếp theo trước khi đưa mọi thông điệp trước đó của bên chứng minh vào bản ghi sẽ phá vỡ thứ tự của bản ghi.

Rút gọn trực tiếp một hàm băm ngắn vào trường lớn có thể làm giảm entropy của thử thách.

Chấp nhận điểm đường cong hoặc scalar không chính tắc có thể khiến các phần mềm khác nhau băm những biểu diễn khác nhau.

Dùng lại tính ngẫu nhiên của bên chứng minh có thể làm lộ nhân chứng bí mật trong các giao thức kiểu Schnorr.

Cho rằng chứng minh bảo mật cổ điển tự động mang lại bảo mật hậu lượng tử cũng là một lỗi nghiêm trọng.

Vì sao phép biến đổi Fiat–Shamir quan trọng với tiền mã hóa?

Mạng tiền mã hóa cần các bằng chứng có thể được người tham gia trên toàn thế giới xác minh độc lập.

Giao dịch blockchain không thể phụ thuộc vào cuộc trao đổi riêng tư với mọi node có thể xác minh giao dịch đó trong tương lai.

Fiat–Shamir cho phép đóng gói lập luận mật mã tương tác thành một đối tượng bằng chứng tĩnh.

Điều này hỗ trợ chữ ký gọn, hệ thống bảo mật quyền riêng tư, zero-knowledge rollup, thực thi hợp đồng thông minh có thể xác minh, ví ngưỡng và các ứng dụng blockchain khác.

Phép biến đổi cũng thể hiện một nguyên tắc thiết kế quan trọng trong crypto.

Hàm băm không chỉ tạo mã giao dịch; nó còn có thể tạo thử thách có vẻ khó dự đoán, gắn kết toàn bộ bản ghi giao thức.

Khả năng này phụ thuộc vào cấu trúc cẩn thận, tuần tự hóa chính xác, phân tách miền mạnh và chứng minh bảo mật phù hợp.

Câu hỏi thường gặp

Phép biến đổi Fiat–Shamir làm gì?

Phép biến đổi thay các thử thách ngẫu nhiên của bên xác minh trong một số giao thức tương tác bằng thử thách được suy ra từ hàm băm mật mã của bản ghi.

Vì sao Fiat–Shamir hữu ích trong tiền mã hóa?

Kỹ thuật này cho phép node blockchain xác minh bằng chứng và chữ ký về sau mà không cần trao đổi trực tiếp với bên chứng minh.

Ai tạo ra phép biến đổi Fiat–Shamir?

Amos Fiat và Adi Shamir giới thiệu kỹ thuật này trong công trình được trình bày năm 1986.

Phép biến đổi Fiat–Shamir có giống hàm băm không?

Không, đây là phép biến đổi giao thức dùng hàm băm để tạo thử thách cho bên xác minh.

Bằng chứng tương tác là gì?

Đây là giao thức trong đó bên chứng minh và bên xác minh trao đổi cam kết, thử thách và phản hồi.

Giao thức public-coin là gì?

Đây là giao thức tương tác trong đó thông điệp của bên xác minh là các thử thách ngẫu nhiên được công khai.

Bản ghi Fiat–Shamir là gì?

Đây là tập hợp có thứ tự gồm tham số công khai, mệnh đề, cam kết, thử thách, phản hồi, thông điệp và ngữ cảnh được dùng trong bằng chứng.

Mô hình oracle ngẫu nhiên là gì?

Đây là mô hình bảo mật lý tưởng hóa xem hàm băm như một hàm ngẫu nhiên công khai với đầu ra nhất quán.

Hàm băm thực tế có phải oracle ngẫu nhiên không?

Không, hàm băm thực tế là tất định, dù giao thức có thể phân tích hàm băm như thể nó hoạt động giống oracle ngẫu nhiên lý tưởng.

Fiat–Shamir có tự động tạo zero-knowledge không?

Không, giao thức ban đầu và cấu trúc sau biến đổi phải đáp ứng các điều kiện zero-knowledge cần thiết.

Fiat–Shamir có tạo chữ ký số không?

Kỹ thuật này có thể chuyển một số giao thức nhận dạng thành chữ ký nếu thông điệp được đưa vào hàm băm tạo thử thách.

Bitcoin có sử dụng mô hình Fiat–Shamir không?

Chữ ký Schnorr BIP 340 của Bitcoin sử dụng thử thách tạo từ hàm băm, gắn cam kết nonce, khóa công khai và thông điệp.

Fiat–Shamir có được dùng trong zero-knowledge rollup không?

Nhiều hệ thống chứng minh rollup dùng thử thách bản ghi theo kiểu Fiat–Shamir để chuyển giao thức chứng minh tương tác thành không tương tác.

Fiat–Shamir có được dùng trong STARK không?

Có, bên chứng minh và bên xác minh STARK có thể dùng kênh Fiat–Shamir để suy ra thử thách không tương tác từ các cam kết.

Fiat–Shamir có được dùng trong Halo2 không?

Có, Halo2 triển khai mô tả bằng chứng tương tác dưới dạng lập luận không tương tác thông qua Fiat–Shamir.

Phân tách miền là gì?

Phân tách miền thêm nhãn riêng của giao thức vào đầu vào hàm băm để tránh nhầm lẫn đầu ra giữa các phép toán mật mã khác nhau.

Vì sao phải băm khóa công khai?

Băm khóa công khai gắn bằng chứng hoặc chữ ký với danh tính dự định, đồng thời có thể ngăn tấn công thay thế khóa hoặc tấn công xuyên khóa.

Vì sao phải băm thông điệp?

Đưa thông điệp vào hàm băm bảo đảm chữ ký tạo cho thông điệp này không thể được dùng lại cho thông điệp khác.

Challenge grinding là gì?

Challenge grinding là việc liên tục tạo cam kết cho đến khi hàm băm bản ghi sinh ra thử thách có lợi cho bên chứng minh.

Bằng chứng Fiat–Shamir có thể bị phát lại không?

Bằng chứng công khai có thể bị sao chép, vì vậy giao thức cần tính mới phải bổ sung và xác minh ngữ cảnh phiên hoặc giao dịch phù hợp.

Tuần tự hóa chính tắc là gì?

Tuần tự hóa chính tắc quy định một dạng biểu diễn byte được chấp nhận duy nhất cho mỗi giá trị trong bản ghi.

Vì sao thứ tự bản ghi quan trọng?

Mỗi thử thách phải phụ thuộc vào mọi thông điệp trước đó để bên chứng minh không thể thay đổi cam kết sau khi biết thử thách.

Có thể dùng Fiat–Shamir với đường cong elliptic không?

Có, bằng chứng và chữ ký Schnorr thường áp dụng kỹ thuật này trong các nhóm đường cong elliptic.

Có thể dùng Fiat–Shamir trong mật mã hậu lượng tử không?

Có, các cấu trúc liên quan xuất hiện trong chữ ký hậu lượng tử, nhưng cần phân tích lượng tử phù hợp để xác định tính bảo mật.

Mô hình oracle ngẫu nhiên lượng tử là gì?

Đây là mô hình trong đó đối thủ lượng tử có thể truy vấn oracle ngẫu nhiên bằng trạng thái chồng chập lượng tử.

Chứng minh bảo mật cổ điển có còn hiệu lực trước đối thủ lượng tử không?

Không tự động, vì chứng minh có thể chưa tính đến truy vấn oracle lượng tử hoặc giới hạn trích xuất trong môi trường lượng tử.

Fiat–Shamir có cơ chế hủy bỏ là gì?

Đây là biến thể cho phép người ký khởi động lại khi phản hồi không đáp ứng điều kiện phân phối hoặc kích thước cần thiết.

Fiat–Shamir có phải thiết lập tin cậy không?

Không, bản thân phép biến đổi không yêu cầu thiết lập tin cậy, dù hệ thống bằng chứng nền tảng có thể có yêu cầu thiết lập riêng.

Hợp đồng thông minh có thể xác minh bằng chứng Fiat–Shamir không?

Có, nếu hợp đồng có thể tính lại hàm băm bản ghi và kiểm tra hiệu quả các phương trình bằng chứng.

Rủi ro triển khai lớn nhất là gì?

Các rủi ro lớn thường gặp gồm gắn kết bản ghi không đầy đủ, mã hóa mơ hồ, phân tách miền yếu, tạo nonce không an toàn và giả định bảo mật chưa được hỗ trợ.

Kết luận

Phép biến đổi Fiat–Shamir chuyển các giao thức tương tác public-coin tương thích thành bằng chứng không tương tác hoặc chữ ký số.

Phép biến đổi thay thử thách khó dự đoán do bên xác minh trực tiếp tạo bằng thử thách suy ra từ hàm băm mật mã của bản ghi bằng chứng.

Nhờ đó, bằng chứng có thể được tạo một lần rồi xác minh độc lập bởi node blockchain, ví, hợp đồng thông minh và các ứng dụng crypto khác.

Phép biến đổi hỗ trợ chữ ký Schnorr, hệ thống bằng chứng zero-knowledge, STARK, giao thức kiểu Halo2, chữ ký ngưỡng và nghiên cứu chữ ký hậu lượng tử.

Tính bảo mật phụ thuộc vào các thuộc tính của giao thức tương tác ban đầu và giả định dùng để mô hình hóa hàm băm.

Triển khai đúng phải gắn toàn bộ mệnh đề, cam kết, thông điệp, tham số công khai, ngữ cảnh và phiên bản giao thức vào một bản ghi chính tắc.

Triển khai cũng phải dùng phân tách miền mạnh, thử thách đủ lớn, tạo nonce an toàn và quy tắc ánh xạ thử thách được thẩm định kỹ.

Phép biến đổi Fiat–Shamir không tự động tăng cường bảo mật cho mọi giao thức chứng minh.

Đây là cấu trúc mạnh mẽ nhưng mức độ an toàn phụ thuộc vào thiết kế giao thức nghiêm ngặt, kỷ luật triển khai và phân tích bảo mật trước cả đối thủ cổ điển lẫn lượng tử.