scientific article
From MaRDI portal
Publication:3729902
zbMath0596.65002MaRDI QIDQ3729902
Silvio Micali, Shafi Goldwasser, Oded Goldreich
Publication date: 1986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitypolynomial-time algorithmrandomnessone-way functionsprediction problemsrandom functionspseudo random number generation
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Random number generation in numerical analysis (65C10)
Related Items
Hidden cosets and applications to unclonable cryptography ⋮ Computational hardness of optimal fair computation: beyond Minicrypt ⋮ Evolving homomorphic secret sharing for hierarchical access structures ⋮ MoSS: modular security specifications framework ⋮ Certifying trapdoor permutations, revisited ⋮ A simple construction of iO for Turing machines ⋮ FE and iO for Turing machines from minimal assumptions ⋮ Watermarking PRFs under standard assumptions: public marking and security with extraction queries ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Pattern matching on encrypted streams ⋮ Quantum algorithms for the \(k\)-XOR problem ⋮ Functional encryption for Turing machines with dynamic bounded collusion from LWE ⋮ Targeted lossy functions and applications ⋮ Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time ⋮ A construction of the simplest super pseudorandom permutation generator ⋮ Leakage-resilient cryptography from minimal assumptions ⋮ Efficient noise generation to achieve differential privacy with applications to secure multiparty computation ⋮ Function-private conditional disclosure of secrets and multi-evaluation threshold distributed point functions ⋮ Kernels as features: on kernels, margins, and low-dimensional mappings ⋮ Incremental cryptography revisited: PRFs, nonces and modular design ⋮ Simpler constructions of asymmetric primitives from obfuscation ⋮ CCA secure \textit{a posteriori} openable encryption in the standard model ⋮ On the security of two identity-based conditional proxy re-encryption schemes ⋮ Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions ⋮ Performance improvement for the GGM-construction of pseudorandom functions ⋮ Mathematical problems in cryptology ⋮ Tree-based cryptographic access control ⋮ An unpredictability approach to finite-state randomness ⋮ Lightweight, maliciously secure verifiable function secret sharing ⋮ Incompressible cryptography ⋮ Distributed (correlation) samplers: how to remove a trusted dealer in one round ⋮ Batch-OT with optimal rate ⋮ A study of password security ⋮ Revocable hierarchical identity-based encryption with shorter private keys and update keys ⋮ From cryptomania to obfustopia through secret-key functional encryption ⋮ From minicrypt to obfustopia via private-key functional encryption ⋮ Matrix PRFs: constructions, attacks, and applications to obfuscation ⋮ Long-term security and universal composability ⋮ Checking the correctness of memories ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation ⋮ FORSAKES: a forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes ⋮ New proofs for NMAC and HMAC: security without collision resistance ⋮ Efficient authentication from hard learning problems ⋮ Keymill: side-channel resilient key generator, a new concept for SCA-security by design ⋮ Provably-secure time-bound hierarchical key assignment schemes ⋮ Leakage-resilient cryptography from puncturable primitives and obfuscation ⋮ Non-interactive secure computation from one-way functions ⋮ Simple and more efficient PRFs with tight security from LWE and matrix-DDH ⋮ On learning a union of half spaces ⋮ On the impossibility of structure-preserving deterministic primitives ⋮ Computational indistinguishability: A sample hierarchy ⋮ On the universal steganography of optimal rate ⋮ On the security of the WOTS-PRF signature scheme ⋮ A random number generator based on elliptic curve operations ⋮ Universal forecasting algorithms ⋮ Almost everywhere high nonuniform complexity ⋮ Security proof of the canonical form of self-synchronizing stream ciphers ⋮ Functional encryption for randomized functionalities in the private-key setting from minimal assumptions ⋮ Pseudorandom functions in NC class from the standard LWE assumption ⋮ The communication complexity of addition ⋮ Multi-input functional encryption in the private-key setting: stronger security from weaker assumptions ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ A randomness test for block ciphers ⋮ Obfuscation for cryptographic purposes ⋮ How should we solve search problems privately? ⋮ Bounds on the efficiency of black-box commitment schemes ⋮ Bandwidth-efficient attribute-based key-insulated signatures with message recovery ⋮ QUAD: A multivariate stream cipher with provable security ⋮ Constrained pseudorandom functions from functional encryption ⋮ Revocable hierarchical identity-based encryption with adaptive security ⋮ Adaptively secure distributed PRFs from \(\mathsf{LWE}\) ⋮ Adaptively secure lattice-based revocable IBE in the QROM: compact parameters, tight security, and anonymity ⋮ Cryptography in the multi-string model ⋮ Limits on the efficiency of (ring) LWE-based non-interactive key exchange ⋮ A proof of security of Yao's protocol for two-party computation ⋮ Separating models of learning with faulty teachers ⋮ Private information retrieval with sublinear online time ⋮ Efficient simulation of random states and random unitaries ⋮ Handling expected polynomial-time strategies in simulation-based security proofs ⋮ Prediction-preserving reducibility ⋮ Adventures in crypto dark matter: attacks and fixes for weak pseudorandom functions ⋮ Reducing complexity assumptions for statistically-hiding commitment ⋮ Upper and lower bounds on black-box steganography ⋮ Shared generation of pseudo-random functions ⋮ Cryptography with constant input locality ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Protecting data privacy in private information retrieval schemes ⋮ Adaptively secure constrained pseudorandom functions in the standard model ⋮ Black-box use of one-way functions is useless for optimal fair coin-tossing ⋮ Efficient oblivious evaluation protocol and conditional disclosure of secrets for DFA ⋮ Guaranteeing the diversity of number generators ⋮ Collision-resistant and pseudorandom function based on Merkle-Damgård hash function ⋮ Bit commitment using pseudorandomness ⋮ Hardness results for neural network approximation problems ⋮ Efficient, perfect polynomial random number generators ⋮ Theory revision with queries: Horn, read-once, and parity formulas ⋮ Definitions and properties of zero-knowledge proof systems ⋮ On the streaming indistinguishability of a random permutation and a random function ⋮ Key-homomorphic pseudorandom functions from LWE with small modulus ⋮ Pseudorandom correlation functions from variable-density LPN, revisited ⋮ Secure two-party input-size reduction: challenges, solutions and applications ⋮ Let attackers program ideal models: modularity and composability for adaptive compromise ⋮ Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness ⋮ Programmable distributed point functions ⋮ Pseudorandom (function-Like) quantum state generators: new definitions and applications ⋮ Forward-secure encryption with fast forwarding ⋮ Sublinear secure computation from new assumptions ⋮ mrNISC from LWE with polynomial modulus ⋮ mrNISC from LWE with polynomial modulus ⋮ Collusion-resistant functional encryption for RAMs ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ When messages are keys: is HMAC a dual-PRF? ⋮ Noise-free thumbnail-preserving image encryption based on MSB prediction ⋮ Succinct interactive oracle proofs: applications and limitations ⋮ SoftSpokenOT: quieter OT extension from small-field silent VOLE in the Minicrypt model ⋮ Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication ⋮ Building blocks of sharding blockchain systems: concepts, approaches, and open problems ⋮ Correlated pseudorandomness from expand-accumulate codes ⋮ Moz\(\mathbb{Z}_{2^k}\)arella: efficient vector-OLE and zero-knowledge proofs over \(\mathbb{Z}_{2^k}\) ⋮ \textsf{ISAP+}: \textsf{ISAP} with fast authentication ⋮ Universal reductions: reductions relative to stateful oracles ⋮ No-directional and backward-leak uni-directional updatable encryption are equivalent ⋮ A framework for statistically sender private OT with optimal rate ⋮ \textsf{TreePIR}: sublinear-time and polylog-bandwidth private information retrieval from DDH ⋮ The security of the cipher block chaining message authentication code ⋮ On the complexity of compressing obfuscation ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation ⋮ Cryptography with Updates ⋮ Natural proofs ⋮ Pseudorandom generators without the XOR lemma ⋮ The truth behind the myth of the folk theorem ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Watermarking cryptographic functionalities from standard lattice assumptions ⋮ Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness ⋮ Verifiable random functions from non-interactive witness-indistinguishable proofs ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ Simple and generic constructions of succinct functional encryption ⋮ On the exact round complexity of secure three-party computation ⋮ Obfustopia built on secret-key functional encryption ⋮ Session resumption protocols and efficient forward security for TLS 1.3 0-RTT ⋮ Minicrypt primitives with algebraic structure and applications ⋮ Boosting in the presence of noise ⋮ A New Pseudorandom Generator from Collision-Resistant Hash Functions ⋮ Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange ⋮ Cryptography from Learning Parity with Noise ⋮ Fast and Adaptively Secure Signatures in the Random Oracle Model from Indistinguishability Obfuscation (Short Paper) ⋮ Limits on the Power of Indistinguishability Obfuscation and Functional Encryption ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ The GGM Function Family Is a Weakly One-Way Family of Functions ⋮ More efficient DDH pseudorandom generators ⋮ Single-Key to Multi-Key Functional Encryption with Polynomial Loss ⋮ Sparse pseudorandom distributions ⋮ Pseudorandom sources for BPP ⋮ Generalizing PMAC Under Weaker Assumptions ⋮ Watermarking Cryptographic Capabilities ⋮ Structural analysis of polynomial-time query learnability ⋮ Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings ⋮ A Fair and Efficient Mutual Private Set Intersection Protocol from a Two-Way Oblivious Pseudorandom Function ⋮ Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness ⋮ Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions ⋮ Efficient Computations over Encrypted Data Blocks ⋮ On Efficient Leakage-Resilient Pseudorandom Functions with Hard-to-Invert Leakages ⋮ On Symmetric Encryption with Distinguishable Decryption Failures ⋮ A new framework for deniable secure key exchange ⋮ Communication efficient Zero-knowledge Proofs of knowledge ⋮ Pseudo-mixing Time of Random Walks ⋮ Authenticated Key Exchange and Key Encapsulation in the Standard Model ⋮ Block encryption of quantum messages ⋮ Towards Tightly Secure Lattice Short Signature and Id-Based Encryption ⋮ Computational Security of Quantum Encryption ⋮ Error-Correcting Codes Against Chosen-Codeword Attacks ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ A Proof of Security in O(2 n ) for the Benes Scheme ⋮ Unknown-Input Attacks in the Parallel Setting: Improving the Security of the CHES 2012 Leakage-Resilient PRF ⋮ The learnability of quantum states ⋮ Lower bounds and impossibility results for concurrent self composition ⋮ The round complexity of quantum zero-knowledge ⋮ Separating Models of Learning with Faulty Teachers ⋮ Simulatable verifiable random function from the LWE assumption ⋮ Unnamed Item ⋮ A one-time stegosystem and applications to efficient covert communication ⋮ One-Round Cross-Domain Group Key Exchange Protocol in the Standard Model ⋮ McCulloch-Pitts Brains and Pseudorandom Functions ⋮ Cryptography and cryptographic protocols ⋮ Chosen-ciphertext secure multi-hop identity-based conditional proxy re-encryption with constant-size ciphertexts ⋮ Improved proxy re-encryption schemes with applications to secure distributed storage ⋮ Resource-aware protocols for authenticated group key exchange in integrated wired and wireless networks ⋮ Bi-homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ On the Effects of Pirate Evolution on the Design of Digital Content Distribution Systems ⋮ Monkey: Black-Box Symmetric Ciphers Designed for MONopolizing KEYs ⋮ On the Security of the Winternitz One-Time Signature Scheme ⋮ Practical construction and analysis of pseudo-randomness primitives ⋮ Constrained Pseudorandom Functions for Unconstrained Inputs Revisited: Achieving Verifiability and Key Delegation ⋮ Constraining Pseudorandom Functions Privately ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ Private Puncturable PRFs from Standard Lattice Assumptions ⋮ QUAD: A Practical Stream Cipher with Provable Security ⋮ Composition Implies Adaptive Security in Minicrypt ⋮ A Provable-Security Treatment of the Key-Wrap Problem ⋮ Luby-Rackoff Ciphers from Weak Round Functions? ⋮ Unclonable Group Identification ⋮ Basing PRFs on Constant-Query Weak PRFs: Minimizing Assumptions for Efficient Symmetric Cryptography ⋮ The Layered Games Framework for Specifications and Analysis of Security Protocols ⋮ Round-Optimal Password-Based Group Key Exchange Protocols in the Standard Model ⋮ Indistinguishability Obfuscation: From Approximate to Exact ⋮ Output-Compressing Randomized Encodings and Applications ⋮ Homomorphic Evaluation Requires Depth ⋮ On the Correlation Intractability of Obfuscated Pseudorandom Functions ⋮ Perfect Structure on the Edge of Chaos ⋮ On the complexity of constructing pseudorandom functions (especially when they don't exist) ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Short Redactable Signatures Using Random Trees ⋮ On the Security Loss in Cryptographic Reductions ⋮ Order-Preserving Symmetric Encryption ⋮ A Leakage-Resilient Mode of Operation ⋮ A Noiseless Key-Homomorphic PRF: Application on Distributed Storage Systems ⋮ Candidate One-Way Functions Based on Expander Graphs ⋮ The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles ⋮ Three XOR-Lemmas — An Exposition ⋮ Randomness and Computation ⋮ On Security Preserving Reductions – Revised Terminology ⋮ Another Motivation for Reducing the Randomness Complexity of Algorithms ⋮ Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions ⋮ Constrained PRFs for Unbounded Inputs with Short Keys ⋮ Building Secure Block Ciphers on Generic Attacks Assumptions ⋮ On Statistically Secure Obfuscation with Approximate Correctness ⋮ Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium ⋮ On the Existence of Extractable One-Way Functions ⋮ Fine-Grained Cryptography ⋮ XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions ⋮ Leakage resilience from program obfuscation ⋮ Counter-in-Tweak: Authenticated Encryption Modes for Tweakable Block Ciphers ⋮ Constrained pseudorandom functions for Turing machines revisited: how to achieve verifiability and key delegation ⋮ How to Use Indistinguishability Obfuscation: Deniable Encryption, and More ⋮ On Related-Secret Pseudorandomness ⋮ Composition of Zero-Knowledge Proofs with Efficient Provers ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ From non-adaptive to adaptive pseudorandom functions ⋮ Computing on authenticated data ⋮ The Complexity of Public-Key Cryptography ⋮ Breaking the Sub-Exponential Barrier in Obfustopia
