66
votes
Accepted
Are one-time pads crackable in theory?
For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can ...
- 91.7k
24
votes
Are one-time pads crackable in theory?
To begin with, your definition of perfect secrecy is non-standard. The standard definition is given in an excellent answer to the question how is the OTP perfectly secure?.
Essentially, perfect ...
- 21.2k
21
votes
Is OTP still perfectly secure if we limit message and key space
Does that violate the perfect secrecy in any way?
Yes, obviously. Restricting the message space doesn't hurt in any way (the attacker can't get any additional information about the message, even if ...
- 145k
21
votes
why XOR is recommended/Used in every paper I read for encryption and decryption stream cipher?
Why can't I use other opeartions such as NAND, AND, OR
Because it needs to be invertible.
For example, if you use NAND, then if the bit from the key generator is a 0, then the output of the NAND will ...
- 145k
16
votes
Accepted
Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?
Salt-less password hashing is only a problem since the amount of passwords actually used in practice is comparably small and also not evenly distributed. Thus it is both in terms of time and memory ...
- 1,538
14
votes
Accepted
Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?
No it does not.
Perfect forward secrecy implies that even if you retrieve the private key of the asymmetric key pair that you cannot read any of the past or future messages within a connection. It is ...
- 91.7k
14
votes
Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
The answer is incorrect, but it's a bit more subtle than it seems. To make this clear, note that encrypting $x$ by computing $c=\operatorname{AES}_{0}(k) \oplus x$ would be perfectly secure (here the ...
- 27.6k
13
votes
Are one-time pads crackable in theory?
I'll try a practical example:
I trade stocks. Instructions to my broker use a simple Caesar shift cipher, but the shift varies by values in a one-time encryption pad. Common 8-char instructions ...
- 231
13
votes
Accepted
An unbreakable Hill cipher?
The Hill cipher is vulnerable to known-plaintext attack. Once the attacker gets $n$ plaintext/ciphertext pair it can break the cipher by solving a system of linear equations. Consider AES, it is not ...
- 47.5k
11
votes
What are the ways to generate Beaver triples for multiplication gate?
Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, ...
- 19.1k
11
votes
Accepted
Does Shannon perfect secrecy imply a deterministic encryption algorithm?
In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic
Actually, the standard definition doesn't actually imply that. It is necessary that $|K| ...
- 145k
9
votes
Accepted
Definitions of secrecy
In cryptography, forward secrecy = perfect forward secrecy, backward secrecy = future secrecy.
First, recall some background. The above terms are often discussed in the setting of secure channel ...
- 2,695
8
votes
Accepted
2 party AND computation under passive perfect security
The intuition behind the proof is as follows. Since the output of AND equals 0 when party P2 has input 0, then the transcript is distributed identically when P1 has input 0 and when P2 has input 1. ...
- 27.6k
8
votes
Are one-time pads crackable in theory?
However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.
When cryptographers use ...
- 14.4k
8
votes
Multi-Embedded Xor for Perfect OTP
What if we XOR it multiple times with different keys, like this:
$Cyphertext=((((((Plaintext⊕K1)⊕K2)⊕K3)⊕K4)⊕K5)....⊕Kn$
This is equivalent to XOR with a single key $K$ where $K = K_1 \oplus K_2 \...
- 19.5k
8
votes
Accepted
What is the difference between information-theoretic and perfect types of security?
Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional ...
- 19.1k
8
votes
Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?
We choose groups like RFC 3526 Group #14 or larger so that the precomputation is so large it is not feasible. The main problem with weakdh/logjam is that the chosen groups were originally chosen to ...
- 47.9k
8
votes
why XOR is recommended/Used in every paper I read for encryption and decryption stream cipher?
Edit: For any additive group operation, including addition modulo $k$ if the added keystream symbols $z_t$ are uniformly distributed, which means
$$
Pr(z_t=a)=1/k, \quad \forall a \in
\{0,\ldots, k-1\...
- 21.2k
7
votes
Accepted
Optimal threshold for passive and perfect security
The way to extend the proof to arbitrary $t,n$ and this threshold is as follows. Assume that there exists a protocol for any $n$ parties that withstands a threshold of $t=n/2$ corrupted parties, for ...
- 27.6k
7
votes
Are one-time pads crackable in theory?
The reason you can't crack a one-time-pad is because brute forcing will just end up generating every possible solution. But you'll be no closer to knowing which of those solutions is the right one! ...
- 171
7
votes
Accepted
Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
No, one can not claim that AES has perfect secrecy for a key size and message size of 128 bits. The answer quoted in the second part of the question is seriously wrong.
Perfect secrecy is an ...
- 138k
7
votes
why XOR is recommended/Used in every paper I read for encryption and decryption stream cipher?
The first reason obviously is that XOR is reversible. AND and NAND are not reversible.
But the important reason is found by looking at the truth table for XOR
Let $x$ be the plain text bit & let ...
- 2,169
7
votes
Accepted
Does CCA security imply perfect secrecy?
Perfect secrecy & [the traditional/standard definition of] CCA security are incompatible.
Shannon's theorem says that if you want perfect secrecy, then the key needs to be longer than the total ...
- 12k
6
votes
Accepted
An example of of an information theoretically secure protocol that is not cryptographically secure
In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is ...
- 27.6k
6
votes
Accepted
Cryptography - Perfect secrecy $\implies$ adversarial indistinguishability - proof
Hopefully I'm able to at least give a partial answer. In the first step of the three equalities, there are three simultaneous steps taken:
$$Pr[M=m_0]=Pr[M=m_1]=\frac{1}{2}$$ and $$Pr[b'=b|M=m_0]=Pr[...
- 3,459
6
votes
Perfect secrecy with XOR & SHIFT?
Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to ...
- 4,883
6
votes
When does multiple OTP encryption become insecure if new keys are permuted?
This is an inconsequential variation on a two-time pad and falls just as readily.
Say your pad is $n$ symbols long. Fix a permutation $\pi \in S_n$ of $\{1,2,\dots,n\}$—this is determined by your $\...
- 47.9k
5
votes
Accepted
Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held
You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to ...
- 27.6k
5
votes
Accepted
Does a stream cipher provide perfect secrecy?
First, do not ever use RC4.
Second, it depends on how you use that stream...
If you use AES-CTR as a stream cipher (see more here), you will specify a key $K$ (and a nonce $IV$). The CTR mode of AES ...
- 9,969
5
votes
Accepted
Would using a one-time pad multiple times with some conditions be safe?
For perfect secrecy of any cryptosystem, it must hold that |key|≥|all messages exchanged|.
Proof by contraposition: assume |key|<|all messages exchanged|, and there exists a deterministic ...
- 138k
Only top scored, non community-wiki answers of a minimum length are eligible