 # Polynomial Secret Keys

Sep 19th, 2020 (edited)
1,024
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
3. import {Tensor, arange} from "ds.cf"
4.
5. data Point = (Num x, Num y)
6.
7. -- Solving for the secret
8.
9. points_to_xy_tensors :: [Points] ->> (Tensor.1D, Tensor.1D)
10. pts => (Tensor.1D pts@\.x, Tensor.1D pts@\.y)
11.
12. polynomial :: Tensor.1D, Tensor.Scalar ->> Tensor.Scalar
13. -- P here is the list of coefficients, starting from the x^0 coef
14. P, x => zip P [0..] >\ (y, (p, i) => y + p * x ** i) 0
15.
16. vandermonde_matrix :: Int, Tensor.1D ->> Tensor.2D
17. N, x => (x ** (arange N)[:, Empty]).T
18.
19. polyfit_weights :: Tensor.1D, Tensor.1D, Int ->> Tensor.1D
20. xs, ys, n => lstqs (_vm xs) ys
21. where _vm = vandermonde_matrix n
22.
23. try_to_get_secret :: [Point] ->> Num
24. keys => polynomial (polyfit_weights xs ys keys.length) 0
25. where xs, ys = points_to_xy_tensors keys
26.
27. -- Generating the secret / keys
28.
29. WEIGHT_HIGHER_BOUND = Static 3
30. WEIGHT_LOWER_BOUND = Static -3
31. KEY_HIGHER_BOUND = Static 100
32. KEY_LOWER_BOUND = Static 100
33.
34. random_weights :: Int ->> Random Tensor.1D
35. n => Tensor.Random.rand WEIGHT_LOWER_BOUND WEIGHT_HIGHER_BOUND [n]
36.
37. random_polynomial :: Int ->> Random (Tensor.Scalar ->> Tensor.Scalar)
38. n => polynomial (random_weights n) <0?>
39.
40. polynomial_with_secret :: Num, Int ->> Random (Tensor.Scalar ->> Tensor.Scalar)
41. secret, n => polynomial Tensor.1D [secret, ... random_weights n-1] <0?>
42.
43. get_keys :: (Tensor.Scalar ->> Tensor.Scalar), Int ->> Random [Tensor.Scalar]
44. f, n ~> {
45.     f, n => f, Tensor.Random.rand KEY_LOWER_BOUND KEY_HIGHER_BOUND [n],
46.     f, r => r @\ (x => Point(x, f x))
47. }
RAW Paste Data