|
Next-bit Test
In cryptography and the theory of computation, the next-bit testAndrew Chi-Chih YaoTheory and applications of trapdoor functions In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982. is a test against pseudo-random number generators. We say that a sequence of bits passes the next bit test for at any position i in the sequence, if any attacker who knows the i first bits (but not the seed) cannot predict the (i+1)st with reasonable computational power. Precise statement(s) Let P be a polynomial, and S=\ be a collection of sets such that S_k contains P(k)-bit long sequences. Moreover, let \mu_k be the probability distribution of the strings in S_k. We now define the next-bit test in two different ways. Boolean circuit formulation A predicting collectionManuel Blum and Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, in SIAM J. COMPUT., Vol. 13, No. 4, November 1984 C=\ is a collection of boolean circuits, such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), adversarial behavior. More generally, cryptography is about constructing and analyzing Communication protocol, protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security (confidentiality, data confidentiality, data integrity, authentication, and non-repudiation) are also central to cryptography. Practical applications of cryptography include electronic commerce, Smart card#EMV, chip-based payment cards, digital currencies, password, computer passwords, and military communications. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theory Of Computation
In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: ''"What are the fundamental capabilities and limitations of computers?".'' In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine. Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Andrew Chi-Chih Yao
Andrew Chi-Chih Yao ( zh , c = 姚期智 , p = Yáo Qīzhì; born December 24, 1946) is a Chinese computer scientist, physicist, and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Yao used the minimax theorem to prove what is now known as Yao's principle. Yao was raised in Taiwan and graduated from National Taiwan University. He earned a master's degree and his PhD in physics from Harvard University, then earned a second doctorate in computer science from the University of Illinois Urbana-Champaign. Yao was a naturalized U.S. citizen, and worked for many years in the U.S. In 2015, together with Yang Chen-Ning, he renounced his U.S. citizenship and became an academician of the Chinese Academy of Sciences. Early life and education Yao was born in Shanghai, China, in 1946. His parents later moved to Hong Kong and then Taiwan, where Yao was raised. Yao graduated with his Bac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pseudo-random
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as traditional sources of randomness available to humans (such as rolling dice) rely on physical processes not readily available to computer programs, although developments in hardware random number generator technology have challenged this. Background The generation of random numbers has many uses, such as for random sampling, Monte Carlo methods, board games, or gambling. In physics, however, most processes, such as gravitational acceleration, are deterministic, meaning that they always produce the same outcome from the same starting point. Some notable exceptions are radioactive decay and quantum measurement, which are both modeled as being truly random processes in the underlying physics. Since these processes are not practical sources of r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Probability Distribution
In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical description of a Randomness, random phenomenon in terms of its sample space and the Probability, probabilities of Event (probability theory), events (subsets of the sample space). For instance, if is used to denote the outcome of a coin toss ("the experiment"), then the probability distribution of would take the value 0.5 (1 in 2 or 1/2) for , and 0.5 for (assuming that fair coin, the coin is fair). More commonly, probability distributions are used to compare the relative occurrence of many different random values. Probability distributions can be defined in different ways and for discrete or for continuous variables. Distributions with special properties or for especially important applications are given specific names. Introduction A prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Manuel Blum
Manuel Blum (born 26 April 1938) is a Venezuelan-born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking". Education Blum was born to a Jewish family in Venezuela. Blum was educated at MIT, where he received his bachelor's degree and his master's degree in electrical engineering in 1959 and 1961 respectively. In MIT, he was recommended to Warren S. McCulloch, and they collaborated on some mathematical problems in neural networks. He obtained a Ph.D. in mathematics in 1964 supervised by Marvin Minsky.. Career Blum worked as a professor of computer science at the University of California, Berkeley until 2001. From 2001 to 2018, he was the Bruce Nelson Professor of Computer Science at Carnegie Mellon University, where his wife, Lenore Blum, was also a professor of computer science. In 2002, he was elected to the Unit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Silvio Micali
Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand, a proof-of-stake blockchain cryptocurrency protocol. Micali's research at the MIT Computer Science and Artificial Intelligence Laboratory centers on cryptography and information security. In 2012, he received the Turing Award for his work in cryptography. Personal life Micali graduated in mathematics at La Sapienza University of Rome in 1978 and earned a PhD degree in computer science from the University of California, Berkeley in 1982; for research supervised by Manuel Blum. Micali has been on the faculty of MIT's Electrical Engineering and Computer Science Department since 1983. He has also served on the faculty of the University of Pennsylvania, University of Toronto, and Tsinghua University. His research interests are cryptography, zero knowledge, pseudorandom generation, secure protocols, and mechanism design. Car ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Circuits
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length. Boolean circuits are defined in terms of the logic gates they contain. For example, a circuit might contain binary AND and OR gates and unary NOT gates, or be entirely described by binary NAND gates. Each gate corresponds to some Boolean function that takes a fixed number of bits as input and outputs a single bit. Boolean circuits provide a model for many digital components used in computer engineering, including multiplexers, adders, and arithmetic logic units, but they exclude sequential logic. They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as metastability, fanout, glitches, power consumption, and propagation delay variability. Formal definition In giving a formal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Probabilistic Turing Machines
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can (unlike a deterministic Turing machine) have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution. In the case of equal probabilities for the transitions, probabilistic Turing machines can be defined as deterministic Turing machines having an additional "write" instruction where the value of the write is uniformly distributed in the Turing machine's alphabet (generally, an equal likelihood of writing a "1" or a "0" on to the tape). Another common reformulation is simply a deterministic Turing machine with an added tape full of random bits call ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
P/poly
In computational complexity theory, P/poly is a complexity class that can be defined in both circuit complexity and non-uniform complexity. Since the two definitions are equivalent, this concept bridges the two areas. In the perspective of circuit complexity, P/poly is the class of problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. In the perspective of non-uniform complexity, P/poly is defined in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. For example, the popular Miller–Rabin primality test can be formulated as a P/poly algorithm: the "advice" is a list of candidate values to test. It ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Time Complexity
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is gene ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Yao's Test
In cryptography and the theory of computation, Yao's test is a test defined by Andrew Chi-Chih Yao in 1982,Andrew Chi-Chih YaoTheory and applications of trapdoor functions In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982. against pseudo-random sequences. A sequence of words passes Yao's test if an attacker with reasonable computational power cannot distinguish it from a sequence generated uniformly at random. Formal statement Boolean circuits Let P be a polynomial, and S=\_k be a collection of sets S_k of P(k)-bit long sequences, and for each k, let \mu_k be a probability distribution on S_k, and P_C be a polynomial. A predicting collection C=\ is a collection of boolean circuits of size less than P_C(k). Let p_^C be the probability that on input s, a string randomly selected in S_k with probability \mu(s), C_k(s)=1, i.e. p_^C= s\in S_k\text\mu_k(s)/math> Moreover, let p_^C be the probability that C_k(s)=1 on input s a P(k)-bit long sequen ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
