Some consequences of cryptographical conjectures for \(S_2^1\) and EF
type: Item
instance of: scholarly article
title: Some consequences of cryptographical conjectures for \(S_2^1\) and EF
zbMATH Open document ID: 0892.68029
author: Jan Krajíček
author: Pavel Pudlák
published in: Information and Computation
publication date: 1998-05-04T00:00:00Z
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 1138510
zbMATH Keywords: RSA cryptosystem
MaRDI profile type: Publication
full work available at URL: inco.1997.2674
OpenAlex ID: W2068363706
Wikidata QID: Q106785148
cites work: RSA and Rabin Functions: Certain Parts are as Hard as the Whole
cites work: Lower bounds for cutting planes proofs with small coefficients
cites work: Q3794177
cites work: Q4228469
cites work: Q4133141
cites work: The relative efficiency of propositional proof systems
cites work: Fragments of Bounded Arithmetic and Bounded Query Classes
cites work: Lower bounds to the size of constant-depth propositional proofs
cites work: Q4856172
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: Interpolation by a Game
cites work: Q4395611
cites work: Propositional proof systems, the consistency of first order theories and the complexity of computations
cites work: Quantified propositional calculi and fragments of bounded arithmetic
cites work: Bounded arithmetic and the polynomial hierarchy
cites work: Q4744264
cites work: A lower bound for the complexity of Craig's interpolants in sentential logic
cites work: Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
cites work: Q4298260
cites work: Q3689182
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: Every Prime Has a Succinct Certificate
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Q3140644
DOI: 10.1006/INCO.1997.2674
description: scientific article; zbMATH DE number 1138510