Permuted puzzles and cryptographic hardness

DOI10.1007/978-3-030-36033-7_18MaRDI QIDQ2175950zbMATH OpenOpenAlexFDO

Authors Elette Boyle, Justin Holmgren, Mor Weiss

Publication date 30 April 2020

Full work available at URL https://doi.org/10.1007/978-3-030-36033-7_18

zbMATH Keywords

hard permuted puzzlespermuted puzzle problems

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Cryptography (94A60)

Recommendations

• On basing private information retrieval on NP-hardness
• The iterated random permutation problem with applications to cascade encryption
• Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
• Towards doubly efficient private information retrieval
• The query complexity of finding a hidden permutation

Cites work

• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• scientific article; zbMATH DE number 1024063 (Why is no real title available?)
• scientific article; zbMATH DE number 1759771 (Why is no real title available?)
• scientific article; zbMATH DE number 1842483 (Why is no real title available?)
• A method for obtaining digital signatures and public-key cryptosystems
• Advances in Cryptology - CRYPTO 2003
• Can we access a database both locally and privately?
• Candidate indistinguishability obfuscation and functional encryption for all circuits
• Circular-Secure Encryption from Decision Diffie-Hellman
• Cryptographic assumptions: a position paper
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Fiat-Shamir and correlation intractability from strong KDM-secure encryption
• Fiat-Shamir: from practice to theory
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
• From obfuscation to the security of Fiat-Shamir for proofs
• Fully homomorphic encryption using ideal lattices
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• New directions in cryptography
• Noise-tolerant learning, the parity problem, and the statistical query model
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• On lattices, learning with errors, random linear codes, and cryptography
• PKP-based signature scheme
• Separating succinct non-interactive arguments from all falsifiable assumptions
• The hunting of the SNARK
• Towards doubly efficient private information retrieval

Cited in

(6)

• Two-server distributed ORAM with sublinear computation and constant rounds
• Lower bounds for (batch) PIR with private preprocessing
• Collusion-resistant functional encryption for RAMs
• Single-server private information retrieval with sublinear amortized time
• Cryptoschemes based on difficulty of simultaneous solving two different difficult problems
• Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE

This page was built for publication: Permuted puzzles and cryptographic hardness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175950)