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.
658
questions
1
vote
1
answer
84
views
Is it appropriate to prohibit an adversary from querying a specific input in an algorithm in some situation?
There are two algorithms in my framework, $E_1(\cdot)$ and $E_2(\cdot)$.
In particular, executing $E_1(\cdot)$ on a specific input $x$ (i.e., $E_1(x)$) is equivalent to executing $E_2(y)$ for some ...
- 103
2
votes
1
answer
29
views
Reduction from Distinguisher to Indishtinguishability
Content and Informal Problem
Suppose a protocol $\pi$ doing an arbitrary task between two users A and B. I only know that $\pi$ relies on a IND-CPA symmetric encryption scheme $\mathcal{E} = $(KeyGen, ...
- 23
0
votes
0
answers
39
views
Security assumption: Where is an assumption from (who provides and formalizes it)?
Is there a list of all the (most) assumptions (such as RSA and DDH assumptions) used in cryptography and the corresponding properties?
- 73
5
votes
0
answers
120
views
+50
Are rejected Dilithium commitments secret?
On 6 March, Yi Lee sent over the NIST mailing list an announcement of their submitted paper that found a flaw in the original security proof for Dilithium. In their manuscript, they fix the proof on ...
- 1,115
2
votes
0
answers
22
views
Stand-alone simulation proof: Ideal functions and leakage collection
Are ideal functions and leakage collections the terms of UC security? Why I often see them in a simulation-based proof under stand-alone model? Some papers use the definition in Lindell's How to ...
- 73
1
vote
1
answer
31
views
Simulation based proofs: how many simulators should be constructed?
In simulation based proof of cryptographic scheme, if k parties are invovled in the scheme, then k simulators should be ...
- 73
2
votes
1
answer
95
views
Expanding stand-alone simulation-based proofs to UC proofs
This is a follow-up question to Mikero’s answer to Simulation-based proofs and universal composability proofs.
Let there be some protocol $\pi$ running between two parties $A$ and $B$.
Furthermore, ...
- 23
1
vote
2
answers
67
views
Showing that CPA encryption schemes cannot preserve the length of a message
I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am stuck on the following problem.
Let $\mathcal{E}$ be be an encryption scheme where messages and ...
0
votes
1
answer
118
views
How many bits of encryption are enforced in WEP (wired equivalent protocol)
I'm currently taking a computer security module in University and as part of a problem have been asked:
My thought for the question is that no it does not provide 64 bits of security strength. This ...
- 77
0
votes
1
answer
92
views
Proof for secure stream cipher implies secure PRG
I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am not sure if my proof for the following problem in the book is correct. The problem asks to prove that if a ...
3
votes
0
answers
71
views
Semantic Security equivalent to Real/Random Semantic Security
I'm reading Boneh and Shoup's book "A Graduate Course in Applied Cryptography." Im doing one of the questions at the end of the stream ciphers chapter. I'm not sure how to do this problem:
...
2
votes
3
answers
238
views
Is exposing hash of private key provably secure?
Let's say we have an IND-CPA secure public key encryption scheme $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$. Construct a new PKE $\Pi' = (\text{Gen}', \text{Enc}', \text{Dec}')$ that behaves exactly ...
0
votes
1
answer
237
views
Is 7-Zip Encryption really secure? [duplicate]
Is 7-Zip really a good encryption tool? I wonder what kind of encryption is used in 7-zip. I see most people using 7-Zip. Just curious about what extent it is safe.
- 231
2
votes
0
answers
89
views
Automated Security Protocol tool that models algebraic operations
Are there any automated security protocol verification tools that model algebraic operations; specifically addition.
I am familiar with AVISPA and Verifpal, and they are both great and user-friendly ...
- 157
0
votes
0
answers
27
views
Game-based security notion and hybrid proofs - adversarial randomness
Say we have a game-based definition of security and wish to prove the security of our construction using a series of hybrids. Can we somehow "fix" an adversary that we interact with in one ...
- 61
4
votes
1
answer
131
views
Random oracles and the Borel-Cantelli Lemma
I am trying to understand the implication of the Borel-Cantelli Lemma to the random oracle model.
I think understanding a special case, say, a random oracle is one-way with probability 1, would be ...
- 295
2
votes
0
answers
78
views
Composability of state-separable proofs
Brzusk et al. introduced the state-separation proof technique to tame complexity in game-based security proofs. The framework allows for modular, easy to understand, and reusable proofs. It has been ...
- 2,073
2
votes
1
answer
95
views
Alternative definition of security for MAC
In the usual definition of security for message authentication codes, we let an adversary $A$ have access to an oracle for $Mac_k(.)$. However, if we consider that there exists a more powerful type of ...
1
vote
1
answer
53
views
Reduction from Real-Or-Random to Left-Or-Right
I am reading the paper A Concrete Security Treatment of Symmetric Encryption and am confused by the reduction from ROR to LOR on page 11. Specifically, when it says:
When $\mathcal{O}_2(\cdot)=\...
- 13
4
votes
0
answers
150
views
XOR of a secure PRF is modified weakly secure PRF
While reading A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. There was the next exercise (Ex. 4.2 (b)), let $F$ be a secure PRF over $(K,X,Y)$ where $Y := \{0,1\}^n$ and $|X|$...
- 66
2
votes
0
answers
75
views
Regev PKE not CPA secure for specific $A$?
I encountered notes stating that, for certain fixed $A$, such as $A \in M_{n\log(q)\times n}$ as follows:
\begin{bmatrix}
1 & 0 & 0 &\dots\\
2 & 0 & 0 &\dots\\
4 & 0 & ...
- 321
0
votes
1
answer
39
views
QR-PKE not CCA secure
Due to a comment stating "... QR-PKE is secure (CPA)..." I've been thinking of how to prove that it's not CCA secure, and would like to understand whether my proof is correct.
Here's the QR-...
- 321
1
vote
0
answers
44
views
Adversary's advantages against mode of operation instantiated with random permutation and block cipher relation
I'm reading an article "A Tweakable Enciphering Mode" by Halevi and Rogavay and wondering about one statement. On page 6 there are 3 inequalities:
$$
\begin{equation}
\begin{split}
\...
- 208
2
votes
1
answer
67
views
Why we need to consider a probability ensemble and not just a probability distribution in the definition of Security under Simulation?
I'm currently reading this classic paper "How To Simulate It" and on most of the definitions it is using the term probability ensemble to represent the message space. From my understanding a ...
- 826
1
vote
1
answer
114
views
Can we achieve statistical Completeness, Soundness and Zero Knowledge in an Interactive Proof?
The question is mainly stated in the title, sorry for it being a bit small of a question. I was reading about ZK proofs and I was wondering what do we know about their limits only their properties. Do ...
- 826
1
vote
1
answer
65
views
How to complete this proof of statistically indistinguishable distributions?
Given that:
$$ SD\bigg( (r, \langle r, s \rangle),(r, b) \bigg) < \mathrm{negl}(n)$$
where $SD$ stands for statistical distance, $r$ is random uniform in $\{0,1\}^n$, $s$ is random uniform in $S \...
- 321
2
votes
0
answers
72
views
A Question on the "rewinding" technique in secure computation
Consider secure two-party computation against malicious adversaries in the standalone model.
I know that the "rewinding" technique can be used to extract the corrupt party's input, e.g., in $...
- 414
0
votes
0
answers
39
views
Provable security with over-computing power
Suppose we are trying to construct a cryptographic scheme, say public key encryption, and I can prove the IND-CPA security of the PKE scheme when any adversaries perform at least $T$ queries. That is, ...
- 139
0
votes
0
answers
72
views
Provably secure and Practical ciphers
Are there any ciphers that are
provably secure (reducable to a hard problem (including like factorization, not necessarily to NP-Complete or harder) )
are practical (not necessarily for too much ...
- 41
2
votes
0
answers
19
views
How to prove the security of the MT-based multiplication protocol via the simulation paradigm
It is known that Multiplicaiton Triple (MT) can be used for secure online multiplication, which is defined by $\mathsf{Mul}(x, y)=(z_0, z_1)$, where $x\cdot y = z_0 + z_1$
$P_0$ sample random $a$, ...
- 21
1
vote
0
answers
36
views
Can the proof only be the stateful?
Let SE be stateful encryption.
Then, it is well known that the oracle for the security proof becomes stateful too. (We only consider the IND-CPA security game.)
On the other hand, assume that E is ...
- 11
4
votes
0
answers
80
views
How to get started with Simulation and UC proofs?
I've been in my PhD program for a few months, and every time I try to understand the simulation and UC proof-paradigms I get so confused.
I feel like what I really need is an easy set of (guided) ...
- 41
0
votes
0
answers
41
views
Whats a practical and safe encryption to use today? [duplicate]
I'm new to making applications that encrypt sensitive data and so don't know where to start.
My question is what is a good encryption scheme that can be run in a good time for normal application and ...
- 101
0
votes
0
answers
23
views
Correct definition of circular security - multiple encryptions of $sk$ allowed?
As I understand the definition, it's an extension of CPA security where the attacker can ask for an encryption of the secret key, using the public key.
My question is - does the definition allow the ...
- 321
2
votes
0
answers
71
views
How Cut-and-Choose can leak information?
I'm currently reading the book "A Pragmatic Introduction to Secure Multi-Party Computation". On pages 103-104 I came across the following related to the Cut-and-Choose technique:
If $P_2$ ...
- 826
2
votes
0
answers
48
views
Noise flooding with Renyi divergence
According to this question, I found papers that deal with noise flooding with Renyi divergence. However, the answer is still unclear to me on how to use Renyi divergence on the noise flooding ...
- 21
0
votes
0
answers
71
views
Is Regev’s public-key encryption with $sk$ chosen from $\{0, 1\}^n$ circular secure under CPA security?
I thought maybe this is true with something like the following reduction (if we assume for contradiction that it is not circular secure):
For $A$ to 'break' CPA security, let $C$ be the 'collaborator' ...
- 321
3
votes
1
answer
82
views
In reduction from search LWE to decsion LWE why sampling needs to repeat a polynomial number of times?
I've been reading through MIT's lecture notes on learning with errors here, and I'm trying to understand the reduction from Search LWE to Decision LWE, as described there in Section 2.7, "...
- 321
1
vote
1
answer
101
views
Why do we need the leftover hash lemma for this hybrid proof (Learning with Errors)?
I've been reading about Learning with Errors here. On p. 7 there's a proof for the security of the PKE scheme, that goes through the leftover hash lemma, in order to prove that: $$ (pk, Enc(0))\equiv (...
- 321
0
votes
3
answers
250
views
Do we want to allow/Have we allowed parallelization (e.g GPU programming) to enter the cryptographic field? What are the consequences?
With the term GPU programming, I'm referring to highly parallelizable computing in general.
Lastly, I have built a bit of a background in cryptography. So I have started to wonder if/where GPU ...
- 826
1
vote
0
answers
66
views
Is the following statistically close to uniform? (and how does one prove such claims in general)
For every $a \in \{0,1\}^n$ define:
$$h_a : \{0,1\}^n\to \{0,1\}$$
$$ h_a(b)=\langle a,b \rangle$$
So $\{h_a\}_{a \in \{0,1\}^n}$ is known to be a universal hash function family.
This means that if we ...
- 321
1
vote
1
answer
80
views
When does the need of random data become an assumption?
Suppose an encrypion scheme uses a random string to encrypt and decrypt, which is publicly available, such as an IV or nonce. In all the cases I am aware of, the existence of say an IV is not "...
- 514
1
vote
1
answer
77
views
Question on Simulation based security proof for Oblivious Transfer (OT) against semi-honest adversaries
I'm currently reading this How To Simulate It – A Tutorial on the Simulation Proof Technique.
On p. 10, there is a proof using simulation for 1/2-OT, against semi-honest adversaries. Briefly, the ...
- 826
0
votes
1
answer
88
views
Question on notation of random variables in probability ensembles
Let's consider this definition of computational indistinguishability.
Computational indistinguishability. A probability ensemble $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ is an infinite ...
- 826
1
vote
2
answers
90
views
Relative bits of security of slower functions
Leaving memory-hardness assumptions aside, some slow hash functions are iterated salted hash-chain versions of regular cryptographic hashes. This is usually defined by a ...
- 222
0
votes
0
answers
34
views
Difference of unconditional and perfect security in terms of IND-Game
Both unconditional and perfect security were very clear to me, until I bumped upon different sources that confused me.
For example : 1 2 3.
Also in 3 the DH76 paper is referenced and it doesn't ...
- 826
1
vote
1
answer
108
views
A security issue of a Bit commitment scheme constructed by Naor in 1990
In the Section 3.12 of book writen by Boneh and Shoup, a Bit commitment from secure PRGs is presented as follow:
Bob commits to bit $b_0\in_R\{0,1\}$:
Step 1: Alice chooses a random $r\in R$ and sends ...
- 316
0
votes
0
answers
45
views
How to securely implement a deadpool in a PoW blockchain?
Imagine you have a blockchain where the Proof of Work scheme is integer factorization. There is an opcode that takes two integers $N,M$ where it returns true if $M\not\in \{0,1,N\}$ and $N \mod M \...
- 23
2
votes
0
answers
94
views
Quantitative security of signature scheme obtained by Fiat-Shamir tranform
I'm looking for a quantitative yet simple proof of the EUF-CMA security of a signature scheme obtained by Fiat-Shamir transform.
Recall the Fiat-Shamir transform starts from a 3-pass identification ...
- 132k
0
votes
0
answers
39
views
BB - IBE and the BDDH assumption
Given the BB-IBE scheme how can changing the hash fnc. result in the scheme no longer being IND-SID-CPA secure?
- 159