A somewhat-homomorphic (insecure) cryptosystem
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

trostle-parrish.go 2.4KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
  1. package trostle_parrish
  2. import (
  3. "crypto/rand"
  4. "math/big"
  5. )
  6. // TrostleParrish implements a somewhat-homomorphic cryptosystem outlined by [1] and [2]
  7. // [1] Trostle, Jonathan, and Andy Parrish. "Efficient computationally private information retrieval from anonymity or trapdoor groups." International Conference on Information Security. Springer, Berlin, Heidelberg, 2010.
  8. // [2] Mayberry, Travis, Erik-Oliver Blass, and Agnes Hui Chan. "PIRMAP: Efficient private information retrieval for MapReduce." International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2013.
  9. type TrostleParrish struct {
  10. m, b, T, N *big.Int
  11. // We precompute these values.
  12. bInv *big.Int
  13. twon *big.Int
  14. }
  15. // More readable type definitions
  16. type Ciphertext *big.Int
  17. // Generate sets up a Trostle-Parish cryptosystem
  18. // This system is "somewhat-homomorphic"
  19. // 2^t = number of additions to support
  20. // n = max plaintext bit size
  21. func Generate(t int, n int) (pk TrostleParrish) {
  22. for {
  23. // choose secret m and b
  24. pk.m, _ = rand.Prime(rand.Reader, (t*2)+n)
  25. pk.b, _ = rand.Int(rand.Reader, pk.m)
  26. pk.N = big.NewInt(int64(n))
  27. pk.twon = new(big.Int).Exp(big.NewInt(2), pk.N, pk.m)
  28. // T is our parameter that determines how many addition operations we can safely do
  29. tbi := big.NewInt(int64(n/t))
  30. pk.T = new(big.Int).Exp(big.NewInt(2), tbi, pk.m)
  31. // Check that b has an inverse mod m
  32. pk.bInv = new(big.Int).ModInverse(pk.b, pk.m)
  33. for pk.bInv != nil {
  34. return
  35. }
  36. }
  37. }
  38. // Encrypt takes in a Plaintext(x) and a keyset (pk)
  39. func (pk TrostleParrish) Encrypt(x *big.Int) Ciphertext {
  40. r, _ := rand.Int(rand.Reader, pk.T)
  41. // r * 2^n
  42. rtwon := new(big.Int).Mul(r, pk.twon)
  43. // r * 2^n + x
  44. rtwonx := new(big.Int).Add(rtwon, x)
  45. // b * (r * 2^n + x)
  46. bmod := new(big.Int).Mul(pk.b, rtwonx)
  47. // b * (r * 2^n + x) mod m
  48. return new(big.Int).Mod(bmod, pk.m)
  49. }
  50. // Add two ciphertexts together and return the result.
  51. // Note that the number of meaningful additions is limited by the encryption parameters
  52. func Add(a Ciphertext, b Ciphertext) Ciphertext {
  53. return new(big.Int).Add(a, b)
  54. }
  55. // Decrypt takes in a Ciphertext(c) and Keyset(pk) and outputs the Plaintext
  56. func (pk TrostleParrish) Decrypt(c Ciphertext) *big.Int {
  57. // b^-1 * c
  58. plaintext := new(big.Int).Mul(pk.bInv, c)
  59. // b^-1 * c mod m
  60. modm := new(big.Int).Mod(plaintext, pk.m)
  61. // b^-1 * c mod m mod 2^n
  62. return new(big.Int).Mod(modm, pk.twon)
  63. }