Skip to main content

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
1 answer
86 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 ...
X. G.'s user avatar
  • 424
1 vote
1 answer
298 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. ...
fgrieu's user avatar
  • 142k
1 vote
2 answers
224 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 ...
alfred's user avatar
  • 35
3 votes
0 answers
60 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 ...
telamon's user avatar
  • 131
1 vote
1 answer
74 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}...
a196884's user avatar
  • 381
-1 votes
1 answer
217 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 ...
Amor's user avatar
  • 13
0 votes
1 answer
144 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 ...
Mike's user avatar
  • 117
0 votes
1 answer
80 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 ...
phi.nm's user avatar
  • 15
2 votes
0 answers
66 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 ...
Krishna Mallick's user avatar
2 votes
0 answers
49 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 ...
Venkat Chenam's user avatar
0 votes
0 answers
156 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 ...
Mona's user avatar
  • 197
2 votes
1 answer
72 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(...
Wu Shuang's user avatar
4 votes
0 answers
190 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 ...
fgrieu's user avatar
  • 142k
6 votes
1 answer
225 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 ...
fgrieu's user avatar
  • 142k
1 vote
1 answer
45 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, ...
Mikhail Koipish's user avatar
3 votes
0 answers
86 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?
WeCanBeFriends's user avatar
1 vote
0 answers
66 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 ...
synack's user avatar
  • 123
2 votes
0 answers
72 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 ...
Daniel-耶稣活着's user avatar
2 votes
1 answer
444 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 ...
Marc Ilunga's user avatar
  • 3,338
4 votes
0 answers
149 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 ...
István András Seres's user avatar
1 vote
2 answers
5k 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 ...
learnerX's user avatar
  • 687
3 votes
1 answer
82 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_{...
Alex Ideal's user avatar
1 vote
0 answers
48 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 ...
Léo Colisson's user avatar
0 votes
2 answers
117 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-...
Kirill Tsar.'s user avatar
3 votes
1 answer
562 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 ...
securitymensch's user avatar
2 votes
1 answer
437 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 ...
securitymensch's user avatar
3 votes
0 answers
110 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 ...
Bob Semple's user avatar
1 vote
1 answer
128 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{...
Cryptomath's user avatar
2 votes
0 answers
76 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 ...
UTF-8's user avatar
  • 264
2 votes
1 answer
317 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?
votunglinh's user avatar
1 vote
0 answers
595 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 ...
CTN's user avatar
  • 11
3 votes
0 answers
1k views

Are there any hash functions that are commutative yet secure for ordered lists?

I'm looking for a hashing function that can combine random numbers together in any order yet still find the same value. But it needs to be secure against hackers. The idea is if I'm hashing together: ...
mczarnek's user avatar
  • 203
0 votes
0 answers
49 views

Simulation-based proof in a particular scenario

Suppose we have a two-party protocol in the semi-honest model, which is based on an additive homomorphic cryptosystem like Paillier.(P2 will generate the public and private key and publish the public ...
Amirhossein Adavoudi's user avatar
1 vote
0 answers
84 views

Simulation-based proof in the semi-honest model when a party is corrupted

Full paper Would you mind telling me based on the attached file, why in case 3(corrupted client B), the authors did not use the real input which is $S_B$ and instead they have generated $S'_B$? In ...
Amirhossein Adavoudi's user avatar
32 votes
3 answers
33k views

Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers

Given that much of our ECC crypto primitives provide “only” 128-bit security when defined over a 256-bit curve due to pollard-rho, is it then still safe in 2020 to consider 128-bit security safe for ...
Woodstock's user avatar
  • 1,424
2 votes
0 answers
65 views

Need help in proving of disproving security of generic partially-blind-signature construction

I have a project where I need to use a linear partially blind signature scheme. I looked at Abe-Okamoto, but I can't easily make it linear. So I looked at Okamoto-Schnorr blind signatures (here and ...
Alex Pinto's user avatar
2 votes
1 answer
88 views

Help understanding syntax used in security proof

I am looking through this paper and am trying to understand the proofs better. One of the theorems the authors are proving (Theorem 5.1) contains syntax of Adv followed by "cdh" in the superscript and ...
kansas_bulldog382's user avatar
4 votes
0 answers
525 views

Security properties of ElGamal encryption variants

I'll use Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984) as ...
fgrieu's user avatar
  • 142k
8 votes
2 answers
738 views

Is non-adaptive CPA strictly weaker than standard CPA security?

Today during a cryptography lecture an interesting question came up: Whether non-adaptive CPA security is equivalent to adaptive (FtG / LOR) CPA security. Now for a short description of what this ...
SEJPM's user avatar
  • 46.1k
2 votes
0 answers
49 views

decrypting a one-time-pad that outputs 0,1 in preknown probabilities

assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason ...
alberto123's user avatar
31 votes
2 answers
5k views

What are standard cryptographic assumptions?

I am struggling to understand what is meant by "standard cryptographic assumption". The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first ...
3nondatur's user avatar
  • 617
2 votes
1 answer
394 views

Does an information-theoretically secure hash function exist?

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)
09182736471890's user avatar
1 vote
0 answers
51 views

Computationally indistinguishably vs Perfect Indistinguishably [duplicate]

I know that perfect security means absolutely no information about the plaintext is leaked to the adversary while computational secrecy is okay with a tiny amount of leak. But, what is the difference ...
Emrah Sariboz's user avatar
1 vote
0 answers
52 views

Again on discrete gaussians over lattices [duplicate]

Define $$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$ and $$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$ Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is ...
Kirill Tsar.'s user avatar
2 votes
1 answer
329 views

The security level of double encryption

Let PKE $\Pi' = (Gen', Enc', Dec')$ and it is secure in the sense of $S'$. Let PKE $\Pi'' = (Gen'', Enc'', Dec'')$ and it is secure in the sense of $S''$. $S'$ and $S''$ may be separation which means ...
Blanco's user avatar
  • 1,622
8 votes
2 answers
2k views

Statistical closeness implies computational indistinguishability

This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness. We say that two ensembles $X_n$ and $Y_n$ are statistically close, if $$ \Delta(n) ...
Kirill Tsar.'s user avatar
2 votes
0 answers
145 views

Security of MAC-Then-Encrypt without MAC key authentication

We have the following settings in our system: TLS 1.2 using legacy cipher suite - OFB mode (using 64 bit block cipher) and trunkated CBC-MAC (32 bit). The goal is to achieve authenticated encryption ...
zma's user avatar
  • 43
-1 votes
1 answer
1k views

1/(2^n)! is negligible function?

By definition $\frac {1} {n}$, $\frac{1}{2^n}$ and $\frac{1}{n!}$ are negligible functions. I have got the function $$f(n) = \frac{1}{(2^n)!}$$ where $n$ is security parameter. I don't understand, ...
user71394's user avatar
0 votes
1 answer
889 views

How does the challenger choose the message randomly in the one-wayness security game of PKE?

I have read some papers that give the definition of one-wayness of PKE schemes. Let $\Pi = (G,E,D)$ be a PKE scheme, and the security game of OW-CPA is defined as follow: $$\mathrm{Adv}_{\Pi,\...
Blanco's user avatar
  • 1,622
1 vote
1 answer
91 views

How does the security parameter within a digital locker help prove that it unlocked correctly?

I refer to Canetti et all, "Reusable Fuzzy Extractors for Low-Entropy Distributions", available here. Paraphrasing the relevant part from §3:- The locking algorithm $lock(key,val)$ outputs ...
Paul Uszak's user avatar
  • 15.5k

1
3 4
5
6 7
14