Permuted puzzles and cryptographic hardness

DOI10.1007/978-3-030-36033-7_18zbMATH Open1455.94131OpenAlexW2990338322MaRDI QIDQ2175950FDOQ2175950

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

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

zbMATH Keywords

hard permuted puzzlespermuted puzzle problems

Mathematics Subject Classification ID

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

Cites Work

• Fully homomorphic encryption using ideal lattices
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• A method for obtaining digital signatures and public-key cryptosystems
• New directions in cryptography
• Title not available (Why is that?)
• Title not available (Why is that?)
• Noise-tolerant learning, the parity problem, and the statistical query model
• Circular-Secure Encryption from Decision Diffie-Hellman
• Advances in Cryptology - CRYPTO 2003
• Candidate indistinguishability obfuscation and functional encryption for all circuits
• Separating succinct non-interactive arguments from all falsifiable assumptions
• Title not available (Why is that?)
• Title not available (Why is that?)
• PKP-based signature scheme
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• Cryptographic assumptions: a position paper
• 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
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Title not available (Why is that?)
• Fiat-Shamir: from practice to theory
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir

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)