# Tag Info

## Hot answers tagged provable-security

8

Not all ciphers can be broken, even by infinitely powerful adversaries. When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two ...

6

I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time" Using a perfectly random key which is as long as the message itself, not a pseudo-random key, cannot be broken no matter how fast the attacker's computer is. This scheme is called one-time-pad and its security is guaranteed by information theory ...

5

Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distingush between, for example, two messages. For example, say you encrypt (with proper padding) the messages $0$ and $1$ using RSA and send them to the adversary. We would not want the adversary to be able to distinguish ...

4

Basically, every time you choose a group where the required hard problem is not hard, then you will run into problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography. Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a ...

3

DrLecter gave a good answer, I just wanted to include another well-known example. The Pohlig-Hellman algorithm can be used to compute discrete logs in groups whose order is a smooth integer. If two parties executing a textbook Diffie-Hellman key exchange use as their modulus a prime $p$ such that $p-1$ has only small factors (is 'smooth') an eavesdropping ...

2

One might imagine that the object of a security proof is to know that if someone breaks your system, that means they have (essentially) found a way to do some computation that you couldn't do before. Sort of a consolation prize. However, it is better to consider it as a statement of beliefs and consequences of those beliefs. We believe factoring is hard. If ...

2

We are talking about hash-function families $\{h_k\}_{k\in K}$ here. The parameter $k$ is used to rule out the trivial collision search algorithm that simply prints a collision for a given $h$ (such algorithms exist, but are difficult to find). For large $K$ such an algorithm would be too large. The parameter $k$ is called a key, but it is not actually ...

2

Here is the actual proof (hopefully in close to plain English) that to encrypt n bits with perfect security you need n bits of key, and if you have less your system is Information-theoreticly unsecure and can be broken by an adversary with unlimited computing power. The basic principle of what we mean by secure here is, for all messages m in the message ...

2

Can we state that $Adv_{G0} \le Adv_{G_1}$ ? Absolutely. Let us call $S0$ the strategy that $A$ can use in game $G0$ to achieve advantage $Adv_{G0}$; we notice that $A$ can also use strategy $S0$ to achieve that exact same advantage in $G1$, and hence we see that the maximum advantage he can achieve in $G1$ must be at least as large as in $G0$ Can ...

1

Consider that a cryptogram is only one very tiny piece of a secure message communication system. People focus unnecessarily on it because it contains and protects the actual secret, but every piece of the overall system has to be secure for the secret to remain protected. That system includes not only the obvious technical problems (exchanging and ...

Only top voted, non community-wiki answers of a minimum length are eligible