# 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.

504 questions
Filter by
Sorted by
Tagged with
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 ...
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?
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....
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 ...
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), ...
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-...
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 ...
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 ...
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%...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
30 views

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 ...
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 ...
38 views

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 = ...
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 ...
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 ...
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 ...
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 ...
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&...
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 ...
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 ...
62 views

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 ...
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-...
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)?
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 ...
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 ...
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 ...
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{...
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....
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 ...