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
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 ...
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, ...
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, ...
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} \...
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, ...
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) ...
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 ...
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 "...
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 ...
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

1
2 3 4 5
14