# Tag Info

12

Disclaimer: I use Coq on daily basis... I have seen in some places that people use formal verification and/or computer-aided verification for cryptography. To my knowledge, there aren't that many places that do such a thing. :) First lets make sure we talk about the same concepts: Formal Verification: The act of proving the correctness of ...

9

This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper ...

8

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $IND-$ notation ...

8

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt. If $\mathrm{Gen}_1$ and ...

8

Just looking for a Turing machine vs circuit is a bit misleading. The important distinction is uniform (complexity class BPP) vs non-uniform (complexity class P/poly) adversaries. You can characterize P/poly in terms of circuit families, but also in terms of Turing machines with arbitrary "advice strings." In fact, the latter is the more traditional ...

7

I think @CortAmmon hit the nail on the head: cryptographic structures (hashes, ciphers, etc) are specifically designed to be hard for bad guys to analyse / reverse / find patterns in. It should come as no surprise that this is a double-edged sword: they are also hard for good guys to analyse in the form of mathematical proofs. As @CortAmmon said: ...

6

Let me try to answer your second question, and hopefully shed some light on the first one in doing so. When we encrypt a message, it's because we want to keep something about that message secret. But what is it that we actually want to protect? Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON ...

6

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

5

Before answering the actual question, I will offer some general advice. It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this ...

5

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP. ...

5

As the other answers already state here, game-based definitions are easier to write proofs for, but simulation-based definitions are often clearer in terms of the security guarantee that you get. The best example of this is IND-CPA (game-based definition) versus semantic security (simulation-based definition). Note that IND-CPA is really not a convincing ...

5

What does this mean, exactly? The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things ...

5

Informally, CCA2 does not permit any kind of modification of ciphertexts, while RCCA permits some alteration as long as it does not alter the original message. For example, think of a publicly randomizable encryption scheme, that is, a scheme that permits to alter the original randomness used during encryption. CCA2 would consider these ciphertexts as ...

5

The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything. The simple solution Now, the simple solution is, as is mentioned in the comment and the linked question, is to secret-share your message into two shares and encrypt each share separately. The final ciphertext ...

5

In the vast majority of cases, the simulator sets the random tape of the adversary simply because it has to (by the definition). So, the simulator sets it in the beginning to be uniform, and this is then ignored from then on. There is one cases that I know of that this is actually really important, and this is non-black-box zero knowledge. Specifically, in ...

5

1) In the selective unforgeability game (often also denoted universal unforgeability), the adversary is given the public key and a target message for which it needs to produce a forgery (instead of giving the adversary only the public key and letting the adversary choose the target message). 2) No, any scheme that is EUF-CMA is also SUF-CMA (this is easy ...

4

The point why a simulation must not deviate too much from the real game is due to the following reasoning. You assume you have an adversary that wins the original game, but you do not know how the adversary acts if you deviate from the behaviour of the real game and the adversary can notice this. Exactly because you make no assumption whatsoever about the ...

4

I would think these numbers would have been put on the google search engine, and yield (probably) many hits. This assumption is wrong. Certificate serial numbers are not indexed by common search engines, nor are they typically posted to any HTML site. Frankly, I'm not sure why you would assume they'd be indexed. The Wordpress certificate is used for ...

4

Your proof certainly has to work even if the adversary doesn't use the random oracle. One technique that you can try is to begin by proving a separate lemma that if the adversary doesn't ask a certain query first, then it definitely cannot succeed in distinguishing. Then, you proceed to prove the simulation conditioned on it asking this query. However, if ...

4

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the ...

4

This is very strange, and somewhat suspect. The abort here is one that prevents the client from getting output. However, the real-world adversary may behave in a way that the client does get output. I suggest writing to the authors to ask and/or going through this very carefully. Without having gone through the details at all, my initial guess is that this ...

4

Realizes vs Implements Given the context of the cited papers, they mean the same thing. That said, I would prefer realizes. Implements has a connotation of a source code implementation. There could be implementation flaws (buffer overflow, etc) that impact security. The protocol design is secure, but the implementation is not. That, to me, is the primary ...

4

Ricky already gave the answer, but here are some additional details. "Entropy smoothing" hash functions are randomness extractors. Extractors are functions that extract almost uniform bits from weak sources of entropy. In a way, they spread the min-entropy of the input source almost evenly over the (shorter) extracted source, hence the smoothing. The ...

4

Why don't we have any, say, public-private key system that is NP complete to break? $\mathbf{NP}$-completeness is not the appropriate framework to think about the "security" of an encryption scheme, both in theory and in practice. Remember that the complexity classes $\mathbf{P}$, $\mathbf{NP}$, et al. are classes of decision problems, which are ...

3

Note that in the definition you gave, it says that in order for $\Pi$ to be an indistinguishable scheme, then the above inequality must hold for all PPT adversaries. So it seems that if $\Pi$ holds the indistinguishability, then there should not exist any adversary A that $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for ...

3

"simulator": That's a definition of security in a model that is related to but weaker than the universal composability framework (thanks to Yehuda Lindell for making that clear and you can look at the paper in his comment). You could also look up the wiki link and I think there are also several question on this site. As @Yehuda Lindell mentions in a ...

3

The simplest example I know of is actually for a pathological case. Namely, it is presented in Chapter 2 of the book of Hazay and Lindell as an example of a two-party MPC protocol which is secure against a malicious adversary but not against a semi-honest one (in the classical sense, for this reason they prefer the notion of augmented semi-honest ...

3

First, recall that in a chosen-ciphertext attack (CCA) model, the attacker has access to a decryption oracle. A scheme is said CCA-secure if access to a decryption oracle does not give any advantage to the attacker. Knowing this, a very simple CCA attack can be done on BasicIdent. I will use the description of the scheme from Wikipedia. As you can see, ...

3

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ ...

3

Let's take a set with $p$ uniquely defined elements. A uniformly random distribution is that every element has a chance $1/p$ to be picked. What if the last element is never picked and the rest are with an uniform probability of $(p-1)^{-1}$? If you see $k$ items you expect to see the last one with probability $1-(1-1/n)^k$. When $n$ is large, that is ...

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