This page explains how to use the software accompanying the paper "Short generators without quantum computers: the case of multiquadratics".

### Prerequisites

You need the Sage computer-algebra system.
We have used two environments:
Ubuntu 14.04 with Sage 7.5.1 compiled from source
inside `/home/sage`,
with a symlink from
`/home/sage/sage-latest` to
`/home/sage/sage-7.5.1`;
and Fedora 23 with its supplied Sage 6.5 package.
Porting to other environments will often require
adjusting the `-I` directories at the top of `Makefile` in the multiquad software,
and maybe more serious changes.

### Usage

To download and compile:

wget https://multiquad.cr.yp.to/multiquad-20170312.tar.gz gunzip multiquad-20170312.tar.gz tar -xf multiquad-20170312.tar cd multiquad-20170312 make

There are several `*_test.sage` scripts
designed to check whether various functions produce plausible results.
Example:
`sage units_test.sage`
checks that various unit groups computed by our algorithm
match unit groups computed by Sage's built-in `NumberField` functions
for degrees 2, 4, 8, 16.
Matches are checked by Python assertions;
any mismatches abort with Python error messages.
The normal outputs are various lines such as "4" indicating degree 16;
"(2, 3, 11, 19)" (chosen randomly on each run)
indicating the field **Q**(√2,√3,√11,√19);
and occasional warnings such as "the PARI stack overflows !"
from the `NumberField` functions.

For `cryptosystem_test.sage`,
an output line such as

5 decrypt 0.03 0.05 0.38 0.66 0.94 1.00 1.00 1.00 1.00 1.00 1.00

indicates that, for *one* key in degree 32,
the probability of successful decryption is
3% (in 100 experiments) for messages with a 0-bit gap,
5% for messages with a 1-bit gap,
38% for messages with a 2-bit gap,
66% for messages with a 3-bit gap,
etc.
Separate output lines are for separate keys.

There are also several `*_profile.sage` scripts
designed to collect timing information.
The most important is

sage attack_profile.sagensx

which runs *x* attack experiments
in the field defined by *n* primes starting from *s*.
Each attack experiment recovers a generator from a randomly chosen public key.
The final `canskipenumeration` output line
indicates how often this generator is
exactly the secret key g or −g.

### Changes from conference version

The software differs in the following ways from the software used for the conference version of the paper.

Multiplication, division, etc. now merge groups of 8 consecutive primes into a single modulus.

Interpolation now uses the Moenck–Borodin approach, with the Buergisser–Clausen–Shokrollahi computation of inverses, rather than the Heindel–Horowitz approach.

A new `centermod` module handles reductions of various vectors mod q
into the range [−q/2,q/2].

Some low-level functions no longer take the time to collect profiles.

The cryptosystem now generates g mod p, for each small prime p,
as a uniform random invertible element of
(**Z**/p)[x_{1}...,x_{n}]/(x_{1}^{2}−d_{1},...,x_{n}^{2}−d_{n});
this is equivalent to forcing p to not divide the norm of g.
In the previous software,
g mod p was generated as a uniform random invertible element
of **Z**/p;
this is more restrictive.

In `idealsqrtshorten`,
h and units both fall back to backup symbols
in case h bumps into some sqrtprime.

Unit computation has been generalized: it no longer requires real fields, it no longer requires squarefree d's, and it no longer requires coprime d's.

### To-do list

Use modern vectorized-arithmetic techniques, GPUs, etc. to speed up Hadamard etc.

In square-root computation,
prune the branch
s = f_{0}^{2} − f_{1}^{2} d
if h_{0}−s is not divisible by 2d,
and prune the branch
s = f_{1}^{2} d − f_{0}^{2}
if h_{0}+s is not divisible by 2d.

Use q precomputation to speed up `centermod`.

Speed up the division in `expandseckey`
using the fact that the numerator is an integer.

Speed up `decrypt`
using the fact that the output is
guaranteed to be between −max(mmax) and max(mmax).

Precompute the inverse of an invertible full-rank submatrix of unitsymbols, as mentioned in paper; and limit the number of hsymbols accordingly.

There's redundant code in div, subsetprod, powerprod; clean this up.

Use Lupanov's algorithm inside subsetprod. Use Pippenger's algorithm inside powerprod.

Understand when one-at-a-time multiplication in `units.squares`
is faster than subsetprod and when it's slower.

Use remainder trees in `sqrt.twisted`, as per paper.

Before computing the square root of a product, and even before computing the product itself, shorten the product (at least using the MQ units), with the objective of limiting the number of output bits. This is already done for the square root in generator computation, but not for the square roots in unit computation.

Track logs through field operations, including square roots. This is already done for units but not for generators.

Experiment with representing units as algebraic algorithms (including compact representations as a special case), as discussed in paper.

The unit computation in Pari (via Sage) fails once units are large enough. Consider doing a new implementation. This is probably required anyway if the unit representation is changed.

There are some cases (very small d) where the algorithm frequently finds a longer g. Explore ways to shorten more (in unit computation and then in generator computation): nearest plane, some enumeration, etc. Try shortening with the MQ units first. Try shortening with all units of subfields first. Consider whether the right goal is to have a basis, or merely a generating set; reducing a generating set to a basis is helpful for symbols, but is it helpful for shortening?

Experiments indicate that permuting d (e.g., reversing it) sometimes produces a better basis. Analyze why, and try variants such as always removing smallest regulators.

Short units tend to come from subfields. For example, (1+√5)/2 also appears as (1+0√2+√5+0√10)/2, (1+0√2+0√3+0√6+√5+0√10+0√15+0√30)/2, and so on. Writing down, and performing arithmetic on, these zeros is a waste of space and time. Instead implement a unified MQ field, the composite of all quadratic fields, and put each element into the smallest subfield that contains it (or at least don't frivolously take it out of that field).

**Version:**This is version 2017.05.01 of the Software web page.