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

Question

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

本质上，加密系统使用Shamir的秘密共享来组合密钥的份额。多项式是列表'a‘中的每个成员乘以多项式的参数的递增幂。为了简化代码，我省略了mod by prime，因为实际实现通过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)

它的工作方式和预期的一样。