Computational Security is a guarantee of security on ciphertext on assuming that computing resources are limited, and the time required or cost to decrypt the ciphertext is too long or too large to be valuable.
Computational Security
- TNS3131 Chapter 2: Conventional Encryption and Message Confidentiality
- TAC3121 Chapter 1: Introduction
-
Rivest-Shamir-Adleman (RSA)
RSA is an #Asymmetric Cryptography scheme based on exponentiation in a Galois Field over integers modulo a prime which utilises integers as large as 1024 bits. The running time for exponentiation is \(o((\log n^3))\) operations, which is reasonable. However, to break the #algorithm, it needs \(o(e^{\log n \log \log n})\) factorisations, thus it is hard to crack#.
Note: Current \(n\) is of \(2^{1024}\) to \(2^{2048}\) bit size. It is currently assumed to be computational secure#.
-
Message Authentication Code (MAC)
It should be computationally infeasible# to find another message with same MAC knowing a message and MAC
-
Hash Function
collision resistant/strong collision resistant (computationally infeasible# to find any pair \((x, y)\) such that \(H(x) = H(y)\))preimage resistant/one-way property (given \(h\), computationally infeasible# to find \(y\) (preimage) such that \(H(y) = h\))second preimage resistant/weak collision resistant (given \(x\) (first preimage), computationally infeasible# to find \(y\) (second preimage) such that \(H(x) = H(y)\))
-
Asymmetric Cryptography
The requirements for a secure Asymmetric Cryptographic scheme, defined by Diffie and Hellman in 1976, is to have easily computed key pair generation, encryption, and decryption, but computationally infeasible# to determine private key given public key and recover plaintext given public key and ciphertext. Furthermore, the order of the encryption and decryption shouldn’t matter. Encryption can be done first then decryption or the other way around.