Skip to main content

Questions tagged [perfect-secrecy]

Confidentiality in a very strong sense. Ciphers reaching perfect-secrecy can't be broken to disclose informations over the plaintext from the ciphertext, even with unlimited computing power. The most known example cipher reaching perfect screcy is the one-time-pad.

Filter by
Sorted by
Tagged with
8 votes
2 answers
3k views

What is the difference between information-theoretic and perfect types of security?

I'm having a hard time pinning down an exact definition of the difference between information-theoretic and perfect types of security. A rigorous definition seems elusive... A. Wikipedia puts the ...
Paul Uszak's user avatar
  • 15.5k
13 votes
3 answers
14k views

One time pad: why is it useless in practice?

The symmetric cryptosystem one-time pad (OTP) seems to be very beautiful since it is perfectly secret according to Shannon. Many books, however, point out the main drawback: one must create a secret ...
Dubious's user avatar
  • 273
14 votes
2 answers
3k views

Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?

While looking at this question I discovered the following here (question 5), and wanted to ask it as a separate question. Alice knows that she will want to send a single 128-bit message to Bob ...
daniel's user avatar
  • 912
3 votes
2 answers
1k views

An unbreakable Hill cipher?

Why don't we use a Hill cipher of 100 × 100? Or even bigger? That would be close to unbreakable. The number of possible keys in a 2 × 2 Hill cipher is 157248. For 100 × 100 the number is beyond limits....
Manoharsinh Rana's user avatar
2 votes
3 answers
4k views

Does perfect secrecy imply uniform ciphertext distribution?

I suspect the answer is no, but I am not able to either prove it, or provide an example. In Katz and Lindell's book, it is only said that with a perfectly secret encryption scheme, the plain and ...
wmnorth's user avatar
  • 252
12 votes
2 answers
8k views

Definitions of secrecy

I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them. I ...
M-elman's user avatar
  • 1,248
7 votes
3 answers
666 views

Manual secret sharing?

What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\...
fgrieu's user avatar
  • 142k
2 votes
1 answer
5k views

Why cant Public Key Encryption be perfectly secure? [duplicate]

I would be very grateful for any help. I cant figure out why (probabilistic) public key encryption schemes can never provide perfect secrecy? Any Ideas? Excerpt: In contrast to the private-key ...
Gordon's user avatar
  • 517
1 vote
2 answers
180 views

Is it possible to use an algorithm to generate an OTP?

I am a software developer, not a cryptologist. I like the idea of perfect secrecy and would like to use a one-time pad (OTP) to encrypt/decrypt files up to, say, 50Mb. Is there a way that I can use ...
DatsunBing's user avatar
1 vote
1 answer
3k views

What is Perfect forward secrecy?

I have read that when a user contacts an entity like a bank, it creates a pre-master key and then selects a master key for subsequent communications. Can the lack of PFS, create a security flaw if ...
PDHide's user avatar
  • 247
17 votes
2 answers
13k views

Is perfect-forward secrecy achieved with RSA?

I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl. From what I understand Symmetric key distribution systems like Kerberos do not provide PFS ...
Ben Lamm's user avatar
  • 273
9 votes
1 answer
3k views

Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?

Does perfect forwarding secrecy, as used for e.g. the DHE_ and ECDHE_ TLS ciphersuites make it impossible for quantum analysis ...
Maarten Bodewes's user avatar
  • 93.2k
4 votes
1 answer
2k views

Is the one-time pad still perfectly secret if all-zero keys are excluded?

I'm trying to solve this question related to one-time pads and perfect secrecy: My solution is: I assumed that the current message space is $M = \left\{ 0,1 \right\}^l$ and the new keyspace after ...
Mitch5355's user avatar
4 votes
2 answers
17k views

Shannon theorem of perfect secrecy

From the class: Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability). Proof: Consider ...
Jjang's user avatar
  • 365
4 votes
2 answers
2k views

Perfect Secrecy for two distinct messages

We say that and encryption scheme $\pi$ is perfectly secret for two distinct messages, if for all distributions over $\mathcal{M}\times\mathcal{M}$ ($\mathcal{M}$ is the message space), for all $m_1,...
A-P's user avatar
  • 175
3 votes
2 answers
902 views

Almost (epsilon) perfect secrecy - lower bound of keyspace size

As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography. Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, ...
Jung's user avatar
  • 31
3 votes
3 answers
14k views

How can a cryptosystem be unconditionally secure?

The definition of an unconditionally secure cryptosystem states that the cryptosystem cannot be broken even with infinitely computational ressources and time. However, since most books define the ...
Shuzheng's user avatar
  • 321
2 votes
1 answer
263 views

Unconditional authentication

I have a few questions regarding universal-hash functions: Is there a way universal hash functions can be used to provide unconditional authentication in the way the OTP provides unconditional ...
dylan7's user avatar
  • 551
2 votes
3 answers
2k views

Does a stream cipher provide perfect secrecy?

From WAR10CK here: If I actually do create a machine using RC4 or AES-CTR and have a TRNG continually feed it a constant steady stream of random bits. Provided that the stream of bits is purged ...
Biv's user avatar
  • 10k
2 votes
1 answer
816 views

Proving that a scheme is $\epsilon$-perfectly secret

I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell: Let $\epsilon > 0$ be a constant. Say an ...
eee3's user avatar
  • 23
2 votes
2 answers
1k views

Is there such a thing as perfect CPA security?

Consider the following experiment. If we require that $$\operatorname{P}\left( \mathcal A \text{ succeeds} \right) = \frac{1}{2}$$ for any adversary $\mathcal A$ in order to call the scheme $\Pi$ ...
CRYPTONEWBIE's user avatar
2 votes
2 answers
3k views

Can you help me prove perfect secrecy?

I'm actually new to cryptography and a friend of mine requested that I should read the Katz and Lindell book – “introduction to modern cryptography”. As I read the book I found it very interesting but ...
dev's user avatar
  • 49
1 vote
1 answer
489 views

To which game-based security definition is Perfect Secrecy equivalent?

We all know the classic definitions of perfect secrecy, being $$\Pr[M=m|C=c]=\Pr[M=m]$$ and $$H(M|C)=H(M)$$ But now what I've asked myself: If we were to remove the polynomial restriction on the ...
SEJPM's user avatar
  • 46.1k
1 vote
1 answer
310 views

Please prove distinguishability given a non-perfectly secure cipher

I'm trying to prove that a perfectly secure cipher yields indistinguishability. I already know and can prove that a perfect cipher => indistinguishability by the following proof: \begin{align} \Pr(...
student_96's user avatar
1 vote
3 answers
452 views

Generating OTP using Digital Dead Drop

I've had a thought and I'm wondering if this would be a useful way to devise and distribute a one-time pad. It relies on a digital dead drop and a hash function. The digital dead drop could take a ...
Paul S's user avatar
  • 11
1 vote
1 answer
134 views

Optimal threshold for passive and perfect security

The authors of the book titled "Secure Multiparty Computation and Secret Sharing" claim that there exist functions which cannot be computed with passive perfect security for $t \geq n/2$ corrupt ...
sun's user avatar
  • 540
0 votes
1 answer
258 views

Multi-Embedded Xor for Perfect OTP

I am looking for a perfect OTP design, so let's see if this design is good. There are 2 issues when it comes to a good OTP system, the key and the plaintext, we will use XOR as cypher: If the ...
cryptonoob400's user avatar
0 votes
2 answers
1k views

Why does the key for a one-time pad have to be uniformly distributed? [duplicate]

I would like an intuitive argument for what goes wrong in the proof that that a one-time pad provides perfect secrecy, if the key $K$ is not chosen uniformly at random from the entire key space.
john's user avatar
  • 31