Artifacts for "MPC in the head using the subfield bilinear collision problem"

This folder contains the artifacts for the paper "MPC in the head using the subfield bilinear collision problem" submitted to CRYPTO 2024. This includes the necessary source code to reproduce the results from the paper.

The artifact contains the files 'maketest.sh', 'maketest-sha.sh', 'SBChypercube-unified.c', 'SBCtools.c', 'SBCunified.h' and 'SBCunified-CPUspecific.h'

The code was primarily developped on Intel/AMD processors with AES instructions available. A more portable version is also provided, however, it is much slower.

To use the Intel/AMD version, it is necessary to install the "libmd-dev" package (to get access to SHA256).
To use the more portable version, it is necessary to install crypto-algorithms by Brad Conte. This is achieved by running the command:
git clone https://github.com/B-Con/crypto-algorithms.git
in the PARENT directory of the present code artefact.

The selection between portable and Intel/AMD is done by providing an argument to the 'maketest.sh' and 'maketest-sha.sh' scripts (see below).

The code from 'SBChpbercube-unified.c' contains the implementations of all versions of the SBC scheme used in the comparison form Section 6 in the paper.
All versions use the 128-bit security level with parameters q=2, k=257 and n=130 as specified in Section 4.

The number of parties used in the signature scheme can be specified using the '-DL$i' command. We use the parameters for the 128-bit security level specified in Table 1 on page 18 of the paper. The number of parties and the number of rounds is set according the value of $i given.
$i corresponds to the log of the number of parties N=2^D that should be used.
The different versions using '-DL8', '-DL9', '-DL10', '-DL11', '-DL12', '-DL13', '-DL15', '-DL16' correspond to the parameters for N and tau specified in Table 1 in the paper.

The option '-DSBC_BASIC' means that the "SBC GGM" version of the protocol specified in Section 6 is used.

The option '-DDONTfixX' means that a basic GGM tree is used in the protocol. Not using this options means that the correlated GGM (cGGM) tree is used, obtaining a smaller signature size compared to the basic version.

The option '-DSBC_HASHED_T' means that a hash function is used to derive the value of t_0 during the protocol execution. This version is named using the superscript "SBC^H(t_0)" in the paper.

The option '-DCLASSICAL_SHA_TREE' uses SHA256 in the construction of the GGM tree. If this is not specified, a construction based on AES is used.

The option '-DCLASSICAL_FOLDING' uses the standard folding of the tree. If this is not specified, the fast folding algorithm described in Section 6.2 is used in the protocol.

With these options, the different versions of the SBC signature scheme compared in Section 6 are specified.

By running the file 'maketest.sh', a script is run which executes every parameter choice for the different versions of the SBC problem specified in Table 2 in the paper (using AES for the GGM tree).
By running the file 'maketest-sha.sh', a script is run which executes the protocol using the different GGM constructions specified in Table 5: A version using SHA256 and regular folding, a version using AES and regular folding and a version using AES and fast folding.
The outputs include the work memory size, the signature size, as well as the timings and clock cycles of the key generation, signature and verification algorithms.

To run the Intel/AMD versions using libmd, just execute 'maketest.sh' and 'maketest-sha.sh' without any argument.
To run the portable versions there are two options:
- Execute 'maketest.sh portable' or 'maketest-sha.sh portable' to use the portable AES and SHA functions from the "crypto-algorithms" repository
- Execute 'maketest.sh portablesha' or 'maketest-sha.sh portablesha' to use the SHA function from the "crypto-algorithms" repository

Warning:
The Intel/AMD versions and the portable versions do not give the exact same keys or signatures, due to a different endianness for the respective AES implementations.