Skip to content

Prove knowledge of a message and its signature, without revealing either.

Notifications You must be signed in to change notification settings

Dustin-Ray/blind-rsa

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Today on another episode of impossible problems solved with cryptography:

Suppose agent Bob has a sealed envelope. Contained within is a message, and Bob claims the message is signed by President Alice. However, the message and the signature are top-secret and cannot be revealed. Can we verify that a secret message and its signature are valid, without ever opening the envelope?

Initial Setup:

  • Alice's RSA public key is $(e, n)$.
  • The prover (Bob) knows a signature $s$ such that $s^e \equiv m \mod n$.
  • The prover picks some random non-zero $z \mod{n}$.
  • The prover commits to $c = z^e \cdot m \mod{n}$. This directly implies that $c = (s \cdot z)^e \mod{n}$, and that $s \cdot z \mod{n}$ is a valid signature for $c$.

The ZK Proof Process (Repeated $k$ Times for soundness error $2^{-k}$ ):

  1. Prover's Randomization:

    • The prover picks a random number $r_i \mod{n}$, and computes $d = r_i^e \mod{n}$. $r_i$ is secret, and $d$ is publicly known.
  2. Verifier's Challenge:

    • The Verifier picks a random bit $b_i$ and sends it back to the prover.
  3. Prover's Response:

    • If $b_i = 0$: The prover reveals $r_i$. The Verifier checks that $r_i^e = d$.
    • If $b_i = 1$: The prover reveals $u = r \cdot s \cdot z \mod{n}$. The verifier checks that $u^e = d \cdot c \mod{n}$.

Zero-Knowledge: The protocol is blinding for both the message and the signature. If $z$ is chosen at random, then $c$ is perfectly blinded as a one-time-pad. The only assumption is that RSA is secure and signatures cannot be forged. The partially-homomorphic property of RSA allows for multiplications on blinded values.

Fixed-time: Although entirely insecure, this toy version of RSA is powered by crypto-bigint . All operations are thus performed in fixed-time. Additionally, note that values are represented in Montgomery form, reducing the need for expensive modular reductions.

Thanks: Thank you once again to Dr. Barreto for the riveting exercise.

About

Prove knowledge of a message and its signature, without revealing either.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages