Index operations are not constant time #5
Comments
|
The recent Gray code iterator added in #17 for index decomposition does a vector comparison that is not a constant-time operation. This is easy to fix using The updated decomposition still includes modular reduction and integer division that may need to be separately addressed. |
AaronFeickert
added a commit
that referenced
this issue
Feb 2, 2024
This PR adds a Gray decomposition function that runs in constant time. This is useful since decomposition of the signing index currently uses modular reduction and division operations that do not run in constant time. The functionality is accomplished in a somewhat kludgy manner using `crypto-bigint`, which represents its `Uint` types internally using target-specific word sizes. To ensure we support 32-bit targets, we use a single-limb `Uint<1>` type to represent the index and modulus for Gray decomposition; this limb wraps [a 32-bit word](https://github.com/RustCrypto/crypto-bigint/blob/e925f370995da5ca519db482906aff4679656c4a/src/limb.rs#L36-L38) on 32-bit targets, and [a 64-bit word](https://github.com/RustCrypto/crypto-bigint/blob/e925f370995da5ca519db482906aff4679656c4a/src/limb.rs#L48-L50) on 64-bit targets. Once we complete the required decomposition operations in constant time, we reach into the `Uint<1>` limb and extract the word, converting to a `u32` in a target-dependent manner. It would be nice if there were an easier way to support constant-time operations with a `U32` type supplied by the library in a way that allowed for cleanly extracting the underlying `u32`, but this is not the case. The Triptych prover and verifier each iterate over all possible Gray-decomposed indexes, while the prover additionally decomposes the signing index separately. For this reason, we keep the existing variable-time decomposition functionality as `GrayIterator::decompose_vartime`, and support the new constant-time functionality as `GrayIterator::decompose`. When constructing a `GrayIterator` for iteration, the variable-time functionality is chosen. This keeps things speedy in the case when no secret data is being used. Closes #5.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The implementation makes no guarantees about witness index operations being constant time, though signing key operations should get this for free thanks to the curve library's use of
subtle.Recent work in #4 makes the Kronecker delta, which is applied to an index decomposition, a constant-time operation. However, the decomposition itself uses modular reduction and integer division that should be addressed. It's not immediately clear the best approach to take for this. One option could be using the
crypto-bigintlibrary.The text was updated successfully, but these errors were encountered: