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
1
vote
0answers
16 views

Technological based solution needed for a real world problem of transferring a physical object between two untrusted parties [closed]

Suppose I have a physical object A. Another person also has some rights over the object A. After some litigations, a schedule has been made under which object A will be passed for some time to the ...
0
votes
0answers
17 views

Formal Verification using ProVerif

I want to implement a table with variable values in Proverif but I have no pattern. Can you help me? Also how do I model attacks on tables?
5
votes
2answers
214 views

Can a PRF distiguisher invoke the function's algorithm?

The definition of a function $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $\mathcal F$, and there is no P.P.T....
0
votes
0answers
29 views

Is ORAM security definition adaptive?

Based on the "obliviousness" definition of the access pattern of the ORAM: Given the RAM, after a sequence of read/write operations, the physical addresses accessed will be computationally ...
1
vote
2answers
190 views

Which of those functions are PRFs?

Assume that $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$ is PRF. Examine if the following functions are PRFs: $$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), ...
1
vote
1answer
46 views

Using Optimal Prime Field in ECC

"Optimal Prime Field is a family of 'low-weight' prime fields that allow for efficient software implementation of all operations requiring a modular reduction, in particular the field-...
1
vote
1answer
49 views

Security proof, Sequence of games

I hope someone can help me with the sequence of games security proof for protocols. Here are my questions: What is the aim of each individual game? i.e. why can't we do this in one indistinguishable ...
0
votes
0answers
18 views

Extractability of random oracle in simulation-based proof

I am working on the simulation-based proof, where Random Oracle (RO) is used to extract malicious parties' input. In particular, the RO considered in the proof has a small range (whose size is ...
0
votes
0answers
33 views

Security Proof, Sequence of games and birthday paradox

The sequence of games security proof approach is very confusing. For example, I am trying to understand it in the following paper https://www.dropbox.com/s/dhsgsognxviwacv/Provably%20Secure%...
3
votes
0answers
46 views

Boneh DDH Paper - Sampling Integers in Random Reduction

I've been reading Dan Boneh's DDH paper, in particular section 3.1 which covers DDH randomized reduction. The first two sentences of theorem 3.1 state: Let $\Bbb G = \{G_p\}$ be a family of finite ...
0
votes
0answers
31 views

What is a quantifier in game-based definitions?

I'd like to know what are quantifiers in game-based security definitions (in cryptography) Some relevant examples and sources are also much appreciated. Edit: for example, in a formal definition, we ...
0
votes
0answers
23 views

A combination of game-based and simulation definitions to analyse a protocol security

Consider the case we want to design a crypto protocol: $P_1$, say for verifiable computation. We define the protocol by designing a game and prove its security. Consider that we want to design another ...
1
vote
1answer
28 views

Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known?

Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any ...
1
vote
1answer
71 views

Security of block cipher PRP(k⊕m)⊕k

Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions. ...
1
vote
2answers
108 views

Proving security of $\Pi' = E_k(E_k(m))$ knowing $\Pi = E_k(m)$ is secure

I recently started studying cryptography but I am not sure I quite understand the concept of proof by reduction. Question I am trying to solve is as follow: Suppose $\Pi$ is a symmetric encryption ...
3
votes
0answers
51 views

trust-less blind execution environment (thought experiment)

I apologize for the theoretical nature of this question, but It has cost me a lot of sleep over the past months. Querying my immediate peers has so far failed to produce results. I assume this ...
1
vote
1answer
30 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
0
votes
0answers
14 views

Integrated Signatures and Encryption Scheme

Suppose we have a scheme ISE that combines $n$ signature schemes and one encryption scheme, where the same keys are used. It is composed of the following algorithms: Setup, KeyGen, $Sign_1,...,Sign_n, ...
0
votes
0answers
35 views

Security analysis of encrypting a matrix after homomorphic encryption by the random mask

Problem Definition Alice has two private matrices $M_A$ ($N*M$), $M_a$, where $M_a$ is the binary matrix of $M_A$ Bob has a private matrix $M_B$($N*M$) Alice and Bob are semi-honest server and ...
0
votes
0answers
7 views

Unable to understand coin variable used in hash(H2)function querie

I have some hash function queries representations, which I find it hard to understand. I have searched a lot but didn't found anything helpful. Please help me understand the hash(H2) function query I ...
0
votes
0answers
38 views

Short one-time pad security

I am somewhat new to Cryptography and I'm struggling with this proof I came across in my Intro to Cryptography course. I understand the proof of security for a one-time pad: Pr[M = m | C = c] = Pr[M = ...
-2
votes
1answer
112 views

Does the following protocol of secure a matrix satisfy one-time-pad?

Problem Definition: Alice wants to send a matrix $MR_A$ which encrypts its original private matrix $M_A$ ($M\times N$ size, all elements in $M_A$ is in {0,1,2,3,4,5}) to Bob without letting Bob knows ...
0
votes
1answer
58 views

On the Acceptability of a Naive Pseudo Random Number Generator

My question is probably both philosophical and technical. Background I was developing a CSPRNG, and I needed to shuffle the bits in one step in the middle of the algorithm - any naive shuffle would ...
0
votes
1answer
65 views

May an adversary be fooled by a random-looking input that in reality is fixed?

I want to prove the EUF-CMA-security of a signature scheme. It is a variation on an established scheme, therefore I would ideally like to reduce the new-scheme-security to the old-scheme-security. the ...
2
votes
0answers
49 views

Secure Protocol

How to show there is no secure protocol to compute OR? I need to know the mathematical proof of this statement. I am understanding this statement using the matrix representation of $f(x,y)$ but unable ...
0
votes
0answers
12 views

Why is Dolev Yao a local Inference System but blind signatures aren't?

I am currently working on this tutorial: https://www.infsec.cs.uni-saarland.de/wp-content/uploads/sites/2/2017/04/CK-fntpl-14.pdf However, I am struggling with the term "local inference system&...
2
votes
0answers
33 views

How are security proofs performed for Certificateless PEKS schemes?

I have been studying several CLPEKS (CertificateLess Public-key Encryption scheme with Keyword Search) schemes and I understand the security assumptions and the several types of security models used ...
0
votes
0answers
72 views

Semantic Security in Formal Security Proofs

I have a trivial question, and I hope someone can help me. I am reading several papers on formal security proofs based on the indistinguishably game. Specifically, the adversary is challenged in an ...
2
votes
1answer
62 views

Difficulty to find the pre-images of a pair of hash result such that given $a,b$, $H(x_1)=aH(x_2)+b$?

Suppose given fix values $a,b$, how difficult to find a pair of sha256 pre-images $x_1,x_2$ such that $H(x_2)=aH(x_1)+b$? How difficult to find 4 hash pre-images $x_1,x_2,x_3,x_4$ such that $\dfrac{H(...
3
votes
0answers
56 views

Multi-users RSA problem

Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user. What's the state of the art in ...
5
votes
1answer
134 views

“Reduced to” vs “deduced from”

Assume it's proven: "Security of protocol $\Pi$ can be deduced from hardness of problem $P$". Is it correct to state: "Security of protocol $\Pi$ can be reduced to (hardness of) problem $P$" ? My ...
1
vote
1answer
35 views

Assumption of difficulty of attack in restricted short time

As well known, different assumptions of difficulty of some problems are used in provable security. E.g., if some crypto-scheme is breakable only in case the attacker finds preimages for hash function, ...
3
votes
0answers
74 views

Are there only two ways to prove a cryptographic protocol is secure?

If I want to prove my protocol is secure, can I just use a game based approach and/or a simulator approach? Or are there other common approaches?
1
vote
0answers
42 views

What is the underlying hard problem in the reduction of game-based proofs?

I am confused by how game-based proofs fit in the provable security paradigm. I understand reductions in the style of proving secrecy of RSA reducing it to integer factorization. However, when proving ...
2
votes
0answers
32 views

Balanced Feistel networks: Are there any lower bounds on the computational complexity of breaking a $k$-round Feistel cipher?

This paper by Patarin presents an attack (section 9) on balanced Feistel networks with $k$ rounds, where the input is a bit-string is of length $2n$. (Since it is balanced, this means each PRF takes ...
0
votes
1answer
71 views

MAC security game

In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that one can modify SUF-CMA game by removing verify oracle access to the adversary. Therefore, the two versions are ...
4
votes
0answers
107 views

The security of blind RSA signatures with modular exponentiation as padding

It is known that (blind) RSA signature implementations should apply some sort of padding to messages before signing or blinding them. Does blind RSA signature with modular exponentiation as a padding ...
1
vote
2answers
711 views

Using RSA encryption to encrypt large files

The following post discusses the use of RSA for file encryption: https://medium.com/@ismailakkila/black-hat-python-encrypt-and-decrypt-with-rsa-cryptography-bd6df84d65bc The file encrypted is a JPEG ...
3
votes
1answer
59 views

Time cost of security reduction

The following theorem is the description of one-more unforgeability in the paper lattice based blind signatures. I want to ask if the time $t^{'}$ is an exponential time since the $q_{H}$ and $q_{...
1
vote
0answers
35 views

Abstract Cryptography: why local simulators?

In the paper that introduced Abstract Crypto [MauRen11], the Theorem 2 page 15 states that, basically, if there exists some local simulators that can be pluged on a resource $S$ such that this new ...
0
votes
2answers
57 views

LOR implies unpredictability?

It should be true that classical LOR(Left or Right)-indistinguishability of some mode of operation implies unpredictability. However I've got stuck with the proof of this fact. LOR-...
0
votes
0answers
23 views

Related-key impossible differential search on SIMECK via MILP?

What should be the objective function , constraints and bounds for the model for Related-key impossible differential search on simeck cipher using mixed integer linear programming (MILP)?
3
votes
1answer
108 views

Proof by reduction definition in “Serious Cryptography”: Cipher reduced to hardness problem or other way around?

In Serious Cryptography by Jean-Philippe Aumasson on p. 46, paragraph "Provable Security", it says: Provable security is about proving that breaking your crypto scheme is at least as hard as ...
1
vote
0answers
55 views

Proofs that NM-CPA implies IND-Cpa and $\text{IND-CCA} \leftrightarrow \text{NM-CCA}$

I am looking for a proof for the following two claims from "Serious Cryptography" by Aumasson. NM-CPA implies IND-CPA. [...] IND-CCA and NM-CCA are equivalent notions that imply the presence of the ...
3
votes
0answers
64 views

Provably secure way of expanding permutations

Gimli is a 384-bit permutation that makes use of an internal 96-bit permutation which works on columns. Every 4 rounds starting from the 1st a "small swap" is performed and every 4 rounds ...
1
vote
0answers
37 views

Regarding security of blind signature schemes

I'm new to blind signatures, trying to understand security notions of it: blindness and one-more unforgeability. I found out that in the security game for blindness property, the adversary $\mathcal{...
0
votes
0answers
42 views

Understanding a security proof

I am reading the paper "RingCT 3.0 for Blockchain Confidential Transaction: Shorter Size and Stronger Security" (https://eprint.iacr.org/2019/508.pdf), an improvement to Ring Confidential Transactions....
2
votes
0answers
51 views

Why does the random oracle receive much more criticism than the ideal cipher?

The random oracle model seems to be criticized a lot as lacking practical relevance, making wrong predictions, being programmable, etc. However, I have never heard such criticism about the ideal ...
2
votes
1answer
103 views

Is the EdDSA signature scheme provable security?

The EdDSA signature scheme is a deterministic scheme. So could it be proven provable security in Random oracle model?
1
vote
0answers
105 views

Game-based proofs and semantic security

After reading this question, I understood that "game-based" and "simulation-based" have to do with the way that security properties are postulated. In particular, IND-CPA is a canonical example of ...

1
2 3 4 5
11