基于 Shamir 的秘密共享的模式的拉格朗日插值

Question

我正在尝试调试阈值加密方案实施的问题。我已经在 crypto 上发布了 this question 以获得有关实际方案的一些帮助，但希望对我正在使用的简化代码进行健全性检查。

本质上，加密系统使用 Shamir 的秘密共享来组合密钥的份额。多项式是列表 'a' 的每个成员乘以多项式参数的递增幂。我省略了 prime 的 mod 以简化代码，因为实际实现通过 Haskell 包装器使用 PBC。

我有多项式

poly :: [Integer] -> Integer -> Integer
poly as xi = (f 1 as)
  where
    f _ [] = 0
    f 0 _ = 0
    f s (a:as) = (a * s) + f (s * xi) as

拉格朗日插值是：

interp0 :: [(Integer, Integer)] -> Integer
interp0 xys = round (sum $ zipWith (*) ys $ fmap (f xs) xs)
  where
    xs = map (fromIntegral .fst) xys
    ys = map (fromIntegral .snd) xys

f :: (Eq a, Fractional a) => [a] -> a -> a
f xs xj = product $ map (p xj) xs

p :: (Eq a, Fractional a) => a -> a -> a
p xj xm = if xj == xm then 1 else negate (xm / (xj - xm))

拆分合并代码为

execPoly as@(a0:_) = do
  let xs = zipWith (,) [0..] (fmap (poly as) [0..100])
  let t = length as + 1
  let offset = 1
  let shares = take t (drop offset xs)
  let sm2 = interp0 shares
  putText ("poly and interp over " <> show as <> " = " <> show sm2 <> ". Should be " <> show a0)

main :: IO ()
main = do
  execPoly [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150] --1
  execPoly [10,20,30,40,50,60,70,80] -- 2

execPoly(1) 无法合并为 10，但 execPoly(2) 合并正确。魔法门槛好像是8.

我的代码正确吗？我在实施中遗漏了将阈值大小限制为 8 的内容？

Answer 1

正如 MathematicalOrchid 所说，这是一个精度问题。

将代码更新为：

f :: (Eq a, Integral a) => [a] -> a -> Ratio a
f xs xj = product $ map (p xj) xs

p :: (Eq a, Integral a)=> a -> a -> Ratio a
p xj xm = if xj == xm then (1 % 1) else (negate xm) % (xj - xm)

它按预期工作。

基于 Shamir 的秘密共享的模式的拉格朗日插值

Lagrange Interpolation for a schema based on Shamir's Secret Sharing

interpolation

haskell

cryptography

polynomials