Rejection Sampling For Polynomial Coefficient Generator

Abstract

A polynomial coefficient generator includes a random number generator to generate a random bit string. A buffer is coupled to receive bits of the random bit string and a rejection sampler is coupled to the buffer to receive n+1 sets of p bits of buffered bits of the random bit string, where n is an integer having a value of at least four, and sample each set of n bits in parallel to identify valid sets of p bits A valid coefficient queue is coupled to receive the valid sets of p bits, and a polynomial multiplier is coupled to receive the valid sets of p bits from the valid coefficient queue. A method uses the generator to generate valid coefficients.

1 . A method comprising:
 receiving a random bit string;   selecting n+1 sets of p bits of the random bit string, where n is an integer having a value of at least four;   rejection sampling each set of p bits in parallel to identify valid sets of p bits;   storing the valid sets of p bits in a queue; and   providing n sets of p bits of the stored valid sets of p bits from the queue to a polynomial multiplier.   
     
     
         2 . The method of  claim 1  where n=4 and p=24, and wherein the rejection sampling ensures that each set of p bits is less than a selected prime number. 
     
     
         3 . The method of  claim 1  wherein the received random bit string is generated by a Keccak random number generator. 
     
     
         4 . The method of  claim 1  and further comprising buffering the random bit string in a buffer, wherein the sets of p bits are selected from the buffer. 
     
     
         5 . The method of  claim 4  and further comprising:
 determining if the buffer has at least n+1 sets of p bits; and 
 in response to the buffer not having at least n+1 sets of p bits, receiving a next random bit string. 
 
     
     
         6 . The method of  claim 1  wherein the queue has a length greater than n. 
     
     
         7 . The method of  claim 6  wherein the queue length is 2*n. 
     
     
         8 . The method of  claim 1  wherein the selecting, rejection sampling, buffering, and providing are repeated for successive n+1 sets of p bits of the random bit string. 
     
     
         9 . The method of  claim 8  and further comprising tracking a fullness of the queue. 
     
     
         10 . The method of  claim 9  and further comprising in response to the queue being full, delaying selecting of a next n+1 sets until the queue is not full. 
     
     
         11 . A polynomial coefficient generator comprising:
 a random number generator to generate a random bit string;   a buffer coupled to receive bits of the random bit string;   a rejection sampler coupled to the buffer to receive n+1 sets of p bits of buffered bits of the random bit string, where n is an integer having a value of at least four, and sample each set of n bits in parallel to identify valid sets of p bits;   a valid coefficient queue coupled to receive the valid sets of p bits; and   a polynomial multiplier coupled to receive the valid sets of p bits from the valid coefficient queue.   
     
     
         12 . The generator of  claim 11  where n=4 and p=24. 
     
     
         13 . The generator of  claim 11  wherein the random number generator is a Keccak random number generator. 
     
     
         14 . The generator of  claim 11  and further comprising a controller configured to:
 determine if the buffer has at least n+1 sets of p bits; and 
 in response to the buffer not having at least n+1 sets of p bits, cause the random number generator to provide additional bits of the random bit string to the buffer. 
 
     
     
         15 . The generator of  claim 11  wherein the queue has a length greater than n. 
     
     
         16 . The generator of  claim 15  wherein the queue length is 2*n. 
     
     
         17 . The generator of  claim 11  and further comprising a controller configured to cause the generator to iterate over successive n+1 sets of p bits of the random bit string. 
     
     
         18 . The generator of  claim 17  wherein the controller tracks a fullness of the queue. 
     
     
         19 . The generator of  claim 18  wherein the controller, in response to the queue being full, delays rejection sampler from receiving a next q+1 sets until the queue is not full. 
     
     
         20 . A hardware implemented method comprising:
 receiving a random bit string;   storing the random bit string in a buffer;   selecting n+1 sets of p bits from the buffer where q is an integer having a value of at least four;   rejection sampling each set of p bits in parallel to identify valid sets of p bits;   storing the valid sets of p bits in a queue; and   providing n sets of p bits of the stored valid sets of p bits from the queue to a polynomial multiplier.