Some consequences of cryptographical conjectures for S 2 1 and EF

This publication has 10 references indexed in Scilit:

• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
  Izvestiya: Mathematics, 1995
• Lower bounds to the size of constant-depth propositional proofs
  The Journal of Symbolic Logic, 1994
• Fragments of bounded arithmetic and bounded query classes
  Transactions of the American Mathematical Society, 1993
• Bounded arithmetic and the polynomial hierarchy
  Annals of Pure and Applied Logic, 1991
• Propositional proof systems, the consistency of first order theories and the complexity of computations
  The Journal of Symbolic Logic, 1989
• RSA and Rabin Functions: Certain Parts are as Hard as the Whole
  SIAM Journal on Computing, 1988
• Counting problems in bounded arithmetic
  Lecture Notes in Mathematics, 1985
• A method for obtaining digital signatures and public-key cryptosystems
  Communications of the ACM, 1978
• Every Prime Has a Succinct Certificate
  SIAM Journal on Computing, 1975
• Feasibly constructive proofs and the propositional calculus (Preliminary Version)
  Published by Association for Computing Machinery (ACM) ,1975