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
41 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 ...
1
vote
1answer
113 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 ...
0
votes
0answers
37 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
61 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
38 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 ...
8
votes
1answer
303 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 ...
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 \...
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-...
-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
72 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 ...
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 ...
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)] \...
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, ...
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 ...
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 ...
4
votes
1answer
778 views

What is adversary's advantage in cryptography and why we use it?

The definition of adversary's advantage seems a bit odd for me and I am wondering why do we use it to measure the power of an adversary rather than just use the probability of a PPT adversary ...
4
votes
2answers
261 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....
2
votes
1answer
285 views

Security proof in pairing based cryptography

Let : $G_{0}$ and $G_{1}$ be two multiplicative cyclic groups of prime order $p$, $g$ be a generator of $G_{0}$ and $e$ be a bilinear map, $e : G_0 \times G_0 → G_1$ and let $𝐶_{1} = 𝑔^{𝛽𝑠_{1}...
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 ...
15
votes
2answers
256 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?
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
4
votes
0answers
111 views

Efficient proof of knowledge using Wegman-Carter hash

A verifier wants to ensure, with only little exchange of data with other systems, that a large block of data $M$ that the verifier holds is also available to some other system(s). It is not an ...
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 ...
3
votes
0answers
45 views

What is the restriction on $k$, for the $k$th composite residuosity problem to be hard?

The paper “Residuosity Problem and Its Applications to Cryptography” considers the exponent to be an odd integer. When $k = 2$, it is called the quadratic residuosity problem (mod $n$, where $n$ is ...
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_{...
1
vote
0answers
134 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
316 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
174 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 ...
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?
12
votes
2answers
112 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 ...
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 ...
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^...
5
votes
4answers
1k views

Security proofs for CBC mode

I'm looking for different approaches to proofs for the security of CBC mode encryption. What are the best sources of information about this subject?
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 ...
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 ...
12
votes
1answer
1k 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. ...
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 ...
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?