Lattice-based cryptography được dựa trên các định nghĩa và tính chất của lý thuyết lưới. Lý thuyết lưới là một lĩnh vực trong đại số tuyến tính nghiên cứu về các tập hợp tuyến tính các điểm trong không gian nhiều chiều, được gọi là lưới. Các lưới thường được định nghĩa bằng cách xếp các điểm lưới thành các cột và các hàng song song và được biểu diễn bởi ma trận nếu chúng đồng quy.
Một số khái niệm chính trong lý thuyết lưới bao gồm:
- Cơ sở lưới (lattice basis): Là một tập hợp các vector cơ sở tạo thành lưới.
- Số lượng các vector cơ sở (lattice dimension): Là số vector cơ sở trong một tập hợp tạo thành lưới.
- Khoảng cách (lattice spacing): Là khoảng cách giữa hai điểm gần nhất trên lưới.
- Các hệ số Shortest Vector Problem (SVP) và Closest Vector Problem (CVP): SVP là vấn đề tìm vector ngắn nhất trên lưới, trong khi CVP là vấn đề tìm vector trên lưới gần với một vector cho trước nhất.
Các thuật toán lattice-based cryptography sử dụng các tính chất của lý thuyết lưới để tạo ra các hệ mã hóa khóa công khai và khóa bí mật. Các thuật toán này thường sử dụng các tính chất như tính định hướng và khó giải quyết SVP và CVP để đảm bảo tính bảo mật của các hệ mã hóa.
Lattice basis
Lattice basis (cơ sở lưới) là một tập hợp các vector cơ sở tạo thành lưới. Các vector này thường được sử dụng để biểu diễn các điểm trong lưới và có thể được sử dụng để tạo ra các thuật toán mã hóa khóa công khai và khóa bí mật trong lattice-based cryptography.
Ví dụ, trong một lưới hai chiều, một tập hợp hai vector có thể được sử dụng như một cơ sở lưới. Các vector này có thể được biểu diễn bởi các hàng hoặc cột trong ma trận. Ví dụ:
| 1 0 | | 0 1 | | 1 1 | hoặc | 1 0 |
Các vector này tạo thành một lưới hai chiều, với các điểm trong lưới được biểu diễn bởi tất cả các tổ hợp nguyên dương của các vector cơ sở, ví dụ như (0,0), (1,0), (0,1), (1,1), (2,1), (1,2), vv.
Cơ sở lưới quan trọng trong lattice-based cryptography vì chúng được sử dụng để tạo ra các hệ mã hóa khóa công khai và khóa bí mật. Các thuật toán trong lattice-based cryptography thường sử dụng các thuộc tính của cơ sở lưới để đảm bảo tính bảo mật của các hệ mã hóa.
Các tính chất của lattice basis
Các tính chất của lattice basis (cơ sở lưới) trong lattice-based cryptography bao gồm:
- Linear independence: Các vector cơ sở phải độc lập tuyến tính, nghĩa là không có vector nào trong tập hợp này có thể được biểu diễn bằng tổ hợp tuyến tính của các vector khác.
- Spanning: Các vector cơ sở phải đủ để tạo ra tất cả các điểm trong lưới.
- Shortest Vector Problem (SVP): SVP là vấn đề tìm kiếm vector ngắn nhất trong lưới. Nó là một trong những vấn đề quan trọng trong lattice-based cryptography, và các hệ mã hóa thường được thiết kế để làm cho việc giải quyết SVP là khó khăn.
- Closest Vector Problem (CVP): CVP là vấn đề tìm kiếm vector trong lưới gần với một vector bên ngoài lưới nhất định. Nó cũng là một vấn đề quan trọng trong lattice-based cryptography và các hệ mã hóa thường được thiết kế để làm cho việc giải quyết CVP là khó khăn.
- Basis Reduction: Bộ thuật toán basis reduction được sử dụng để tìm kiếm một cơ sở lưới tối ưu, với các vector cơ sở ngắn và đủ gần nhau. Thuật toán này là cơ sở cho các hệ mã hóa khóa công khai và khóa bí mật trong lattice-based cryptography.
- Orthogonality: Các vector cơ sở phải là vuông góc với nhau. Tính chất này giúp cho việc tính toán trong lattice-based cryptography dễ dàng hơn.
Tất cả các tính chất này đều rất quan trọng trong lattice-based cryptography và được sử dụng để tạo ra các hệ mã hóa khóa công khai và khóa bí mật an toàn và bảo mật.
Lattice dimension
Lattice dimension (kích thước lưới) là số vector trong một tập hợp cơ sở của lưới, được ký hiệu bằng k. Nó cũng tương đương với số chiều của không gian mà lưới được nhúng vào. Trong lattice-based cryptography, k thường được chọn là một số nguyên dương lớn để làm cho việc giải quyết các vấn đề lưới như SVP và CVP trở nên khó khăn.
Khi k tăng lên, lưới có thể chứa nhiều hơn các điểm và trở nên khó khăn hơn để giải quyết các vấn đề liên quan đến lưới, nhưng đồng thời cũng tăng độ phức tạp tính toán và tăng thời gian xử lý. Do đó, lựa chọn k phải cân bằng giữa độ an toàn và hiệu suất của hệ mã hóa.
Các tính chất của lattice dimension
Một số tính chất của lattice dimension (kích thước lưới) bao gồm:
- Độ an toàn của lưới tăng khi k tăng lên: Khi k tăng lên, lưới có nhiều hơn các điểm và trở nên khó khăn hơn để giải quyết các vấn đề liên quan đến lưới như tìm kiếm ngắn nhất đường vector (SVP) và tìm kiếm ngắn nhất đường vector tương đương (CVP).
- Độ phức tạp tính toán tăng khi k tăng lên: Khi k tăng lên, độ phức tạp tính toán để giải quyết các vấn đề liên quan đến lưới như SVP và CVP cũng tăng lên. Do đó, lựa chọn k phải cân bằng giữa độ an toàn và hiệu suất của hệ mã hóa.
- Kích thước lưới ảnh hưởng đến độ phức tạp tính toán: Khi lưới được sử dụng trong các hệ mã hóa, kích thước lưới ảnh hưởng đến độ phức tạp tính toán. Kích thước lưới lớn hơn sẽ làm tăng độ phức tạp tính toán và thời gian xử lý.
- Kích thước lưới ảnh hưởng đến bảo mật: Kích thước lưới cũng ảnh hưởng đến bảo mật của hệ mã hóa. Khi kích thước lưới quá nhỏ, nó dễ dàng bị tấn công bằng cách tìm kiếm ngắn nhất đường vector, trong khi khi kích thước lưới quá lớn, độ phức tạp tính toán và thời gian xử lý tăng lên, làm giảm hiệu suất của hệ mã hóa.
- Kích thước lưới phải được chọn cẩn thận: Kích thước lưới phải được chọn cẩn thận để đảm bảo độ an toàn và hiệu suất của hệ mã hóa. Một số thuật toán giải quyết các vấn đề liên quan đến lưới có thể tìm được vector ngắn nhất trong lưới, do đó, kích thước lưới cần phải đủ lớn để tránh bị tấn công. Tuy nhiên, quá nhiều vector trong lưới cũng làm tăng độ phức tạp tính toán và giảm hiệu suất của hệ mã hóa.
Lattice spacing
Lattice spacing trong mật mã học là khoảng cách giữa hai điểm lưới liên tiếp trên cùng một cạnh của lưới. Điều này có thể được biểu diễn bằng một số thực dương, thường được đại diện bằng ký hiệu α, được gọi là giá trị gần đúng của độ lớn của các vector đại diện cho điểm lưới.
Nói cách khác, lattice spacing là khoảng cách tối thiểu giữa hai điểm của lưới. Nó phụ thuộc vào cách định nghĩa của lattice basis, bởi vì lattice spacing bằng độ dài của các vector cột trong lattice basis. Lattice spacing càng nhỏ thì độ chặt chẽ của lưới càng lớn, và độ phức tạp của các thuật toán sử dụng lưới sẽ tăng lên.
Khi xây dựng hệ mã hóa sử dụng lưới, lattice spacing phải được chọn cẩn thận để đảm bảo tính an toàn của hệ thống. Nếu lattice spacing quá lớn, thì các thuật toán tấn công lưới có thể dễ dàng tìm kiếm ngắn nhất đường vector và đánh bại hệ thống. Nếu lattice spacing quá nhỏ, thì độ phức tạp của các thuật toán sử dụng lưới sẽ tăng lên, làm giảm hiệu suất của hệ thống.
Các tính chất lattice spacing
Một số tính chất của lattice spacing trong mật mã học là:
- Lattice spacing là một số thực dương, được đại diện bởi ký hiệu α.
- Lattice spacing phụ thuộc vào cách định nghĩa của lattice basis.
- Lattice spacing càng nhỏ thì độ chặt chẽ của lưới càng lớn, và độ phức tạp của các thuật toán sử dụng lưới sẽ tăng lên.
- Nếu lattice spacing quá lớn, thì các thuật toán tấn công lưới có thể tìm kiếm ngắn nhất đường vector và đánh bại hệ thống.
- Nếu lattice spacing quá nhỏ, thì độ phức tạp của các thuật toán sử dụng lưới sẽ tăng lên, làm giảm hiệu suất của hệ thống.
- Lattice spacing có thể được sử dụng để tính toán thời gian tìm kiếm ngắn nhất đường vector của một lưới, đóng vai trò quan trọng trong việc đánh giá tính an toàn của hệ thống.
- Việc chọn lattice spacing phải được thực hiện cẩn thận để đảm bảo tính an toàn của hệ thống.
Shortest Vector Problem (SVP)
Shortest Vector Problem (SVP) là một bài toán quan trọng trong lý thuyết lattice, nó yêu cầu tìm kiếm ngắn nhất đường vector trong một lattice. Cụ thể hơn, cho một lattice L được tạo bởi một tập các vector linearly independent, SVP yêu cầu tìm một vector v trong lattice L sao cho độ dài của nó là ngắn nhất. Tức là, tìm một vector v thuộc L sao cho ||v|| là nhỏ nhất có thể.
SVP là một trong những bài toán quan trọng nhất trong mật mã học lattice, nó được sử dụng để đánh giá tính an toàn của nhiều hệ thống mật mã lattice-based, bao gồm cả các thuật toán mã hóa, chữ ký và trao đổi khóa.
Tuy nhiên, SVP là một bài toán khó tính, có thể là không thể giải được trong thời gian đa thức. Với SVP, độ phức tạp tính toán tăng lên theo cấp số nhân khi kích thước của lattice tăng lên, do đó nó làm cho việc giải quyết bài toán này vô cùng khó khăn trên các lattice lớn. Các thuật toán hiện đại để giải quyết SVP phụ thuộc vào cấu trúc của lattice và thường chỉ đạt được hiệu quả trên các lattice đặc biệt.
Closest Vector Problem (CVP)
Closest Vector Problem (CVP) là một bài toán quan trọng trong lý thuyết lattice, nó yêu cầu tìm kiếm vector trong lattice gần nhất với một vector bên ngoài lattice cho trước. Cụ thể hơn, cho một lattice L được tạo bởi một tập các vector linearly independent, CVP yêu cầu tìm một vector v thuộc L sao cho khoảng cách từ v đến vector cho trước là nhỏ nhất có thể.
CVP cũng là một trong những bài toán quan trọng nhất trong mật mã học lattice-based, nó được sử dụng để đánh giá tính an toàn của nhiều hệ thống mật mã lattice-based, bao gồm cả các thuật toán mã hóa, chữ ký và trao đổi khóa.
Tuy nhiên, CVP là một bài toán khó tính, có thể là không thể giải được trong thời gian đa thức. Các thuật toán hiện đại để giải quyết CVP phụ thuộc vào cấu trúc của lattice và thường chỉ đạt được hiệu quả trên các lattice đặc biệt. Một cách tiếp cận thông thường để giải quyết CVP là thông qua thuật toán LLL (Lenstra–Lenstra–Lovász), một thuật toán đơn giản và hiệu quả cho các lattice có kích thước nhỏ.
