----- How to use it -----

- install python
- install numpy
- install scipy
- install tqdm
- run script


----- Description -----

We have provided 1 script. Running it, the user is asked to decide whether to obtain parameters for "polynomials over R_q" or for "polynomials over Z_q", and then to specify the polynomial degree among the provided options. The script then prints sizes and parameters.

Security parameter is always fixes, lambda = 128. 

For the "polynomials over R_q" option, the user can choose to compute parameters for polynomials of degree 2^{12}, 2^{16}, and 2^{20} respectively over ring R_q. Parameters and efficiency numbers are summarized on table 4 from our full version.

For the "polynomials over Z_q" option, the user can choose to compute parameters for polynomials of degree 2^{15}, 2^{20}, 2^{25}, and 2^{30} respectively, over field Z_q. Efficiency numbers are summarized on table 5 from our full version. This option accounts for Fiat-Shamir loss for 2^{64} random oracle queries.


----- Analysis of Scripts -----

The script does the following:

	- it computes the smallest block size of BKZ algorithm so that runtime of such algorithm would be exponential (one gets 338)
	- it computes the Hermite root factor for such block size (one gets approx 1.0044)
	- it runs over all possible parameters choices of logq, n, d, alpha, r0, r1 (in the scripts we have already set very short ranges where we get good efficiency numbers, but these can be modified arbitrarily)
	- for any such parameters set, it determines the remaining parameters, i.e., ell, kappa or omega, delta, beta, beta1, beta2, betap, and r2
	- it checks that such set of parameters satisfies MSIS hardness w.r.t. Hermite root factor we have computed (for coordinate-wise special soundness and relaxed binding)
	- if all checks pass, it computes the commitment size and proof size and appends the result to the array Params	
	- after it has run over all parameters choices, it orders the array Params by smallest size of commit size + proof size
	- it outputs parameters set that minimizes commit size + proof size

For "polynomials over R_q", we do not take into accont loss obtained when applying Fiat-Shamir transformation (logQ = 0). For "polynomials over Z_q", we consider an adversary that performs at most 2^{64} random oracle queries, and consider the loss obtained when applying the Fiat-Shamir transform (logQ = 64). Moreover, for this second option, we provide instantiation of a polynomial commitment scheme over field Z_q. We do so by relying on the generic transformation from [AFLN23, Section 5.5]. Since such transformation reduces proving polynomial evaluations over Z_q for degree L polynomials to proving polynomial evaluations over R_q for degree L/d polynomials, we choose d = 256 in this second group (see section A.4 of our full version for more details).