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
votes
0answers
28 views

what are the kind of mathematical proofs that i need to be familiarized with to understand (or do) cryptography? [on hold]

I know reductions are highly used to show that encryption schemes are secure under certain conditions, but i don´t know what other math proofs are needed. PD: English is not my native language so ...
0
votes
0answers
36 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
100 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
60 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+...
2
votes
1answer
37 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? Many Thanks
4
votes
0answers
60 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
34 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 \...
-1
votes
0answers
24 views

Assumption for security proof in the given scheme (identity based encryption)

In identity-based encryption schemes,mostly,assumption is used to prove the scheme. Using DBDH assumption,assume $T=aP,T1=bP$ and Given $[T,T1,rP,k]$ where $k \in e(T,T1)^{r}$ or not.Decide if $k=e(T,...
2
votes
1answer
55 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
71 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
44 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 ...
4
votes
0answers
42 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
260 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 ...
5
votes
1answer
46 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
25 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 ...
2
votes
0answers
24 views

What is bounded-retrieval model?

What is bounded-retrieval model in cryptography? How is it related (or apply) to leakage-resilient cryptography?
3
votes
1answer
67 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
69 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 ...
2
votes
1answer
62 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 ...
4
votes
1answer
72 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: ...
6
votes
1answer
971 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 ...
5
votes
1answer
79 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 ...
3
votes
1answer
62 views

How can I convert a mathematical formula into a logical formula?

I'm using cryptominisat2.9.6 to solve equation set (including more than 160 equations). There are 160 variables in total, which are as follows: $x_0,x_1,x_2,...,x_{78},x_{79},y_0,y_1,y_2,..,y_{78},y_{...
0
votes
1answer
109 views

How are security proofs done in ABE Schemes?

I have been studying several ABE schemes and I understand the security assumptions and the several types of security models used for the security game between the Challenger and the Adversary. What ...
1
vote
0answers
133 views

Simulation-Based Proof: When a Secret Key is Involved

Assume we have a protocol in which a party receives an encrypted random polynomial. The polynomial is encrypted using his public key. We want to construct a simulator for this party (so this party ...
2
votes
1answer
315 views

An example of of an information theoretically secure protocol that is not cryptographically secure

Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? ...
8
votes
3answers
173 views

How to prove the security of block ciphers

I see very often proofs of security for asymmetric crypto algorithms, for instance, using reductions to known hard problems, or game based proofs... In the field of protocols (like authentication) it ...
12
votes
2answers
111 views

Practical differences between circuits and turing machines for cryptography

In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more ...
0
votes
0answers
31 views

How is Extended Euclidean Algorithm related to Approximate-GCD problem?

I had a doubt regarding the connection between the Extended Euclidean Algorithm and the Approximate-GCD problem. Are there any relations? i.e., the hardness of A-GCD is derived from EEA. Is there any ...
3
votes
1answer
83 views

How to prove hardness of approximate-GCD problem?

I am trying to prove the security of my system using the hardness assumption of the approximate-GCD problem using contradiction, i.e. If the attacker is able to break in our scheme, then attacker ...
2
votes
1answer
188 views

What is the meaning of IND-CCA secure under standard model? [duplicate]

I notice that in many research papers (viz. "Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption" by Cramer and Shoup) the authors showed that their ...
1
vote
0answers
22 views

Should we use exponent 3 in RSA-OAEP?

As I understand it the proof that RSA-OAEP is secure in the random oracle model is much tighter for exponent 3. Does that mean that exponent 3 should be chosen?
15
votes
2answers
255 views

Formal verification in cryptography

I have seen in some places that people use formal verification and/or computer-aided verification for cryptography (tools like ProVerif, CryptoVerif, etc.). How do these approaches work?
0
votes
0answers
31 views

Is original DSA a TEGTSS-I scheme?

Brickell et al. define TEGTSS-I scheme in paper "Design validations for discrete logarithm based signature schemes" In this paper original DSA is generalized as DSA-I variant where $r = g^k \bmod p \...
2
votes
1answer
62 views

A confusion on the proof of Yao's theorem (Yao 82)

I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim: My question is: How can we say "without loss of generality" here? Since $H^...
11
votes
1answer
154 views

Explanation and proof of a well-know probabilistic lemma

Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma: Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \...
1
vote
0answers
18 views

Finding missing probabilities for formal proofs

In formal proofs, you often need to use probabilities to show that the Advantage of an algorithm is negligible. In proofs by contradiction, these probabilities are often tied to probabilities of other,...
2
votes
2answers
116 views

Shannon theorem of perfect secrecy

From the class: Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability). Proof: ...
5
votes
1answer
81 views

Does concatenation of two pair computational indistinguishable distributions still indistinguishable?

Let $X,X',Y,Y'$ be some distribution ensembles such that $X\sim X'$ and $Y\sim Y'$, where $\sim$ means computational indistinguishable. Define $(X,Y)$ be the distribution ensemble over $\{0,1\}^{2n}$ ...
3
votes
1answer
60 views

Selective and existential unforgability of signature schemes

I understand that one can define EUF-CMA of a signature scheme is terms of a game where the adversary is allowed to query signatures on messages of his choosing, and at the end of the game he must ...
2
votes
1answer
69 views

Are the following schemes based on a pseudo-random permutation secure?

I am currently working on the following task: Let F be a pseudorandom permutation. Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses ...
3
votes
1answer
77 views

How can I formally verify fuzzy commitment scheme based security protocol?

I am currently working on designing a security protocol which involves usage of fuzzy commitment schemes, for. eg Reed-Solomon codes which allows us to tolerate a certain level of error. I was ...
5
votes
1answer
516 views

One-Way property of Random Oracle

I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but ...
7
votes
4answers
206 views

Why haven't we proven many things computationally secure yet?

Brute Force is infeasible for just about every algorithm we use today. Yet, attacks are feasible. This is because weaknesses keep coming up in our algorithms. Why? We have proven lower bounds for ...
1
vote
2answers
93 views

How to show that this modification of CBC-MAC is insecure?

I'm working on some cryptography problems, found this and I'm not sure how to solve it: Modify CBC-MAC so that all blocks $t_1,\dots,t_l$ are output rather than just $t_l$ and prove it is not ...
2
votes
1answer
150 views

Difference left-or-right CPA security, IND-CPA security

I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to ...
1
vote
0answers
65 views

Is $E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ PRF?

$E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ and F is PRF which maps $\left \{0,1 \right \}^n \times \left \{0,1 \right \}^n $ to $\left \{0,1 \right \}^n$. Let two messages $m_{0} = 0^l $ and $m_{1} ...
3
votes
1answer
54 views

Difference between Constructor and Destructor terms

I was thinking that in the formal model (or symbolic model?) the destructor terms were used to model processes that could abort generating some errors or something like that. But then, I realized that ...
1
vote
2answers
83 views

Is a PRF applied to a secure MAC also a secure MAC?

Suppose I apply a PRF to a secure MAC. Do I still have a secure MAC?
3
votes
1answer
52 views

About the necessity simulators set adversary random-tape

In the ideal/real proof paradigm we sometimes find simulators with the capacity of set adversary random tape. My question: when do we have to consider the necessity of simulators set adversary random-...