The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
From MaRDI portal
Recommendations
- I/O-Efficiently Pruning Dense Spanners
- The input/output complexity of sparse matrix multiplication
- The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
- Sparsification and subexponential approximation
- Optimal sparse matrix dense vector multiplication in the I/O-model
- On the limits of sparsification
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
- Computing sparse permanents faster
Cites work
- \(k\)-round multiparty computation from \(k\)-round oblivious transfer via garbled interactive circuits
- A generic approach to constructing and proving verifiable random functions
- A Pseudorandom Generator from any One-way Function
- Advances in Cryptology - EUROCRYPT 2004
- Advances in Cryptology - EUROCRYPT 2004
- Advances in Cryptology – CRYPTO 2004
- Bounded key-dependent message security
- Breaking the sub-exponential barrier in obfustopia
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- Chosen-Ciphertext Secure Fully Homomorphic Encryption
- Circular-Secure Encryption from Decision Diffie-Hellman
- Compactness vs collusion resistance in functional encryption
- Constrained pseudorandom functions and their applications
- Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness
- Efficient Identity-Based Encryption Without Random Oracles
- Fiat-Shamir and correlation intractability from strong KDM-secure encryption
- Function secret sharing
- Functional signatures and pseudorandom functions
- Graded encoding schemes from obfuscation
- How to obfuscate programs directly
- How to use indistinguishability obfuscation
- scientific article; zbMATH DE number 1583797 (Why is no real title available?)
- scientific article; zbMATH DE number 1088253 (Why is no real title available?)
- scientific article; zbMATH DE number 1951605 (Why is no real title available?)
- scientific article; zbMATH DE number 1842483 (Why is no real title available?)
- Impossibility of VBB obfuscation with ideal constant-degree graded encodings
- Indistinguishability obfuscation from compact functional encryption
- Indistinguishability obfuscation from functional encryption
- Indistinguishability obfuscation from semantically-secure multilinear encodings
- Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs
- Indistinguishability obfuscation from trilinear maps and block-wise local PRGs
- New negative results on differing-inputs obfuscation
- Obfuscation for Cryptographic Purposes
- Obfuscation of probabilistic circuits and applications
- On Best-Possible Obfuscation
- On extractability obfuscation
- On non-black-box simulation and the impossibility of approximate obfuscation
- On obfuscating point functions
- On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input
- On the impossibility of approximate obfuscation and applications to resettable cryptography
- On virtual grey box obfuscation for general circuits
- Perfect Non-interactive Zero Knowledge for NP
- Programmable Hash Functions and Their Applications
- Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps
- Public-coin differing-inputs obfuscation and its applications
- Replacing a random oracle: full domain hash from indistinguishability obfuscation
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Securely Obfuscating Re-encryption
- Short and Stateless Signatures from the RSA Assumption
- Single-key to multi-key functional encryption with polynomial loss
- Spooky Encryption and Its Applications
- Standard security does not imply indistinguishability under selective opening
- The Magic of ELFs
- Two-round multiparty secure computation from minimal assumptions
- Two-round secure MPC from indistinguishability obfuscation
- Universal proxy re-encryption
- Verifiable random functions from non-interactive witness-indistinguishable proofs
Cited in
(8)- Universal proxy re-encryption
- Indistinguishability obfuscation with non-trivial efficiency
- Obfuscation of probabilistic circuits and applications
- Instantiability of classical random-oracle-model encryption transforms
- Searching for ELFs in the cryptographic forest
- Adaptive security in SNARGs via iO and lossy functions
- Anamorphic resistant encryption: the good, the bad and the ugly
- Client-server homomorphic secret sharing in the CRS model
This page was built for publication: The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041157)
