Lược đồ chữ ký số tổng quát
Trong một lược đồ chữ ký, mỗi người dùng (hay còn được gọi là người ký)
công bố một khóa công khai trong khi giữ lại cho bản thân một khóa bí mật (riêng).
Theo đó, chữ ký của người dùng trên thông điệp là một giá trị phụ thuộc vào
và khóa bí mật của người dùng đó theo cách mà bất kỳ ai cũng có thể kiểm tra sự
hợp lệ của chữ ký trên thông điệp chỉ bằng khóa công khai. Trong một số trường
hợp, khóa công khai cũng có thể được sử dụng trong quá trình tạo chữ ký. Đối với
các lược đồ chữ ký số, yêu cầu cơ bản được đặt ra là việc giả mạo một chữ ký của
người dùng mà không biết khóa bí mật của của một người dùng nào đó phải là khó
về mặt tính toán. Trong phần này, luận án sẽ phát biểu lại một định nghĩa hình thức
của một lược đồ chữ ký tổng quát và các tấn công có thể được tính đến trên lược đồ
như vậy. Những định nghĩa này được dựa trên cơ sở công trình của S. Goldwasser
và các cộng sự [42].
Định nghĩa 1.1 [68]. Một lược đồ chữ ký số được định nghĩa thông qua bộ-3 thuật
toán ( ) như sau:
 Thuật toán sinh khóa ( ): Nhận đầu vào , với là tham số an
toàn, tạo ra một cặp khóa công khai và khóa bí mật thích hợp ( ). Thuật toán
sinh khóa phải là một thuật toán xác suất.
Thuật toán ký: Cho trước thông điệp và một cặp khóa công
khai và bí mật, thuật toán tạo ra một chữ ký . Thuật toán sinh chữ ký
có thể là thuật toán xác suất, và trong một vài lược đồ nó cũng có thể nhận thêm
các đầu vào khác.
Thuật toán xác minh : Cho trước chữ ký , một thông
điệp và một khóa công khai , thuật toán Verify kiểm tra là chữ ký hợp lệ của
thông điệp tương ứng với khóa hay không