The 2024 Developer Survey results are live! See the results

# 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.

687 questions
Filter by
Sorted by
Tagged with
54 views

### Deterministic vs probabilistic adversaries in a proof-of-knowledge context

In several security games, it is safe to replace probabilistic polynomial-time adversaries with deterministic ones without reducing the adversarial advantage. The relevant argument can be found here. ...
129 views

• 11
82 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 ...
• 99
72 views

• 101
1 vote
176 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 ...
• 467
344 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 ...
• 844
1 vote
56 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$ ...
• 546
1 vote
145 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 ...
52 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
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,547
160 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 ...
• 105
1 vote
74 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
168 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, ...
120 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
109 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 ...
• 63
90 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) ...
• 392
1 vote
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
78 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
50 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?
• 137
245 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
39 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 ...
• 137
1 vote
50 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 ...
• 137
195 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
208 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 ...
263 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
194 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 ...
124 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: ...
300 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 ...
106 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 ...
• 327