Permuted puzzles and cryptographic hardness

DOI10.1007/978-3-030-36033-7_18zbMath1455.94131OpenAlexW2990338322MaRDI QIDQ2175950

Justin Holmgren, Mor Weiss, Elette Boyle

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

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

Related Items (5)

Single-server private information retrieval with sublinear amortized time ⋮ Collusion-resistant functional encryption for RAMs ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE ⋮ Two-server distributed ORAM with sublinear computation and constant rounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fiat-Shamir and correlation intractability from strong KDM-secure encryption
• From obfuscation to the security of Fiat-Shamir for proofs
• Can we access a database both locally and privately?
• Towards doubly efficient private information retrieval
• The hunting of the SNARK
• PKP-based signature scheme
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• Cryptographic Assumptions: A Position Paper
• Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
• Circular-Secure Encryption from Decision Diffie-Hellman
• New directions in cryptography
• A method for obtaining digital signatures and public-key cryptosystems
• Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
• Fully homomorphic encryption using ideal lattices
• Fiat-Shamir: from practice to theory
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
• Separating succinct non-interactive arguments from all falsifiable assumptions
• Advances in Cryptology - CRYPTO 2003
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Noise-tolerant learning, the parity problem, and the statistical query model
• On lattices, learning with errors, random linear codes, and cryptography

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