Updates for CGGMP'24 #170

fjarri · 2024-12-17T23:45:59Z

Fixes #157
Fixes #43
Fixes #91
Fixes #5 (in progress)

Updated paper references in PAPER.md, removed obsolete items.
Updated to the new range definition (±2^l now means [-2^(l-1)+1, 2^(l-1)] instead of the previous [-2^l, 2^l]). This caused a bit of a chain reaction:
- SecretSigned::assert_exponent_range() logic changed.
- SecretSigned::random_in_exp_range*() logic changed, and also exp was changed to exponent to match the assertion name.
- PublicSigned::from_xof_reader_bounded() changed its behavior to produce the number according to the new range definition, and was renamed to from_xof_reader_in_range().
- PublicSigned::in_range_bits() changed its behavior according to the new range definition, and was renamed to is_in_exponent_range().
- Wherever scalars are passed to proofs and Ciphertext constructor they are passed as SecretSigned, to comply with the range requirements in the proofs.
- conversions::secret_unsigned_from_scalar() removed.
- Added SecretSigned::new_modulo() constructor to make a signed number in range [-N/2, N/2] from an Uint in range [0, N).
- Removed Ciphertext::new() and decrypt() (which took unsigned plaintexts), renamed new_signed() and decrypt_signed() to new() and decrypt().
- Ciphertext::new_with_randomizer() was renamed to new_with_randomizer_unsigned(), since it's now a special one, only used in P_mul. Renamed new_with_randomizer_signed() to new_with_randomizer(), and new_public_with_randomizer_signed() to new_public_with_randomizer().
Following that, wherever in the paper e <-- ±q is used, we are sampling the challenge as a Scalar using the new Scalar::from_xof_reader() method (and using that in П^sch as well).
Updated paper references and notation in aff-g proof.
Updated paper references in prm proof, and started using BitVec for its commitment.
Updated dec proof (there were significant changes). Temporarily, it is located in dec_new.rs, will be moved to dec.rs when Presigning is updated.
Added elog proof.
Added enc-elg proof.
Added aff-g* proof.
Updated paper references and notation in fac proof, and implemented necessary changes to the algorithm (some variables are calculated differently, and the challenge is now a signed Uint and not a Scalar)
Updated paper references and notation in mod proof, and enforced invertibility conditions that were added in '24
Updated paper references and notation sch proof
Removed enc, log*, mul, mul* proofs - they are not used anymore.
Encapsulated the invertibility check in an IsInvertible trait, documenting the choice between GCD and invert()
Updated KeyInit and filled in the code for evidence generation/checking. In particular, fixed Self-contained proof of malicious behavior for Round 3 of KeyGen #103 (by using an echo broadcast in Round 2)
Updated KeyRefresh to the new version and filled in the code for evidence generation/checking.
Updated Presigning/Signing to the new version

TODO:

There is still a question of how to trigger aff-g* star checks in Rounds 5 and 6 - what kind of messages does a malicious node need to send? Are they even needed given that we echo-broadcast D, F, \hat{D}, and \hat{F}?
Implement AuxGen by cutting out parts of KeyRefresh responsible for share changes (this should wait until we stabilize all the shortcuts and code style)
Implement the recommended scheme parameters from Section C.1. Note that there are two possible sets, for 112 bits and 128 bits of security.

codecov · 2024-12-19T02:50:15Z

Codecov Report

Attention: Patch coverage is 96.37496% with 128 lines in your changes missing coverage. Please review.

Project coverage is 95.89%. Comparing base (a3bbfc6) to head (add029f).

Files with missing lines	Patch %	Lines
synedrion/src/cggmp21/aux_gen.rs	43.13%	29 Missing ⚠️
synedrion/src/www02/key_resharing.rs	30.55%	25 Missing ⚠️
synedrion/src/cggmp21/entities.rs	79.24%	11 Missing ⚠️
synedrion/src/cggmp21/key_refresh.rs	98.28%	9 Missing ⚠️
synedrion/src/tools/protocol_shortcuts.rs	85.24%	9 Missing ⚠️
synedrion/src/cggmp21/sigma/aff_g_star.rs	96.51%	7 Missing ⚠️
synedrion/src/cggmp21/interactive_signing_tests.rs	99.06%	6 Missing ⚠️
synedrion/src/cggmp21/key_init.rs	95.62%	6 Missing ⚠️
synedrion/src/cggmp21/sigma/enc_elg.rs	97.12%	5 Missing ⚠️
synedrion/src/tools/protocol_shortcuts_dev.rs	97.40%	4 Missing ⚠️
... and 8 more

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #170      +/-   ##
==========================================
+ Coverage   92.46%   95.89%   +3.43%     
==========================================
  Files          35       37       +2     
  Lines        7030     9454    +2424     
==========================================
+ Hits         6500     9066    +2566     
+ Misses        530      388     -142

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

dvdplm

I have looked at Key_init and Key_refresh tests only.

As mentioned I think it's very cool to see the fault injection machinery come together, it's going to be a major help. The code is verbose and repetitive at times, but this is a complex protocol and its tests are always going to reflect that complexity.
Having the right testing tools is about finding that delicate balance between readability&maintainability and expressiveness. I'm sure we'll fiddle with this plenty mroe in the future but this strikes me as much better than we had before.

dvdplm · 2025-01-10T15:00:16Z

synedrion/src/cggmp21/key_init_tests.rs

+        .collect()
+}
+
+fn check_evidence<M>(expected_description: &str) -> Result<(), LocalError>


Naming nitpick: this does more than merely checking some data against some other; it actually drives the protocol (and checks the outcome). In my head "check" is more "compare these two things and yell if they don't match".

How about a refactor to something more classic like "let r: Result<…, …> = run(); assert_eq!(r, …, "bla bla");"?

Less invasively: a rename to assert_outcome(expected)?

How about a refactor to something more classic like "let r: Result<…, …> = run(); assert_eq!(r, …, "bla bla");"?

It checks a number of things internally:

the malicious node does not create any malicious behavior evidence

all the other nodes create an evidence for the malicious node

the evidence description matches the expected one

Not sure if it's worth packing in one variable.

synedrion/src/cggmp21/key_init_tests.rs

synedrion/src/cggmp21/key_refresh_tests.rs

dvdplm · 2025-01-10T15:08:12Z

synedrion/src/cggmp21/key_refresh_tests.rs

+
+fn check_evidence<M>(expected_description: &str) -> Result<(), LocalError>
+where
+    M: Misbehaving<Id, (), EntryPoint = KeyRefresh<P, Id>>,


It's a pity that check_evidence and make_entry_points have to be instantiated for each EntryPoint. As a new reader of the code, I have to look rather carefully before I spot that this one is for KeyRefresh and the other is KeyInit.
Maybe we can have a macro at some point to make the critical parts more visible, e.g.:
check_evidence!(KeyInit, …, …);
check_evidence!(KeyRefresh, …, …);

synedrion/src/tools/protocol_shortcuts_dev.rs

dvdplm · 2025-01-10T15:11:57Z

synedrion/src/tools/protocol_shortcuts_dev.rs

+    EP: 'static + Debug + EntryPoint<SP::Verifier>,
+    SP: SessionParameters,
+{
+    let prefix = match part {


Not sure, but maybe "phase" is more descriptive than "part" here? ModifyPhase and CheckPhase etc?

It's not really a phase, since they are delivered simultaneously. It mimics the ProtocolMessagePart terminology from manul

synedrion/src/tools/protocol_shortcuts_dev.rs

synedrion/src/cggmp21/key_init_tests.rs

synedrion/src/tools/protocol_shortcuts_dev.rs

To replace the old dec when we are converting Presigning

dvdplm

Review of PAPER.md and README.md

README.md

PAPER.md

dvdplm · 2025-01-24T15:05:14Z

PAPER.md


-Q: In Fig. 5 the initial commitment in the Schnorr proof (`A_i`) is sent twice (in R2 and then R3, as a part of `psi_i`), and then the equality of those two values is checked in Output, right before checking the proof itself. But the commitment value is used right after that in the `vrfy` step, so if it doesn't match the rest of the proof, the verification will fail. So is there any security reason for sending the commitment twice? (I understand that it does constitute a minor performance optimization)
+The above item leads to another problem. If those values are indeed echo-broadcasted, what malicious actions of one node can lead to passing the `П^{dec}` check on other nodes, but failing one of the `П^{aff-g*}` ones?


This seems a little bit concerning. Something worth asking the authors directly?

I did, about a week ago (along with sending them the list of all the other new typos). No response yet.

I guess it's not concerning for them since it's an extra check, not a missing check, so it doesn't compromise the security. But it is concerning for me since I can't test it :)

Also, it sort of hinges on whether we're interested in provable aborts. The authors always talk about identifiable aborts only, which don't need echo-broadcasting of those values, so these checks may be needed to make the П^{aff-g*} aborts identifiable. But my understanding is that we do want provable aborts (which I questioned in entropyxyz/manul#39), so I'm operating based on that.

PAPER.md

dvdplm

Reviewed aff_g_star.rs

dvdplm · 2025-01-24T16:54:34Z

synedrion/src/cggmp21/sigma/aff_g_star.rs

+    elements: Box<[AffGStarProofElement<P>]>,
+}
+


Is it really ok to crash the whole process when this happens? I mean maybe it is, but perhaps it's a design constraint we should make very clear that we're making: when synedrion encounters a catastrophic error (a bug) it will go down.

Is this comment supposed to be attached to the assertions at the start of new()? I thought about it myself, and actually thought I filed an issue about it, but I guess I haven't. Filed #181

Not for this PR though.

synedrion/src/paillier/rsa.rs

dvdplm · 2025-01-24T17:13:25Z

synedrion/src/cggmp21/sigma/aff_g_star.rs

+
+                let cap_a = (public.cap_c * &alpha + Ciphertext::new_with_randomizer(public.pk0, &beta, &r)).to_wire();
+                let cap_r = secret_scalar_from_signed::<P>(&alpha).mul_by_generator();
+                let cap_b = Ciphertext::new_with_randomizer(public.pk1, &beta, &s).to_wire();
+
+                let ephemeral = AffGStarProofEphemeral::<P> { alpha, beta, r, s };
+                let commitment = AffGStarProofCommitment { cap_a, cap_r, cap_b };
+
+                (ephemeral, commitment)
+            })
+            .unzip();
+
+        let mut reader = XofHasher::new_with_dst(HASH_TAG)
+            // commitments
+            .chain(&commitments)


This is the Shamir transform right? How can I double check (against the paper?) that we actually have all the data that we need baked into the reader? Does the order of the params matter here you reckon?

Yep, Shamir transform. That's described in Section 3.4.1. x there are the public parameters, and w are the secret parameters. So as far as I understand it, it prescribes hashing both the public parameters and the commitment into the challenge.

Ideally I think we should have the corresponding public parameters struct to implement Hashable, that will remove the need for duplication of the parameter list.

As for the order, I don't think it matters, it's a hash after all. As long as it's the same on both sides.

synedrion/src/cggmp21/sigma/aff_g_star.rs

fjarri self-assigned this Dec 17, 2024

fjarri force-pushed the new-cggmp branch from b9ed866 to 68a123a Compare December 19, 2024 02:47

fjarri force-pushed the new-cggmp branch 10 times, most recently from 12afc7a to e0565ce Compare December 25, 2024 21:04

fjarri force-pushed the new-cggmp branch 2 times, most recently from cdb7c84 to 0ca10d8 Compare December 31, 2024 22:56

fjarri mentioned this pull request Dec 31, 2024

API adjustments for CGGMP'24 entropyxyz/manul#79

Merged

fjarri force-pushed the new-cggmp branch 2 times, most recently from 0fc38fb to 235afa0 Compare January 3, 2025 22:51

fjarri mentioned this pull request Jan 4, 2025

Protocol writing shortcuts entropyxyz/manul#81

Open

fjarri force-pushed the new-cggmp branch 9 times, most recently from 3efcfd4 to 0f86f18 Compare January 10, 2025 02:47

dvdplm reviewed Jan 10, 2025

View reviewed changes

fjarri commented Jan 10, 2025

View reviewed changes

synedrion/src/tools/protocol_shortcuts_dev.rs Outdated Show resolved Hide resolved

fjarri force-pushed the new-cggmp branch 5 times, most recently from 9a937ba to d3a940f Compare January 22, 2025 23:59

fjarri added 5 commits January 22, 2025 16:04

Update to manul trunk

6c130d9

Update the paper Q&A to the new version

b9aca9e

Change to the new range definition.

597140b

Create challenges as Scalars where +-q range is used

5ed9a52

Add some operator impls

dd9ef42

fjarri force-pushed the new-cggmp branch from d3a940f to 33a6436 Compare January 23, 2025 00:05

fjarri added 15 commits January 23, 2025 11:33

Update aff-g

9e79afa

Update prm, and use BitVec for its challenge

d86bc97

Add the new version of dec

f5ab61c

To replace the old dec when we are converting Presigning

Add elog

acb89a8

Add enc-elg

6682c9a

Add aff-g*

a07cad1

Update fac

563b3ea

Update mod

a299252

Update sch

ab84b76

Use a single method to check for invertibility

30f7d85

Move uint_from_xof to uint::traits

b0cc8e8

Update README

3935dc5

Update KeyInit

887817f

Update KeyRefresh

5bf183d

Update InteractiveSigning

d1131ca

fjarri force-pushed the new-cggmp branch from 33a6436 to d1131ca Compare January 23, 2025 22:03

dvdplm reviewed Jan 24, 2025

View reviewed changes

RFC part 1

add029f

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Updates for CGGMP'24 #170

Updates for CGGMP'24 #170

fjarri commented Dec 17, 2024 •

edited

Loading

codecov bot commented Dec 19, 2024 •

edited

Loading

dvdplm left a comment

dvdplm Jan 10, 2025

fjarri Jan 10, 2025

dvdplm Jan 10, 2025

dvdplm Jan 10, 2025

fjarri Jan 24, 2025

dvdplm left a comment

dvdplm Jan 24, 2025

fjarri Jan 24, 2025

fjarri Jan 24, 2025

dvdplm left a comment

dvdplm Jan 24, 2025

fjarri Jan 24, 2025

fjarri Jan 24, 2025

dvdplm Jan 24, 2025

fjarri Jan 24, 2025


		Q: In Fig. 5 the initial commitment in the Schnorr proof (`A_i`) is sent twice (in R2 and then R3, as a part of `psi_i`), and then the equality of those two values is checked in Output, right before checking the proof itself. But the commitment value is used right after that in the `vrfy` step, so if it doesn't match the rest of the proof, the verification will fail. So is there any security reason for sending the commitment twice? (I understand that it does constitute a minor performance optimization)
		The above item leads to another problem. If those values are indeed echo-broadcasted, what malicious actions of one node can lead to passing the `П^{dec}` check on other nodes, but failing one of the `П^{aff-g*}` ones?

Updates for CGGMP'24 #170

Are you sure you want to change the base?

Updates for CGGMP'24 #170

Conversation

fjarri commented Dec 17, 2024 • edited Loading

codecov bot commented Dec 19, 2024 • edited Loading

Codecov Report

dvdplm left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dvdplm left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dvdplm left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

fjarri commented Dec 17, 2024 •

edited

Loading

codecov bot commented Dec 19, 2024 •

edited

Loading