sample.go

Documentation: github.com/cloudflare/circl/sign/dilithium/mode2/internal

     1  // Code generated from mode3/internal/sample.go by gen.go
     2  
     3  package internal
     4  
     5  import (
     6  	"encoding/binary"
     7  
     8  	"github.com/cloudflare/circl/internal/sha3"
     9  	"github.com/cloudflare/circl/sign/dilithium/internal/common"
    10  	"github.com/cloudflare/circl/simd/keccakf1600"
    11  )
    12  
    13  // DeriveX4Available indicates whether the system supports the quick fourway
    14  // sampling variants like PolyDeriveUniformX4.
    15  var DeriveX4Available = keccakf1600.IsEnabledX4() && !UseAES
    16  
    17  // For each i, sample ps[i] uniformly from the given seed and nonces[i].
    18  // ps[i] may be nil and is ignored in that case.
    19  //
    20  // Can only be called when DeriveX4Available is true.
    21  func PolyDeriveUniformX4(ps [4]*common.Poly, seed *[32]byte, nonces [4]uint16) {
    22  	var perm keccakf1600.StateX4
    23  	state := perm.Initialize(false)
    24  
    25  	// Absorb the seed in the four states
    26  	for i := 0; i < 4; i++ {
    27  		v := binary.LittleEndian.Uint64(seed[8*i : 8*(i+1)])
    28  		for j := 0; j < 4; j++ {
    29  			state[i*4+j] = v
    30  		}
    31  	}
    32  
    33  	// Absorb the nonces, the SHAKE128 domain separator (0b1111), the
    34  	// start of the padding (0b...001) and the end of the padding 0b100...
    35  	// Recall that the rate of SHAKE128 is 168 --- i.e. 21 uint64s.
    36  	for j := 0; j < 4; j++ {
    37  		state[4*4+j] = uint64(nonces[j]) | (0x1f << 16)
    38  		state[20*4+j] = 0x80 << 56
    39  	}
    40  
    41  	var idx [4]int // indices into ps
    42  	for j := 0; j < 4; j++ {
    43  		if ps[j] == nil {
    44  			idx[j] = common.N // mark nil polynomial as completed
    45  		}
    46  	}
    47  
    48  	done := false
    49  	for !done {
    50  		// Applies KeccaK-f[1600] to state to get the next 21 uint64s of each
    51  		// of the four SHAKE128 streams.
    52  		perm.Permute()
    53  
    54  		done = true
    55  
    56  	PolyLoop:
    57  		for j := 0; j < 4; j++ {
    58  			if idx[j] == common.N {
    59  				continue
    60  			}
    61  			for i := 0; i < 7; i++ {
    62  				var t [8]uint32
    63  				t[0] = uint32(state[i*3*4+j] & 0x7fffff)
    64  				t[1] = uint32((state[i*3*4+j] >> 24) & 0x7fffff)
    65  				t[2] = uint32((state[i*3*4+j] >> 48) |
    66  					((state[(i*3+1)*4+j] & 0x7f) << 16))
    67  				t[3] = uint32((state[(i*3+1)*4+j] >> 8) & 0x7fffff)
    68  				t[4] = uint32((state[(i*3+1)*4+j] >> 32) & 0x7fffff)
    69  				t[5] = uint32((state[(i*3+1)*4+j] >> 56) |
    70  					((state[(i*3+2)*4+j] & 0x7fff) << 8))
    71  				t[6] = uint32((state[(i*3+2)*4+j] >> 16) & 0x7fffff)
    72  				t[7] = uint32((state[(i*3+2)*4+j] >> 40) & 0x7fffff)
    73  
    74  				for k := 0; k < 8; k++ {
    75  					if t[k] < common.Q {
    76  						ps[j][idx[j]] = t[k]
    77  						idx[j]++
    78  						if idx[j] == common.N {
    79  							continue PolyLoop
    80  						}
    81  					}
    82  				}
    83  			}
    84  			done = false
    85  		}
    86  	}
    87  }
    88  
    89  // Sample p uniformly from the given seed and nonce.
    90  //
    91  // p will be normalized.
    92  func PolyDeriveUniform(p *common.Poly, seed *[32]byte, nonce uint16) {
    93  	var i, length int
    94  	var buf [12 * 16]byte // fits 168B SHAKE-128 rate and 12 16B AES blocks
    95  
    96  	if UseAES {
    97  		length = 12 * 16
    98  	} else {
    99  		length = 168
   100  	}
   101  
   102  	sample := func() {
   103  		// Note that 3 divides into 168 and 12*16, so we use up buf completely.
   104  		for j := 0; j < length && i < common.N; j += 3 {
   105  			t := (uint32(buf[j]) | (uint32(buf[j+1]) << 8) |
   106  				(uint32(buf[j+2]) << 16)) & 0x7fffff
   107  
   108  			// We use rejection sampling
   109  			if t < common.Q {
   110  				p[i] = t
   111  				i++
   112  			}
   113  		}
   114  	}
   115  
   116  	if UseAES {
   117  		h := common.NewAesStream128(seed, nonce)
   118  
   119  		for i < common.N {
   120  			h.SqueezeInto(buf[:length])
   121  			sample()
   122  		}
   123  	} else {
   124  		var iv [32 + 2]byte // 32 byte seed + uint16 nonce
   125  		h := sha3.NewShake128()
   126  		copy(iv[:32], seed[:])
   127  		iv[32] = uint8(nonce)
   128  		iv[33] = uint8(nonce >> 8)
   129  		_, _ = h.Write(iv[:])
   130  
   131  		for i < common.N {
   132  			_, _ = h.Read(buf[:168])
   133  			sample()
   134  		}
   135  	}
   136  }
   137  
   138  // Sample p uniformly with coefficients of norm less than or equal η,
   139  // using the given seed and nonce.
   140  //
   141  // p will not be normalized, but will have coefficients in [q-η,q+η].
   142  func PolyDeriveUniformLeqEta(p *common.Poly, seed *[64]byte, nonce uint16) {
   143  	// Assumes 2 < η < 8.
   144  	var i, length int
   145  	var buf [9 * 16]byte // fits 136B SHAKE-256 rate and 9 16B AES blocks
   146  
   147  	if UseAES {
   148  		length = 9 * 16
   149  	} else {
   150  		length = 136
   151  	}
   152  
   153  	sample := func() {
   154  		// We use rejection sampling
   155  		for j := 0; j < length && i < common.N; j++ {
   156  			t1 := uint32(buf[j]) & 15
   157  			t2 := uint32(buf[j]) >> 4
   158  			if Eta == 2 { // branch is eliminated by compiler
   159  				if t1 <= 14 {
   160  					t1 -= ((205 * t1) >> 10) * 5 // reduce mod  5
   161  					p[i] = common.Q + Eta - t1
   162  					i++
   163  				}
   164  				if t2 <= 14 && i < common.N {
   165  					t2 -= ((205 * t2) >> 10) * 5 // reduce mod 5
   166  					p[i] = common.Q + Eta - t2
   167  					i++
   168  				}
   169  			} else if Eta == 4 {
   170  				if t1 <= 2*Eta {
   171  					p[i] = common.Q + Eta - t1
   172  					i++
   173  				}
   174  				if t2 <= 2*Eta && i < common.N {
   175  					p[i] = common.Q + Eta - t2
   176  					i++
   177  				}
   178  			} else {
   179  				panic("unsupported η")
   180  			}
   181  		}
   182  	}
   183  
   184  	if UseAES {
   185  		h := common.NewAesStream256(seed, nonce)
   186  
   187  		for i < common.N {
   188  			h.SqueezeInto(buf[:length])
   189  			sample()
   190  		}
   191  	} else {
   192  		var iv [64 + 2]byte // 64 byte seed + uint16 nonce
   193  
   194  		h := sha3.NewShake256()
   195  		copy(iv[:64], seed[:])
   196  		iv[64] = uint8(nonce)
   197  		iv[65] = uint8(nonce >> 8)
   198  
   199  		// 136 is SHAKE-256 rate
   200  		_, _ = h.Write(iv[:])
   201  
   202  		for i < common.N {
   203  			_, _ = h.Read(buf[:136])
   204  			sample()
   205  		}
   206  	}
   207  }
   208  
   209  // Sample v[i] uniformly with coefficients in (-γ₁,…,γ₁]  using the
   210  // given seed and nonce+i
   211  //
   212  // p will be normalized.
   213  func VecLDeriveUniformLeGamma1(v *VecL, seed *[64]byte, nonce uint16) {
   214  	for i := 0; i < L; i++ {
   215  		PolyDeriveUniformLeGamma1(&v[i], seed, nonce+uint16(i))
   216  	}
   217  }
   218  
   219  // Sample p uniformly with coefficients in (-γ₁,…,γK1s] using the
   220  // given seed and nonce.
   221  //
   222  // p will be normalized.
   223  func PolyDeriveUniformLeGamma1(p *common.Poly, seed *[64]byte, nonce uint16) {
   224  	var buf [PolyLeGamma1Size]byte
   225  
   226  	if UseAES {
   227  		h := common.NewAesStream256(seed, nonce)
   228  		h.SqueezeInto(buf[:])
   229  	} else {
   230  		var iv [66]byte
   231  		h := sha3.NewShake256()
   232  		copy(iv[:64], seed[:])
   233  		iv[64] = uint8(nonce)
   234  		iv[65] = uint8(nonce >> 8)
   235  		_, _ = h.Write(iv[:])
   236  		_, _ = h.Read(buf[:])
   237  	}
   238  
   239  	PolyUnpackLeGamma1(p, buf[:])
   240  }
   241  
   242  // For each i, sample ps[i] uniformly with τ non-zero coefficients in {q-1,1}
   243  // using the given seed and w1[i].  ps[i] may be nil and is ignored
   244  // in that case.  ps[i] will be normalized.
   245  //
   246  // Can only be called when DeriveX4Available is true.
   247  //
   248  // This function is currently not used (yet).
   249  func PolyDeriveUniformBallX4(ps [4]*common.Poly, seed *[32]byte) {
   250  	var perm keccakf1600.StateX4
   251  	state := perm.Initialize(false)
   252  
   253  	// Absorb the seed in the four states
   254  	for i := 0; i < 4; i++ {
   255  		v := binary.LittleEndian.Uint64(seed[8*i : 8*(i+1)])
   256  		for j := 0; j < 4; j++ {
   257  			state[i*4+j] = v
   258  		}
   259  	}
   260  
   261  	// SHAKE256 domain separator and padding
   262  	for j := 0; j < 4; j++ {
   263  		state[4*4+j] ^= 0x1f
   264  		state[16*4+j] ^= 0x80 << 56
   265  	}
   266  	perm.Permute()
   267  
   268  	var signs [4]uint64
   269  	var idx [4]uint16 // indices into ps
   270  
   271  	for j := 0; j < 4; j++ {
   272  		if ps[j] != nil {
   273  			signs[j] = state[j]
   274  			*ps[j] = common.Poly{} // zero ps[j]
   275  			idx[j] = common.N - Tau
   276  		} else {
   277  			idx[j] = common.N // mark as completed
   278  		}
   279  	}
   280  
   281  	stateOffset := 1
   282  	for {
   283  		done := true
   284  
   285  	PolyLoop:
   286  		for j := 0; j < 4; j++ {
   287  			if idx[j] == common.N {
   288  				continue
   289  			}
   290  
   291  			for i := stateOffset; i < 17; i++ {
   292  				var bs [8]byte
   293  				binary.LittleEndian.PutUint64(bs[:], state[4*i+j])
   294  				for k := 0; k < 8; k++ {
   295  					b := uint16(bs[k])
   296  
   297  					if b > idx[j] {
   298  						continue
   299  					}
   300  
   301  					ps[j][idx[j]] = ps[j][b]
   302  					ps[j][b] = 1
   303  					// Takes least significant bit of signs and uses it for the sign.
   304  					// Note 1 ^ (1 | (Q-1)) = Q-1.
   305  					ps[j][b] ^= uint32((-(signs[j] & 1)) & (1 | (common.Q - 1)))
   306  					signs[j] >>= 1
   307  
   308  					idx[j]++
   309  					if idx[j] == common.N {
   310  						continue PolyLoop
   311  					}
   312  				}
   313  			}
   314  
   315  			done = false
   316  		}
   317  
   318  		if done {
   319  			break
   320  		}
   321  
   322  		perm.Permute()
   323  		stateOffset = 0
   324  	}
   325  }
   326  
   327  // Samples p uniformly with τ non-zero coefficients in {q-1,1}.
   328  //
   329  // The polynomial p will be normalized.
   330  func PolyDeriveUniformBall(p *common.Poly, seed *[32]byte) {
   331  	var buf [136]byte // SHAKE-256 rate is 136
   332  
   333  	h := sha3.NewShake256()
   334  	_, _ = h.Write(seed[:])
   335  	_, _ = h.Read(buf[:])
   336  
   337  	// Essentially we generate a sequence of τ ones or minus ones,
   338  	// prepend 196 zeroes and shuffle the concatenation using the
   339  	// usual algorithm (Fisher--Yates.)
   340  	signs := binary.LittleEndian.Uint64(buf[:])
   341  	bufOff := 8 // offset into buf
   342  
   343  	*p = common.Poly{} // zero p
   344  	for i := uint16(common.N - Tau); i < common.N; i++ {
   345  		var b uint16
   346  
   347  		// Find location of where to move the new coefficient to using
   348  		// rejection sampling.
   349  		for {
   350  			if bufOff >= 136 {
   351  				_, _ = h.Read(buf[:])
   352  				bufOff = 0
   353  			}
   354  
   355  			b = uint16(buf[bufOff])
   356  			bufOff++
   357  
   358  			if b <= i {
   359  				break
   360  			}
   361  		}
   362  
   363  		p[i] = p[b]
   364  		p[b] = 1
   365  		// Takes least significant bit of signs and uses it for the sign.
   366  		// Note 1 ^ (1 | (Q-1)) = Q-1.
   367  		p[b] ^= uint32((-(signs & 1)) & (1 | (common.Q - 1)))
   368  		signs >>= 1
   369  	}
   370  }
   371
View as plain text