Concrete security

Last updated

In cryptography, concrete security or exact security is a practice-oriented approach that aims to give more precise estimates of the computational complexities of adversarial tasks than polynomial equivalence would allow.[ citation needed ] It quantifies the security of a cryptosystem by bounding the probability of success for an adversary running for a fixed amount of time. [1] [ better source needed ] Security proofs with precise analyses are referred to as concrete. [2] [ better source needed ]

Contents

Traditionally, provable security is asymptotic: it classifies the hardness of computational problems using polynomial-time reducibility. Secure schemes are defined to be those in which the advantage of any computationally bounded adversary is negligible. While such a theoretical guarantee is important, in practice one needs to know exactly how efficient a reduction is because of the need to instantiate the security parameter - it is not enough to know that "sufficiently large" security parameters will do. An inefficient reduction results either in the success probability for the adversary or the resource requirement of the scheme being greater than desired.[ citation needed ]

Concrete security parametrizes all the resources available to the adversary, such as running time and memory, and other resources specific to the system in question, such as the number of plaintexts it can obtain or the number of queries it can make to any oracles available. Then the advantage of the adversary is upper bounded as a function of these resources and of the problem size. It is often possible to give a lower bound (i.e. an adversarial strategy) matching the upper bound, hence the name exact security.[ citation needed ]

Examples

Concrete security estimates have been applied to cryptographic algorithms:

In addition, a software tool named the "Foundational Cryptography Framework", which embeds into Coq, is able to formally verify proofs of concrete security. [7] For example, it is able to verify the concrete security of ElGamal encryption. [7]

Related Research Articles

In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.

Malleability is a property of some cryptographic algorithms. An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext , it is possible to generate another ciphertext which decrypts to , for a known function , without necessarily knowing or learning .

A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

In cryptography, a random oracle is an oracle that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

In cryptography, a secure channel is a means of data transmission that is resistant to overhearing and tampering. A confidential channel is a means of data transmission that is resistant to overhearing, or eavesdropping, but not necessarily resistant to tampering. An authentic channel is a means of data transmission that is resistant to tampering but not necessarily resistant to overhearing.

In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message , and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length. This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy means that the ciphertext reveals no information at all about the plaintext, whereas semantic security implies that any information revealed cannot be feasibly extracted.

Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.

Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack. Indistinguishability under chosen plaintext attack is equivalent to the property of semantic security, and many cryptographic proofs use these definitions interchangeably.

Offset codebook mode is an authenticated encryption mode of operation for cryptographic block ciphers. OCB mode was designed by Phillip Rogaway, who credits Mihir Bellare, John Black, and Ted Krovetz with assistance and comments on the designs. It is based on the integrity-aware parallelizeable mode (IAPM) of authenticated encryption by Charanjit S. Jutla. The OCB2 version was proven insecure, while the original OCB1 as well as OCB3 from 2011 are still considered secure.

Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.

Plaintext-awareness is a notion of security for public-key encryption. A cryptosystem is plaintext-aware if it is difficult for any efficient algorithm to come up with a valid ciphertext without being aware of the corresponding plaintext.

EAX mode (encrypt-then-authenticate-then-translate) is a mode of operation for cryptographic block ciphers. It is an Authenticated Encryption with Associated Data (AEAD) algorithm designed to simultaneously provide both authentication and privacy of the message with a two-pass scheme, one pass for achieving privacy and one for authenticity for each block.

Mihir Bellare is a cryptographer and professor at the University of California San Diego. He holds a Bachelor of Science degree from Caltech and a Ph.D. from Massachusetts Institute of Technology. He has published several seminal papers in the field of cryptography, many of which were co-written with Phillip Rogaway. Bellare has published a number of papers in the field of Format-Preserving Encryption. His students include Michel Abdalla, Chanathip Namprempre, Tadayoshi Kohno and Anton Mityagin. Bellare is one of the authors of skein.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing 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 are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

In cryptography, format-preserving encryption (FPE), refers to encrypting in such a way that the output is in the same format as the input. The meaning of "format" varies. Typically only finite sets of characters are used; numeric, alphabetic or alphanumeric. For example:

Post-quantum cryptography (PQC) is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.

In cryptography, the pseudorandom-function advantage of an algorithm on a pseudorandom function family is a measure of how effectively the algorithm can distinguish between a member of the family and a random oracle. Consequently, the maximum pseudorandom advantage attainable by any algorithm with a fixed amount of computational resources is a measure of how well such a function family emulates a random oracle.

Probabilistic Signature Scheme (PSS) is a cryptographic signature scheme designed by Mihir Bellare and Phillip Rogaway.

References

  1. ↑ "Modern symmetric-key Encryption". University of Maryland. Archived from the original on 2017-09-10. Retrieved 6 May 2021.
  2. ↑ Kamara, Seny. "Lectures 2+3: Provable Security" (PDF). Archived (PDF) from the original on 2017-02-15. Retrieved 6 May 2021.
  3. ↑ Bellare, Mihir; Rogaway, Philip (1996). "The Exact Security of Digital Signatures-How to Sign with RSA and Rabin" (PDF). Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. Vol. 1070. Springer-Verlag. pp. 399–416. doi:10.1007/3-540-68339-9_34. ISBN   978-3-540-68339-1.
  4. ↑ Bellare, Mihir; Desai, A.; Jokipii, E.; Rogaway, Philip (Oct 1997). "A concrete security treatment of symmetric encryption" (PDF). Proceedings 38th Annual Symposium on Foundations of Computer Science. pp. 394–403. doi:10.1109/SFCS.1997.646128. ISBN   0-8186-8197-7. S2CID   42604387.
  5. ↑ Walter, Michael (2017). "On the Concrete Security of Lattice-Based Cryptography". UC San Diego. Retrieved 6 May 2021.
  6. ↑ Yang, Jian; Guo, Qian; Johansson, Thomas; Lentmaier, Michael (3 Mar 2021). "Revisiting the Concrete Security of Goldreich's Pseudorandom Generator". arXiv: 2103.02668 [cs.CR].
  7. 1 2 Petcher, Adam (14 Oct 2014). "The Foundational Cryptography Framework". arXiv: 1410.3735 [cs.PL].


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.