Haskell中Paillier部分同态加密的正负与浮点数处理方案问询

一、负数编码策略 #

1. 偏移量映射法 #

利用Paillier明文空间为模n（公钥核心参数）的特性，将负数映射到合法正整数区间：

• 编码：对于满足|x| < n/2的负数x，编码为n + x
• 解码：解密得到结果r后，若r > n/2，则转换为r - n

示例代码：

encodeNegative :: Integer -> Integer -> Integer
encodeNegative n x = if x < 0 then n + x else x

decodeNegative :: Integer -> Integer -> Integer
decodeNegative n r = if r > n `div` 2 then r - n else r

2. 模补码法 #

基于模n的补码规则处理负数：

• 编码：负数x的补码为n - abs x
• 解码：同偏移量法，判断结果是否超过n/2后转换为负数

二、浮点数编码改进方案 #

针对之前定点数编码在同态乘法中失效的问题，优化如下：

1. 定点数约束编码 #

• 选择精度系数k（如10^6），将浮点数f转换为整数x = round (f * k)
• 严格保证x落在明文安全区间(-n/2, n/2)内，若超出则调整k或选用更大的n
• 同态乘法执行后，对结果做mod n处理，确保回到明文空间
• 解码：解密得到r后，计算fromIntegral r / k

示例代码：

encodeFloat :: Integer -> Integer -> Double -> Integer
encodeFloat n k f = encodeNegative n (round (f * fromIntegral k))

decodeFloat :: Integer -> Integer -> Integer -> Double
decodeFloat n k r = fromIntegral (decodeNegative n r) / fromIntegral k

-- 同态乘法后修正逻辑
postMultiply :: Integer -> Integer -> Integer
postMultiply n cipher = cipher `mod` n

2. 分数编码（局限性较大） #

将浮点数表示为a/b的分数形式，分别加密分子a和分母b。但Paillier不支持同态除法，仅当b与n互质时，可通过模逆元实现解密后的除法，仅适用于特定场景。

三、修改cryptonite的expSafe函数支持负数模运算 #

若必须直接处理负数底数的模幂运算，可调整expSafe的逻辑：

• 对于(-a)^e mod m，转换规则为：
  • 当e为奇数：(m - (a^e mod m)) mod m
  • 当e为偶数：a^e mod m
• 先对底数取模m，确保绝对值小于m后再处理符号

修改后的核心逻辑示例：

import Crypto.Number.ModArithmetic (expSafe)

expSafeWithNegative :: Integer -> Integer -> Integer -> Integer
expSafeWithNegative base exp modu =
  let absBase = abs base
      baseMod = absBase `mod` modu
      rawResult = expSafe baseMod exp modu
  in if base < 0
     then if odd exp
          then (modu - rawResult) `mod` modu
          else rawResult
     else rawResult

最优策略建议 #

优先选择偏移量编码+定点数约束编码的组合方案，理由如下：

1. 无需修改底层库，兼容性强，维护成本低
2. 实现逻辑简洁，能覆盖绝大多数负数与浮点数的加密场景
3. 通过约束明文区间和运算后模n处理，可彻底解决同态乘法失效问题

仅当业务场景必须直接处理负数模幂时，再考虑修改expSafe函数，但需注意保留原函数的安全特性（如抗时序攻击）。

内容的提问来源于stack exchange，提问作者Abhiroop Sarkar