File size: 6,618 Bytes
9d232fb fd14a7f 9d232fb fd14a7f 9d232fb 8cf3619 9d232fb 8cf3619 9d232fb 8cf3619 9d232fb 8cf3619 2ae5160 8cf3619 076a42b 9d232fb | 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 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 | use serde::{Deserialize, Serialize};
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub enum Severity {
Critical,
Warning,
Info,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct ParamDiagnostic {
pub severity: Severity,
pub message: String,
pub suggested_fix: Option<String>,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct ValidationResult {
pub n: usize,
pub q: u64,
pub beta_or_sigma: f64,
pub is_cbd: bool,
pub noise_budget_max: f64,
pub noise_budget_rms: f64,
pub decryption_budget: f64,
pub failure_prob: f64,
pub expected_failures_in_500: f64,
pub passes: bool,
pub diagnostics: Vec<ParamDiagnostic>,
pub suggested_beta: f64,
pub suggested_q: u64,
}
pub struct ParamValidator;
impl ParamValidator {
pub fn validate_lwe(n: usize, q: u64, beta: f64) -> ValidationResult {
Self::validate_inner(n, q, beta, false)
}
pub fn validate_kyber(n: usize, q: u64, eta: usize) -> ValidationResult {
let mut r = Self::validate_inner(n, q, eta as f64, true);
r.beta_or_sigma = eta as f64;
r
}
pub fn validate_gaussian(n: usize, q: u64, sigma: f64) -> ValidationResult {
Self::validate_inner(n, q, sigma, false)
}
fn validate_inner(n: usize, q: u64, noise_param: f64, is_cbd: bool) -> ValidationResult {
let q_f = q as f64;
let n_f = n as f64;
let std_per_coeff = if is_cbd {
(noise_param / 2.0).sqrt()
} else {
noise_param
};
let beta_max = if is_cbd { noise_param } else { 3.0 * std_per_coeff };
let noise_budget_rms = std_per_coeff * (3.0 * n_f).sqrt() * beta_max;
let noise_budget_max = beta_max * beta_max * n_f * 3.0;
let decryption_budget = q_f / 4.0;
let total_std = std_per_coeff * beta_max * (3.0 * n_f).sqrt();
let z = decryption_budget / total_std.max(1e-10);
let failure_prob = 2.0 * gaussian_q_function(z);
let expected_failures_in_500 = failure_prob * 500.0;
let passes = noise_budget_rms < decryption_budget * 0.8;
let mut diagnostics = Vec::new();
if noise_budget_max >= decryption_budget && expected_failures_in_500 > 1e-3 {
diagnostics.push(ParamDiagnostic {
severity: Severity::Critical,
message: format!(
"WORST-CASE noise ({:.1}) EXCEEDS expected limit and probability of failure is high. Decryption WILL fail for some inputs.",
noise_budget_max
),
suggested_fix: Some(format!(
"Either: (a) reduce β to ≤{:.1}, or (b) increase q to ≥{}",
(decryption_budget / (n_f * 3.0)).sqrt(),
(noise_budget_max * 4.0).ceil() as u64
)),
});
} else if noise_budget_max >= decryption_budget {
diagnostics.push(ParamDiagnostic {
severity: Severity::Info,
message: format!(
"WORST-CASE noise bound ({:.1}) exceeds budget ({:.1}), but failure probability is low. Typical for practical RLWE.",
noise_budget_max, decryption_budget
),
suggested_fix: None,
});
} else if noise_budget_max > decryption_budget * 0.85 {
diagnostics.push(ParamDiagnostic {
severity: Severity::Warning,
message: format!(
"WORST-CASE noise ({:.1}) is dangerously close to budget ({:.1}). Rare failures may occur.",
noise_budget_max, decryption_budget
),
suggested_fix: Some("Increase q or decrease noise to increase margin".to_string()),
});
} else if noise_budget_rms >= decryption_budget * 0.5 {
diagnostics.push(ParamDiagnostic {
severity: Severity::Warning,
message: format!(
"RMS noise ({:.1}) is {:.0}% of budget ({:.1}). Failure rate ≈{:.2}%. Marginal parameters.",
noise_budget_rms,
100.0 * noise_budget_rms / decryption_budget,
decryption_budget,
failure_prob * 100.0
),
suggested_fix: Some("Increase q by 2x or decrease β by √2".to_string()),
});
} else {
diagnostics.push(ParamDiagnostic {
severity: Severity::Info,
message: format!(
"Noise budget OK: RMS noise {:.1} is {:.0}% of q/4={:.1}.",
noise_budget_rms,
100.0 * noise_budget_rms / decryption_budget,
decryption_budget
),
suggested_fix: None,
});
}
let estimated_security = estimate_security_bits(n, q, std_per_coeff);
if estimated_security < 80.0 {
diagnostics.push(ParamDiagnostic {
severity: Severity::Critical,
message: format!(
"Parameters provide only ~{:.0} bits of security (need ≥128).",
estimated_security
),
suggested_fix: Some("Use n≥256 and q≥3329 for any security claim".to_string()),
});
}
let suggested_beta = (decryption_budget / (n_f * 3.0)).sqrt() * 0.5;
let suggested_q = (noise_budget_max * 8.0).ceil() as u64;
ValidationResult {
n,
q,
beta_or_sigma: noise_param,
is_cbd,
noise_budget_max,
noise_budget_rms,
decryption_budget,
failure_prob,
expected_failures_in_500,
passes,
diagnostics,
suggested_beta,
suggested_q,
}
}
}
fn gaussian_q_function(z: f64) -> f64 {
if z > 10.0 { return 0.0; }
if z < 0.0 { return 1.0; }
let t = 1.0 / (1.0 + 0.2316419 * z);
let poly = t * (0.319381530
+ t * (-0.356563782
+ t * (1.781477937
+ t * (-1.821255978
+ t * 1.330274429))));
let phi = (-z * z / 2.0).exp() / (2.0 * std::f64::consts::PI).sqrt();
phi * poly
}
fn estimate_security_bits(n: usize, q: u64, sigma: f64) -> f64 {
let n_f = n as f64;
let q_f = q as f64;
let alpha = sigma / q_f;
if alpha <= 0.0 { return 0.0; }
0.265 * n_f * (-alpha.log2())
}
|