File size: 4,229 Bytes
7da464c | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
export enum Severity {
Critical = "Critical",
Warning = "Warning",
Info = "Info",
}
export interface ParamDiagnostic {
severity: Severity;
message: String;
suggestedFix?: String;
}
export interface ValidationResult {
n: number;
q: number;
betaOrSigma: number;
isCbd: boolean;
noiseBudgetMax: number;
noiseBudgetRms: number;
decryptionBudget: number;
failureProb: number;
expectedFailuresIn500: number;
passes: boolean;
diagnostics: ParamDiagnostic[];
suggestedBeta: number;
suggestedQ: number;
}
export class ParamValidator {
public static validateKyber(n: number, q: number, eta: number): ValidationResult {
const sigma = Math.sqrt(eta / 2.0);
const r = this.validateInner(n, q, sigma, true);
r.betaOrSigma = eta;
return r;
}
public static validateGaussian(n: number, q: number, sigma: number): ValidationResult {
return this.validateInner(n, q, sigma, false);
}
private static validateInner(n: number, q: number, noiseParam: number, isCbd: boolean): ValidationResult {
const qF = q;
const nF = n;
const stdPerCoeff = isCbd ? Math.sqrt(noiseParam / 2.0) : noiseParam;
const betaMax = isCbd ? noiseParam : 3.0 * stdPerCoeff;
// noise ≈ beta * sqrt(3 * n) * std_per_coeff
const noiseBudgetRms = stdPerCoeff * Math.sqrt(3.0 * nF) * betaMax;
const noiseBudgetMax = betaMax * betaMax * nF * 3.0;
const decryptionBudget = qF / 4.0;
const totalStd = stdPerCoeff * betaMax * Math.sqrt(3.0 * nF);
const z = decryptionBudget / Math.max(totalStd, 1e-10);
const failureProb = 2.0 * this.gaussianQFunction(z);
const expectedFailuresIn500 = failureProb * 500.0;
const passes = noiseBudgetRms < decryptionBudget * 0.8;
const diagnostics: ParamDiagnostic[] = [];
if (noiseBudgetMax >= decryptionBudget) {
diagnostics.push({
severity: Severity.Critical,
message: `WORST-CASE noise (${noiseBudgetMax.toFixed(1)}) EXCEEDS decryption budget (${decryptionBudget.toFixed(1)} = q/4). Decryption WILL fail for some inputs.`,
suggestedFix: `Either: (a) reduce β to ≤${Math.sqrt(decryptionBudget / (nF * 3.0)).toFixed(1)}, or (b) increase q to ≥${Math.ceil(noiseBudgetMax * 4.0)}`,
});
} else if (noiseBudgetRms >= decryptionBudget * 0.5) {
diagnostics.push({
severity: Severity.Warning,
message: `RMS noise (${noiseBudgetRms.toFixed(1)}) is ${(100.0 * noiseBudgetRms / decryptionBudget).toFixed(0)}% of budget. Failure rate ≈${(failureProb * 100).toFixed(2)}%.`,
suggestedFix: "Increase q by 2x or decrease β by √2",
});
} else {
diagnostics.push({
severity: Severity.Info,
message: `Noise budget OK: RMS noise ${noiseBudgetRms.toFixed(1)} is ${(100.0 * noiseBudgetRms / decryptionBudget).toFixed(0)}% of q/4.`,
});
}
const estimatedSecurity = this.estimateSecurityBits(n, q, stdPerCoeff);
if (estimatedSecurity < 80.0) {
diagnostics.push({
severity: Severity.Critical,
message: `Parameters provide only ~${estimatedSecurity.toFixed(0)} bits of security (need ≥128).`,
suggestedFix: "Use n≥256 and q≥3329 for any security claim",
});
}
return {
n,
q,
betaOrSigma: noiseParam,
isCbd,
noiseBudgetMax,
noiseBudgetRms,
decryptionBudget,
failureProb,
expectedFailuresIn500,
passes,
diagnostics,
suggestedBeta: Math.sqrt(decryptionBudget / (nF * 3.0)) * 0.5,
suggestedQ: Math.ceil(noiseBudgetMax * 8.0),
};
}
private static gaussianQFunction(z: number): number {
if (z > 10.0) return 0.0;
if (z < 0.0) return 1.0;
const t = 1.0 / (1.0 + 0.2316419 * z);
const poly = t * (0.319381530
+ t * (-0.356563782
+ t * (1.781477937
+ t * (-1.821255978
+ t * 1.330274429))));
const phi = Math.exp(-z * z / 2.0) / Math.sqrt(2.0 * Math.PI);
return phi * poly;
}
private static estimateSecurityBits(n: number, q: number, sigma: number): number {
const nF = n;
const qF = q;
const alpha = sigma / qF;
if (alpha <= 0.0) return 0.0;
return 0.265 * nF * (-Math.log2(alpha));
}
}
|