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.

learn more… | top users | synonyms

1
vote
1answer
38 views

Create a potential input for sha-256 hash given a substring of input?

Let's say I'm given a specific SHA-256 hash. Further assume that the SHA-256 input, that yielded this hash contained a known sub-string. Is there a way to find the input (containing the specific ...
5
votes
1answer
105 views

Is the concept of provably secure hash the same as entropy smoothing hash functions?

Is the concept of provably secure hash the same as entropy smoothing hash functions? In the tutorial Sequences of Games: A Tool for Taming Complexity in Security Proofs V. Shoup shows us a proof of ...
1
vote
0answers
28 views

Is Shamir's Secret Sharing Scheme insecure for larger field? [duplicate]

According to wikipedia, if you are using shamir's secret sharing scheme with a field of order $p$, "High values of $p$ are risky because Eve knows that the chance for $f(x)\pmod{p}=f(x)$ increases ...
0
votes
0answers
29 views

Permuted Hash Table

Suppose we have a hash table, $HT$, consisting of $100$ bins.The hash table uses a hash function $H$ that is public. We all know that given value $a$ we can compute the address in the hash by $H(a)=j$...
4
votes
2answers
75 views

How to generate a random number so server cannot cheat?

Here is the protocol: Bunch of players connected to server. Server creates nonce and hashes it - send hash to clients as bit commitment. Clients make nonces and send hashes to server as their bit ...
1
vote
1answer
61 views

Why Boneh-Franklin BasicIdent IBE is not chosen-ciphertext secure? Why use random oracle?

I don't know why BasicIdent is not chosen-ciphertext secure. If there are anybody who knows well, please explain it to me with example. Moreover, I don't know random oracle and its usage for security ...
3
votes
1answer
56 views

Is it okay to send an encrypted key using XSalsa20-Poly1305, and send subsequent messages using ChaCha20-Poly1305?

I am looking at a cryptographic protocol in a somewhat unusual environment: the communicating parties can share arbitrarily long secret keys over a secure channel. If forward secrecy is not required, ...
3
votes
0answers
70 views

LR-Oracle Experiment in Lindell and Katz

In reference to the LR-Oracle experiment in “Introduction to Modern Cryptography” (2nd edition) by Lindell & Katz, Definition 3.23 states a scheme $\pi = (Gen,Enc_K,Dec_K)$ is CPA secure for ...
1
vote
1answer
49 views

What does this advantage statement signify?

In many Attribute Based Encryption papers I see this line... The advantage of an adversary A in this game is defined as Pr[b' = b] − 1/2. Can someone explain what it means to me? I assume it means ...
2
votes
1answer
74 views

Proven secure scheme under random oracle

Currently I am trying to understand random oracle model in order to make a small presentation about it but I seem to be very confused about it. Since it's an hypothetical model without a real life ...
8
votes
2answers
134 views

Proof that perfect privacy implies that the number of keys is at least the number of messages

I was reading a proof to the statement: Perfect privacy implies that $|K| = |M|$ where I am pretty sure that $K$ is the set of keys and $M$ is the set of messages. The proof is the following, ...
3
votes
2answers
78 views

Why is it allowed to Generate Keys inside the game?

I am studying reductions to prove security of crypto systems. Generally "games" are used for the proofs. For example, the next image was extracted from the page 91 of the book Post-Quantum ...
3
votes
1answer
267 views

Construct IND-CPA secure encryption scheme by combining two given schemes

I have two encryption schemes $\Pi_0, \Pi_1$, at least one of them is IND-CPA secure but I don't know which one. The task is to construct a scheme $\Pi$ that is guaranteed to be CPA secure and to ...
0
votes
0answers
20 views

HMQV and MQV group representation attack

Currently reading Krawczyk's HMQV paper https://eprint.iacr.org/2005/176 and trying to follow what he says about the group respetnation attack on MQV: It says that for any group of prime order $q$, ...
6
votes
1answer
145 views

What is the difference between RCCA and CCA2?

Well, I know it's easy to tell CCA1 from CCA2, but I failed to find the difference between RCCA and CCA2. What is the difference?
3
votes
1answer
177 views

Provable security of cryptographic hash functions

I am working on the following exercise question: Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)). Gen : On input $1^...
2
votes
1answer
53 views

Generalization of the DL-assumption in bilinear group pair

When thinking about a pairing-based cryptographic scheme, I encountered the following problem. Let $e \colon G_1, G_2 \to G_T$ be a Type 3 pairing. Then: Given $P, zP \in G_1$ and $Q, zQ \in G_2$, ...
0
votes
2answers
157 views

Random Coin Flip

Quoting an old question: Consider the following protocol for two parties A and B to flip a fair coin (more complicated versions of this might be used for Internet gambling): A trusted ...
3
votes
0answers
86 views

Brute force attack multiple stream cipher

Assume that a scheme used to secure a specific system $Π=(Gen,Enc,Dec)$ which is thought have indistinguishable multiple encryption in the presence of an eavesdropper. For any adversary $A$ that can ...
8
votes
1answer
332 views

Simulation-based proofs and universal composability proofs

I recently read Ran Canetti's famous UC paper but I'm still trying to wrap my head around the concepts. I think this answer has me confused a bit, particularly where it says The stand-alone ...
1
vote
0answers
22 views

Proving for a single input vs several inputs. Is there any difference?

I am working on a new protocol for pattern matching. While defining the ideal functionality, it is possible to say: Alice sends $p$ and Bob sends $T$ to the ideal functionality. i.e. searching for ...
1
vote
2answers
65 views

Can several run of a semi-honest protocol be used to infer malicious security?

In the ideal world, $A$ sends several inputs $x_1,...,x_\lambda$ to the functionality and $B$ sends input $y$. Functionality sends $f(x_1,y),...,f(x_\lambda,y)$ to $A$ and nothing to $B$. Suppose ...
2
votes
1answer
88 views

What is the difference between “securely realizes” and “securely implements”?

In some security proofs it is stated that "a protocol securely realizes an ideal functionality" while in some others "a protocol securely implements an ideal functionality". Is there a meaningful ...
5
votes
1answer
58 views

Is it possible for a simulator to always abort?

In this paper of J. Baron, et al. (PDF), simulator always aborts the ideal functionality before client outputs its pattern-matching result obtained from the ideal functionality. (See bottom of page 30,...
6
votes
1answer
180 views

Why is only one oracle + challenge-response phase sufficient for IND-CPA security?

The CRYPTUTOR wiki from UIUC uses the following definition of the IND-CPA game: We (privately) choose a key K according to the key generation algorithm: K $\gets \mathsf{KeyGen}$. We (...
9
votes
1answer
306 views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...
5
votes
1answer
248 views

Why is “semantically secure” important for cryptosystems?

The first question: what is the exact definition of semantically secure? Basically, a cryptosystem is semantically secure if given the public key and the ciphertext, an adversary cannot learn any ...
5
votes
1answer
104 views

Difference between oracle behavior and real execution

Suppose that there is a place in a security proof where the behavior of an oracle differs from the corresponding real execution (for example, the decryption oracle rejects certain types of ciphertexts ...
14
votes
1answer
199 views

How is “post-quantum security” proven/shown?

Due to growing concerns over the threat of quantum computing to asymmetric cryptography (RSA, ECC, etc), a number of "quantum resistant" replacements have been proposed (SPHINCS, McBits, and many more)...
1
vote
1answer
37 views

Deriving a Set of Seeds from a Seed

I need a set of seeds $S=\{s_1,..., s_n\}$, for pseudo-random function where seed $s_i$ is used to generate a set of pseudo-random values. Obviously I need to be able to regenerate the sets of pseudo-...
6
votes
1answer
113 views

Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-...
4
votes
0answers
75 views

What level of security is provided when a Feistel Cipher is used as a round function of another Feistel Cipher?

Recently, I was reading: Are there any specific requirements for the function F in a Feistel cipher?, and the answer posted mentions a Feistel Cipher named Turtle, which uses a four-round Feistal ...
2
votes
1answer
41 views

Proving the security of a one-way function with partially known input

Let's say we have a construction like in this question: We have a OWF $h(.)$, a secret salt TXT, and a counter starting at 1, and we compute ...
0
votes
0answers
81 views

Perfect Secrecy of AES file Encryption

Why does AES file encryption not ensure perfect secrecy? I understand that $\Pr[E(K,M_1)=C_1] = \Pr[E(K,M_2)=C_2]$ given $M1\neq M2$ holds for perfect secrecy of a scheme. However, this seems to hold ...
1
vote
1answer
92 views

How can IND-CPA encryption be identity revealing?

This is problem 10 of Chapter 4 "Symmetric Encryption" (pdf) from Lecture notes by Bellare and Rogaway: An IND-CPA secure encryption scheme might not conceal identities, in the following sense: ...
1
vote
1answer
39 views

Do random oracles are called even by honest users in the PAK protocol [BMK00]?

In the full-length proof of PAK scheme, the authors made extensive use of random oracles to extract (guessed) password from the messages generated by the real world adversary for the ideal world ...
2
votes
2answers
46 views

(Uniformly) Random Value when an element is picked with $\frac{1}{p-1}- \frac{1}{(p-1)^2}\ $ probability

Let's $\mathbb{F}_p$ be a finite field where $p$ is a large prime number(e.g. 256-bit) I know if the probability that an element picked from the field is $\frac{1}{p-1}$ we say the element is picked ...
-1
votes
1answer
87 views

How To prove Any Change to $v=a\cdot y+b$ maks $y=(a)^{−1}\cdot (v−b)$ Uni. random value [closed]

This question is related to data integrity. Let a finite field be $\mathbb{F}_p$, where $p$ is a prime number. I have a fixed value $y$ and two uniformly random values $a$ and $b$. Hypothesis: $a,...
1
vote
1answer
172 views

Proving security of TLS handshake with ProVerif

Background For my dissertation I am working on an application protocol for which I require a TLS session. I am looking to achieve Perfect Forward Secrecy, which means I have selected ephemeral Diffie-...
1
vote
2answers
85 views

Indistinguishability game hop

I am trying to prove that changing an input in a security game from a randomly permuted set to a set that is permuted using a pseudorandom permutation (PRP) results in a negligible distinguishing ...
2
votes
1answer
187 views

Simulation Based Proof: How the Corrupted Party's Input is Given To Simulator

Imagine we have a 3-party protocol, including client $A$,client $B$ and a server. In this protocol client $B$ encrypts its input under its public key and sends it to the server. The server performs ...