sample.go

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

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