sample.go

Documentation: github.com/cloudflare/circl/pke/kyber/internal/common

     1  package common
     2  
     3  import (
     4  	"encoding/binary"
     5  
     6  	"github.com/cloudflare/circl/internal/sha3"
     7  	"github.com/cloudflare/circl/simd/keccakf1600"
     8  )
     9  
    10  // DeriveX4Available indicates whether the system supports the quick fourway
    11  // sampling variants like PolyDeriveUniformX4.
    12  var DeriveX4Available = keccakf1600.IsEnabledX4()
    13  
    14  // Samples p from a centered binomial distribution with given η.
    15  //
    16  // Essentially CBD_η(PRF(seed, nonce)) from the specification.
    17  func (p *Poly) DeriveNoise(seed []byte, nonce uint8, eta int) {
    18  	switch eta {
    19  	case 2:
    20  		p.DeriveNoise2(seed, nonce)
    21  	case 3:
    22  		p.DeriveNoise3(seed, nonce)
    23  	default:
    24  		panic("unsupported eta")
    25  	}
    26  }
    27  
    28  // Sample p from a centered binomial distribution with n=6 and p=½ - that is:
    29  // coefficients are in {-3, -2, -1, 0, 1, 2, 3} with probabilities {1/64, 3/32,
    30  // 15/64, 5/16, 16/64, 3/32, 1/64}.
    31  func (p *Poly) DeriveNoise3(seed []byte, nonce uint8) {
    32  	keySuffix := [1]byte{nonce}
    33  	h := sha3.NewShake256()
    34  	_, _ = h.Write(seed[:])
    35  	_, _ = h.Write(keySuffix[:])
    36  
    37  	// The distribution at hand is exactly the same as that
    38  	// of (a₁ + a₂ + a₃) - (b₁ + b₂+b₃) where a_i,b_i~U(1).  Thus we need
    39  	// 6 bits per coefficients, thus 192 bytes of input entropy.
    40  
    41  	// We add two extra zero bytes in the buffer to be able to read 8 bytes
    42  	// at the same time (while using only 6.)
    43  	var buf [192 + 2]byte
    44  	_, _ = h.Read(buf[:192])
    45  
    46  	for i := 0; i < 32; i++ {
    47  		// t is interpreted as a₁ + 2a₂ + 4a₃ + 8b₁ + 16b₂ + ….
    48  		t := binary.LittleEndian.Uint64(buf[6*i:])
    49  
    50  		d := t & 0x249249249249        // a₁ + 8b₁ + …
    51  		d += (t >> 1) & 0x249249249249 // a₁ + a₂ + 8(b₁ + b₂) + …
    52  		d += (t >> 2) & 0x249249249249 // a₁ + a₂ + a₃ + 4(b₁ + b₂ + b₃) + …
    53  
    54  		for j := 0; j < 8; j++ {
    55  			a := int16(d) & 0x7 // a₁ + a₂ + a₃
    56  			d >>= 3
    57  			b := int16(d) & 0x7 // b₁ + b₂ + b₃
    58  			d >>= 3
    59  			p[8*i+j] = a - b
    60  		}
    61  	}
    62  }
    63  
    64  // Sample p from a centered binomial distribution with n=4 and p=½ - that is:
    65  // coefficients are in {-2, -1, 0, 1, 2} with probabilities {1/16, 1/4,
    66  // 3/8, 1/4, 1/16}.
    67  func (p *Poly) DeriveNoise2(seed []byte, nonce uint8) {
    68  	keySuffix := [1]byte{nonce}
    69  	h := sha3.NewShake256()
    70  	_, _ = h.Write(seed[:])
    71  	_, _ = h.Write(keySuffix[:])
    72  
    73  	// The distribution at hand is exactly the same as that
    74  	// of (a + a') - (b + b') where a,a',b,b'~U(1).  Thus we need 4 bits per
    75  	// coefficients, thus 128 bytes of input entropy.
    76  
    77  	var buf [128]byte
    78  	_, _ = h.Read(buf[:])
    79  
    80  	for i := 0; i < 16; i++ {
    81  		// t is interpreted as a + 2a' + 4b + 8b' + ….
    82  		t := binary.LittleEndian.Uint64(buf[8*i:])
    83  
    84  		d := t & 0x5555555555555555        // a + 4b + …
    85  		d += (t >> 1) & 0x5555555555555555 // a+a' + 4(b + b') + …
    86  
    87  		for j := 0; j < 16; j++ {
    88  			a := int16(d) & 0x3
    89  			d >>= 2
    90  			b := int16(d) & 0x3
    91  			d >>= 2
    92  			p[16*i+j] = a - b
    93  		}
    94  	}
    95  }
    96  
    97  // For each i, sample ps[i] uniformly from the given seed for coordinates
    98  // xs[i] and ys[i]. ps[i] may be nil and is ignored in that case.
    99  //
   100  // Can only be called when DeriveX4Available is true.
   101  func PolyDeriveUniformX4(ps [4]*Poly, seed *[32]byte, xs, ys [4]uint8) {
   102  	var perm keccakf1600.StateX4
   103  	state := perm.Initialize(false)
   104  
   105  	// Absorb the seed in the four states
   106  	for i := 0; i < 4; i++ {
   107  		v := binary.LittleEndian.Uint64(seed[8*i : 8*(i+1)])
   108  		for j := 0; j < 4; j++ {
   109  			state[i*4+j] = v
   110  		}
   111  	}
   112  
   113  	// Absorb the coordinates, the SHAKE128 domain separator (0b1111), the
   114  	// start of the padding (0b…001) and the end of the padding 0b100….
   115  	// Recall that the rate of SHAKE128 is 168; ie. 21 uint64s.
   116  	for j := 0; j < 4; j++ {
   117  		state[4*4+j] = uint64(xs[j]) | (uint64(ys[j]) << 8) | (0x1f << 16)
   118  		state[20*4+j] = 0x80 << 56
   119  	}
   120  
   121  	var idx [4]int // indices into ps
   122  	for j := 0; j < 4; j++ {
   123  		if ps[j] == nil {
   124  			idx[j] = N // mark nil polynomials as completed
   125  		}
   126  	}
   127  
   128  	done := false
   129  	for !done {
   130  		// Applies KeccaK-f[1600] to state to get the next 21 uint64s of each of
   131  		// the four SHAKE128 streams.
   132  		perm.Permute()
   133  
   134  		done = true
   135  
   136  	PolyLoop:
   137  		for j := 0; j < 4; j++ {
   138  			if idx[j] == N {
   139  				continue
   140  			}
   141  			for i := 0; i < 7; i++ {
   142  				var t [16]uint16
   143  
   144  				v1 := state[i*3*4+j]
   145  				v2 := state[(i*3+1)*4+j]
   146  				v3 := state[(i*3+2)*4+j]
   147  
   148  				t[0] = uint16(v1) & 0xfff
   149  				t[1] = uint16(v1>>12) & 0xfff
   150  				t[2] = uint16(v1>>24) & 0xfff
   151  				t[3] = uint16(v1>>36) & 0xfff
   152  				t[4] = uint16(v1>>48) & 0xfff
   153  				t[5] = uint16((v1>>60)|(v2<<4)) & 0xfff
   154  
   155  				t[6] = uint16(v2>>8) & 0xfff
   156  				t[7] = uint16(v2>>20) & 0xfff
   157  				t[8] = uint16(v2>>32) & 0xfff
   158  				t[9] = uint16(v2>>44) & 0xfff
   159  				t[10] = uint16((v2>>56)|(v3<<8)) & 0xfff
   160  
   161  				t[11] = uint16(v3>>4) & 0xfff
   162  				t[12] = uint16(v3>>16) & 0xfff
   163  				t[13] = uint16(v3>>28) & 0xfff
   164  				t[14] = uint16(v3>>40) & 0xfff
   165  				t[15] = uint16(v3>>52) & 0xfff
   166  
   167  				for k := 0; k < 16; k++ {
   168  					if t[k] < uint16(Q) {
   169  						ps[j][idx[j]] = int16(t[k])
   170  						idx[j]++
   171  						if idx[j] == N {
   172  							continue PolyLoop
   173  						}
   174  					}
   175  				}
   176  			}
   177  
   178  			done = false
   179  		}
   180  	}
   181  
   182  	for i := 0; i < 4; i++ {
   183  		if ps[i] != nil {
   184  			ps[i].Tangle()
   185  		}
   186  	}
   187  }
   188  
   189  // Sample p uniformly from the given seed and x and y coordinates.
   190  //
   191  // Coefficients are reduced and will be in "tangled" order.  See Tangle().
   192  func (p *Poly) DeriveUniform(seed *[32]byte, x, y uint8) {
   193  	var seedSuffix [2]byte
   194  	var buf [168]byte // rate of SHAKE-128
   195  
   196  	seedSuffix[0] = x
   197  	seedSuffix[1] = y
   198  
   199  	h := sha3.NewShake128()
   200  	_, _ = h.Write(seed[:])
   201  	_, _ = h.Write(seedSuffix[:])
   202  
   203  	i := 0
   204  	for {
   205  		_, _ = h.Read(buf[:])
   206  
   207  		for j := 0; j < 168; j += 3 {
   208  			t1 := (uint16(buf[j]) | (uint16(buf[j+1]) << 8)) & 0xfff
   209  			t2 := (uint16(buf[j+1]>>4) | (uint16(buf[j+2]) << 4)) & 0xfff
   210  
   211  			if t1 < uint16(Q) {
   212  				p[i] = int16(t1)
   213  				i++
   214  
   215  				if i == N {
   216  					break
   217  				}
   218  			}
   219  
   220  			if t2 < uint16(Q) {
   221  				p[i] = int16(t2)
   222  				i++
   223  
   224  				if i == N {
   225  					break
   226  				}
   227  			}
   228  		}
   229  
   230  		if i == N {
   231  			break
   232  		}
   233  	}
   234  
   235  	p.Tangle()
   236  }
   237
View as plain text