Bài báo này trình bày về động cơ phát triển loại hình mật mã này, một số nguyên thủy mật mã đối xứng hạng nhẹ và giới thiệu thuật toán mật mã khóa công khai hạng nhẹ GPS.

Động cơ thúc đẩy phát triển
Mật mã hạng nhẹ hướng tới việc tạo ra các giải pháp cài đặt rất gọn nhẹ nhưng không làm giảm quá nhiều về tính an toàn. Nó là một giải pháp đưa ra thỏa hiệp giữa độ an toàn và tính hiệu quả trong cài đặt của các thuật toán mật mã.
Ngày càng nhiều các sản phẩm được nâng cấp thành các thiết bị thâm nhập khắp nơi nhờ năng lực tính toán nhúng. Quan hệ mật thiết giữa các thiết bị này dẫn đến triển vọng rằng tính toán khắp nơi sẽ là mô hình tiếp theo trong công nghệ thông tin.
Việc triển khai hàng loạt của các thiết bị thâm nhập khắp nơi hứa hẹn đem đến nhiều lợi ích như chi phí “hậu cần” thấp hơn, các chuỗi cung cấp được tối ưu hoặc có thêm các dịch vụ dựa trên xác định vị trí. Ví dụ, công nghệ RFID được tin là công nghệ cho phép đối với liên mạng của các vật dụng (internet of things). Về cơ bản, các thẻ RFID bao gồm một hệ thống phát nhận tín hiệu và một anten có khả năng nhận dữ liệu từ xa, từ một máy chủ RFID hoặc thiết bị đọc. Nhìn chung, các thẻ RFID có thể được chia thành các thiết bị chủ động và bị động: các thẻ chủ động  được trang bị nguồn cung cấp năng lượng riêng (ví dụ ở dạng  pin), trong khi các thẻ bị động chỉ dựa vào năng lượng của tín hiệu mạng được truyền đi bởi thiết bị đọc. Do vậy, các thiết bị RFID bị động không chỉ rẻ hơn, mà còn có kích thước chip nhỏ hơn và có chu kỳ sống lâu hơn.
Tính thâm nhập khắp nơi của thiết bị dẫn đến việc triển khai hàng loạt và việc triển khai hàng loạt lại kéo theo các ràng buộc giảm giá thành đối với công nghệ được sử dụng. Các cài đặt phần mềm thông thường bị ràng buộc về dung lượng của bộ xử lý, bộ nhớ và năng lượng. Vấn đề năng lượng có thể được giải quyết trong quá trình thiết kế bằng cách tránh các truy cập tiêu thụ năng lượng tới bộ nhớ EEPROM hoặc bộ nhớ Flash và bằng cách giảm các chu kỳ đồng hồ được yêu cầu. Các đòi hỏi giảm chi phí đưa đến các yêu cầu năng lực, năng lượng và diện tích cần phải giữ cực tiểu đối với ASIC. Một thẻ RFID giá thành thấp, đầy đủ tính năng, có thể có từ 1.000 đến 10.000 GE (Gate Equivalent), trong đó, các thành phần an toàn chỉ có khoảng 200 - 2.000 GE.
Bên cạnh những lợi ích ở trên, tính toán khắp nơi cũng chứa đựng nhiều hiểm họa. Nhiều ứng dụng yêu cầu cao về độ an toàn, chẳng hạn như các mạng cảm biến không dây cho các ứng dụng quân sự, tài chính hoặc tự động hóa.
Một nhân tố làm tăng nguy cơ mất an toàn là các thiết bị thâm nhập khắp nơi thường triển khai trong một môi trường không được kiểm soát mà là một môi trường mà đối phương có thể truy cập vật lý tới thiết bị hoặc điều khiển thiết bị. Điều đó làm tăng thêm khả năng tấn công vật lý vào các kịch bản tấn công tiềm năng, nhất là các tấn công kênh kề, chẳng hạn như phân tích năng lượng vi sai/phân tích năng lượng tương quan hoặc các tấn công bức xạ điện từ. Thực tế đã chỉ ra rằng, các giải pháp an toàn có sử dụng một thuật toán an toàn về mặt mật mã, nhưng được cài đặt không có các biện pháp chống tấn công kênh kề thì có thể dễ dàng bị phá bởi các tấn công như vậy. Vì thế, khả năng an toàn của bản thân việc cài đặt cần được hết sức chú trọng.

Các nguyên thủy mật mã đối xứng hạng nhẹ
ECRYPT (European Network of Excellence for Cryptology) là một sáng kiến nghiên cứu về mật mã ở châu Âu, được bắt đầu vào năm 2004. ECRYPT đã giới thiệu 4 loại nguyên thủy mật mã là mã khối, mã dòng, hàm băm và mã xác thực thông báo. Những thuật toán đã được đề cập đến bao gồm: Mã khối (DESXL, HIGHT, KASUMI, KATAN, KTANTAN, mCRYPTON, PRESENT, SEA và XTEA), Mã dòng (Grain  1, Grain - 128, MICKEY v2 và Trivium), Hàm băm (MAME, DM-PRESENT, H-PRESEN, Keccak, Quark và Armadillo), Mã xác thực thông báo (SQUASH).
Những báo cáo liên quan tới thuật toán mật mã đối xứng hạng nhẹ cũng đã được trình bày trong hội nghị ECRYPT 2011 như: Mã khối (PUFFIN, PUFFIN2, LBlock, Piccolo, TWINE) và Hàm băm (SPONGENT).

Mật mã khóa công khai hạng nhẹ
Sự phát triển nhanh chóng của giao dịch điện tử trên toàn thế giới tạo ra nhu cầu lớn đối với các giải pháp mật mã khóa công khai an toàn, nhanh và giá thành thấp. Bên cạnh tính bí mật, các nhà mật mã học cần giải quyết hai bài toán quan trọng là xác thực và cung cấp chữ ký số. Một số lược đồ mật mã đã được đề xuất để giải quyết các vấn đề này.
Để đánh giá ưu việt của các lược đồ đã được đề xuất, 3 tính chất chính được đưa ra xem xét, trong đó, quan trọng nhất là độ an toàn. Rõ ràng, một hệ thống được chấp nhận rộng rãi bởi được khẳng định rằng không có ai có khả năng hủy hoại nó. Tất nhiên điều này là quan trọng, nhưng trong nhiều ứng dụng, nó không đủ đảm bảo thỏa mãn yêu cầu về độ an toàn. Một cách khác là cố gắng chứng minh độ an toàn theo nghĩa toán học, tức là, thiết lập các định lý mà khẳng định rằng thực hiện các hành động không hợp pháp, chẳng hạn như mạo danh, cũng khó như việc giải một bài toán cụ thể mà tính khó của nó đã được xác định.
Tiếp theo, kích thước của dữ liệu trong lược đồ có một ý nghĩa thực hành quan trọng. Người ta thường dùng các khóa riêng và khóa công khai ngắn, nhất là khi chúng được lưu trong các thiết bị gọn nhẹ như các thẻ chip, có khả năng lưu trữ nhỏ. Chúng ta cũng muốn giảm lượng thông tin truyền phát và độ dài của các chữ ký. Độ dài chữ ký là một tham số quan trọng trong các ứng dụng, mà đối với chúng nhiều chữ ký cần phải được lưu trữ (ví dụ, trong giao dịch điện tử) hoặc phải truyền đi (ví dụ, truyền hình trả tiền).
Tính chất quan trọng khác là độ phức tạp thời gian, nó trực tiếp chi phối giá thành của các thiết bị có thể cài đặt một lược đồ. Ở đây, cần phải phân biệt giữa những tính toán có thể thực hiện trước (không trực tuyến và được lưu kết quả trong bộ nhớ) với những tính toán phải thực hiện trực tuyến trong quá trình xác thực hoặc tính toán chữ ký. Yếu tố sau thường là điểm “nghẽn cổ chai” của nhiều ứng dụng, đặc biệt khi sử dụng các thẻ thông minh.
Một nhược điểm đã được biết đến của các nguyên thủy mật mã khóa công khai là chúng đòi hỏi chi phí tính toán lớn hơn so với các nguyên thủy mật mã đối xứng hạng nhẹ. Việc thiết kế được một thuật toán mật mã khóa công khai thuộc hạng nhẹ khó hơn so với việc thiết kế ra một thuật toán mật mã đối xứng hạng nhẹ. Chính vì vậy mà có rất ít các nguyên thủy mật mã khóa công khai được coi là hạng nhẹ. Trên trang web của ECRYPT về mật mã hạng nhẹ không nói tới các thuật toán mật mã khóa công khai hạng nhẹ. Tuy nhiên, trong hội nghị ECRYPT về Mật mã hạng nhẹ năm 2011 có đề cập đến 2 giao thức xác thực là Ring- LPN và CANAuth.
Một thuật toán mật mã khóa công khai như vậy đã được đề xuất ứng dụng trong thực tế là GPS (tên ba tác giả của thuật toán là Marc Girault, Guillaume Poupard và Jacques Stern).
GPS được gọi là thuật toán “khi đang chạy” (on the fly), do ứng dụng điển hình của GPS là xác thực xe ôtô “khi đang chạy” tại điểm trả tiền cầu đường. Ý tưởng đầu tiên là trang bị cho mỗi xe ôtô được cấp phép một thẻ thông minh không tiếp xúc với giá thành thấp. Khi xe chạy qua một điểm thu phí, nó không phải dừng mà chỉ cần thực hiện một xác thực GPS để chứng minh rằng nó là một người dùng hợp pháp. Trong một ứng dụng như vậy, thời gian cho phép để truyền dữ liệu và thực hiện các tính toán trực tuyến là rất ngắn, khoảng 100 ms.
Lược đồ GPS đã được đề xuất lần đầu bởi Girault tại hội nghị Eurocrypt 91, như một ví dụ của một lược đồ cùng với các khóa công khai tự chứng thực (self- certified) nhưng không có phân tích độ an toàn. Sau đó, phiên bản đầu tiên của phép chứng minh độ an toàn cho lược đồ GPS đã được báo cáo tại hội nghị Eurocrypt 98. Một tài liệu phát hành năm 2002 đã mô tả những bước hoàn thiện bao gồm: mô hình phân tích độ an toàn chính xác hơn, phép chứng minh độ an toàn đầy đủ hơn, nhiều chi tiết kỹ thuật đã được sắp xếp lại và chỉ giả thiết về tính khó của việc tính các logarit rời rạc cùng với các số mũ ngắn.
Lược đồ GPS đã được đệ trình tới dự án NESSIE của châu Âu và được đưa vào dự án như một nguyên thủy mật mã mạnh. Lược đồ xác thực GPS và lược đồ chữ ký số GPS đã được ISO/IEC chuẩn hoá.
Bài báo “Some Modes of Use of the GPS Identification Scheme” có trình bày chi tiết, mô tả lược đồ xác thực GPS và lược đồ chữ ký GPS. Những ưu điểm của hai lược đồ mật mã này như sau:
- Chúng thuộc dạng an toàn chứng minh được. Phép chứng minh được dựa trên bài toán logarit rời rạc trên nhóm hữu hạn tùy ý.
- Chúng có kích thước khóa ngắn, kích thước chữ ký và các thông tin truyền phát ngắn.
- Chúng được thực hiện với các tính toán trực tuyến cực tiểu. Phép nhân theo modulo cũng được tránh, mà thay vào đó là phép nhân bình thường của các số nguyên.
- Được thực hiện mà không cần phải biết bậc của nhóm cũng như không cần biết bậc của phần tử cơ sở của nhóm.
Bài báo cũng trình bày việc lựa chọn các tham số cùng với các kích thước mà được cho là an toàn vào thời điểm năm 2006, ví dụ như kích thước của nhóm là 1536 bit, đồng thời cũng đưa ra những kết quả cài đặt thử nghiệm. Trên máy tính Pentium III với bộ xử lý tốc độ 450 MHz và chương trình phần mềm C sử dụng thư viện số học có độ chính xác bội GMP, lược đồ nhận thực GPS có thể đạt tới các khoảng thời gian tính toán như sau:
- Sinh tham số: khoảng 1 giây.
- Người chứng minh tính “cam kết”: 10,1 ms (5940 lần trong 1 phút).
- Người chứng minh tính “phúc đáp”: nhỏ hơn 1 ms.
- Người kiểm tra xác minh: 11,8 ms (5084 lần trong 1 phút).
Cũng lược đồ xác thực đó, nhưng khi thực hiện trên ứng dụng thẻ thông minh dựa trên chip 6805 thì kích thước chương trình rất nhỏ, chỉ khoảng 300 byte. Thời gian tính toán nhỏ (dưới 2ms), còn phần lớn thời gian là để cho nhu cầu liên lạc giữa thẻ và máy tính. Nếu tốc độ truyền tin là 9600 bauds thì thời gian truyền tin là 38 ms và tổng thời gian là 40 ms, còn nếu tốc độ truyền tin là 115000 bauds thì thời gian truyền tin là 3,1 ms và tổng thời gian là 5ms.

Năm 2009, một luận án tiến sĩ đã trình bày việc thiết kế một chip phần cứng thực hiện giao thức GPS, nhưng trên nhóm các điểm đường cong ellip.