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.
93
questions
47
votes
1answer
22k 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.
...
76
votes
2answers
19k 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?
20
votes
1answer
4k 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-* ...
20
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 ...
27
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 ...
5
votes
2answers
2k views
What is the relation between computational security and provable security?
I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security.
Let $...
29
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 ...
11
votes
1answer
2k 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 ...
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?
5
votes
1answer
3k 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 ...
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 ...
12
votes
3answers
3k 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?
11
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$ ...
9
votes
7answers
6k 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 ...
1
vote
3answers
1k views
Is there a cryptography algorithm that will remain safe if P=NP?
From what I heard, many encryption algorithms are based on the assumption that some problems are computationally hard, i.e, NP-complete. In the unlikely event that someone proves that P=NP, these ...
42
votes
3answers
18k 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
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 ...
7
votes
1answer
456 views
Relation between decisional SIS and leftover hash lemma in lattices
The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
2
votes
1answer
460 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 ...
4
votes
1answer
2k views
Construct IND-CPA secure encryption scheme by combining two given schemes
I have two encryption schemes $\Pi_0, \Pi_1$, at least one of them is IND-CPA secure but I don't know which one. The task is to construct a scheme $\Pi$ that is guaranteed to be CPA secure and to ...
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 ...
8
votes
1answer
411 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?
59
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 ...
25
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?
30
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)
22
votes
3answers
12k 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 ...
7
votes
1answer
2k 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 ...
5
votes
1answer
2k 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 ...
5
votes
2answers
2k views
Prove the Security of Schnorr's Signature Scheme
I know that Schnorr's signature is important since it is one of the most compact signature schemes whose security has been proved in the random oracle model.
Now, I want to know if such proof is ...
17
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
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 ...
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 ...
9
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 ...
8
votes
1answer
511 views
Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?
I have been reading about homomorphic encryption and ...
6
votes
1answer
4k views
Why is “semantically secure” important for cryptosystems?
The first question: what is the exact definition of semantically secure?
Basically, a cryptosystem is semantically secure if given the public key and the ciphertext, an adversary cannot learn any ...
8
votes
1answer
1k views
Difference between computational and statistical indistinguishabilities
What is the difference between the two notions of computational and statistical indistinguishability?
7
votes
2answers
2k views
Difference left-or-right CPA security, IND-CPA security
I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to ...
0
votes
1answer
95 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: $a,...
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 ...
17
votes
2answers
935 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 ...
14
votes
1answer
6k 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 ...
7
votes
1answer
1k views
Simulation Based Proof: What Can / Can not Simulator Do?
I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance:
...
6
votes
2answers
2k 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 ...
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
1answer
4k 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....
9
votes
1answer
825 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 ...
4
votes
2answers
2k views
Simulation based proofs: Simple examples
I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their ...
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 ...
7
votes
1answer
421 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 ...
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 ...
