|
Decisional Composite Residuosity Assumption
The decisional composite residuosity assumption (DCRA) is a mathematical assumption used in cryptography. In particular, the assumption is used in the proof of the Paillier cryptosystem. Informally, the DCRA states that given a composite n and an integer z, it is hard to decide whether z is an n-residue modulo n^2. ''I.e.'' whether there exists a y such that : z \equiv y^n \pmod. \, See also * Quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which a ... * Higher residuosity problem References * P. Paillier, ''Public-Key Cryptosystems Based on Composite Degree Residuosity Classes'', Eurocrypt 1999. {{DEFAULTSORT:Decisional Composite Residuosity Assumption Computational hardness assumptions ... [...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] |
Paillier Cryptosystem
The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing ''n''-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based. The scheme is an additive homomorphic cryptosystem; this means that, given only the public key and the encryption of m_1 and m_2, one can compute the encryption of m_1+m_2. Algorithm The scheme works as follows: Key generation #Choose two large prime numbers p and q randomly and independently of each other such that \gcd(pq, (p-1)(q-1))=1. This property is assured if both primes are of equal length.Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007 #Compute n=pq and \lambda=\operatorname(p-1,q-1). lcm means Least Common Multiple. #Select random i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Composite Number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Accordingly it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime number, prime, or the Unit (ring theory), unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit. E.g., the integer 14 is a composite number because it is the product of the two smaller integers 2 × 7 but the integers 2 and 3 are not because each can only be divided by one and itself. The composite numbers up to 150 are: :4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative integers. The set (mathematics), set of all integers is often denoted by the boldface or blackboard bold The set of natural numbers \mathbb is a subset of \mathbb, which in turn is a subset of the set of all rational numbers \mathbb, itself a subset of the real numbers \mathbb. Like the set of natural numbers, the set of integers \mathbb is Countable set, countably infinite. An integer may be regarded as a real number that can be written without a fraction, fractional component. For example, 21, 4, 0, and −2048 are integers, while 9.75, , 5/4, and Square root of 2, are not. The integers form the smallest Group (mathematics), group and the smallest ring (mathematics), ring containing the natural numbers. In algebraic number theory, the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Modular Arithmetic
In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book '' Disquisitiones Arithmeticae'', published in 1801. A familiar example of modular arithmetic is the hour hand on a 12-hour clock. If the hour hand points to 7 now, then 8 hours later it will point to 3. Ordinary addition would result in , but 15 reads as 3 on the clock face. This is because the hour hand makes one rotation every 12 hours and the hour number starts over when the hour hand passes 12. We say that 15 is ''congruent'' to 3 modulo 12, written 15 ≡ 3 (mod 12), so that 7 + 8 ≡ 3 (mod 12). Similarly, if one starts at 12 and waits 8 hours, the hour hand will be at 8. If one instead waited twice as long, 16 hours, the hour hand would be on 4. This ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quadratic Residuosity Problem
The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are not obviously quadratic non-residues (see below). The problem was first described by Gauss in his '' Disquisitiones Arithmeticae'' in 1801. This problem is believed to be computationally difficult. Several cryptographic methods rely on its hardness, see . An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite N of unknown factorization is the product of 2 or 3 primes. Precise formulation Given integers a and T, a is said to be a ''quadratic residue modulo T'' if there exists an integer b such that :a \equiv b^2 \pmod T. Otherwise we say it is a quadratic non-residue. When T = p is a prime, it is customary t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Higher Residuosity Problem
In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the ''n''th-residuosity problem) is one such problem. This problem is ''easier'' to solve than integer factorization, so the assumption that this problem is hard to solve is ''stronger'' than the assumption that integer factorization is hard. Mathematical background If ''n'' is an integer, then the integers modulo ''n'' form a ring. If ''n'' = ''pq'' where ''p'' and ''q'' are primes, then the Chinese remainder theorem tells us that :\mathbb/n\mathbb \simeq \mathbb/p\mathbb \times \mathbb/q\mathbb The units of any ring form a group under multiplication, and the group of units in \mathbb/n\mathbb is traditionally denoted (\mathbb/n\mathbb) ^. From the ring isomorphism above, we have :(\mathbb/n\mathbb)^ \simeq (\mathbb/p\mathbb)^ \times (\mathbb/q\mathbb)^ as an isomorphism of groups. Since ''p'' and ''q'' were assumed to be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
