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.sage n s x
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)[x1...,xn]/(x12−d1,...,xn2−dn); 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 = f02 − f12 d if h0−s is not divisible by 2d, and prune the branch s = f12 d − f02 if h0+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.
