fhe.nx source

1// fhe.nx -- fully homomorphic encryption scaffold. 2// 3// EFFICIENCY_ROADMAP §6.1. Compute on ciphertext; the party 4// holding the key never sees plaintext, yet gets the right 5// answer. Targets privacy-preserving analytics, untrusted 6// compute substrates (cloud as "hostile arithmetic factory"). 7// 8// Schemes available today: 9// BFV / BGV -- exact integer arithmetic, SIMD-friendly 10// CKKS -- approximate real arithmetic, batching 11// TFHE -- binary / bit-level, fast bootstrapping 12// 13// Each has its own complexity tradeoffs. Our scaffold exposes 14// a uniform API (`fhe_add`, `fhe_mul`, `fhe_rotate`) + a 15// scheme-selector enum; dispatchable backends land later. 16// 17// Full implementations are ENORMOUS: OpenFHE is ~200k LoC C++, 18// SEAL is ~100k. Phase A here is API-locking + noise-budget 19// accounting so library code that wants to "maybe run FHE 20// someday" can be written in terms of the right abstractions 21// now. 22// 23// Invariants: 24// FHE1 All ciphertext operations are CONSTANT time in the 25// plaintext (leaking neither value nor sign). 26// FHE2 Every op consumes "noise budget"; fhe_budget_left 27// reports remaining. Bootstrap refreshes (expensive). 28// FHE3 Decrypt with the wrong key produces random garbage, 29// NOT an error indication -- semantic security. 30 31import "syscalls.nx" 32 33const FHE_SCHEME_BFV: i64 = 1 34const FHE_SCHEME_BGV: i64 = 2 35const FHE_SCHEME_CKKS: i64 = 3 36const FHE_SCHEME_TFHE: i64 = 4 37 38const FHE_ERR_PENDING: i64 = -1 39const FHE_ERR_BUDGET: i64 = -2 40 41// Opaque handles. The actual ciphertext can be MB in size; 42// we keep a descriptor with metadata + a pointer to heap 43// storage. 44struct FHECtx { 45 scheme: i64, 46 plain_modulus: i64, 47 poly_degree: i64, // typically 2^12 .. 2^15 48 noise_budget: i64, // decreasing; refresh via bootstrap 49} 50 51struct FHECipher { 52 ctx: *FHECtx, 53 data: *u8, // scheme-specific blob 54 data_bytes: i64, 55 noise_used: i64, // consumed portion of budget 56} 57 58// Create a fresh context for a given scheme. 59func fhe_ctx_new(scheme: i64, plain_mod: i64, poly_n: i64) -> *FHECtx { 60 let raw: *u8 = sys_mmap(32) 61 let c: *FHECtx = raw as *FHECtx 62 c.scheme = scheme 63 c.plain_modulus = plain_mod 64 c.poly_degree = poly_n 65 c.noise_budget = 120 // typical starting budget (bits) 66 return c 67} 68 69// Encrypt a plaintext integer. Phase A produces a dummy 70// "ciphertext" that's just the plaintext XOR'd with a constant; 71// replace with real BFV encrypt when the full impl lands. 72func fhe_encrypt(c: *FHECtx, pt: i64) -> *FHECipher { 73 let raw: *u8 = sys_mmap(64) 74 let ct: *FHECipher = raw as *FHECipher 75 ct.ctx = c 76 ct.data_bytes = 8 77 let data: *u8 = sys_mmap(16) 78 ct.data = data 79 let data_i: *i64 = data as *i64 80 *data_i = pt ^ 0xA5A5A5A5 81 ct.noise_used = 0 82 return ct 83} 84 85// Decrypt. Phase A undoes the XOR. 86func fhe_decrypt(c: *FHECtx, ct: *FHECipher) -> i64 { 87 let data_i: *i64 = ct.data as *i64 88 return *data_i ^ 0xA5A5A5A5 89} 90 91// Homomorphic addition. Noise grows slowly (linear in # ops). 92func fhe_add(a: *FHECipher, b: *FHECipher) -> *FHECipher { 93 // Phase A: XOR the plaintext-xor'd ciphertexts. This works 94 // by coincidence for XOR-based scheme but misses the rich 95 // structure of real FHE. 96 let raw: *u8 = sys_mmap(64) 97 let r: *FHECipher = raw as *FHECipher 98 r.ctx = a.ctx 99 r.data_bytes = 8 100 let data: *u8 = sys_mmap(16) 101 r.data = data 102 let a_i: *i64 = a.data as *i64 103 let b_i: *i64 = b.data as *i64 104 let pa: i64 = *a_i ^ 0xA5A5A5A5 105 let pb: i64 = *b_i ^ 0xA5A5A5A5 106 let r_i: *i64 = data as *i64 107 *r_i = (pa + pb) ^ 0xA5A5A5A5 108 r.noise_used = a.noise_used + b.noise_used + 1 109 return r 110} 111 112// Homomorphic multiply. Noise grows multiplicatively. 113func fhe_mul(a: *FHECipher, b: *FHECipher) -> *FHECipher { 114 let raw: *u8 = sys_mmap(64) 115 let r: *FHECipher = raw as *FHECipher 116 r.ctx = a.ctx 117 r.data_bytes = 8 118 let data: *u8 = sys_mmap(16) 119 r.data = data 120 let a_i: *i64 = a.data as *i64 121 let b_i: *i64 = b.data as *i64 122 let pa: i64 = *a_i ^ 0xA5A5A5A5 123 let pb: i64 = *b_i ^ 0xA5A5A5A5 124 let r_i: *i64 = data as *i64 125 *r_i = (pa * pb) ^ 0xA5A5A5A5 126 r.noise_used = a.noise_used + b.noise_used + 20 127 return r 128} 129 130// How many bits of noise budget remain before a bootstrap 131// refresh becomes necessary. 132func fhe_budget_left(ct: *FHECipher) -> i64 { 133 return ct.ctx.noise_budget - ct.noise_used 134} 135 136// Bootstrap: reset noise budget via a costly homomorphic 137// re-encryption. Phase A is a no-op. 138func fhe_bootstrap(ct: *FHECipher) -> i64 { 139 ct.noise_used = 0 140 return 0 141} 142 143// Compile-only smoke. 144func main() -> i64 { 145 let ctx: *FHECtx = fhe_ctx_new(FHE_SCHEME_BFV, 65537, 4096) 146 if ctx.noise_budget != 120 { return 1 } 147 148 let e1: *FHECipher = fhe_encrypt(ctx, 5) 149 let e2: *FHECipher = fhe_encrypt(ctx, 7) 150 let sum: *FHECipher = fhe_add(e1, e2) 151 let prod: *FHECipher = fhe_mul(e1, e2) 152 if fhe_decrypt(ctx, sum) != 12 { return 2 } 153 if fhe_decrypt(ctx, prod) != 35 { return 3 } 154 if fhe_budget_left(sum) >= 120 { return 4 } // noise consumed 155 fhe_bootstrap(sum) 156 if sum.noise_used != 0 { return 5 } 157 return 0 158}