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.
670
questions
0
votes
0
answers
63
views
Distinguishing between two DDH-like tuples
Given a group generator $g$ (in a group where DDH is hard). Let $X_1=g^{x_1}$ and $X_2=g^{x_2}$ be two public elements, where $x_1$ and $x_2$ are selected randomly and kept secret.
Consider a game ...
- 79
0
votes
0
answers
70
views
Reduction for distinguishing to elements
Given a composite number $n=pq$ of primes $p$ and $q$, a secret random element $r$, and two public random elements $x_1$ and $x_2$. An adversary is given two elements, $y_1= x_1^r \mod n$ and $y_2=x_2^...
- 79
0
votes
0
answers
39
views
Is using a CPA secure public key encryption twice on two halves of the message with different keys secure?
If $\Pi=(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ is a CPA secure public key encryption protocol, is the following public key encryption CPA secure?
$\Pi'$:
$\mathrm{Gen'}$: Run $\mathrm{Gen}$ twice ...
3
votes
1
answer
304
views
Is the secret key kept constant in IND-CPA game?
I read the Wikipedia Page on ciphertext indistinguishability. Here it gives the following outline of the IND-CPA game:
The challenger generates a key pair PK, SK based on some security parameter k (e....
- 221
0
votes
0
answers
27
views
Nature of differentially private Laplace mechanisms
In the Wikipedia page on differential privacy, the section on $\varepsilon$-differential privacy for the Laplace mechanism says that the Laplace mechanism is specified for some output as $\mathcal{T}_{...
- 1
1
vote
1
answer
59
views
Unbounded distinguishers and statistical indistinguishability
In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two ...
- 413
3
votes
3
answers
283
views
How big of a threat are *diffusion model* based AIs to cryptographic systems?
The diffusion model, which is used by products like Midjourney and Dall-E, trains AI systems to de-noise (remove added randomness) from data to infer what the original de-noised data is. That would ...
- 785
1
vote
1
answer
54
views
Existence of PRGs satisfying the following weaker definition
Consider the following definition. Let $p(n) > n$ be a polynomial, and $G_n: \{0, 1\}^n \rightarrow \{0, 1\}^{p(n)}$ a PRG. Moreover, given $x \leftarrow \{0, 1\}^n$, we say $S$ is a length $n-1$ ...
- 526
1
vote
1
answer
86
views
Proving an identification-scheme based on a digital signature is secure
I am trying to prove to myself that an identification scheme derived from a digital signature in a challenge/response manner is secure, based on the security of the digital signature scheme. I've ...
2
votes
0
answers
47
views
self-decryption paradox in identity based encryption
In the paper Dual system encryption: realizing fully secure IBE and HIBE under simple assumption (free PDF), the authors said "there is an apparent paradox in this strategy since it seems that ...
- 341
1
vote
0
answers
34
views
Does blockcipher decryption always offer equivalent security as blockcipher encryption? [duplicate]
I'm not sure if anyone explored this area before. Blockcipher encryption definitely fullfills IND-CCA, but what about its inverse? Is there a proof that shows blockcipher decryption is as secure as ...
- 9,001
4
votes
1
answer
95
views
confusion about the meaning of reduction
I'm learning provable security, and I'm a bit confused with the concept of reduction.
So, here's my understanding:
to prove a protocol/scheme/generic construction is at some level of security, there ...
- 85
1
vote
1
answer
69
views
Does game-theoretical fairness work in when the goal of one party is randomness
When we take the coin flip in Blum's algorithm in "Coin flipping by telephone a protocol for solving impossible problems", where Alice and Bob both want ownership over the same car, then one ...
- 13
2
votes
1
answer
149
views
Provably secure cryptography in blockchains
Do you know a blockchain that does not use at all cryptographic primitives standardized by USA or other countries? It is strange to me that the security of many cryptocurrencies is based on ciphers, ...
- 395
2
votes
1
answer
64
views
Is a Pedersen commitment still secure when r is either 0 or 1?
Specifically if we know the $r$ takes values from the set $\{0,1\}$and $c=g^r*h^m$ does the hiding property still hold? I think I already managed to prove that the binding property holds due to the ...
- 23
2
votes
1
answer
81
views
Security of RLWE encryptions of secret keys
Under which conditions is it secure to publish an encryption of the secret key $s$ under itself in terms of an $RLWE_s(s)$ ciphertext? Because for some schemes this is (repeatedly) used in ...
- 43
2
votes
1
answer
56
views
Replacing the Hash function with messages in the BLS signature scheme, the security degenerates from EUF to SUF?
I have been thinking about this question: if I directly replace the hash function with the message in the BLS signature, does the security of the BLS degenerate from existential unforgeability(EUF) ...
- 368
1
vote
1
answer
88
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 ...
- 113
2
votes
1
answer
54
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
47
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?
- 85
7
votes
1
answer
190
views
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,175
2
votes
0
answers
30
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 ...
- 85
1
vote
1
answer
43
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 ...
- 85
2
votes
1
answer
143
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
156
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
158
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
135
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
99
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
267
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
2k
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.
2
votes
0
answers
101
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 ...
- 177
0
votes
0
answers
35
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
150
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
93
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,848
2
votes
1
answer
100
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
71
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
232
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
99
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 & ...
- 383
0
votes
1
answer
49
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-...
- 383
1
vote
0
answers
48
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}
\...
- 223
2
votes
1
answer
84
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 ...
- 878
1
vote
1
answer
168
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 ...
- 878
1
vote
1
answer
97
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 \...
- 383
2
votes
0
answers
110
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
40
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, ...
- 149
0
votes
0
answers
86
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
22
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
37
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
100
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