|
Hybrid Argument (cryptography)
In cryptography, the hybrid argument is a proof technique used to show that two distributions are computationally indistinguishable. History Hybrid arguments had their origin in a papers by Andrew Yao in 1982 and Shafi Goldwasser and Silvio Micali in 1983. Formal description Formally, to show two distributions ''D''1 and ''D''2 are computationally indistinguishable, we can define a sequence of ''hybrid distributions'' ''D''1 := ''H''0, ''H''1, ..., ''H''''t'' =: ''D''2 where ''t'' is polynomial in the security parameter ''n''. Define the advantage of any probabilistic efficient (polynomial-bounded time) algorithm A as :\mathsf_^(\mathbf) := \left, \Pr \stackrel H_i : \mathbf(x)=1- \Pr \stackrel H_ : \mathbf(x)=1\, where the dollar symbol ($) denotes that we sample an element from the distribution at random. By triangle inequality, it is clear that for any probabilistic polynomial time algorithm A, :\mathsf_^(\mathbf) \leq \sum_^\mathsf_^(\mathbf). Thus there must exist som ... [...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] |
Computational Indistinguishability
In computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the difference between them except with negligible probability. Formal definition Let \scriptstyle\_ and \scriptstyle\_ be two distribution ensembles indexed by a security parameter ''n'' (which usually refers to the length of the input); we say they are computationally indistinguishable if for any non-uniform probabilistic polynomial time algorithm ''A'', the following quantity is a negligible function in ''n'': : \delta(n) = \left, \Pr_ A(x) = 1- \Pr_ A(x) = 1\. denoted D_n \approx E_n. In other words, every efficient algorithm ''As behavior does not significantly change when given samples according to ''D''''n'' or ''E''''n'' in the limit as n\to \infty. Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: that any ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Andrew 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 B ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Triangle Inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. This statement permits the inclusion of Degeneracy (mathematics)#Triangle, degenerate triangles, but some authors, especially those writing about elementary geometry, will exclude this possibility, thus leaving out the possibility of equality. If , , and are the lengths of the sides of a triangle then the triangle inequality states that :c \leq a + b , with equality only in the degenerate case of a triangle with zero area. In Euclidean geometry and some other geometries, the triangle inequality is a theorem about vectors and vector lengths (Norm (mathematics), norms): :\, \mathbf u + \mathbf v\, \leq \, \mathbf u\, + \, \mathbf v\, , where the length of the third side has been replaced by the length of the vector sum . When and are real numbers, they can be viewed as vectors in \R^1, and the triang ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pseudorandom Number Generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random number generation, random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's ''random seed, seed'' (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, ''pseudorandom number generators'' are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more cryptographically-secure pseudorandom number generator, elabora ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interactive Proof System
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is assumed to possess unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct. All interactive proof systems have two requirements: * Completeness: if the statement is true, the honest prover (that is, one following the protocol properly) can convince the honest verifier that it is indeed true. * Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, excep ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Universal Composability
The framework of universal composability (UC) is a general-purpose model for the analysis of cryptographic protocols. It guarantees very strong security properties. Protocols remain secure even if arbitrarily composed with other instances of the same or other protocols. Security is defined in the sense of protocol emulation. Intuitively, a protocol is said to emulate another one, if no environment (observer) can distinguish the executions. Literally, the protocol may simulate the other protocol (without having access to the code). The notion of security is derived by implication. Assume a protocol P_1 is secure per definition. If another protocol P_2 emulates protocol P_1 such that no environment tells apart the emulation from the execution of the protocol, then the emulated protocol P_2 is as secure as protocol P_1. Ideal functionality An ideal functionality is a protocol in which a trusted party that can communicate over perfectly secure channels with all protocol participants ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
