multimixer-128
Multimixer-128: Universal Keyed Hashing Based on Integer Multiplication
Overview
$Multimixer_{128}$ is a universal keyed hashing algorithm, based on just integer arithmetic ( addition and multiplication ), proposed in paper https://ia.cr/2023/1357.
A keyed hash function, takes a key and a variable length message as input, compressing it to a fixed length digest. The keyed hashing scheme proposed in $Multimixer_{128}$ paper, takes equal length key and message ( meaning long keys will be required, in case message is long ) s.t. they are multiple of block size ( = 32 -bytes ) and compresses them into a 64 -bytes digest. It's proved to be an ε-∆universal hash function with ε = $2^{−127}$. It can be used during the compression phase of a message authentication code computation scheme. It can also be used in the compression phase of the Farfalle construction - which are used for building deck functions.
As $Multimixer_{128}$ is just based on integer arithmetic, which is pretty fast on most processors, it shows quite promising results during benchmarks. See below.
You can also find more details on how to start using $Multimixer_{128}$ API, below.
Prerequisites
Rust stable toolchain; see https://rustup.rs for installation guide.
# When developing this library, I was using
)
[!TIP] I advise you to use
cargo-criterion
for running benchmark executable. Read more about it @ https://crates.io/crates/cargo-criterion. You can just issue following command for installing it system-wide.
Testing
For ensuring functional correctness and conformance to the specification of $Multimixer_{128}$ i.e. https://ia.cr/2023/1357 ( and its reference implementation https://github.com/Parisaa/Multimixer ), I use known answer tests that I've generated by following instructions described in https://gist.github.com/itzmeanjan/a32eab0244af55eba2847c6472337535.
Benchmarking
Issue following command for benchmarking public function $f_{128}$ and $Multimixer_{128}$, with variable ( non-zero multiple of 32 -bytes ) length input key and message, on target CPU.
[!NOTE] When benchmarking on
x86
,x86_64
,aarch64
orloongarch64
targets, CPU cycles and cycles/ byte metrics are reported, while for other targets, default wallclock timer of criterion.rs is used for reporting time and throughput. I found https://github.com/pornin/crrl/blob/73b33c1efc73d637f3084d197353991a22c10366/benches/util.rs pretty useful for obtaining CPU cycles when benchmarking Rust functions. But I'm using criterion.rs as benchmark harness, hence I decided to go with https://crates.io/crates/criterion-cycles-per-byte plugin, much easier to integrate. But I had to patch it for my usecase and they live in the branchadd-memfence
of my fork ofcriterion-cycles-per-byte
( see my commits @ https://github.com/itzmeanjan/criterion-cycles-per-byte/commits/add-memfence ).
[!NOTE] In case you're running benchmarks on aarch64 target, consider reading https://github.com/itzmeanjan/criterion-cycles-per-byte/blob/d2f5bf8638640962a9b301966dbb3e65fbc6f283/src/lib.rs#L63-L70.
[!CAUTION] When benchmarking make sure you've disabled CPU frequency scaling, otherwise numbers you see can be pretty misleading. I found https://github.com/google/benchmark/blob/b40db869/docs/reducing_variance.md helpful.
# In case you didn't install `cargo-criterion`, you have to run benchmark with
# RUSTFLAGS="-C opt-level=3 -C target-cpu=native" cargo bench --features="internal"
RUSTFLAGS="-C opt-level=3 -C target-cpu=native"
On 12th Gen Intel(R) Core(TM) i7-1260P
)
)
)
)
)
)
)
)
)
)
)
)
On ARM Cortex-A72 i.e. Raspberry Pi 4B
)
)
)
)
)
)
)
)
)
)
)
)
Usage
Using $Multimixer_{128}$ hasher API is pretty straight-forward.
- Add
multimixer-128
to the [dependencies] section of the Cargo.toml file of your project.
[]
= { = "https://github.com/itzmeanjan/multimixer-128" }
# or
= "0.1.4"
# In case you're also interested in using f_128, the public function of multimixer-128,
# enable `internal` feature-gate of this crate.
#
# multimixer-128 = { version = "0.1.4", features = "internal" }
- Get non-zero, equal length key and message s.t. their byte length is a multiple of block size (= 32 -bytes), as input.
use multimixer_128;
- Compute 64 -bytes message digest, given equal length (non-zero) key and message.
I'm maintaining an example program, demonstrating usage of $Multimixer_{128}$ API, living inside examples directory.
[!NOTE] Most of the internal functions of this library crate are implemented as
const fn
i.e. compile-time evaluable functions. That's why I also maintain another example f_128.rs which demonstrates that property of this library using static assertions. Try executing the example program by issuing$ cargo run --example f_128 --features="internal"
and you'll see it.