来点MAYO，搭配你的油和醋吗？

你的油醋酱里要加点 Mayo 吗？

NIST 不希望我们依赖基于格的方法进行数字签名，并且可能也认为它们的签名大小对于许多应用来说有点过大。为此，Dilithium 方法现已由 NIST 标准化为 ML-DSA，对于等效于 128 位安全性的级别，它提供了 1,312 字节的公钥和 2,420 字节的签名。虽然公钥大小可能可以接受，但签名大小对于某些应用来说可能有点大。对于 SLH-DSA，我们有一种基于哈希的方法，它提供了小密钥，但签名大小相当大。

第二轮附加签名方案

因此，NIST 一直在寻找替代方案，其第二轮竞争者包括：

• 多元签名 (4): MAYO, QR-UOV, SNOVA, 和 UOV (非对称油醋法)。
• MPC-in-the-Head 签名 (5): MIRA/MiRitH (MinRank in the Head), MQOM (MQ on my Mind), PERK, RYDE, 和 SDitH (Syndrome Decoding in the Head)。
• 基于格的签名 (1): HAWK。
• 基于代码的签名 (2): CROSS (Codes and Restricted Objects Signature), 和 LESS (Linear Equivalence)。
• 基于对称的签名 (1): FAEST。
• 基于同源的签名 (1): SQIsign。

非对称油醋法 (UOV)

一个众所周知的难题是求解包含 m 个方程和 n 个变量的二次方程。这是一个已知的 NP 难问题，即使在量子计算机的世界中也是如此。这些可以被用作后量子签名方案，其中涉及多元方程。为了理解这些方法，本文概述了一个实现油醋法的简单例子，其中我们有若干个未知油变量和若干个已知醋变量，并且醋变量有助于将难题转化为简单问题。该方法定义在 此处。

多元方法通常由非对称油醋法 (UOV) 定义，该方法旨在提供良好的性能水平和相当不错的密钥大小。但是，在 2022 年 2 月，一篇论文以一个简单的破解，动摇了自 1999 年以来一直存在的参数定义：

因此，让 UOV 重新步入正轨花了一些时间，但正如我们所见，NIST 目前正在评估四种方法。

这些方法

MAYO 具有可接受的公钥大小（对于 128 位安全性为 1,420 字节）和 454 字节的小签名大小：

Method   Sec level    Security  Public key Private key   Signature
-----------------------------------------------------------------------------------------------------
Dilithium2           2     SUF-CMA        1312        2528        2420
Dilithium3           3     SUF-CMA        1952        4000        3293
Dilithium5           5     SUF-CMA        2592        4864        4595
ML-DSA-44           2     SUF-CMA        1312        2560        2420
ML-DSA-65           3     SUF-CMA        1952        4032        3309
ML-DSA-87           5     SUF-CMA        2592        4896        4627
Falcon-512           1     EUF-CMA         897        1281         752
Falcon-1024           5     EUF-CMA        1793        2305        1462
MAYO-1           1     EUF-CMA        1420          24         454
MAYO-2           1     EUF-CMA        4912          24         186
MAYO-3           3     EUF-CMA        2986          32         681
MAYO-5           5     EUF-CMA        5554          40         964

UOV (非对称油醋法) 密码学方法，给出了以下密钥大小：

Method              Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
UOV Level I         278,432            237,896             128         1 (128-bit) Multivariate
UOV Level III       1,225,440          1,044,320           200         3 (192-bit) Multivariate
UOV Level V         2,869,440          2,436,704            260         5 (256-bit) Multivariate

我们看到公钥很大，但签名大小很小。一个有前途的方法是 SNOVA (基于简单非交换环的 UOV，具有密钥随机性对齐)，它具有可接受的公钥大小，但也设法支持相当小的签名大小：

Method          Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
SNOVA-I         1,016                   48                 240        1 (128-bit) Multivariate
SNOVA-III       4,104                   64                 376        3 (192-bit) Multivariate
SNOVA-IV        8,016                   80                 576        5 (256-bit) Multivariate

在性能方面，MAYO 和 SNOVA 比 Dilithium 稍慢，而 UOV 则慢很多：

因此，MAYO 和 SNOVA — 由于其较小的公钥和签名，以及合理的性能 — 看起来是标准化的有力竞争者。OUV 不太可能继续推进，因为它公钥较大，并且比其他 UOV 方法更慢。

Zig 和 Liboqs 实现

为了评估这些方法，我们可以使用 Liboqs 库。在这种情况下，我们有一个用于与 Liboqs 接口的 Zig 程序 [ 此处]：

onst std = @import("std");

const c = @cImport({
    @cInclude("oqs/oqs.h");
});

fn oqsCheck(rc: c_int, what: []const u8) !void {
    // OQS_SUCCESS == 0
    if (rc == c.OQS_SUCCESS) return;
    std.debug.print("{s} failed (rc={d})\n", .{ what, rc });
    return error.OqsError;
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Zig 0.15.2 标准输出写入器模式
    var stdout_buffer: [4096]u8 = undefined;
    var stdout_writer = std.fs.File.stdout().writer(&stdout_buffer);
    const stdout = &stdout_writer.interface;

    const args = try std.process.argsAlloc(allocator);
    defer std.process.argsFree(allocator, args);

    const msg: []const u8 = args[1];

    // "ML-DSA-44", "ML-DSA-65", "ML-DSA-87"
    const alg_name = args[2];

    // 我们需要以 NUL 结尾的 C 字符串用于 OQS_SIG_new
    const alg_z = try std.fmt.allocPrint(allocator, "{s}", .{alg_name});
    defer allocator.free(alg_z);

    const sig_obj = c.OQS_SIG_new(alg_z.ptr);
    defer c.OQS_SIG_free(sig_obj);

    const pk_len: usize = sig_obj.*.length_public_key;
    const sk_len: usize = sig_obj.*.length_secret_key;

    const sig_len_max: usize = sig_obj.*.length_signature;

    const pk = try allocator.alloc(u8, pk_len);
    defer allocator.free(pk);
    const sk = try allocator.alloc(u8, sk_len);
    defer allocator.free(sk);

    // 生成密钥对 (sk - 私钥, pk - 公钥)
    try oqsCheck(c.OQS_SIG_keypair(sig_obj, pk.ptr, sk.ptr), "OQS_SIG_keypair");
    try stdout.print("Verify 5\n", .{});
    try stdout.flush();

    // 使用私钥 (sk) 签署消息
    var signature = try allocator.alloc(u8, sig_len_max);
    defer allocator.free(signature);

    var sig_len: usize = 0;

    try oqsCheck(
        c.OQS_SIG_sign(sig_obj, signature.ptr, &sig_len, msg.ptr, msg.len, sk.ptr),
        "OQS_SIG_sign",
    );
    signature = signature[0..sig_len];

    // 使用公钥 (pk) 验证签名
    const vrc = c.OQS_SIG_verify(sig_obj, msg.ptr, msg.len, signature.ptr, signature.len, pk.ptr);
    const ok = (vrc == c.OQS_SUCCESS);

    try stdout.print("Liboqs. Algorithm: {s}\n", .{alg_name});
    try stdout.print("Message: {s}\n\n", .{msg});

    if (sk_len > 200) {
        try stdout.print("Private key (first 200 bytes): {x} Length: {d}\n\n", .{ sk[0..200], sk_len });
    } else try stdout.print("Private key: {x} Length: {d}\n\n", .{ sk, sk_len });

    if (pk_len > 200) {
        try stdout.print("Public key (first 200 bytes): {x} Length: {d}\n\n", .{ pk[0..200], pk_len });
    } else try stdout.print("Private key: {x} Length: {d}\n\n", .{ pk, pk_len });

    if (sig_len > 200) {
        try stdout.print("Signature (first 200 bytes): {x} Length: {d}\n\n", .{ signature[0..200], sig_len });
    } else try stdout.print("Private key: {x} Length: {d}\n\n", .{ signature, sig_len });

    try stdout.print("Verify: {s}\n\n", .{if (ok) "OK" else "FAIL"});

    try stdout.flush();
}

我们可以使用 Zig 和 liboqs.lib 库进行编译：

zig build-exe zig_liboqs_mldsa.zig -I C:\home\liboqs\build\include  -lc liboqs.lib -target x86_64-windows

对于 MAYO-1，我们得到 454 字节的签名大小和 1,420 字节的公钥大小 [ 此处]：

liboqs version: 0.14.1-dev
Method:     MAYO-1
Message:    Qwerty 123
Version source: round2
======================================================
Public key size:    1420
Private key size:   24
Signature size:     454

Keypair gen time:       7.00 ms
Signature time:         2.00 ms
Verification time:      0.00 ms

Public key (First 200 bytes): 3c0dd0669b062df367a5133430c7382a5f856adf3faae3b8b4c19924891467bb14ab2046a50f6626f6dafa76b41dfc70d767a750e749252187be4d65b5ad6dcf3097ffd1975d734f2a58f6607c27ffcbace546db6bee842fec3939cf0fa4a03979a8478ad182607b42073d7029f155eb2aa6747bca6e6551a8c5a5b810d0453b796d542ec0a300b2f9ed0580b5a53e140211c0cb1ad4ea0865ef572701d200728571011e4ec7a235362e969c7f731bb71cd580d64fefaf08134b35e28aa73b6ea7c8a0b1b6ea96c3

Public key (First 200 bytes): 1dc6f8b4bab9c1f5a22e16997731eb46a0c342137b63098e

Signature (First 200 bytes): 30709cabf67f000037709cabf67f000001010000000000008c050000000000001800000000000000c601000000000000a0b046abf67f000060b146abf67f000070b146abf67f0000a0b146abf67f0000c0b146abf67f0000fb0ba0eb00070090803295b150020000803295b150020000000000000000000002000000000000000100000000000000e07295b15002000000000000000000000900000000000000000000000000000001000000000000000000000000000000fd0bbaeb0008008053006f0066007400
Signature verifies

对于 SNOVA_24_5_4，我们得到 248 字节的小签名大小和 1,016 字节的公钥 [ 此处]：

liboqs version: 0.14.1-dev
Method:     SNOVA_24_5_4
Message:    Qwerty 123
Version source: round2
======================================================
Public key size:    1016
Private key size:   48
Signature size:     248

Keypair gen time:       5.00 ms
Signature time:         4.00 ms
Verification time:      3.00 ms

Public key (First 200 bytes): 77a2af055b8c5c0d8b13205a412948fd3f8144495d1b9be81a88670000114ddec8a4bb8cef68d0cae2217b063650883306936e0b282e87c4da25ca1c3c2af23b30e81aa3759057fea23c9300bce5d86ff00bcb60cfd401cb268cbe400e9f1a183286d30416063262b95670a682a8885a3fc4d02c98cd497389da95259bac61ae911ba38105185383816a6ba5a7ee9c43411ec61c874f7835dc67ba56b9511e590df3798f0fa11cf149e8ecfdad0ccb4071f9a78e4623238dfaed5e60b93ecca5ce5b8e9423be3e7d

Public key (First 200 bytes): 77a2af055b8c5c0d8b13205a412948fdf763af058822951e188c80f51641a1ee8a0b6a811e9f280d78fb3ff36390c1f0

Signature (First 200 bytes): 107a9cabf67f00001d7a9cabf67f00000101000000000000f8030000000000003000000000000000f80000000000000090c746abf67f000050c846abf67f000060c846abf67f000090c846abf67f0000b0c846abf67f0000efcf996c0004009050371c661e02000050371c661e0200000000000000000000ffffffff000000000200000000000000000000000000000090741c661e0200000900000000000000000000000000000002000000000000000000000000000000e9cfa76c0005008053006f0066007400
Signature verifies

结论

虽然 Rainbow 方法在安全性上被证明是薄弱的，但研究人员有望能解决这些问题，并提出更好的方法。当然，这就是研究的意义所在。我认为 SNOVA 和 MAYO 在标准化方面表现良好，并有望看到多元密码学被大规模采用。对此，我感到很高兴。

• 原文链接： billatnapier.medium.com/...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～