On Cryptographic Assumptions and Challenges

By Moni Naor. 2003

343 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Pinocchio: Nearly Practical Verifiable Computation (2013, background): “of cryptographic assumptions that do not lend themselves to efficient falsification [37], though some members have indeed been proven false [38].”
Non-interactive Zaps and New Techniques for NIZK (2006, methodology): “The assumption was introduced by Boneh, Boyen and Shacham in [ BBS04 ].”
Functional Signatures and Pseudorandom Functions (2014, background): “Gentry and Wichs showed in [GW11] that SNARG schemes for NP with proof size r ( k ) · ( | x | + | w | ) o (1) for polynomial r ( · ) cannot be obtained using black-box reductions to falsiﬁable assumptions [Nao03].”
Secure Two-Party Computation is Practical (2009, methodology): “In particular, this assumption is falsifiable according to the definition of Naor [28], meaning that given a candidate function H it is possible to design a challenge which can be broken if H is not correlation robust, whereas it is impossible to design a similar challenge with regards to the modeli”
Structure-Preserving Signatures and Commitments to Group Elements (2010, background): “, without random oracles) and under falsifiable (and thus non-interactive) intractability assumptions [80].”
Short Pairing-Based Non-interactive Zero-Knowledge Arguments (2010, background): “Knowledge of exponent assumptions have been criticized for being unfalsifiable [36] but the use of a non-standard assumption may be unavoidable since Abe and Fehr [1] have demonstrated that no statistical zero-knowledge NIZK argument for an NP-complete language has a “direct black-box” reduction to ”
Expressive Key-Policy Attribute-Based Encryption with Constant-Size Ciphertexts (2011, background): “In addition, it is non-interactive and falsifiable [26].”
Quadratic Span Programs and Succinct NIZKs without PCPs (2013, background): “Recent work [8, 19, 26] (see also [17]) has improved Micali’s construction by removing the random oracle, which is known to be uninstantiable [15], and replacing it with an “extractable collision-resistant hash function” (ECRH), whose security relies on the plausible, but non-falsifiable [37], assum”
Public-Key Cryptosystems Resilient to Key Leakage (2009, background): “However, such a sub-exponential hardness assumption does not seem to be “efficiently falsifiable” according to Naor’s classification [66] (that is, if the assumption is false it is not clear that this fact can be demonstrated in polynomial time).”
Verifiable ASICs (2016, background): “The trade-off is that arguments require cryptographic assumptions (standard ones for interactive arguments, nonfalsifiable [86] ones for SNARKs).”
Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles) (2006, background): “Informally, we say that an assumption is mild if it is tautological in the generic group model [29], and also “efficiently falsifiable” [27] in the sense that its problem instances are stated non-interactively and concisely (e.”
Unidirectional Chosen-Ciphertext Secure Proxy Re-Encryption (2008, unknown): “[39]) complexity assumption in bilinear groups.”