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

46
votes
1answer
7k views

What is the “Random Oracle Model” and why is it controversial?

What is the "Random Oracle Model"? Is it an "assumption" akin to the hardness of factoring and discrete log? Or something else? And why do some researchers have a strong distrust of this model?
11
votes
1answer
827 views

Easy explanation of “IND-” security notions?

There are many schemes that can advertise themselves with certain security notions, usually IND-CPA or IND-CCA2, for example plain ElGamal has IND-CPA security but doesn't provide IND-CCA security. ...
4
votes
1answer
419 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 its security based on any one-way ...
27
votes
2answers
7k views

Why does nobody use (or break) the Camellia Cipher?

If Camellia is of equivalent security and speed to AES, concerns arise. First of all, assuming the above, why is Camellia so rarely used in practice? Why aren't there any breaks in Camellia? Does ...
13
votes
5answers
1k views

Can you make a hash out of a stream cipher?

A comment on another question made me wonder about something: Assume you're on a rather constrained platform — say, a low-end embedded device — with no built-in crypto capabilities, ...
3
votes
1answer
343 views

Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secure

Any thoughts on how this can be done? Let $\Pi_1 = (\mathrm{Gen}_1, \mathrm{Enc}_1, \mathrm{Dec}_1)$ and $\Pi_2 = (\mathrm{Gen}_2, \mathrm{Enc}_2, \mathrm{Dec}_2)$ be two encryption schemes for ...
3
votes
3answers
1k views

What are the differences between proofs based on simulation and proofs based on games?

what are the main pros and cons of proving the "security" of a crypto scheme under simulation proofs instead of game based proofs?
14
votes
3answers
3k 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 ...
3
votes
2answers
959 views

Tools for modelling and analysis of cryptographic protocols

I am designing some cryptographic protocols and I am new to it. Are there any well-known tools that can be used to model and design these protocols? And also verify or analyze their validity? If not ...
7
votes
2answers
1k views

Is SipHash cryptographically secure?

I'm evaluating different hash algorithms for use in my application. One of the kind of algorithms I am looking at are cryptographically secure ones to protect against DOS attacks. SipHash seems ...
4
votes
1answer
632 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 ...
15
votes
1answer
984 views

Does unbalancing a feistel cipher always improve security? Does it improve security at all?

So according to Wikipedia unbalanced feistel ciphers provide greater provable security. Specifically, they state: The Thorp shuffle is an extreme case of an unbalanced Feistel cipher in which one ...
1
vote
1answer
312 views

Secure double encryption using CPA and CCA

Do you mind if you give me any hints, links or ideas about how to improve the security of double regular encryption and decryption, by using CPA game and CCA game, it sounds interesting question, and ...
1
vote
1answer
102 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
votes
1answer
85 views

How To prove Any Change to $v=a\cdot y+b$ maks $y=(a)^{−1}\cdot (v−b)$ Uni. random value [closed]

This question is related to data integrity. Let a finite field be $\mathbb{F}_p$, where $p$ is a prime number. I have a fixed value $y$ and two uniformly random values $a$ and $b$. Hypothesis: ...
15
votes
2answers
1k views

Random oracle model proofs and programmability

Proving the security of a scheme with the random oracle model (ROM) involves two steps: first you prove that the scheme is secure in an idealized world where a random oracle exists, and then you ...
7
votes
1answer
727 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 ...
8
votes
4answers
460 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 ...
8
votes
1answer
581 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 ...
7
votes
1answer
229 views

What is the “artificial abort” technique?

In the security proof of Brent Waters's paper Efficient Identity-Based Encryption Without Random Oracles, he uses a novel “artificial abort” step on page 6. At this point the simulator is still ...
7
votes
3answers
1k views

Are there any secure commutative ciphers?

This answer lists two commutative cipher algorithms - Pohlig-Hellman and SRA. However, they don't appear to be too secure. My question is, here there any commutative ciphers out there that are secure ...
4
votes
1answer
606 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 ...
7
votes
1answer
2k 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 ...
6
votes
4answers
449 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 ...
4
votes
2answers
311 views

Is the reduction from left-or-right IND-CPA to real-or-random IND-CPA tight?

A modern trend in cryptography consists of defining security as rigorously as possible, and then designing schemes which are secure according to those definitions. Proving security comes in the form ...
2
votes
2answers
104 views

Formal security of recycled random blinding in a Paillier scheme

This question is a follow-up/variant on a previous question. Supposing that we are trying to generate a large number of (indistinguishable) ciphertexts of a given plaintext and want to avoid the ...
1
vote
0answers
420 views

Variant of the Decisional Bilinear Diffie Hellman problem

I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem: Let $e: \mathbb G_1 ...
6
votes
2answers
204 views

Hamiltonicity proof of knowledge

I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$. So the question will be ...
6
votes
2answers
400 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 ...
6
votes
5answers
3k views

Is a book cipher provably secure?

I've seen ciphers (usually in spy drama shows) that involve taking a book and writing down an index to individual characters. Essentially it's a keyed substitution cipher, where the key is the name ...
5
votes
1answer
303 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 ...
5
votes
1answer
221 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) = ...
4
votes
2answers
725 views

What does “Worst-case hardness” mean in lattice-based cryptography?

In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below: Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with ...
4
votes
2answers
266 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: ...
3
votes
1answer
73 views

How can I formally verify fuzzy commitment scheme based security protocol?

I am currently working on designing a security protocol which involves usage of fuzzy commitment schemes, for. eg Reed-Solomon codes which allows us to tolerate a certain level of error. I was ...
3
votes
1answer
550 views

Why are protocols often proven secure under the random oracle model instead of a hash assumption?

Is this true that whenever you design a protocol using a hash function, you must prove its security under the random oracle? I mean, is it possible to devise a protocol $P$ using a function $H$, and ...
1
vote
1answer
190 views

Requirement for the length of a HMAC tag?

I've seen NIST requirements about key length. What about the output lengths ? Is 112 bits enough for the HMAC output length ? Can we truncate the tag to keep only 112 bits ? Thank you
1
vote
1answer
309 views

How to prove Security of Onion Layers of encryption?

CryptDB has Onion layers of Encryption to provide wider functionality from weaker forms of encryption. How do we prove such things are indeed secure ? Intuitively It seems ok. Are there any parallels ...
1
vote
3answers
1k 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).
1
vote
1answer
676 views

Is this scheme a provably fair random number generation?

I have thought up a method for generating random numbers between a client and a server which I hope is fair: The client and server decide on a range in advance, $0$ trough $n-1$. The server ...
5
votes
2answers
161 views

Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$?

Given, say, the Blowfish block cipher, which is considered secure but only has a 64-bit block size, can we construct a secure block cipher of 128-bit block size? Say we run the key through two KDFs, ...
5
votes
4answers
1k 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?
2
votes
1answer
167 views

Gap problem for Learning With Errors

Informally, a "Gap problem" arises when solving the computational (or search) version using an oracle for the decisional version. This definition of Gap Problem was introduced by Okamoto and ...
1
vote
1answer
334 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
252 views

Indistinguishability attack example

I want solve the next exercise. The author defined the experiment for the cryptosystem $\Pi$, the adversary $A$ and the security parameter $n$ as follows $\mathsf{PRIV_{EAV}}(\Pi,A,n)$ The ...