indcpa.go 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279
  1. // indcpa.go - Kyber IND-CPA encryption.
  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. import (
  9. "io"
  10. "golang.org/x/crypto/sha3"
  11. )
  12. // Serialize the public key as concatenation of the compressed and serialized
  13. // vector of polynomials pk and the public seed used to generate the matrix A.
  14. func packPublicKey(r []byte, pk *polyVec, seed []byte) {
  15. pk.compress(r)
  16. copy(r[pk.compressedSize():], seed[:SymSize])
  17. }
  18. // De-serialize and decompress public key from a byte array; approximate
  19. // inverse of packPublicKey.
  20. func unpackPublicKey(pk *polyVec, seed, packedPk []byte) {
  21. pk.decompress(packedPk)
  22. off := pk.compressedSize()
  23. copy(seed, packedPk[off:off+SymSize])
  24. }
  25. // Serialize the ciphertext as concatenation of the compressed and serialized
  26. // vector of polynomials b and the compressed and serialized polynomial v.
  27. func packCiphertext(r []byte, b *polyVec, v *poly) {
  28. b.compress(r)
  29. v.compress(r[b.compressedSize():])
  30. }
  31. // De-serialize and decompress ciphertext from a byte array; approximate
  32. // inverse of packCiphertext.
  33. func unpackCiphertext(b *polyVec, v *poly, c []byte) {
  34. b.decompress(c)
  35. v.decompress(c[b.compressedSize():])
  36. }
  37. // Serialize the secret key.
  38. func packSecretKey(r []byte, sk *polyVec) {
  39. sk.toBytes(r)
  40. }
  41. // De-serialize the secret key; inverse of packSecretKey.
  42. func unpackSecretKey(sk *polyVec, packedSk []byte) {
  43. sk.fromBytes(packedSk)
  44. }
  45. // Deterministically generate matrix A (or the transpose of A) from a seed.
  46. // Entries of the matrix are polynomials that look uniformly random. Performs
  47. // rejection sampling on output of SHAKE-128.
  48. func genMatrix(a []polyVec, seed []byte, transposed bool) {
  49. const (
  50. shake128Rate = 168 // xof.BlockSize() is not a constant.
  51. maxBlocks = 4
  52. )
  53. var buf [shake128Rate * maxBlocks]byte
  54. var extSeed [SymSize + 2]byte
  55. copy(extSeed[:SymSize], seed)
  56. xof := sha3.NewShake128()
  57. for i, v := range a {
  58. for j, p := range v.vec {
  59. if transposed {
  60. extSeed[SymSize] = byte(i)
  61. extSeed[SymSize+1] = byte(j)
  62. } else {
  63. extSeed[SymSize] = byte(j)
  64. extSeed[SymSize+1] = byte(i)
  65. }
  66. xof.Write(extSeed[:])
  67. xof.Read(buf[:])
  68. for ctr, pos, maxPos := 0, 0, len(buf); ctr < kyberN; {
  69. val := (uint16(buf[pos]) | (uint16(buf[pos+1]) << 8)) & 0x1fff
  70. if val < kyberQ {
  71. p.coeffs[ctr] = val
  72. ctr++
  73. }
  74. if pos += 2; pos == maxPos {
  75. // On the unlikely chance 4 blocks is insufficient,
  76. // incrementally squeeze out 1 block at a time.
  77. xof.Read(buf[:shake128Rate])
  78. pos, maxPos = 0, shake128Rate
  79. }
  80. }
  81. xof.Reset()
  82. }
  83. }
  84. }
  85. type indcpaPublicKey struct {
  86. packed []byte
  87. h [32]byte
  88. }
  89. func (pk *indcpaPublicKey) toBytes() []byte {
  90. return pk.packed
  91. }
  92. func (pk *indcpaPublicKey) fromBytes(p *ParameterSet, b []byte) error {
  93. if len(b) != p.indcpaPublicKeySize {
  94. return ErrInvalidKeySize
  95. }
  96. pk.packed = make([]byte, len(b))
  97. copy(pk.packed, b)
  98. pk.h = sha3.Sum256(b)
  99. return nil
  100. }
  101. type indcpaSecretKey struct {
  102. packed []byte
  103. }
  104. func (sk *indcpaSecretKey) fromBytes(p *ParameterSet, b []byte) error {
  105. if len(b) != p.indcpaSecretKeySize {
  106. return ErrInvalidKeySize
  107. }
  108. sk.packed = make([]byte, len(b))
  109. copy(sk.packed, b)
  110. return nil
  111. }
  112. // Generates public and private key for the CPA-secure public-key encryption
  113. // scheme underlying Kyber.
  114. func (p *ParameterSet) indcpaKeyPair(rng io.Reader) (*indcpaPublicKey, *indcpaSecretKey, error) {
  115. buf := make([]byte, SymSize+SymSize)
  116. if _, err := io.ReadFull(rng, buf[:SymSize]); err != nil {
  117. return nil, nil, err
  118. }
  119. sk := &indcpaSecretKey{
  120. packed: make([]byte, p.indcpaSecretKeySize),
  121. }
  122. pk := &indcpaPublicKey{
  123. packed: make([]byte, p.indcpaPublicKeySize),
  124. }
  125. h := sha3.New512()
  126. h.Write(buf[:SymSize])
  127. buf = buf[:0] // Reuse the backing store.
  128. buf = h.Sum(buf)
  129. publicSeed, noiseSeed := buf[:SymSize], buf[SymSize:]
  130. a := p.allocMatrix()
  131. genMatrix(a, publicSeed, false)
  132. var nonce byte
  133. skpv := p.allocPolyVec()
  134. for _, pv := range skpv.vec {
  135. pv.getNoise(noiseSeed, nonce, p.eta)
  136. nonce++
  137. }
  138. skpv.ntt()
  139. e := p.allocPolyVec()
  140. for _, pv := range e.vec {
  141. pv.getNoise(noiseSeed, nonce, p.eta)
  142. nonce++
  143. }
  144. // matrix-vector multiplication
  145. pkpv := p.allocPolyVec()
  146. for i, pv := range pkpv.vec {
  147. pv.pointwiseAcc(&skpv, &a[i])
  148. }
  149. pkpv.invntt()
  150. pkpv.add(&pkpv, &e)
  151. packSecretKey(sk.packed, &skpv)
  152. packPublicKey(pk.packed, &pkpv, publicSeed)
  153. pk.h = sha3.Sum256(pk.packed)
  154. return pk, sk, nil
  155. }
  156. // Encryption function of the CPA-secure public-key encryption scheme
  157. // underlying Kyber.
  158. func (p *ParameterSet) indcpaEncrypt(c, m []byte, pk *indcpaPublicKey, coins []byte) {
  159. var k, v, epp poly
  160. var seed [SymSize]byte
  161. pkpv := p.allocPolyVec()
  162. unpackPublicKey(&pkpv, seed[:], pk.packed)
  163. k.fromMsg(m)
  164. pkpv.ntt()
  165. at := p.allocMatrix()
  166. genMatrix(at, seed[:], true)
  167. var nonce byte
  168. sp := p.allocPolyVec()
  169. for _, pv := range sp.vec {
  170. pv.getNoise(coins, nonce, p.eta)
  171. nonce++
  172. }
  173. sp.ntt()
  174. ep := p.allocPolyVec()
  175. for _, pv := range ep.vec {
  176. pv.getNoise(coins, nonce, p.eta)
  177. nonce++
  178. }
  179. // matrix-vector multiplication
  180. bp := p.allocPolyVec()
  181. for i, pv := range bp.vec {
  182. pv.pointwiseAcc(&sp, &at[i])
  183. }
  184. bp.invntt()
  185. bp.add(&bp, &ep)
  186. v.pointwiseAcc(&pkpv, &sp)
  187. v.invntt()
  188. epp.getNoise(coins, nonce, p.eta) // Don't need to increment nonce.
  189. v.add(&v, &epp)
  190. v.add(&v, &k)
  191. packCiphertext(c, &bp, &v)
  192. }
  193. // Decryption function of the CPA-secure public-key encryption scheme
  194. // underlying Kyber.
  195. func (p *ParameterSet) indcpaDecrypt(m, c []byte, sk *indcpaSecretKey) {
  196. var v, mp poly
  197. skpv, bp := p.allocPolyVec(), p.allocPolyVec()
  198. unpackCiphertext(&bp, &v, c)
  199. unpackSecretKey(&skpv, sk.packed)
  200. bp.ntt()
  201. mp.pointwiseAcc(&skpv, &bp)
  202. mp.invntt()
  203. mp.sub(&mp, &v)
  204. mp.toMsg(m)
  205. }
  206. func (p *ParameterSet) allocMatrix() []polyVec {
  207. m := make([]polyVec, 0, p.k)
  208. for i := 0; i < p.k; i++ {
  209. m = append(m, p.allocPolyVec())
  210. }
  211. return m
  212. }
  213. func (p *ParameterSet) allocPolyVec() polyVec {
  214. vec := make([]*poly, 0, p.k)
  215. for i := 0; i < p.k; i++ {
  216. vec = append(vec, new(poly))
  217. }
  218. return polyVec{vec}
  219. }