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
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 ...
Doron's user avatar
  • 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^...
Doron's user avatar
  • 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 ...
Kagura Hitoha's user avatar
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....
Riemann's user avatar
  • 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}_{...
meeeeee's user avatar
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 ...
Lev's user avatar
  • 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 ...
aiootp's user avatar
  • 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$ ...
user918212's user avatar
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 ...
puppet puppet's user avatar
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 ...
Alex Ideal's user avatar
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 ...
DannyNiu's user avatar
  • 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 ...
Daisy Ding's user avatar
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 ...
Mangudai's user avatar
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, ...
Dimitri Koshelev's user avatar
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 ...
GeorgeT's user avatar
  • 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 ...
opag's user avatar
  • 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) ...
ming alex's user avatar
  • 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 ...
Zi-Yuan Liu's user avatar
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, ...
gamarcad's user avatar
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?
Jeffrey's user avatar
  • 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 ...
dusk's user avatar
  • 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 ...
Jeffrey's user avatar
  • 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 ...
Jeffrey's user avatar
  • 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, ...
Simulator's user avatar
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 ...
cryptolearner's user avatar
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 ...
hasin's user avatar
  • 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 ...
cryptolearner's user avatar
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: ...
cryptolearner's user avatar
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 ...
puppet puppet's user avatar
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.
Bhargav - Retarded Skills's user avatar
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 ...
Mona's user avatar
  • 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 ...
Lumlum's user avatar
  • 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 ...
user50394's user avatar
  • 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 ...
Marc Ilunga's user avatar
  • 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 ...
Caio Nogueira's user avatar
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)=\...
ax12345's user avatar
  • 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|$...
seanL's user avatar
  • 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 & ...
Anon's user avatar
  • 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-...
Anon's user avatar
  • 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} \...
Georgy Firsov's user avatar
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 ...
tur11ng's user avatar
  • 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 ...
tur11ng's user avatar
  • 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 \...
Anon's user avatar
  • 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 $...
X. G.'s user avatar
  • 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, ...
filter hash's user avatar
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 ...
xzijoq's user avatar
  • 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$, ...
xxx's user avatar
  • 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 ...
Newbie's user avatar
  • 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) ...
FearfulJoe's user avatar
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 ...
KryptoKing's user avatar

1
2 3 4 5
14