feature. See also
. The project being documented here (as the example) is the Zig library itself.
ml_dsa.MLDSAImpl
fn MLDSAImpl(comptime p: Params) type
File
Code
fn MLDSAImpl(comptime p: Params) type {
return struct {
pub const params = p;
pub const name = p.name;
pub const gamma1: u32 = @as(u32, 1) << p.gamma1_bits;
pub const beta: u32 = p.tau * p.eta;
pub const alpha: u32 = 2 * p.gamma2;
const Self = @This();
const PolyVecL = PolyVec(p.l);
const PolyVecK = PolyVec(p.k);
const MatKxL = Mat(p.k, p.l);
pub const seed_length: usize = 32;
pub const noise_length = 32;
pub const public_key_bytes: usize = 32 + polyT1PackedSize() * p.k;
pub const private_key_bytes: usize = 32 + 32 + p.tr_size +
polyLeqEtaPackedSize() * (p.l + p.k) + polyT0PackedSize() * p.k;
pub const signature_bytes: usize = p.ctilde_size +
polyLeGamma1PackedSize() * p.l + p.omega + p.k;
fn polyLeqEtaPackedSize() usize {
// For eta=4: 4 bits per coefficient (values in [0,8])
const double_eta_bits = if (p.eta == 2) 3 else 4;
return (N * double_eta_bits) / 8;
}
fn polyLeGamma1PackedSize() usize {
return ((p.gamma1_bits + 1) * N) / 8;
}
fn polyT1PackedSize() usize {
return (N * (Q_BITS - D)) / 8;
}
fn polyT0PackedSize() usize {
return (N * D) / 8;
}
fn polyW1PackedSize() usize {
return (N * (Q_BITS - p.gamma1_bits)) / 8;
}
fn crh(comptime outsize: usize, inputs: anytype) [outsize]u8 {
var h = sha3.Shake256.init(.{});
inline for (inputs) |input| {
h.update(input);
}
var out: [outsize]u8 = undefined;
h.squeeze(&out);
return out;
}
fn computeT(A: MatKxL, s1_hat: PolyVecL, s2: PolyVecK) PolyVecK {
const t = A.mulVec(s1_hat).add(s2);
return t.normalize();
}
pub const PublicKey = struct {
pub const encoded_length: usize = 32 + polyT1PackedSize() * p.k;
rho: [32]u8,
t1: PolyVecK,
// Cached values
t1_packed: [polyT1PackedSize() * p.k]u8,
A: MatKxL,
tr: [p.tr_size]u8,
pub fn toBytes(self: PublicKey) [encoded_length]u8 {
var out: [encoded_length]u8 = undefined;
@memcpy(out[0..32], &self.rho);
@memcpy(out[32..], &self.t1_packed);
return out;
}
pub fn fromBytes(bytes: [encoded_length]u8) !PublicKey {
var pk: PublicKey = undefined;
@memcpy(&pk.rho, bytes[0..32]);
@memcpy(&pk.t1_packed, bytes[32..]);
pk.t1 = PolyVecK.unpackT1(pk.t1_packed[0..]);
pk.A = MatKxL.derive(&pk.rho);
pk.tr = crh(p.tr_size, .{&bytes});
return pk;
}
};
pub const SecretKey = struct {
pub const encoded_length: usize = 32 + 32 + p.tr_size +
polyLeqEtaPackedSize() * (p.l + p.k) + polyT0PackedSize() * p.k;
rho: [32]u8,
key: [32]u8,
tr: [p.tr_size]u8,
s1: PolyVecL,
s2: PolyVecK,
t0: PolyVecK,
// Cached values (in NTT domain)
A: MatKxL,
s1_hat: PolyVecL,
s2_hat: PolyVecK,
t0_hat: PolyVecK,
pub fn toBytes(self: SecretKey) [encoded_length]u8 {
var out: [encoded_length]u8 = undefined;
var offset: usize = 0;
@memcpy(out[offset .. offset + 32], &self.rho);
offset += 32;
@memcpy(out[offset .. offset + 32], &self.key);
offset += 32;
@memcpy(out[offset .. offset + p.tr_size], &self.tr);
offset += p.tr_size;
if (p.eta == 2) {
self.s1.packLeqEta(2, out[offset..][0 .. p.l * polyLeqEtaPackedSize()]);
} else {
self.s1.packLeqEta(4, out[offset..][0 .. p.l * polyLeqEtaPackedSize()]);
}
offset += p.l * polyLeqEtaPackedSize();
if (p.eta == 2) {
self.s2.packLeqEta(2, out[offset..][0 .. p.k * polyLeqEtaPackedSize()]);
} else {
self.s2.packLeqEta(4, out[offset..][0 .. p.k * polyLeqEtaPackedSize()]);
}
offset += p.k * polyLeqEtaPackedSize();
self.t0.packT0(out[offset..][0 .. p.k * polyT0PackedSize()]);
offset += p.k * polyT0PackedSize();
return out;
}
pub fn fromBytes(bytes: [encoded_length]u8) !SecretKey {
var sk: SecretKey = undefined;
var offset: usize = 0;
@memcpy(&sk.rho, bytes[offset .. offset + 32]);
offset += 32;
@memcpy(&sk.key, bytes[offset .. offset + 32]);
offset += 32;
@memcpy(&sk.tr, bytes[offset .. offset + p.tr_size]);
offset += p.tr_size;
sk.s1 = if (p.eta == 2)
PolyVecL.unpackLeqEta(2, bytes[offset..][0 .. p.l * polyLeqEtaPackedSize()])
else
PolyVecL.unpackLeqEta(4, bytes[offset..][0 .. p.l * polyLeqEtaPackedSize()]);
offset += p.l * polyLeqEtaPackedSize();
sk.s2 = if (p.eta == 2)
PolyVecK.unpackLeqEta(2, bytes[offset..][0 .. p.k * polyLeqEtaPackedSize()])
else
PolyVecK.unpackLeqEta(4, bytes[offset..][0 .. p.k * polyLeqEtaPackedSize()]);
offset += p.k * polyLeqEtaPackedSize();
sk.t0 = PolyVecK.unpackT0(bytes[offset..][0 .. p.k * polyT0PackedSize()]);
offset += p.k * polyT0PackedSize();
sk.A = MatKxL.derive(&sk.rho);
sk.s1_hat = sk.s1.ntt();
sk.s2_hat = sk.s2.ntt();
sk.t0_hat = sk.t0.ntt();
return sk;
}
pub fn public(self: *const SecretKey) PublicKey {
var pk: PublicKey = undefined;
pk.rho = self.rho;
pk.A = self.A;
pk.tr = self.tr;
// Using power2Round: t = t1 * 2^D + t0
const t = computeT(self.A, self.s1_hat, self.s2);
var t0_unused: PolyVecK = undefined;
pk.t1 = t.power2Round(&t0_unused);
pk.t1.packT1(&pk.t1_packed);
return pk;
}
pub fn signer(self: *const SecretKey, noise: ?[noise_length]u8) !Signer {
return self.signerWithContext(noise, "");
}
pub fn signerWithContext(self: *const SecretKey, noise: ?[noise_length]u8, context: []const u8) ContextTooLongError!Signer {
return Signer.init(self, noise, context);
}
};
pub fn newKeyFromSeed(seed: *const [seed_length]u8) struct { pk: PublicKey, sk: SecretKey } {
var sk: SecretKey = undefined;
var pk: PublicKey = undefined;
const e_seed = crh(128, .{ seed, &[_]u8{ p.k, p.l } });
@memcpy(&pk.rho, e_seed[0..32]);
const s_seed = e_seed[32..96];
@memcpy(&sk.key, e_seed[96..128]);
@memcpy(&sk.rho, &pk.rho);
sk.A = MatKxL.derive(&pk.rho);
pk.A = sk.A;
const s_seed_array: *const [64]u8 = s_seed[0..64];
for (0..p.l) |i| {
sk.s1.ps[i] = expandS(p.eta, s_seed_array, @intCast(i));
}
for (0..p.k) |i| {
sk.s2.ps[i] = expandS(p.eta, s_seed_array, @intCast(p.l + i));
}
sk.s1_hat = sk.s1.ntt();
sk.s2_hat = sk.s2.ntt();
const t = computeT(sk.A, sk.s1_hat, sk.s2);
pk.t1 = t.power2Round(&sk.t0);
sk.t0_hat = sk.t0.ntt();
pk.t1.packT1(&pk.t1_packed);
const pk_bytes = pk.toBytes();
const tr = crh(p.tr_size, .{&pk_bytes});
sk.tr = tr;
pk.tr = tr;
return .{ .pk = pk, .sk = sk };
}
pub const Signature = struct {
pub const encoded_length: usize = p.ctilde_size +
polyLeGamma1PackedSize() * p.l + p.omega + p.k;
c_tilde: [p.ctilde_size]u8,
z: PolyVecL,
hint: PolyVecK,
pub fn toBytes(self: Signature) [encoded_length]u8 {
var out: [encoded_length]u8 = undefined;
var offset: usize = 0;
@memcpy(out[offset .. offset + p.ctilde_size], &self.c_tilde);
offset += p.ctilde_size;
self.z.packLeGamma1(p.gamma1_bits, out[offset .. offset + polyLeGamma1PackedSize() * p.l]);
offset += polyLeGamma1PackedSize() * p.l;
_ = self.hint.packHint(p.omega, out[offset..]);
return out;
}
pub fn fromBytes(bytes: [encoded_length]u8) EncodingError!Signature {
var sig: Signature = undefined;
var offset: usize = 0;
@memcpy(&sig.c_tilde, bytes[offset .. offset + p.ctilde_size]);
offset += p.ctilde_size;
sig.z = PolyVecL.unpackLeGamma1(p.gamma1_bits, bytes[offset .. offset + polyLeGamma1PackedSize() * p.l]);
offset += polyLeGamma1PackedSize() * p.l;
if (sig.z.exceeds(gamma1 - beta)) {
return error.InvalidEncoding;
}
sig.hint = PolyVecK.unpackHint(p.omega, bytes[offset..]) orelse return error.InvalidEncoding;
return sig;
}
pub const VerifyError = Verifier.InitError || Verifier.VerifyError;
pub fn verify(
sig: Signature,
msg: []const u8,
public_key: PublicKey,
) VerifyError!void {
return sig.verifyWithContext(msg, public_key, "");
}
pub fn verifyWithContext(
sig: Signature,
msg: []const u8,
public_key: PublicKey,
context: []const u8,
) VerifyError!void {
if (context.len > 255) {
return error.SignatureVerificationFailed;
}
var h = sha3.Shake256.init(.{});
h.update(&public_key.tr);
h.update(&[_]u8{0});
h.update(&[_]u8{@intCast(context.len)});
if (context.len > 0) {
h.update(context);
}
h.update(msg);
var mu: [64]u8 = undefined;
h.squeeze(&mu);
const z_hat = sig.z.ntt();
const Az = public_key.A.mulVecHat(z_hat);
var Az2dct1 = public_key.t1.mulBy2toD();
Az2dct1 = Az2dct1.ntt();
const c_poly = sampleInBall(p.tau, &sig.c_tilde);
const c_hat = c_poly.ntt();
for (0..p.k) |i| {
Az2dct1.ps[i] = Az2dct1.ps[i].mulHat(c_hat);
}
Az2dct1 = Az.sub(Az2dct1);
Az2dct1 = Az2dct1.reduceLe2Q();
Az2dct1 = Az2dct1.invNTT();
Az2dct1 = Az2dct1.normalizeAssumingLe2Q();
var w1_prime = Az2dct1.useHint(sig.hint, p.gamma2);
var w1_packed: [polyW1PackedSize() * p.k]u8 = undefined;
w1_prime.packW1(p.gamma1_bits, &w1_packed);
const c_prime = crh(p.ctilde_size, .{ &mu, &w1_packed });
if (!mem.eql(u8, &c_prime, &sig.c_tilde)) {
return error.SignatureVerificationFailed;
}
}
pub fn verifier(self: Signature, public_key: PublicKey) !Verifier {
return self.verifierWithContext(public_key, "");
}
pub fn verifierWithContext(self: Signature, public_key: PublicKey, context: []const u8) ContextTooLongError!Verifier {
return Verifier.init(self, public_key, context);
}
};
pub const Signer = struct {
h: sha3.Shake256,
secret_key: *const SecretKey,
rnd: [32]u8,
pub fn init(secret_key: *const SecretKey, noise: ?[noise_length]u8, context: []const u8) ContextTooLongError!Signer {
if (context.len > 255) {
return error.ContextTooLong;
}
var h = sha3.Shake256.init(.{});
h.update(&secret_key.tr);
h.update(&[_]u8{0});
h.update(&[_]u8{@intCast(context.len)});
if (context.len > 0) {
h.update(context);
}
return Signer{
.h = h,
.secret_key = secret_key,
.rnd = noise orelse @splat(0),
};
}
pub fn update(self: *Signer, data: []const u8) void {
self.h.update(data);
}
pub fn finalize(self: *Signer) Signature {
var mu: [64]u8 = undefined;
self.h.squeeze(&mu);
const rho_prime = crh(64, .{ &self.secret_key.key, &self.rnd, &mu });
var sig: Signature = undefined;
var y_nonce: u16 = 0;
var attempt: u32 = 0;
while (true) {
attempt += 1;
if (attempt >= 576) {
@branchHint(.unlikely);
unreachable;
}
const y = PolyVecL.deriveUniformLeGamma1(p.gamma1_bits, &rho_prime, y_nonce);
y_nonce += @intCast(p.l);
const y_hat = y.ntt();
var w = self.secret_key.A.mulVec(y_hat);
w = w.normalize();
var w0: PolyVecK = undefined;
const w1 = w.decomposeVec(p.gamma2, &w0);
var w1_packed: [polyW1PackedSize() * p.k]u8 = undefined;
w1.packW1(p.gamma1_bits, &w1_packed);
sig.c_tilde = crh(p.ctilde_size, .{ &mu, &w1_packed });
const c_poly = sampleInBall(p.tau, &sig.c_tilde);
const c_hat = c_poly.ntt();
var w0mcs2: PolyVecK = undefined;
for (0..p.k) |i| {
w0mcs2.ps[i] = c_hat.mulHat(self.secret_key.s2_hat.ps[i]);
w0mcs2.ps[i] = w0mcs2.ps[i].invNTT();
}
w0mcs2 = w0.sub(w0mcs2);
w0mcs2 = w0mcs2.normalize();
if (w0mcs2.exceeds(p.gamma2 - beta)) {
continue;
}
for (0..p.l) |i| {
sig.z.ps[i] = c_hat.mulHat(self.secret_key.s1_hat.ps[i]);
sig.z.ps[i] = sig.z.ps[i].invNTT();
}
sig.z = sig.z.add(y);
sig.z = sig.z.normalize();
if (sig.z.exceeds(gamma1 - beta)) {
continue;
}
var ct0: PolyVecK = undefined;
for (0..p.k) |i| {
ct0.ps[i] = c_hat.mulHat(self.secret_key.t0_hat.ps[i]);
ct0.ps[i] = ct0.ps[i].invNTT();
}
ct0 = ct0.reduceLe2Q();
ct0 = ct0.normalize();
if (ct0.exceeds(p.gamma2)) {
continue;
}
var w0mcs2pct0 = w0mcs2.add(ct0);
w0mcs2pct0 = w0mcs2pct0.reduceLe2Q();
w0mcs2pct0 = w0mcs2pct0.normalizeAssumingLe2Q();
const hint_result = PolyVecK.makeHintVec(w0mcs2pct0, w1, p.gamma2);
if (hint_result.pop > p.omega) {
continue;
}
sig.hint = hint_result.hint;
return sig;
}
}
};
pub const Verifier = struct {
h: sha3.Shake256,
signature: Signature,
public_key: PublicKey,
pub const InitError = EncodingError;
pub const VerifyError = SignatureVerificationError;
pub fn init(signature: Signature, public_key: PublicKey, context: []const u8) ContextTooLongError!Verifier {
if (context.len > 255) {
return error.ContextTooLong;
}
var h = sha3.Shake256.init(.{});
h.update(&public_key.tr);
h.update(&[_]u8{0});
h.update(&[_]u8{@intCast(context.len)});
if (context.len > 0) {
h.update(context);
}
return Verifier{
.h = h,
.signature = signature,
.public_key = public_key,
};
}
pub fn update(self: *Verifier, data: []const u8) void {
self.h.update(data);
}
pub fn verify(self: *Verifier) SignatureVerificationError!void {
var mu: [64]u8 = undefined;
self.h.squeeze(&mu);
const z_hat = self.signature.z.ntt();
const Az = self.public_key.A.mulVecHat(z_hat);
var Az2dct1 = self.public_key.t1.mulBy2toD();
Az2dct1 = Az2dct1.ntt();
const c_poly = sampleInBall(p.tau, &self.signature.c_tilde);
const c_hat = c_poly.ntt();
for (0..p.k) |i| {
Az2dct1.ps[i] = Az2dct1.ps[i].mulHat(c_hat);
}
Az2dct1 = Az.sub(Az2dct1);
Az2dct1 = Az2dct1.reduceLe2Q();
Az2dct1 = Az2dct1.invNTT();
Az2dct1 = Az2dct1.normalizeAssumingLe2Q();
var w1_prime = Az2dct1.useHint(self.signature.hint, p.gamma2);
var w1_packed: [polyW1PackedSize() * p.k]u8 = undefined;
w1_prime.packW1(p.gamma1_bits, &w1_packed);
const c_prime = crh(p.ctilde_size, .{ &mu, &w1_packed });
if (!mem.eql(u8, &c_prime, &self.signature.c_tilde)) {
return error.SignatureVerificationFailed;
}
}
};
pub const KeyPair = struct {
pub const seed_length = Self.seed_length;
public_key: PublicKey,
secret_key: SecretKey,
pub fn generate(io: std.Io) KeyPair {
var seed: [Self.seed_length]u8 = undefined;
io.random(&seed);
return generateDeterministic(seed) catch unreachable;
}
pub fn generateDeterministic(seed: [32]u8) !KeyPair {
const keys = newKeyFromSeed(&seed);
return .{
.public_key = keys.pk,
.secret_key = keys.sk,
};
}
pub fn fromSecretKey(sk: SecretKey) !KeyPair {
var pk: PublicKey = undefined;
pk.rho = sk.rho;
pk.tr = sk.tr;
pk.A = sk.A;
const t = computeT(sk.A, sk.s1_hat, sk.s2);
var t0: PolyVecK = undefined;
pk.t1 = t.power2Round(&t0);
pk.t1.packT1(&pk.t1_packed);
return .{
.public_key = pk,
.secret_key = sk,
};
}
pub fn signer(self: *const KeyPair, noise: ?[noise_length]u8) !Signer {
return self.secret_key.signer(noise);
}
pub fn signerWithContext(self: *const KeyPair, noise: ?[noise_length]u8, context: []const u8) ContextTooLongError!Signer {
return self.secret_key.signerWithContext(noise, context);
}
pub fn sign(
kp: KeyPair,
msg: []const u8,
noise: ?[noise_length]u8,
) !Signature {
return kp.signWithContext(msg, noise, "");
}
pub fn signWithContext(
kp: KeyPair,
msg: []const u8,
noise: ?[noise_length]u8,
context: []const u8,
) ContextTooLongError!Signature {
var st = try kp.signerWithContext(noise, context);
st.update(msg);
return st.finalize();
}
};
};
}