polyvec.go 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
  1. // polyvec.go - Vector of Kyber polynomials.
  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. type polyVec struct {
  9. vec []*poly
  10. }
  11. // Compress and serialize vector of polynomials.
  12. func (v *polyVec) compress(r []byte) {
  13. var off int
  14. for _, vec := range v.vec {
  15. for j := 0; j < kyberN/8; j++ {
  16. var t [8]uint16
  17. for k := 0; k < 8; k++ {
  18. t[k] = uint16((((uint32(freeze(vec.coeffs[8*j+k])) << 11) + kyberQ/2) / kyberQ) & 0x7ff)
  19. }
  20. r[off+11*j+0] = byte(t[0] & 0xff)
  21. r[off+11*j+1] = byte((t[0] >> 8) | ((t[1] & 0x1f) << 3))
  22. r[off+11*j+2] = byte((t[1] >> 5) | ((t[2] & 0x03) << 6))
  23. r[off+11*j+3] = byte((t[2] >> 2) & 0xff)
  24. r[off+11*j+4] = byte((t[2] >> 10) | ((t[3] & 0x7f) << 1))
  25. r[off+11*j+5] = byte((t[3] >> 7) | ((t[4] & 0x0f) << 4))
  26. r[off+11*j+6] = byte((t[4] >> 4) | ((t[5] & 0x01) << 7))
  27. r[off+11*j+7] = byte((t[5] >> 1) & 0xff)
  28. r[off+11*j+8] = byte((t[5] >> 9) | ((t[6] & 0x3f) << 2))
  29. r[off+11*j+9] = byte((t[6] >> 6) | ((t[7] & 0x07) << 5))
  30. r[off+11*j+10] = byte((t[7] >> 3))
  31. }
  32. off += compressedCoeffSize
  33. }
  34. }
  35. // De-serialize and decompress vector of polynomials; approximate inverse of
  36. // polyVec.compress().
  37. func (v *polyVec) decompress(a []byte) {
  38. var off int
  39. for _, vec := range v.vec {
  40. for j := 0; j < kyberN/8; j++ {
  41. vec.coeffs[8*j+0] = uint16((((uint32(a[off+11*j+0]) | ((uint32(a[off+11*j+1]) & 0x07) << 8)) * kyberQ) + 1024) >> 11)
  42. vec.coeffs[8*j+1] = uint16(((((uint32(a[off+11*j+1]) >> 3) | ((uint32(a[off+11*j+2]) & 0x3f) << 5)) * kyberQ) + 1024) >> 11)
  43. vec.coeffs[8*j+2] = uint16(((((uint32(a[off+11*j+2]) >> 6) | ((uint32(a[off+11*j+3]) & 0xff) << 2) | ((uint32(a[off+11*j+4]) & 0x01) << 10)) * kyberQ) + 1024) >> 11)
  44. vec.coeffs[8*j+3] = uint16(((((uint32(a[off+11*j+4]) >> 1) | ((uint32(a[off+11*j+5]) & 0x0f) << 7)) * kyberQ) + 1024) >> 11)
  45. vec.coeffs[8*j+4] = uint16(((((uint32(a[off+11*j+5]) >> 4) | ((uint32(a[off+11*j+6]) & 0x7f) << 4)) * kyberQ) + 1024) >> 11)
  46. vec.coeffs[8*j+5] = uint16(((((uint32(a[off+11*j+6]) >> 7) | ((uint32(a[off+11*j+7]) & 0xff) << 1) | ((uint32(a[off+11*j+8]) & 0x03) << 9)) * kyberQ) + 1024) >> 11)
  47. vec.coeffs[8*j+6] = uint16(((((uint32(a[off+11*j+8]) >> 2) | ((uint32(a[off+11*j+9]) & 0x1f) << 6)) * kyberQ) + 1024) >> 11)
  48. vec.coeffs[8*j+7] = uint16(((((uint32(a[off+11*j+9]) >> 5) | ((uint32(a[off+11*j+10]) & 0xff) << 3)) * kyberQ) + 1024) >> 11)
  49. }
  50. off += compressedCoeffSize
  51. }
  52. }
  53. // Serialize vector of polynomials.
  54. func (v *polyVec) toBytes(r []byte) {
  55. for i, p := range v.vec {
  56. p.toBytes(r[i*polySize:])
  57. }
  58. }
  59. // De-serialize vector of polynomials; inverse of polyVec.toBytes().
  60. func (v *polyVec) fromBytes(a []byte) {
  61. for i, p := range v.vec {
  62. p.fromBytes(a[i*polySize:])
  63. }
  64. }
  65. // Apply forward NTT to all elements of a vector of polynomials.
  66. func (v *polyVec) ntt() {
  67. for _, p := range v.vec {
  68. p.ntt()
  69. }
  70. }
  71. // Apply inverse NTT to all elements of a vector of polynomials.
  72. func (v *polyVec) invntt() {
  73. for _, p := range v.vec {
  74. p.invntt()
  75. }
  76. }
  77. // Pointwise multiply elements of a and b and accumulate into p.
  78. func (p *poly) pointwiseAcc(a, b *polyVec) {
  79. hardwareAccelImpl.pointwiseAccFn(p, a, b)
  80. }
  81. // Add vectors of polynomials.
  82. func (v *polyVec) add(a, b *polyVec) {
  83. for i, p := range v.vec {
  84. p.add(a.vec[i], b.vec[i])
  85. }
  86. }
  87. // Get compressed and serialized size in bytes.
  88. func (v *polyVec) compressedSize() int {
  89. return len(v.vec) * compressedCoeffSize
  90. }
  91. func pointwiseAccRef(p *poly, a, b *polyVec) {
  92. for j := 0; j < kyberN; j++ {
  93. t := montgomeryReduce(4613 * uint32(b.vec[0].coeffs[j])) // 4613 = 2^{2*18} % q
  94. p.coeffs[j] = montgomeryReduce(uint32(a.vec[0].coeffs[j]) * uint32(t))
  95. for i := 1; i < len(a.vec); i++ { // len(a.vec) == kyberK
  96. t = montgomeryReduce(4613 * uint32(b.vec[i].coeffs[j]))
  97. p.coeffs[j] += montgomeryReduce(uint32(a.vec[i].coeffs[j]) * uint32(t))
  98. }
  99. p.coeffs[j] = barrettReduce(p.coeffs[j])
  100. }
  101. }