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
8
votes
1answer
517 views

Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

Assume that $f$ is a one-way function (OWF), and let $\mathbin\|$ denote string concatenation. Consider the function $g$ defined by $g(x) = f(x) \mathbin\| f(f(x))$. It is easy to prove that $g$ is a ...
4
votes
1answer
500 views

Is AES (or DES) provably secure? What is the hardness assumption underlying these cryptosystems? [duplicate]

I have taken a course in applied Cryptography. I do not understand the hardness problem underlying AES (or DES). As in RSA is based on the RSA assumption. ElGamal is based on the hardness of ...
19
votes
1answer
3k views

What do the signature security abbreviations like EUF-CMA mean?

From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes. The most common ones are the *UF-* ...
3
votes
1answer
545 views

Are these functions pseudo random? Why or why not?

So I am stuck on this problem and have absolutely no intuition as to what the right answer is or how to prove it. Any help would be appreciated. Let $F$ be a length-preserving pseudorandom function. ...
2
votes
1answer
327 views

Why is adaptive security stronger than CCA1 security, and weaker than CCA2 security?

We know in CCA1 security, after seeing the challenge ciphertext, no more decryption oracles are allowed to the adversary. But in adaptive security, what should the adversary do? ​ Please help me ...
1
vote
0answers
132 views

Whcih one is computationally more expensive: Zero knowledge proof or cut-and-choose

As we know, in order to have multi-party protocol secure against the malicious parties, researchers usually utilise the standard techniques such as zero-knowledge proofs or cut-and-choose technique. ...
0
votes
1answer
512 views

random oracle model vs standard model vs selective model

Can someone clearly outline the main difference between each of the three security models: random oracle model standard model selective model This post What is the "Random Oracle Model" ...
4
votes
1answer
826 views

Security difference(s) between Shamir's Secret Sharing Scheme and Blakley's Secret Sharing Scheme?

We know that Blakley's scheme is less space-efficient than Shamir's and that they both work based on pretty different aspects (Shamir = polynomial-based; Blakley = hyperplane-based). Looking at how ...
-4
votes
1answer
535 views

Why does SHA512 start with “1”?

I just used this hashed = str(bin(int(hashlib.sha512(input1).hexdigest(), 16))[2:]) and then just see that the first bit is always 1 I have noticed quite an ...
1
vote
0answers
98 views

Chosen plain-text attack proof for Bethencourt CP-ABE scheme

Consider the CPA security game which consists of the following steps: Initialization Setup Phase 1 Challenge Phase 2 Guess Can someone provide the proof for this game under Bethencourt ...
7
votes
1answer
1k views

CPA-security of CTR mode

I'm self-studying Katz' book (2nd ed), and I have a small question about Theorem 3.32, which says: If $F$ is a pseudorandom permutation, then $CTR$ mode is $CPA-$secure. They present a proof there,...
0
votes
1answer
129 views

Using simulation proofs

I am formulating a simulation based proof, but I'm not sure how much power I can give the simulator. For example if a simulator needs to simulate the output of a symmetric key encryption algorithm ...
2
votes
1answer
236 views

Security proof. Adversary source of random coins.

Consider the game-based security proofs, i.e. a game played between the challenger and a PPT adversary. My question is... what is the source of random coins for the adversary? Is is valid to say ...
2
votes
0answers
272 views

Understanding hybrid arguments in detail

Assume we are given three distributions $H_{1}$, $H_{2}$ and $H_{3}$ and the following security games: $Game_{1}$: Distinguish between $H_{1}$ and $H_{3}$. $Game_{2}$: Distinguish between $H_{1}$ ...
4
votes
1answer
224 views

What is straight line black box reduction?

I understand the notion of black box reduction. But what is straight line black box reduction?
0
votes
2answers
106 views

Why should keys be hidden from an eavesdropper for a pseudorandom function?

What advantage would knowing the key used for a given pseudorandom function give over having access to an oracle for that function $F_k(\cdot)$ and the actual key $k$ which will be used? Thanks very ...
0
votes
1answer
134 views

Negative negligible functions

If f(n) is a negligible function, is -f(n) also negligible by definition? Since $$f(n) < \frac{1}{p(n)}$$ for all positive polynomials $p(n)$ and for some integer N such that $n > N$ Thus $$-f(...
1
vote
2answers
486 views

Proof by reduction clarification

If I execute a proof by reduction using a given adversary A as a subroutine to A'. How do I know that using adversary A which can solve a given hard subproblem, is the most efficient subroutine to use ...
1
vote
1answer
108 views

Computational Assumption For the extended discrete logarithm

Choose randomly $P\in G_1, (s,a \in Z_q)$. let the attackers know $a,P$ and keep $s$ as secret. Also the following is given. $$sP,(a+s)^{-1}P$$ Individually, From $sP$, trying to reveal ($s$) will ...
1
vote
0answers
116 views

Does using pseudorandom generator more than once cause security loss?

Everytime we use the generator with itself there is security loss. Even if this loss is not enough to loose all cryptographic security, there is still some small loss in security. Is there any way to ...
3
votes
1answer
162 views

Can you help me understand indistinguishably as described in the CPA security definition?

When I read the definition of the CPA indistinguishably encryption scheme, I see that the adversary can use an oracle as many times (to get as many encryptions of any messages it choose). An the end ...
9
votes
1answer
766 views

Is there a formal language to define a cryptographic protocol?

I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol ...
4
votes
1answer
150 views

Why is cryptographic model not considered formal methods?

I have just started looking at different methods for analyzing the security of cryptographic protocols. According to my reading, there are two main approaches in this area. The first approach is so-...
2
votes
1answer
97 views

How any attack on a cipher carried out? Are these practical or only theoretical?

I have been reading about successful attacks on AES and other ciphers. One such mention is here (see excerpt below): AES was published under the name Rijndael in 1998. Refereed cryptanalytic ...
8
votes
1answer
142 views

Relaxing Semi-Honest Security in Multiparty Computation

I am currently reading Lindell's tutorial on simulation-based proofs and I am trying to understand the reasoning why the security notions are they way the are. In simple words, in the case of semi-...
1
vote
0answers
445 views

Padding in hash functions

What are the consequences, in terms of security, of using a padding rule at the beginning of the message? Instead of the end? For instance, in most hash functions, we are using the following padding ...
27
votes
2answers
748 views

Uniform vs discrete Gaussian sampling in Ring learning with errors

The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
3
votes
1answer
151 views

Secure communication protocol for equality test

I'm solving a theoretical problem with two entities, each having one secret number. They need to find out whether these number equal without disclosing their number when they differ. Easy solution is ...
2
votes
0answers
74 views

Can we use a pseudorandom function in both models of a simulation based proof?

Assume in the real model a party blinds a fixed element $b$ as: $v_i=r_i\cdot b$, where $r_i$ is a output of pseudorandom function. So we give $v_i$ to a semi-honest adversary. Now we want to sketch ...
29
votes
4answers
5k views

Why does Neumann think cryptography isn't the solution?

What did Peter G. Neumann mean by: If you think cryptography is the answer to your problem, then you don't know what your problem is. (eg: quoted in the New York Times, February 20 2001)
0
votes
1answer
100 views

Independence of answers to queries sent to a random oracle

Assume we have an algorithm which asks random oracle $\mathcal{O}$ $Q$ queries $u_1, \ldots, u_Q$. All queries are unique, $u_i \neq u_j$ for $i \neq j$. Queries $u_i$ are random variables, too. What ...
1
vote
1answer
158 views

Do I need to prove this?

I am using ABE scheme that has already proven under BDHE assumption. Here is the scheme https://eprint.iacr.org/2008/290.pdf In the key generation algorithm, I want to tie the user secret key ...
1
vote
1answer
91 views

Given $ g^s, g^y , g^r, g^t, g^{st-rs}, g^{(yr+d)/t}$ , is it hard to distinguish $e(g,g)^{syr}$ from a random value?

Where $g$ is a group element in bilinear group $G$, $e(g,g)∈GT$ and $s, y, r, t, d$ are randomly chosen. I understand it is very similar to the conventional DBDH problem, but $g^t, g^{st-rs}, g^{(yr+...
5
votes
1answer
152 views

Given $g^a, Y$, is it hard to distinguish $e(g,g)^{ab}$ from a random value?

where $g$ is a group element in bilinear group $G$ $Y = M.e(g,g)^{ab}$ $M$ is a message Does anyone know the answer or suggest some material for reference?
3
votes
1answer
352 views

Is security against semi honest adversary inheritable?

I have a two party protocol, let's call it $M$. At some point, there are $k$ steps, each one involving an oblivious transfer protocol, which is known to be secure against semi honest adversaries. ...
7
votes
0answers
139 views

Replacing signer with simulator

Assume we can prove security of digital signature scheme against key-only (no message) attacks. Now we want to prove security against adaptive chosen message attack. We use random oracle model. The ...
1
vote
1answer
114 views

Randomized functions cannot increase statistical distance

In these lecture notes instructor Chris Peikert states the following lemma without a proof Let $f$ be a (randomized) function on the domain of $X$, $Y$. We have $\triangle (f(X), f(Y)) \leq \...
2
votes
1answer
83 views

Random oracles and independence

I'm reading an unpublished paper in which the author makes the following conclusions several times: Assumptions: finite probability space, $H$ is a random oracle, $X$ and $Y$ are two (not necessarily ...
3
votes
1answer
167 views

Why is the simulation required in these identity-based encryption security proofs?

In identity-based encryption papers (i.e.this) it is very difficult for me to understand security proof. I don't know why they prove assumption (BDH, BDDH) for security of their scheme. Some uses ...
2
votes
0answers
168 views

Proof of IND-q-CCA security

I have some questions about the paper Bounded CCA2-Secure Encryption (pdf). On page eight "3.2 Construction", the authors have done a black-box construction of an IND-q-CCA security schema and then ...
7
votes
0answers
305 views

Security proof in (Ciphertext-Policy) Attribute-Based Encryption

I am having hard time understanding the security proof in Attribute-Based Encryption, especially in Ciphertext-Policy Attribute-Based Encryption. To do reduction in CP-ABE scheme, how do I check that ...
4
votes
2answers
2k views

The main differences between Sketch of Proof and Full proof

My question in general is: Question 1: What are the differences between sketch of proof and full proof? In simulation-based proof, in semi-honest model, we construct a view that is computationally ...
7
votes
1answer
377 views

How simple can the PRP used in the Even-Mansour scheme be?

For example, in the question “Is there any reason not to use Single-Key EM with AES and a constant key?” it is proposed to use AES with a fixed key as the permutation in a xor-permute-xor construction....
3
votes
0answers
55 views

Incorrect answers to queries in Waters' IBE proof by Bellare and Ristenpart

In "Simulation without the artificial abort: Simplified proof and improved concrete security for Waters' IBE scheme", Bellare and Ristenpart present a new proof for Waters' IBE scheme that does not ...
5
votes
1answer
140 views

Parameterizing adversaries with security parameters

In many cryptographic games, the adversary doesn't seem to be parameterized by the security parameter.‡ Are such games equivalent to variants in which the adversary is parameterized by the security ...
0
votes
0answers
257 views

Security Proof in Fuzzy Identity Based Encryption?

Been having a great deal of difficulty understanding the use of simulators to prove security of ABE schemes so I though I would start from the first ABE paper (Fuzzy Identity Based Encryption) to try ...
3
votes
1answer
152 views

How to prove a lemma that is based on phi-hiding assumption?

Assume that the $\phi$-hiding assumption is true, i.e. that for a composite number $m$, a PPT adversary A cannot distinguish between a prime $p_0$ that divides $\phi(m)$ and another prime $p_1$ that ...
3
votes
1answer
106 views

Enhance security by combining bits of 4 different hashes

Assuming that performances do not matter, is there any real benefit in terms of security (in general) in combine hashes in this way: hash functions: ...
7
votes
1answer
2k views

how to prove our algorithm is secure against chosen plaintext attack?

I am working on a topic in cryptography where I have tried to develop an encryption scheme. How could I prove mathematically that my algorithm is secure against chosen plaintext attacks?. Will it be ...
5
votes
1answer
452 views

How many blocks can securely be encrypted with XTS

I could not find in the NIST recommendations on XTS how many blocks can securely be encrypted with XTS-AES. Through the recommendations, I've found: The length of the data unit for any instance of ...