cbd.go 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
  1. // cbd.go - Centered binomial distribution.
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to the software, using the Creative
  5. // Commons "CC0" public domain dedication. See LICENSE or
  6. // <http://creativecommons.org/publicdomain/zero/1.0/> for full details.
  7. package kyber
  8. // Load bytes into a 64-bit integer in little-endian order.
  9. func loadLittleEndian(x []byte, bytes int) uint64 {
  10. var r uint64
  11. for i, v := range x[:bytes] {
  12. r |= uint64(v) << (8 * uint(i))
  13. }
  14. return r
  15. }
  16. // Given an array of uniformly random bytes, compute polynomial with
  17. // coefficients distributed according to a centered binomial distribution
  18. // with parameter eta.
  19. func (p *poly) cbd(buf []byte, eta int) {
  20. switch eta {
  21. case 3:
  22. var a, b [4]uint32
  23. for i := 0; i < kyberN/4; i++ {
  24. t := loadLittleEndian(buf[3*i:], 3)
  25. var d uint32
  26. for j := 0; j < 3; j++ {
  27. d += uint32((t >> uint(j)) & 0x249249)
  28. }
  29. a[0] = d & 0x7
  30. b[0] = (d >> 3) & 0x7
  31. a[1] = (d >> 6) & 0x7
  32. b[1] = (d >> 9) & 0x7
  33. a[2] = (d >> 12) & 0x7
  34. b[2] = (d >> 15) & 0x7
  35. a[3] = (d >> 18) & 0x7
  36. b[3] = (d >> 21)
  37. p.coeffs[4*i+0] = uint16(a[0] + kyberQ - b[0])
  38. p.coeffs[4*i+1] = uint16(a[1] + kyberQ - b[1])
  39. p.coeffs[4*i+2] = uint16(a[2] + kyberQ - b[2])
  40. p.coeffs[4*i+3] = uint16(a[3] + kyberQ - b[3])
  41. }
  42. case 4:
  43. var a, b [4]uint32
  44. for i := 0; i < kyberN/4; i++ {
  45. t := loadLittleEndian(buf[4*i:], 4)
  46. var d uint32
  47. for j := 0; j < 4; j++ {
  48. d += uint32((t >> uint(j)) & 0x11111111)
  49. }
  50. a[0] = d & 0xf
  51. b[0] = (d >> 4) & 0xf
  52. a[1] = (d >> 8) & 0xf
  53. b[1] = (d >> 12) & 0xf
  54. a[2] = (d >> 16) & 0xf
  55. b[2] = (d >> 20) & 0xf
  56. a[3] = (d >> 24) & 0xf
  57. b[3] = (d >> 28)
  58. p.coeffs[4*i+0] = uint16(a[0] + kyberQ - b[0])
  59. p.coeffs[4*i+1] = uint16(a[1] + kyberQ - b[1])
  60. p.coeffs[4*i+2] = uint16(a[2] + kyberQ - b[2])
  61. p.coeffs[4*i+3] = uint16(a[3] + kyberQ - b[3])
  62. }
  63. case 5:
  64. var a, b [4]uint64
  65. for i := 0; i < kyberN/4; i++ {
  66. t := loadLittleEndian(buf[5*i:], 5)
  67. var d uint64
  68. for j := 0; j < 5; j++ {
  69. d += (t >> uint(j)) & 0x0842108421
  70. }
  71. a[0] = d & 0x1f
  72. b[0] = (d >> 5) & 0x1f
  73. a[1] = (d >> 10) & 0x1f
  74. b[1] = (d >> 15) & 0x1f
  75. a[2] = (d >> 20) & 0x1f
  76. b[2] = (d >> 25) & 0x1f
  77. a[3] = (d >> 30) & 0x1f
  78. b[3] = (d >> 35)
  79. p.coeffs[4*i+0] = uint16(a[0] + kyberQ - b[0])
  80. p.coeffs[4*i+1] = uint16(a[1] + kyberQ - b[1])
  81. p.coeffs[4*i+2] = uint16(a[2] + kyberQ - b[2])
  82. p.coeffs[4*i+3] = uint16(a[3] + kyberQ - b[3])
  83. }
  84. default:
  85. panic("kyber: eta must be in {3,4,5}")
  86. }
  87. }