Advanced Concepts in Zero-Knowledge Proofs

Unique NIZKs Unique NIZKs and and Steganography Steganography Detection Detection W I L L Y W I L L Y Q U A C H Q U A C H , , L A K Y AH T Y N E R L A K Y AH T Y N E R , , A N D D A N I E L A N D D A N I E L W I C H S W I C H S

Motivation Motivation Zero-knowledge proofs were introduced in 1985 by Goldwasser, Micali and, Rackoff ? ?? ?? ? ????? ???

Motivation Motivation Zero-knowledge proofs were introduced in 1985 by Goldwasser, Micali and, Rackoff ? ?? ?? ? ????? ???

Motivation Motivation Zero-knowledge proofs were introduced in 1985 by Goldwasser, Micali and, Rackoff ? ?? ?? ? ????? ??

Motivation Motivation What if we remove interaction? Blum, Feldman, and Micali 1988 tells us we need a ??? ??? ? ?? ?? ??? ?? ??? [BFM88, FLS90, CHK03, GOS06, CCH+19, PS19]

Motivation Motivation Sahai-Waters NIZK (from iO) has a deterministic prover ??? ? ?? ?? ??? So the prover send the same proof for a given statement

Motivation Motivation Adversary could find a different proof that the verifier accepts ??? ? ?? ?? ??? ? ?? ?? ??

Motivation Motivation Could there exists only a single unique accepting proof for a statement ?? ??? ? ?? ?? ???

Motivation Motivation Uniqueness implies witness encryption, even when the prover is honest and even without ZK ??? ? ?? ?? ??? ? ? We can convert Sahai-Waters proof into a unique proof using injective OWF

The Model and Our Results The Model and Our Results We consider a version of unique zero-knowledge proofs (UNIZKs) [Lepinski, Micali, shelat 05] with the following two relaxations: Stat. unique proofs proofs ? for NP languages with comp. unique witnesses witnesses ? 1. Any malicious ? who can produce accepting ? ? for ? also knows valid ? ? UNIZKs with prover setup. Given a ??? the prover samples random (??,??) 2. ?? is used to generate proofs for arbitrarily many statements. Once ?? is fixed, subsequent proofs are unique * We show that removing either relaxation implies witness encryption

The Model and Our Results The Model and Our Results Assuming the hardness of Learning with Errors (LWE), we build multi- theorem Unique NIZKs (UNIZKs) for NP satisfying adaptive* soundness/uniqueness/zero-knowledge. *Adversary can see the ??? before choosing statement

Prior Work Prior Work Fair Zero-Knowledge [Lepinski, Micali, shelat 05] Essentially equivalent definition of uniqueness but they achieve UNIZKs under Quadratic Residuosity Open question to get UNIZKs from other assumptions Steganography Free Zero Knowledge (SF-ZK) [Abdolmaleki et al. 22] Similar definition but interactive proof and interactive setup between P and V

Application: Steganography Detection Application: Steganography Detection Consider a server that generates DSA signatures

Application: Steganography Detection Application: Steganography Detection If the server is compromised then it could leak information about ?? steganographically The signatures are randomized so the server could intelligently choose which signatures to send

Application: Steganography Detection Application: Steganography Detection Authority sets up a PRF Server uses a UNIZK to prove that randomness used is from PRF

Recall: Recall: Multi-theorem UNIZK satisfying adaptive soundness/uniqueness/zero-knowledge against maliciously generated keys

Recall: Recall: Multi-Single theorem UNIZK satisfying adaptive soundness/uniqueness/zero-knowledge against maliciouslyhonestly generated keys

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ?

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ? {0,1} ?

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ??? ? {0,1} ?

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ?? ? {0,1} ?

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ?? ?,? ? ? commitments to labels

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ?? *permuted for ? ?,? ? } ?? = { , , commitments to garbling randomness commitments to labels ?? = { } , openings to labels openings to garbling randomness

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ?? ?,? Opening to labels for ?||?

Single Theorem UNIZK with Honest Prover Setup Single Theorem UNIZK with Honest Prover Setup ? } ?? = { , , ?? commitments to garbling randomness commitments to labels Opening to labels for ?||? correspond? and openings labels (?,?) ? {0,1}

Proof Intuition Proof Intuition *permuted for ? } ????? = { ? } ?? = { , , Opening to labels for ?||? commitments to garbling randomness commitments to labels Soundness follows from binding of commitments and correctness of garbling Uniqueness holds as long as commitments have statistically unique openings Zero-Knowledge follow from hiding of the commitments

Recall: Recall: Multi-Single theorem UNIZK satisfying adaptive soundness/uniqueness/zero-knowledge against maliciouslyhonestly generated keys

Recall: Recall: Multi-theorem UNIZK satisfying adaptive soundness/uniqueness/zero-knowledge against maliciouslyhonestly generated keys

Transformation to Multi Transformation to Multi- -theorem: Take 1 theorem: Take 1 Similar to transformation from one Similar to transformation from one- -time to many time to many- -time signatures time signatures (??,??) (??0,??0) (??1,??1) (??01,??01) (??00,??00) (??10,??10) (??11,??11) . . . . . .

Transformation to Multi Transformation to Multi- -theorem: Take 1 theorem: Take 1 Similar to transformation from one Similar to transformation from one- -time to many time to many- -time signatures time signatures commitment to PRF (??0,??0) Madre (??01,??01) Ni a (??00,??00) Ni o Generates ??00,??00 and (??01,??01) Proves that task #1 is done wrt a committed PRF key using single theorem UNIZK

Transformation to Multi Transformation to Multi- -theorem: Take 1 theorem: Take 1 Similar to transformation from one Similar to transformation from one- -time to many time to many- -time signatures time signatures (??,??) commitment to PRF (??0,??0) (??1,??1) . . . . . . (??01,??01) (??00,??00) (??10,??10) (??11,??11) (???,???)

Transformation to Multi Transformation to Multi- -theorem: Take 1 theorem: Take 1 Similar to transformation from one Similar to transformation from one- -time to many time to many- -time signatures time signatures (??,??) commitment to PRF (??0,??0) (??1,??1) . . . . . . (??01,??01) (??00,??00) (??10,??10) (??11,??11) (???,???)

Multi Multi- -theorem: Take 1 Summary theorem: Take 1 Summary Similar to transformation from one Similar to transformation from one- -time to many time to many- -time signatures time signatures ????? ???? (??,??) ?? = { } ?,? (???,???) commitment to PRF ? (??0,??0) Single theorem UNIZK (??01,??01) s? = { ? } , opening for ? commitment (???,???) The security of the parent single theorem proofs ensures soundness + uniqueness of the child proofs

Issue with previous attempt Issue with previous attempt Recall that ?? for single theorem proof includes garbled ? which grows with ||?|| *permuted for ? ? } ?? = { , , commitments to garbling randomness commitments to labels

Issue with previous attempt Issue with previous attempt | generated child keys using ? | = ? | generated child keys using ? | = ?

Issue with previous attempt Issue with previous attempt | generated child keys using ? | = ? |??0| | generated child keys using ? | = ? |??1|

Issue with previous attempt Issue with previous attempt ?? ??0 + ??1 2? | generated child keys using ? | = ? |??0| | generated child keys using ? | = ? |??1|

Issue with previous attempt Issue with previous attempt ?? ??0 + ??1 2? | generated child keys using ? | = ? |??0| | generated child keys using ? | = ? |??1| Need a single-theorem UNIZK that can prove statements about setup efficiently Use FHE to get one with fixed key size for arbitrary statements

Recall: Recall: Multi-theorem UNIZK satisfying adaptive soundness/uniqueness/zero-knowledge against maliciouslyhonestly generated keys

Recall: Recall: Multi-theorem UNIZK satisfying adaptive soundness/uniqueness/zero-knowledge against maliciously generated keys

Multi Multi- -theorem with Malicious Keys theorem with Malicious Keys ????? (??,??) (??0,??0) (??1,??1) (??01,??01) (??00,??00) (??10,??10) (??11,??11) . . . . . .

Summary Summary Defining UNIZKs Application for Steganography Detection Constructed Single-theorem UNIZKs Constructed Multi-theorem UNIZKs from Single-theorem Constructed Multi-theorem UNIZKs with malicious keys

Thank you!

Proof Intuition for Multi Proof Intuition for Multi- -theorem theorem

Proof Intuition: Multi Proof Intuition: Multi- -theorem Zero Knowledge theorem Zero Knowledge ????? ???? (??,??) ?,? ?? = { } {???}? , (???,???) commitment to PRF ? (??0,??0) (??01,??01) Single theorem UNIZK s? = { } ? {???}? , , (???,???) opening for ? commitment

Proof Intuition: Soundness Proof Intuition: Soundness ????? ???? (??,??) pseudo ?,? ?? = { } {???}? , (???,???) commitment to PRF ? (??0,??0) pseudo (??01,??01) pseudo Single theorem UNIZK s? = { } ? {???}? , , (???,???) pseudo opening for ? commitment

Proof Intuition: Uniqueness Proof Intuition: Uniqueness (??,??) (??,??) ?,? ?,? (???,???) (???,???) (??0,??0) (??0,??0) (??01,??01) (??01,??01) Single theorem UNIZK Single theorem UNIZK (???,???) (???,???) Proof #1 Proof #2

Proof Intuition: Uniqueness Proof Intuition: Uniqueness (??,??) (??,??) ?,? ?,? (???,???) (???,???) (??0,??0) (??0,??0) (??01,??01) (??01,??01) Single theorem UNIZK Single theorem UNIZK (???,???) (???,???) Proof #1 Proof #2

Proof Intuition: Uniqueness Proof Intuition: Uniqueness (??,??) (??,??) ?,? ?,? (???,???) (???,???) (??0,??0) (??0,??0) (??01,??01) (??01,??01) Single theorem UNIZK Single theorem UNIZK (???,???) (???,???) Proof #1 Proof #2

Proof Intuition: Uniqueness Proof Intuition: Uniqueness statement = generated child keys using ? statement = generated child keys using ? witness = {?, witness = {?, } } opening for ? commitment opening for ? commitment Proof #1 Proof #2