In this paper, the authors propose a solution to improve the secure of digital signature schemes, this solution is implemented on two levels of digital signature scheme construction. At the first level, the authors propose a new hard problem, this hard problem belongs to the class of hard problems for which there is currently no solution (except by “brute force attack" method). At the second level, the authors propose a method to construct new digital signature algorithms based on this hard problem.Trong bài báo này, nhóm tác giả đề xuất giải pháp nâng cao tính an toàn của lược đồ chữ ký số, giải pháp này được triển khai trên hai cấp độ xây dựng lược đồ chữ ký số. Ở cấp độ thứ nhất, nhóm tác giả đề xuất một dạng bài toán khó mới, bài toán khó này thuộc lớp bài toán khó mà hiện nay chưa có cách giải (ngoại trừ phương pháp “tấn công vét cạn"). Ở cấp độ thứ hai, nhóm tác giả đề xuất phương pháp xây dựng thuật toán chữ ký số mới dựa trên bài toán khó này.