A primitive or protocol with provable security is accompanied by a mathematical proof that shows how to reduce the security claims about the protocol to a set of assumptions.

learn more… | top users | synonyms

3
votes
2answers
175 views

CDH problem and Square-DH problem

CDH problem roughly says that choose $U=g^u, V=g^v$ uniformly at random from cyclic group $G$, it's hard to compute $CDH(U,V)=g^{uv}$. Square-DH problem roughly says choose $U=g^u$ uniformly at ...
4
votes
2answers
178 views

Can we say that if $P=NP$ there is no CPA secure public key encryption?

I've learned that public key encryption is based on the problem of Discrete Log (as regard to group theory) which believed to be hard. But, can we say that it doesn't matter on which problem our ...
1
vote
1answer
57 views

Are those two distributions indistinguishable?

The Decision composite residuosity problem problem states that is impossible two distinguish between those two ensembles: $\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r \in ...
4
votes
1answer
197 views

Unforgeability and type of adversary

When trying to prove security of asymmetric signature, for instance for existential (or strong) unforgeability against chosen messages attack, do we need to consider the signer as a possible ...
4
votes
1answer
145 views

How can I tell how many bits of security a secure hash function has?

How can I tell how many bits of security a secure hash function has? For example, how would I calculate or tell how many bits of security a secure hash function with 160 bits output would have? ...
0
votes
1answer
62 views

The real-life meaning of proving over a group that doesn't support the oracle?

If I proved a scheme's security under GDH assumption, in real-life, if this DDH oracle does exist, then it's good, but what about other side ? In real-life, if this DDH oracle doesn't exist, then ...
2
votes
1answer
158 views

Flaw in the security definition of *Stateful* Authenticated Encryption?

I'm in search of the correct definition of a stateful authenticated encryption scheme (sAE), and its related security notion. This has been treated several times in the academic literature, however, ...
3
votes
1answer
194 views

Is $q(n)=1/n$ a negligible function?

By definition - $q(n)$ is a negligible function if for every positive integer $c>0$ there exist an integer $N_c$ such that for all $x>N_c$ : $q(n)<1/x^c$ So for the function $1/x$, if we ...
3
votes
1answer
99 views

Difference between computational and statistical indistinguishabilities

What is the difference between the two notions of computational and statistical indistinguishability?
1
vote
1answer
58 views

order between adversaries and type of resources given

We have a game $G0$ for which an adversary $A$ has access to a certain amount of ressources. Let us suppose that the maximum advantage for the adversary to win this game is $Adv_{G0}$. If we modify ...
6
votes
4answers
279 views

Is there a proof for showing any cryptogram is crackable?

I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time". Is there a proof to show that any cryptogram is "crackable"? The proof may be of a more ...
1
vote
1answer
96 views

SHA-1 Keyed Hash Function

I know that SHA-1 is an unkeyed cryptographic hash function when used in practice. But, in the theory, all hash function are defined with keys. My question is: How I will be able to formalize the ...
4
votes
2answers
232 views

Can anyone give an example where (asymmetric) crypto can go wrong due to selection of wrong groups?

Basically the title says it all. It would be great if someone could tell give an example using provable security. More information about groups can be found at: ...
1
vote
2answers
120 views

PPT eavesdroper able to output $m_{0}$ and $m_{1}$ of different lengths

I've read the following two questions and their answers: Messages of different lengths and one-time computationally-secret Why is a non fixed-length encryption scheme worse than a fixed-length one? ...
1
vote
1answer
108 views

Security based on PRF

I've seen that there is several kinds of PRF, and sometimes people speak about strong PRFs. When proofs of a protocol or algorithm are given based on the assumption of the use of a PRF, are they ...
5
votes
3answers
313 views

Security proofs for CBC mode

I'm looking for different approaches to proofs for the security of CBC mode encryption. What are the best sources of information about this subject?
0
votes
1answer
64 views

Hash of multiset of values, which lets me compute the hash of the union

Cryptographic hash functions normally take as input a bitstring. I am looking for a hash function that takes as input a finite multiset of values. In other words, given $S \subset \{0,1\}^*$, I want ...
1
vote
1answer
178 views

Is there proof to the relation between the gap Diffie-Hellman problem and the the Cha-Cheon signature scheme?

I am trying to prove that: "If the gap Diffie-Hellman problem is easy, then the Cha-Cheon signature scheme will be broken." Can you help me to prove it? Is there any proof to the relation between ...
1
vote
1answer
67 views

Safety when disclosing hashes of secrets used to calculate other secrets

In my application, I am generating a big random number and publishing a SHA256 hash of it. After the hash it published (but not the secret), anyone can submit any number, and the system will calculate ...
4
votes
1answer
172 views

Proof that MACing a hash of the message is also a secure MAC

I found a theorem that says: Let $MAC = (S,V)$ be a MAC for short messages over $(K,M,T)$. Let $H: M^{big} → M$. Define $MAC^{big} = (S^{big},V^{big})$ over $(K,M^{big},T)$ as: $S^{big}(k,m) = ...
2
votes
0answers
60 views

Protocol/algorithms based on a variable-length input PRF

Are the proofs based on a PRF assumption still valid when using a variable-length input PRF ? The answer might be obvious, but I have a doubt.
2
votes
1answer
111 views

Is this EAX extension weakening the (provable) security of EAX?

I would like to insert a key deriving function into EAX mode, in order to hamper brute-force attacks for a key-size restricted cipher (56 bits). The modification inserts an identical multi-block ...
2
votes
2answers
161 views

Where does the meaning of reduction to a hard problem lie?

Given you a protocol, if we can reduce breaking the protocol to a hard problem, such as DLP or CDH, then we can say that this protocol is secure. Theoretically speaking, reduction is a good method ...
4
votes
2answers
417 views

What is the definition of “security beyond the birthday paradox”?

I'm reading a paper about MACs and I would like to be sure about the meaning of a security beyond the birthday paradox. Is there a definition?
2
votes
1answer
141 views

The Goldreich-Goldwasser-Micali Construction with bad PRGS

I understand that if we have a secure PRG then the Goldreich-Goldwasser-Micali construction gives us a secure PRF. However, what I've not been able to find much material on is how will the GGM ...
2
votes
2answers
146 views

how much trust can we place in protocol verifiers? [closed]

I read many papers on authenticated key exchange protocols, and most security proofs are done by the authors. In this method, you can imagine that the efficiency is low. Moreover, even if you have ...
3
votes
1answer
134 views

Is this really the correct way to do an IND-CPA test?

In a description of IND-CPA (indistinguishability under the chosen plaintext attack), I have been reading the following, simple test: The adversary can generate as many messages as he wants. Then, ...
4
votes
2answers
232 views

Is this a structural weakness of Feistel networks?

I'm doing a lot of reading about Feistel networks. Something occurred to me a bit ago that I hadn't realized previously, namely that in any Feistel construction there are bits of the plaintext that ...
5
votes
1answer
104 views

Is there any existing analysis for this construction to turn a tweakable blockcipher into a PRF?

I'm basically looking at this construction to turn a tweakable blockcipher $E_c(x)$ taking a key $k$, nonce $n$, counter $c$ (forming tweak $t = c||n$) and an input $x$ into a PRF on an ...
2
votes
1answer
244 views

some of my confusions about DDH assumption

The wiki defines the decisional Diffie–Hellman assumption as follows: Decisional Diffie–Hellman assumption Consider a (multiplicative) cyclic group $G$ of order $q$, and with generator $g$. The DDH ...
0
votes
1answer
259 views

Is my understanding of CPA indistinguishability experiment correct?

Following are steps to conduct Chosen Plaintext Attack (CPA) indistinguishibility experiment $PrivK_\mathcal{A,E}^{eav}(n)$. $\mathcal{A}$ is the adversary $\mathcal{E}$ is the encryption scheme ...
3
votes
1answer
611 views

Proof that IND$-CPA implies IND-CPA?

I've read a few papers recently that used a notion of security called "indistinguishability from random bits/strings" under chosen plaintext attack, also called IND\$-CPA. See e.g. ...
8
votes
1answer
249 views

Is the inverse of a secure PRP, also a secure PRP?

If a block cipher is a secure PRP, is it's inverse a secure PRP as well? My intuition says yes but I'm not exactly sure. On a related note, if a block cipher is a secure sPRP, is it's inverse a ...
1
vote
1answer
70 views

what is PFS game?

when i reading about this paper, in the Setup of SIM section 5.2, it says that "According to the definition of PFS game", i wonder what the definition of PFS game ...
12
votes
3answers
1k views

What is the ideal cipher model?

What is the ideal cipher model? What assumptions does it make about a block cipher? How does it relate to assuming that my block cipher is a pseudo-random permutation (PRP)? When is the ideal ...
2
votes
1answer
137 views

Can you help me understand PFS and wPFS?

Every time I encounter the concepts of PFS (perfect forward secrecy) and wPFS (weak perfect forward secrecy), I feel uncertain about them. My understanding is that: PFS ensures that, if the ...
4
votes
2answers
272 views

Hash function based on block cipher (and proof of security in the PRP model)

Do there exist proofs of security for primitives like hash functions (based on a block cipher) in the PRP model. I often see proofs in the random oracle model (for hash function based on compression ...
8
votes
4answers
338 views

Automated security protocol verification tool for eCK model

I want a tool that (runs on Win7 and) can perform automated verification of a protocol in the eCK security model as described in Microsoft Research's paper "Stronger Security of Authenticated Key ...
0
votes
2answers
121 views

Why do PKI schemes need security proofs? [closed]

When it comes to designing new PKI-based key-exchange protocols, why are security proofs needed? Without them, can we show a protocol's security? Does there exist a PKI-based key-exchange protocol ...
4
votes
1answer
822 views

What is it meant by a “hybrid argument”?

Can anyone explain (or point to a reference for) what a hybrid argument is in a security proof, and when it's convenient or preferable to use it? Among some of the places where I've seen it ...
2
votes
1answer
152 views

Security of cloud computational protocols in UC Framework?

The universal composability allows one to the analyze security of cryptographic protocols . But it does have some gaps when it comes to analyzing few protocols especially two party cases when there is ...
6
votes
1answer
163 views

Is there a security proof for the Triple-DES construction in the ideal cipher model?

Suppose one has an ideal block cipher $E \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w ...
3
votes
1answer
101 views

Does there exist a two-pass AKE protocol that is secure in eCK model and also has PFS?

As we can know that the best two-pass AKE protocols with DH message can achieve is the weak form of perfect forward security (wPFS) which guarantees security against the passive adversary. But ...
7
votes
1answer
357 views

understanding forking lemma

Every time when I read a paper that has digital signature, when it comes to prove the security of a digital signature scheme, many chances that the author will use the forking lemma. The forking ...
1
vote
3answers
696 views

Hash function based on pseudorandom functions and security

Are there hash functions that make use of pseudorandom functions. Precisely, I'm looking for a specification of a hash function based on PRF (and based on the security of such a primitive).
3
votes
1answer
267 views

Relation between attack and attack model for signatures

I would like to know: What is the relationship between an attack and an attack model. For example, let $\Pi$ be the Lamport signature scheme. This signature has it's security based on the one-way ...
4
votes
6answers
423 views

A block cipher with independent keys for each round

I want to modify a standard block cipher in the following way. I replace each round key by a key picked at random. Is this block cipher as secure as the original one ? Thank you. EDIT Some missing ...
2
votes
0answers
124 views

Ideal system for an encryption scheme

What is the ideal system for an encryption scheme? For a pseudorandom permutation the ideal one is a random permutation, for a pseudorandom function the ideal one is a random function. For an ...
4
votes
1answer
187 views

Questions about the ideal cipher model

I've read that we can study the security of modes of operation by assuming the use of an ideal block cipher. I've also seen a paper suggesting that the ideal cipher model could be something else than ...
3
votes
1answer
250 views

Proofs of security methodologies

I'm looking for course material on the subject of proofs, reductions, and games, as used to prove cryptographic schemes secure. What are the methodologies? What are the preferred ones? In what cases ...