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

4
votes
0answers
22 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
22 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
28 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 ...
3
votes
2answers
58 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
31 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
33 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
48 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 ...
2
votes
1answer
44 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 ...
2
votes
2answers
53 views

Why Generate Keys are inside game

I am studying reductions to prove security of crypto systems. Generally are used "games" for the proves. For example, the next image is extracted from the page 91 of the book Postquantum Cryptography. ...
3
votes
1answer
171 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
16 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
104 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?
2
votes
0answers
110 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 1n ...
2
votes
1answer
35 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
119 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
83 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 ...
7
votes
1answer
88 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
20 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
51 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
77 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
53 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 ...
5
votes
1answer
142 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 ...
4
votes
0answers
57 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 ...
3
votes
1answer
114 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
92 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 ...
13
votes
1answer
158 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 ...
1
vote
1answer
35 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 ...
4
votes
0answers
59 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
39 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
64 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
86 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
35 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
84 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: ...
1
vote
1answer
140 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 ...
1
vote
2answers
79 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
128 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 ...
0
votes
0answers
66 views

CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm Enc ...
1
vote
1answer
182 views

Simulation Based Proof: What Can / Can not Simulator Do?

I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance: ...
2
votes
2answers
51 views

Simulator in Private Outsourced Computation over Outsourced Datasets

Please, consider two honest parties $A$ and $B$ outsourced their private data to a malicious server $S$. So the parties store their data in the server. Then at a later point in time they want to ask ...
3
votes
1answer
325 views

How to prove that a function is not pseudorandom?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one: Let G(k) be a PRG with ...
3
votes
1answer
84 views

What does “simulator” and “interactive” mean in a cryptographic credential system's definition of security?

Definition 1 on Page 7 of “An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation” by Camenisch and Lysyanskaya, uses the term “simulator” in defining the ...
1
vote
2answers
193 views

Simulation based proofs: Simple examples

I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their ...
1
vote
1answer
64 views

Does anyone still use BAN or GNY logic in practice?

I want to implement a simple protocol, and I'd like to verify it through BAN or GNY logic. I would assume that if these logics are still used that there would be some programs available that would ...
7
votes
1answer
421 views

Easy explanation of “IND-” security notions?

There are many schemes that can advertise themselves with certain security notions, usually IND-CPA or IND-CCA2, for example plain ElGamal has IND-CPA security but doesn't provide IND-CCA security. ...
3
votes
1answer
123 views

Simulation aborted because the adversary doesn't use the random oracle

I'm trying to construct a proof for an encryption scheme in the Random Oracle model. This encryption scheme is like a PKE scheme but with an additional function that kind of "alters" ciphertexts ...
4
votes
1answer
71 views

On Proving That a Primitive Does Not Exist

In the paper of Hsiao and Reyzin, Section $1.4$: Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $Q$ does not exist Since the statement is about trying ...
1
vote
2answers
51 views

Definition of indistinguishable schemes

Let $\mathsf{Exp}_{A,\Pi}(\lambda)$ be some indistinguishability experiment that finally outputs 1 if A outputs $b'$ that satisfies $b' = b$, otherwise 0. Then the textbooks often define the security ...
7
votes
1answer
155 views

Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation

Recently, Fujisaki and Okamoto provided a revised version of the Fujisaki-Okamoto transformation [1], a generic transformation for achieving IND-CCA2 security in the Random Oracle model. This new ...
1
vote
3answers
86 views

Is it possible to encrypt a message's destination as well as its content?

I have imagined a way to break through any kind of censorship but since I don't have enough professional knowledge of cryptography I don't know whether it is feasible or not. If there is a method ...