Questions tagged [provable-security]

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.

Filter by
Sorted by
Tagged with
81
votes
2answers
22k 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?
61
votes
6answers
9k views

Soft question: Examples where lack of mathematical rigour cause security breaches?

Cryptographic tools can often become adopted even when their security proofs lack mathematical rigour - or altogether missing. Are there famous cases of security breaches in the industry, where the ...
51
votes
1answer
25k 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. ...
42
votes
3answers
19k 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 ...
32
votes
8answers
10k views

Why do some people believe that humans are "bad at" generating random numbers/characters like this?

I'm not even sure if they are serious, but I've heard many times that some people refuse to not only trust their computer to generate a random string (which is understandable) but also don't trust ...
31
votes
4answers
6k views

Why does Neumann think cryptography isn't the solution?

What did Peter G. Neumann mean by: If you think cryptography is the answer to your problem, then you don't know what your problem is. (eg: quoted in the New York Times, February 20 2001)
30
votes
1answer
1k views

Uniform vs discrete Gaussian sampling in Ring learning with errors

The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
29
votes
3answers
5k 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 ...
29
votes
2answers
4k views

Formal verification in cryptography

I have seen in some places that people use formal verification and/or computer-aided verification for cryptography (tools like ProVerif, CryptoVerif, etc.). How do these approaches work?
29
votes
2answers
4k views

What are standard cryptographic assumptions?

I am struggling to understand what is meant by "standard cryptographic assumption". The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first ...
25
votes
3answers
18k views

Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers

Given that much of our ECC crypto primitives provide “only” 128-bit security when defined over a 256-bit curve due to pollard-rho, is it then still safe in 2020 to consider 128-bit security safe for ...
21
votes
3answers
8k 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 ...
21
votes
1answer
5k views

What do the signature security abbreviations like EUF-CMA mean?

From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes. The most common ones are the *UF-* ...
19
votes
4answers
3k views

Are encryption algorithms with fixed-point free permutations inherently flawed?

Flaw in Enigma One of the Enigma machine's flaw was the derangement (fixed-point free permutation) of the produced ciphertext, or simply put: No plaintext-letter can be enciphered to itself. See this ...
19
votes
2answers
1k views

Practical differences between circuits and turing machines for cryptography

In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more ...
18
votes
2answers
3k views

Simulation-based proofs and universal composability proofs

I recently read Ran Canetti's famous UC paper but I'm still trying to wrap my head around the concepts. I think this answer has me confused a bit, particularly where it says The stand-alone ...
17
votes
4answers
2k 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, but ...
17
votes
1answer
7k views

uniform vs. non-uniform PPT

I'm trying to understand PPT and in particular what the differences are in uniform and non-uniform PPT's. First, this is how I see it: A probabilistic polynomial-time (PPT) algorithm $A$ is an ...
17
votes
3answers
5k 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 ...
16
votes
1answer
2k 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 ...
16
votes
1answer
864 views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...
14
votes
7answers
4k views

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

In CPA, it is said that the adversaries get ciphertext for the choice of plaintext of adversaries through an encryption oracle. Is this a realistic assumption in real-world, in which the adversaries ...
14
votes
1answer
308 views

Explanation and proof of a well-know probabilistic lemma

Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma: Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \...
13
votes
2answers
3k 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 ...
13
votes
1answer
2k 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 ...
13
votes
1answer
4k views

Proofs by reduction and times of adversaries

I have some difficulties to understand, when we construct a reduction, how we determine the time for the constructed adversary to break a target security property. In general these details are not ...
13
votes
1answer
519 views

How is "post-quantum security" proven/shown?

Due to growing concerns over the threat of quantum computing to asymmetric cryptography (RSA, ECC, etc), a number of "quantum resistant" replacements have been proposed (SPHINCS, McBits, and many more)...
13
votes
1answer
699 views

How did the Koblitz/Menezes papers affect the cryptography community?

Two highly-critical papers by Koblitz and Menezes (two well-regarded mathematicians who've contributed to the crypto community) were published years ago: Another Look at “Provable Security” in 2004, ...
12
votes
3answers
4k 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?
12
votes
2answers
5k views

Why don't we use Blowfish if it hasn't been cracked?

Since Blowfish is old, well-audited, and has no published attacks, why are we using AES instead? I know that Bruce Schneier said that Blowfish is insecure and told people to transition to Twofish, but ...
12
votes
2answers
1k views

Are CDH and Square-DH equally hard?

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

Relation between attack and attack model for signatures

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 function. The Grover ...
11
votes
1answer
3k 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 ...
11
votes
1answer
2k views

CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm $Enc$ chooses ...
10
votes
2answers
3k 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 ...
10
votes
1answer
561 views

Are DSA and ECDSA provably secure assuming DL security?

Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
10
votes
4answers
633 views

Signature security proof in the Random Oracle model

As a study case, I consider the BLS signature scheme, but the following question is relevant in the general context of security proofs in the Random Oracle model. Let us briefly recall BLS signature ...
10
votes
3answers
2k views

How to prove the security of block ciphers

I see very often proofs of security for asymmetric crypto algorithms, for instance, using reductions to known hard problems, or game based proofs... In the field of protocols (like authentication) it ...
10
votes
1answer
5k 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. http://pdf.aminer....
10
votes
1answer
4k 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 mentioned,...
10
votes
0answers
607 views

What level of security is provided when a Feistel Cipher is used as a round function of another Feistel Cipher?

Recently, I was reading: Are there any specific requirements for the function F in a Feistel cipher?, and the answer posted mentions a Feistel Cipher named Turtle, which uses a four-round Feistel ...
9
votes
4answers
390 views

Why haven't we proven many things computationally secure yet?

Brute Force is infeasible for just about every algorithm we use today. Yet, attacks are feasible. This is because weaknesses keep coming up in our algorithms. Why? We have proven lower bounds for ...
9
votes
1answer
2k views

Difference between computational and statistical indistinguishabilities

What is the difference between the two notions of computational and statistical indistinguishability?
9
votes
4answers
6k 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?
9
votes
3answers
725 views

Are there any symmetric cryptosystems based on computational complexity assumptions?

Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer ...
9
votes
2answers
238 views

Are interactive proofs more secure their non-interactive counterpart?

Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure? Are there any new attack vectors that get introduced? Is there any reason to use the ...
9
votes
1answer
860 views

Is there a formal language to define a cryptographic protocol?

I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol ...
9
votes
1answer
1k views

Why is EdDSA collision-resilient with SHA-512?

In the Bernstein et al. paper about EdDSA, the authors claim EdDSA is resilient against collisions (i.e. it can still be secure even if the hash function used isn't collision-resistant), drawing on a ...
9
votes
1answer
927 views

Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

Assume that $f$ is a one-way function (OWF), and let $\mathbin\|$ denote string concatenation. Consider the function $g$ defined by $g(x) = f(x) \mathbin\| f(f(x))$. It is easy to prove that $g$ is a ...
8
votes
8answers
2k 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 ...

1
2 3 4 5
12