0
$\begingroup$

I've recently understood the difference between Interactive Proofs and Arguments, but even if several standard variations of IP are well known and thoroughly described in textbooks (Goldreich for instance) Arguments are not so well documented.

In particular I'm having a hard time to find a well established definition for the notion of argument of knowledge (I understand that intuitively the extractor has access to a PPT prover with auxiliary input) that could also possibly be cited

thank in advance

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The notion of proofs (resp., argument) of knowledge was introduced in [GMR] (resp., [BCLL]), but the definition in both the papers is more intuitive than formal. Attempts were made at more formal definitions in [FFS] and [FS]. The culmination of these lines of work (I believe) is [BG], which is what I would recommend reading since (i) it post-dates the other works and (ii) it provides a good summary of the previous definitions (see Appendix A). [BG] focuses on proofs of knowledge, but the definitions for arguments of knowledge is similar (see §4.7).

Addendum. As @Yehuda Lindell points out, the textbook definition in [G] is worth looking into and it seems that the definition there closely follows [BG] (see the historical notes in §4.12.1).

[BCLL], Brassard, Crépeau, Laplante and Léger, Computationally Convincing Proofs of Knowledge, STACS'91

[BG] Bellare and Goldreich, On Defining Proofs of Knowledge, Crypto'92

Feige, Fiat and Shamir, Zero-knowledge proofs of identity, STOC'87

Feige and Shamir, Witness indistinguishable and witness hiding protocols, STOC'90

Goldwasser, Micali and Rackoff, The Knowledge Complexity of Interactive Proof-Systems, STOC'85

Goldreich, Foundations of Cryptography, Volume 1

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I would just add that Oded deals with proofs of knowledge in his textbook "Foundations of Cryptography, volume 1" as well. It's worth looking there too. $\endgroup$
    – Yehuda Lindell
    Commented Jul 28, 2020 at 7:41
  • $\begingroup$ True, that's actually my starting point, but for what regards arguments only the computational soundness is defined (assuming I didn't miss anything) $\endgroup$
    – JayTuma
    Commented Jul 28, 2020 at 11:41
  • $\begingroup$ Beyond limiting the prover to be polynomial time, what difference does it make? The definition should be unchanged beyond this point. No? $\endgroup$
    – Yehuda Lindell
    Commented Jul 29, 2020 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.