Short factoring proofs: Addition of phi(N)
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 25/100
- Issue type
- Documentation
- Clarity
- Needs clarification
- Activity status
- Stale
- Domain
- cryptography, documentation
Research direction
Start at the short factoring proof and the vanilla protocol verifier check described in the issue; verify the exponent algebra and the group-order reasoning. Done when the documentation clearly answers whether replacing N−φ(N) with N+φ(N) is valid and records the corrected explanation if needed.
Written by the indexing model from the issue text.
Description
In the short factoring proof, there is the line $y = r + (N - \varphi(N))e$. In the vanilla protocol, the verifier checks $x \overset{?}{\equiv} z^{y - eN} \mod N$. Because $\varphi(N)$ is the order of the multiplicative group of integers modulo $N$, taking the exponent of a multiple of $\varphi(N)$ gives you the identity 1 for all group elements, so $z^{\varphi(N)e} \equiv 1 \mod N$. This is my understanding how the protocol works.
I was wondering, can we define $y = r + (N + \varphi(N))e$ instead? The minus sign seems redundant to me and the above argument should still work, shouldn't it?
- Dominant language
- HTML
- Stars
- 189
- Forks
- 50
- PR merge metrics
- No merged PRs in 30d
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from trailofbits/zkdocs
-
Dark modeOpen
Difficulty 4/5 3-5 days Newbie friendliness 45/100
trailofbits/zkdocs#69 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 30/100
trailofbits/zkdocs#44 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 25/100
trailofbits/zkdocs#19 · 2 comments ·
-
HACSpecOpen
Difficulty 5/5 Over a week Newbie friendliness 15/100
trailofbits/zkdocs#7 · 2 comments ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 45/100
trailofbits/zkdocs#6 · 1 comment ·
All issues in trailofbits/zkdocs
Similar issues
-
bug: native AES-CBC byte operations read mutated input after invocationPossibly taken @harrshita123 claimed this today. Open
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
google/webcrypto.dart#436 · 1 comment ·
Maintainers usually reply within 7 days
-
psbt/musig2.py cites the closed btclib ISS 257Possibly taken A pull request linked to this issue is open or already merged. Open
Difficulty 1/5 Under an hour Newbie friendliness 78/100
btclib-org/btclib-wallet#350 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
Maintainers usually reply within 1 day
-
French BIP39 wordlist starts with a UTF-8 BOM, so generated French mnemonics carry U+FEFF and derive a non-canonical seedPossibly taken @Kshot3000 claimed this 2 days ago. Open
Difficulty 1/5 Under an hour Newbie friendliness 91/100
ergoplatform/sigma-rust#976 ·
Maintainers usually reply within 1 day
-
init variableOpen
Difficulty 1/5 Under an hour Newbie friendliness 88/100
EVerest/EVerest#3052 · 1 reaction ·
Maintainers usually reply within 2 days