Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
22 views

Perfect Indistinguishability in shift cipher

I have the following question: Which of the following attackers can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability? ...
0
votes
0answers
81 views

Prove or refute: An encryption scheme is perfectly secret

Prove or refute: An encryption scheme with message space $\mathcal M$ is perfectly secret if and only if for every probability distribution over $\mathcal M$ and every $c_0, c_1 \in \mathcal C$ we ...
2
votes
1answer
65 views

How well is it understood mathematically why encryption schemes are hard to crack?

I have read some intro material into cryptography. It mainly goes into the current encryption schemes like AES, but not very deeply into the mathematics of why they are secure. I know that encryption ...
-3
votes
4answers
135 views

Practical perfect security in bitwise XOR vs integer addition/subtraction cipher

XOR already provides perfect security in theory but it's hard to apply it in practice due to strict requirements. I was thinking about whether simple addition/subtraction in integer format would not ...
0
votes
0answers
60 views

Showing that a cipher is not a perfect cipher

I was given this problem: Prove that the following ciphers are not perfect, using as few blocks as you can. There is no need to prove that the number of blocks is indeed minimal. DES AES-128 AES-256 ...
1
vote
3answers
97 views

Is perfect forward secrecy (PFS) possible without public key cryptography

I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public ...
1
vote
1answer
94 views

Perfect Secrecy prove

There was a question on my final exam, but I could not get a point. I really want to know the right answer. Question is: Suppose a cryptosystem has perfect secrecy. Prove that H(P|C) = H(P) H(...
-1
votes
1answer
64 views
1
vote
2answers
73 views

Is perfectly secret key exchange provably impossible?

We know that perfect secrecy in encryption is possible (one-time pad). Now, the concept of key exchange like Diffie-Hellman is that we can establish a shared key without an interceptor knowing, and ...
1
vote
1answer
72 views

(Im)perfect Secrecy: |K| < |M|

I have a basic understanding of perfect secrecy. In the case where |K| == |M|, I see that there is only one key to encrypt a given m to a given c. Therefore each m is equally likely with same ...
2
votes
0answers
54 views

Necessity of Randomness when Privately Computing a Sum

I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing ...
3
votes
1answer
107 views

Proving one time pad is perfectly secret

I'm reading about one-time pad in "Introduction to Modern Cryptography" by Katz and Lindell. I can understand the definition of perfect secrecy. However, how is OTP proven to be perfectly secure ? I'm ...
2
votes
1answer
160 views

Proving that there is no scheme which would be perfectly CPA-secure

A private-key encryption scheme Π = (Gen, Enc, Dec) has perfectly indistinguishable encryptions under a chosen-plaintext attack, if for all probabilistic polynomial-time adversaries A it holds that Pr[...
0
votes
0answers
13 views

Perfect secrecy of OTP [duplicate]

When using the one-time pad with the key k = 0l, we have Enck(m) = k ⊕ m = m and the message is sent in the clear! It has therefore been suggested to modify the one-time pad by only encrypting with k ...
4
votes
1answer
140 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 ...
1
vote
0answers
48 views

Perfect Secrecy for some distribution implies perfect secrecy for any distribution

I'm quite thrilled about this question I got for homework, even though we were given the answer to the problem. It goes like this: Let $\mathcal{M}$ be the set of plaintexts of a symmetric encryption ...
0
votes
1answer
49 views

One-time pad and Perfect secrecy

Consider the following property of one-time symmetric encryption scheme $(\mathsf{Enc}, \mathsf{Dec}, \mathsf{K})$. For Every message distribution $M$, every pair of messages $m_0,m_1$ belonging to $M$...
-1
votes
1answer
41 views

Question on probability distribution

I computed $\Pr[\mathsf{CT} = 1] = \Pr[\mathsf{CT} = 2] = \Pr[\mathsf{CT} = 4] = 2/9$ and $\Pr[\mathsf{CT} = 3] = 1/3$. When I calculate the first entry in the table, I get 1/2 not 1/9. Is my ...
1
vote
0answers
87 views

Perfectly secret scheme for two distinct messages

Following the same definition in this question for perfect secrecy for two messages $m,m' \in \mathcal{M}$. I don't understand how the accepted answer produces a secure system? I mean The adversary ...
3
votes
0answers
123 views

Epsilon Perfect Secrecy: Size of Key Space

I am solving a homework problem which defines $(1-\epsilon)$-perfect secrecy as the secrecy satisfied by the encryption scheme when the following inequality holds $\Pr[M=m\mathrel|C=c]\leq (1+\...
0
votes
0answers
42 views

On computing probability of some cipher text

One presentation shows how one could compute probability of some cipher text occurring: Which I understand. However, also for computing probability that a plain text occurs given a ciphertext occured,...
1
vote
2answers
111 views

clarify perfect secrecy definition

One of the notes defined perfect secrecy (PS) as Let E = (E,D) be a Shannon cipher defined over (K,M, C). Consider a ...
10
votes
2answers
2k 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 ...
1
vote
1answer
113 views

How Shannon’s concept of perfect secrecy is linked with mutual information?

For a system to be unconditionally secure $H(K) \geq H(M)$, i.e entropy of the secret key must be at least as great as the entropy of the plaintext The mutual information is: $I(X;Y)=H(X)-H(X\...
2
votes
1answer
118 views

Secure multiparty sum computation corruption bound

In Section 3.4 of the book Secure Multiparty Computation and Secret Sharing, it is claimed that for a secure multiparty computation problem with $n$ parties, the optimal corruption bound (concerning ...
0
votes
1answer
61 views

secure system in the perfect sense

a secure system in the perfect sense verifies the definition of perfect security. My question is as follows: There is always a way to check for perfect security by solving the first degree equation by ...
5
votes
1answer
251 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\...
1
vote
2answers
272 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$ ...
0
votes
1answer
146 views

Perfect secrecy of block ciphers

Is it right that all block ciphers don't provide perfect secrecy like AES? If it's true, how can we prove that? If it's not true can you tell me a sample? Any reference or guidance would be ...
1
vote
3answers
145 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 ...
1
vote
1answer
659 views

Understanding how to proof an encryption scheme is perfectly secret

Consider each of the following encryption schemes and state whether the scheme is perfectly secret or not. Justify your answer by giving a detailed proof if your answer is Yes, and a ...
1
vote
1answer
97 views

Corruption bound of MPC when n>2

In the book titled "Secure Multiparty Computation and Secret Sharing" stated that MPC protocol is not secure when the adversary $t>n/2$. This was proved by using a 2 party protocol, but I can't ...
0
votes
1answer
97 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 ...
1
vote
2answers
48 views

Does High Frequency Randomisation of valid and dummy messages in a high volume channel add security?

This was originally posed as this question: "Does randomisation of valid and dummy messages in a high volume channel add security?" But due to the reformulation based on answers provided, Tylo (https:...
0
votes
1answer
222 views

Perfect secrecy with some considerartion

According to eavesdropping indistinguishability experiment $PrivK_{A,\Pi}^{eav}$ from page 34 of this book, I define $\varepsilon$-perfect secrecy as this($\varepsilon>0)$: For every adversary $A$ ...
0
votes
0answers
58 views

What is different between Strictly Ideal and Perfect Secure?

Consider a Cipher $C = (X, Y, Z, \Pr[X], \Pr[Z], E, D)$. $X$ is the plaintext, $Y$ is the ciphertext, $Z$ is a set of keys, $E$ is the encryption function, $D$ is the decryption function. $\Pr[X]$ is ...
1
vote
1answer
268 views

What are the vulnerabilities of XOR in the following scenario?

What are the security vulnerabilities of the XOR operator in the following scenario: The Key, The Cyphertext and the Plaintext are the same size in bits. The Key is only used once and it's secret The ...
1
vote
1answer
38 views

Equivalance Operator - Perfect Secrecy

The equivalance operator is the inverse of the XOR operator, it's symmetric. Would this mean that it would also provide theoretical perfect secrecy just like XOR? XOR ...
16
votes
12answers
12k views

Are one-time pads crackable in theory?

I've been taught that one-time pads are the only perfect encryption, since the only way to recover the message is by knowing the key. For example, for a target bitstring of 100 bits, I cannot scan ...
0
votes
3answers
104 views

Perfect Secrecy with 1 Time Complex Secret Cypher

Is it possible to achieve perfect secrecy, unbreakable, unguessable, uncrackable by using a totally secret cypher? The following conditions must apply: Using the secret cypher only 1 time, so that ...
0
votes
0answers
53 views

Interpretation of message space distribution in the definition of perfect secrecy of encryption schemes

I am a beginner to cryptography, and have started reading Katz and Lindell's book titled "Introduction to Modern Cryptography". I'm unable to understand what the probability distribution over the ...
0
votes
2answers
427 views

Perfect secrecy with XOR & SHIFT?

I have read that XOR provides perfect secrecy, when the key is perfectly random. However it's technically hard to generate truly random numbers, especially on computers, so that is why people use AES, ...
5
votes
1answer
267 views

Can AKE keys provide PFS

Can the channel keys that are derived from an AKE (authenticated key exchange) protocol be used in a secure channel that wants to have perfect forward secrecy? If the goal of AKE is to establish ...
1
vote
2answers
162 views

Distributing shares in a particular monotone access structure

Consider 6 people, $A,B,C,D,E,F$ and a secret. Construct a scheme which enables the following subsets of people to retrieve the secret: three players from the set $\{A,B,C,D\}$ two players from the ...
1
vote
2answers
184 views

A perfect $(2; 2)$-threshold scheme

Given a symmetric encryption scheme with $|K| = |C| = |M|$ that provides perfect secrecy, it is possible to share a secret $s ∈ M$ between two players by giving one player a key $k ∈ K$ and the other ...
2
votes
1answer
225 views

AES function with 128 bit key and 128 bit input size - does it have perfect secrecy?

If I look at the version of AES that gets key of size 128 bit and encrypts messages of size 128 bits. If I get some random key for the function, can I say it has a perfect secrecy and why? After a ...
4
votes
2answers
504 views

Prove Vigenere cipher isn't perfectly secret

As part of a homework assignment I have to prove/disprove that a Vigenère Cipher with a key of length n, uniformly distributed in the alphabet, on a plain text of length 2n, also uniformly distributed ...
0
votes
1answer
1k views

Prove that a given encryption scheme is perfectly secret

I'm studying for an upcoming test and I can't figure out the following sample question: Let $\Pi = (\operatorname{Gen}, \operatorname{Enc}, \operatorname{Dec})$ be an encryption scheme with key ...
4
votes
0answers
273 views

Shannon cipher with fewer keys than messages

Alice and Bob have a set $\mathcal{M}$ of $|\mathcal{M}|$ messages and a set $\mathcal{K}$ of $|\mathcal{K}|$ keys. Alice wants to send a message $m \in \mathcal{M}$ to Bob. She uniformly picks a key $...
4
votes
2answers
437 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,...