article Free AccessRelativized Questions Involving Probabilistic Algorithms Author: Charles Rackoff Department of Computer Science, University of Toronto, Toronto, ...
Tópico(s): Logic, Reasoning, and Knowledge
1982 - Association for Computing Machinery | Journal of the ACM
Nick Rackoff, Charles Wiseman, Walter A. Ullrich,
As the pace of competition intensifies in the 80's, the use of information systems as competitive weapons is accelerating. Among the now classic cases are the computerized reservation system of American Airlines, the Cash Management Account of Merrill Lynch, and the order entry system of American Hospital Supply. These are examples of strategic information systems (SIS). The work that gave rise to this paper addresses the question, How can an organization discover such SIS opportunities systematically? ...
Tópico(s): ERP Systems Implementation and Impact
1985 - MIS Quarterly | MIS Quarterly
Jorge E. Cortés, Maher Albitar, Deborah A. Thomas, Francis J. Giles, Razelle Kurzrock, Alain Thibault, Wayne Rackoff, Charles Koller, Susan O’Brien, Guillermo Garcia‐Manero, Moshe Talpaz, Hagop M. Kantarjian,
Tópico(s): Myeloproliferative Neoplasms: Diagnosis and Treatment
2003 - Elsevier BV | Blood
New decision procedures for the covering and boundedness problems for vector addition systems are obtained. These procedures require at most space 2cn log n for some constant c. The procedures nearly achieve recently established lower bounds on the amount of space inherently required to solve these problems, and so are much more efficient than previously known non-primitive-recursive decision procedures.
Tópico(s): Optimization and Packing Problems
1978 - Elsevier BV | Theoretical Computer Science
Jeanne Ferrante, Charles Rackoff,
Consider the first order theory of the real numbers with the function + (plus) and the predicate $ < $ (less than). Let S be the set of true sentences of this theory. We first present an elimination of quantifiers decision procedure for S, and then analyze it to show that it takes at most time $2^{2cn} $, where c is a constant, to decide sentences of length n. We next show that a given sentence does not change in truth value when each of the quantifiers is limited to range over an appropriately chosen finite ...
Tópico(s): History and Theory of Mathematics
1975 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Stephen Cook, Charles Rackoff,
A restricted model of a Turing machine called a JAG (Jumping Automaton for Graphs) is introduced for solving the maze threadability problem (determining whether there is a path joining two distinguished nodes in an input graph). A JAG accesses its input graph by moving pebbles from a limited supply along the edges of the graph under a finite state control, and detecting when two pebbles coincide. It can also cause one pebble to jump to another. We prove that for every N there is a JAG which can determine ...
Tópico(s): DNA and Biological Computing
1980 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Jeanne Ferrante, Charles Rackoff,
and background.- Ehrenfeucht games and decision procedures.- Integer addition - An example of an Ehrenfeucht game decision procedure.- Some additional upper bounds.- Direct products of theories.- Lower bound preliminaries.- A technique for writing short formulas defining complicated properties.- A lower bound on the theories of pairing functions.- Some additional lower bounds.
Tópico(s): Advanced Algebra and Logic
1979 - Springer Nature | Lecture notes in mathematics
Charles Rackoff, Joel Seiferas,
If the time bounds defining two nondeterministic complexity classes are too close for separation by the two known techniques, then they are almost too close for separation by any relativizable technique. Proof of an analogous result for space would be a major breakthrough, implying $\operatorname{NSPACE}(\log n) = \operatorname{DSPACE}(\log n)$.
Tópico(s): graph theory and CDMA systems
1981 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Leslie G. Valiant, Sven Skyum, S. J. Berkowitz, Charles Rackoff,
It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in $O((\log d)(\log C + \log d))$ steps using only $(Cd)^{O(1)} $ processors.
Tópico(s): Polynomial and algebraic computation
1983 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Michael Luby, Charles Rackoff,
We prove relationships between the security of a function generator when used in an encryption scheme and the security of a function generator when used in a UNIX-like password scheme.
Tópico(s): User Authentication and Security Systems
1989 - Springer Science+Business Media | Journal of Cryptology
Shafi Goldwasser, Silvio Micali, Charles Rackoff,
Usually, a proof of a theorem contains more knowledge than the mere fact that the theorem is true. For instance, to prove that a graph is Hamiltonian it suffices to exhibit a Hamiltonian tour in it; however, this seems to contain more knowledge than the single bit Hamiltonian/non-Hamiltonian. In this paper a computational complexity theory of the “knowledge” contained in a proof is developed. Zero-knowledge proofs are defined as those proofs that convey no additional knowledge other than the correctness ...
Tópico(s): Computability, Logic, AI Algorithms
1989 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Silvio Micali, Charles Rackoff, Bob Sloan,
Three very different formal definitions of security for public-key cryptosystems have been proposed—two by Goldwasser and Micali and one by Yao. We prove all of them to be equivalent. This equivalence provides evidence that the right formalization of the notion of security has been reached.
Tópico(s): Cryptographic Implementations and Security
1988 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Michael Luby, Charles Rackoff,
We show how to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator. Goldreich, Goldwasser and Micali ["How to construct random functions," Proc. 25th Annual Symposium on Foundations of Computer Science, October 24–26, 1984.] introduce the notion of a pseudorandom function generator and show how to efficiently construct a pseudorandom function generator from a pseudorandom bit generator. We use some of the ideas behind the design of the Data ...
Tópico(s): Cryptographic Implementations and Security
1988 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Vladimir Kolesnikov, Charles Rackoff,
We study the problem of Key Exchange (KE), where authentication is two-factor and based on both electronically stored long keys and human-supplied credentials (passwords or biometrics). The latter credential has low entropy and may be adversarily mistyped. Our main contribution is the first formal treatment of mistyping in this setting. Ensuring security in presence of mistyping is subtle. We show mistyping-related limitations of previous KE definitions and constructions (of Boyen et al. [6,7,10] and ...
Tópico(s): Biometric Identification and Security
2008 - Springer Science+Business Media | Lecture notes in computer science
Vladimir Kolesnikov, Charles Rackoff,
We propose a new model for key exchange (KE) based on a combination of different types of keys. In our setting, servers exchange keys with clients, who memorize short passwords and carry (stealable) storage cards containing long (cryptographic) keys. Our setting is a generalization of that of Halevi and Krawczyk [16] (HK), where clients have a password and the public key of the server. We point out a subtle flaw in the protocols of HK and demonstrate a practical attack on them, resulting in a full password ...
Tópico(s): Cryptography and Data Security
2006 - Springer Science+Business Media | Lecture notes in computer science
Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff,
We study the random composition of a small family of O(n3) simple permutations on {0,1}n. Specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k-wise independent. We improve on a result of Gowers [An almost m-wise independent random permutation of the cube, Combin. Probab. Comput. 5(2) (1996) 119–130] and show that up to a polylogarithmic factor, n3k3 compositions of random permutations from this family suffice. We further show that the result applies ...
Tópico(s): Algorithms and Data Compression
2005 - Elsevier BV | Theoretical Computer Science
Michael J. Fischer, Silvio Micali, Charles Rackoff,
Tópico(s): Cryptographic Implementations and Security
1996 - Springer Science+Business Media | Journal of Cryptology
Rafail Ostrovsky, Charles Rackoff, Adam Smith,
A consistent query protocol (cqp) allows a database owner to publish a very short string c which commits her and everybody else to a particular database D, so that any copy of the database can later be used to answer queries and give short proofs that the answers are consistent with the commitment c. Here commits means that there is at most one database D that anybody can find (in polynomial time) which is consistent with c. (Unlike in some previous work, this strong guarantee holds even for owners ...
Tópico(s): Privacy-Preserving Technologies in Data
2004 - Springer Science+Business Media | Lecture notes in computer science
Valentine Kabanets, Charles Rackoff, Stephen Cook,
We define a class, denoted APP, of real-valued functions f : {0, 1}n → [0, 1] such that f can be approximated to within any > 0 by a probabilistic Turing machine running in time poly(n, 1/ ). The class APP can be viewed as a generalization of BPP. We argue that APP is more natural and more important than BPP, and that most results about BPP are better stated as results about APP. We show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit. In contrast, ...
Tópico(s): Algorithms and Data Compression
2000 - Society for Industrial and Applied Mathematics | Electronic colloquium on computational complexity
Erez Petrank, Charles Rackoff,
Tópico(s): DNA and Biological Computing
2000 - Springer Science+Business Media | Journal of Cryptology
... new way the results of Michael Luby and Charles Rackoff "How to construct pseudorandom permutations from pseudorandom functions", ...
Tópico(s): Benford’s Law and Fraud Detection
1991 - Springer Science+Business Media | Lecture notes in computer science
Michael J. Fischer, Michael J. Paterson, Charles Rackoff,
Abstract : Protocols are developed and analyzed for transmitting a secret bit between a sender and a receiver process using only the information contained in a random deal of hands of specified sizes from a deck of n distinct cards. The sender's and receiver's algorithms are known i advance, and all conversation between sender and receiver is public and is heard by all. A correct protocol always succeeds in transmitting the secret bit, and the other player(s), who receive the remaining cards and are ...
Tópico(s): Biometric Identification and Security
1991 - | DIMACS series in discrete mathematics and theoretical computer science
Allan Borodin, Morten Nielsen, Charles Rackoff,
Tópico(s): Advanced Bandit Algorithms Research
2003 - Springer Science+Business Media | Algorithmica
... inco.1994.1059 95e:94066 CrossrefISIGoogle Scholar[16] Charles Rackoff and , Joel Seiferas, Limitations on separating nondeterministic complexity ...
Tópico(s): Quantum Computing Algorithms and Architecture
1998 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
M.J. Fischer, Silvio Micali, Charles Rackoff,
Tópico(s): Advanced Authentication Protocols Security
1996 - Springer Science+Business Media | Journal of Cryptology
Michael Luby, Charles Rackoff,
Our work is motivated by the question of whether or not the password scheme used in UNIX is secure. The following password scheme is a somewhat simplified version of the actual password scheme used in UNIX. We feel that this simplified version captures the essential features of the actual password scheme used in UNM. When a user logs in for the first time he creates a random password and types his user name together with the password into the system. The system creates an encryption of the password ...
Tópico(s): Advanced Malware Detection Techniques
1988 - Springer Science+Business Media | Lecture notes in computer science
Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff,
We study the random composition of a small family of O(n 3) simple permutations on {0,1} n . Specifically we ask what is the number of compositions needed to achieve a permutation that is close to k-wise independent. We improve on a result of Gowers [8] and show that up to a polylogarithmic factor, n 3 k 3 compositions of random permutations from this family suffice. We further show that the result applies to the stronger notion of k-wise independence against adaptive adversaries. This question is essentially ...
Tópico(s): DNA and Biological Computing
2004 - Springer Science+Business Media | Lecture notes in computer science
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka,
Tópico(s): Algorithms and Data Compression
2009 - Birkhäuser | Computational Complexity
Tópico(s): Coding theory and cryptography
1990 - Springer Science+Business Media | Lecture notes in computer science
Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis,
The question whether Identity-Based Encryption (IBE) can be based on the Decisional DiffieHellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where ...
Tópico(s): Geometric and Algebraic Topology
2012 - Society for Industrial and Applied Mathematics | Electronic colloquium on computational complexity