Short proofs of knowledge for factoring
The paper considers the problem of how to prove to a verifier that one knows the factorization of a public modulus without giving any information about the decomposition. An interactive proof of knowledge for the factorization of any public integer \(n\) whose prime factors cannot be found by simple trial division. The protocol is statistical zero knowledge and is a proof of knowledge of a small discrete logarithm of \(z^n \pmod{n}\) for a few randomly chosen elements \(z \pmod{n}\). The communication complexity of the scheme is \(O(k + |n|)\) bits. Results on the probability of generating \(Z^*_{p^e}\) for randomly chosen elements are given and used to prove the security of the protocol given. One round of the protocol consists of the prover randomly choosing an integer \(r \in [0,A[\) and computing for \(i=1,2, \cdots ,K\) the commitments \(x_i = z_i^r \pmod{n}\). The \(x_i\)'s are sent to the verifier who answers with a challenge \(e\) randomly chosen in \([0,B[\). The prover computes \(y=r+(n - \phi (n)) \times e\) and sends it to the verifier who checks \(0 \leq y <A\) and \(z_i^{y-n \times e} = x_i \pmod{n}\). The protocol is repeated \(\ell\) times. The efficiency of the protocol is examined and observations given as how to make it more efficient. A variant is suggested that allows it to work for when \(n\) has small prime factors. For the entire collection see [Zbl 0931.00050].
- Simple zero-knowledge proof of knowing \(\sqrt{X_1}\) or \(\sqrt{X_2}\) mod \(N\)
- Hashing solutions instead of generating problems: on the interactive certification of RSA moduli
- Threshold ECDSA with an offline recovery party
- Bandwidth-efficient threshold EC-DSA
- Blind polynomial evaluation and data trading
- Demonstrating possession without revealing factors and its application
- Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model
- Unifying Zero-Knowledge Proofs of Knowledge
- scientific article; zbMATH DE number 4041785 (Why is no real title available?)
- Proving in zero-knowledge that a number is the product of two safe primes
- Statistical zero knowledge protocols to prove modular polynomial relations
- scientific article; zbMATH DE number 2079923 (Why is no real title available?)
- A zero-knowledge identification protocol in the ring of Gaussian integers
- Argument of knowledge protocol for a Goppa codeword and for an error of a bounded weigth
- Topics in Cryptology – CT-RSA 2004
- One round threshold ECDSA without roll call
- PURED: a unified framework for resource-hard functions
- A discrete logarithm implementation of perfect zero-knowledge blobs
This page was built for publication: Short proofs of knowledge for factoring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4950041)
