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 ...
Maarten Bodewes's user avatar
  • 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 ...
kodlu's user avatar
  • 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 ...
poncho's user avatar
  • 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 ...
poncho's user avatar
  • 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 ...
Steffen Ullrich's user avatar
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 ...
Maarten Bodewes's user avatar
  • 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 ...
Yehuda Lindell's user avatar
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 ...
Alan Campbell's user avatar
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 ...
kelalaka's user avatar
  • 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, ...
Geoffroy Couteau's user avatar
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| ...
poncho's user avatar
  • 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 ...
Shan Chen's user avatar
  • 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. ...
Yehuda Lindell's user avatar
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 ...
Luis Casillas's user avatar
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 \...
Ella Rose's user avatar
  • 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 ...
Geoffroy Couteau's user avatar
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 ...
Squeamish Ossifrage's user avatar
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\...
kodlu's user avatar
  • 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 ...
Yehuda Lindell's user avatar
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! ...
industry7's user avatar
  • 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 ...
fgrieu's user avatar
  • 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 ...
user93353's user avatar
  • 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 ...
Mikero's user avatar
  • 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 ...
Yehuda Lindell's user avatar
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[...
CurveEnthusiast's user avatar
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 ...
Elias's user avatar
  • 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 $\...
Squeamish Ossifrage's user avatar
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 ...
Yehuda Lindell's user avatar
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 ...
Biv's user avatar
  • 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 ...
fgrieu's user avatar
  • 138k

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