tari-project / triptych

BSD 3-Clause "New" or "Revised" License
0 stars 3 forks source link

feat: add constant-time index decomposition #47

Closed AaronFeickert closed 7 months ago

AaronFeickert commented 7 months ago

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 on 32-bit targets, and a 64-bit word 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.

CjS77 commented 7 months ago

Just a thought: Is subtle not suitable for this?

AaronFeickert commented 7 months ago

I'd hoped so, but it really only handles bitwise operations directly. I didn't see a way to cleanly handle all the operations required for the Gray decomposition. If there is, I'd be happy to switch to it. The method I used is not particularly elegant, but it's definitely safer than nothing.