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

LOR implies unpredictability?

It should be true that classical LOR-indistinguishability of some mode of operation implies unpredictability. However I've got stuck with the proof of this fact. LOR-indistinguishability of some mode ...
0
votes
0answers
19 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)?
1
vote
1answer
46 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
15 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 ...
2
votes
0answers
39 views

Provably secure way of expanding permutations

Gimli is a 384-bit permutation which 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 starting ...
1
vote
0answers
31 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
37 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
48 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
72 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
51 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
vote
0answers
51 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: ...
0
votes
0answers
31 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 ...
1
vote
0answers
26 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 ...
20
votes
3answers
8k 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 ...
2
votes
0answers
42 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 ...
0
votes
0answers
23 views

How to intuitively realize the Diverse Group System in the Hash Proof System(HPS)?

In the paper Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption by Cramer & Shoup, projective hash family derived from group system can be easily ...
2
votes
1answer
64 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 ...
4
votes
0answers
76 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 ...
6
votes
2answers
108 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 ...
2
votes
0answers
36 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 ...
27
votes
2answers
3k 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 ...
1
vote
1answer
98 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.)
1
vote
0answers
22 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 ...
1
vote
0answers
28 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 ...
2
votes
1answer
83 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 ...
6
votes
2answers
469 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) ...
2
votes
0answers
76 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 ...
-1
votes
1answer
97 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, ...
0
votes
1answer
171 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,\...
1
vote
1answer
42 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 ...
-2
votes
1answer
102 views

On the security definitions [duplicate]

What are the differences between: perfect security information-theoretic security semantic security indistinguishability Are there any other definitions which are closely related? Do these security ...
3
votes
0answers
42 views

Are there any more ways to validate a security proof except peer review?

Are there any ways better than peer review to validate a security proof? Are there any ways to make your security proof easier to validate; using a simulator based proof instead of a game based proof? ...
0
votes
0answers
63 views

Do simulator based proofs still rely on the random oracle model?

I have seen many game based proofs using the random oracle model (ROM), do simulator based proofs require it? Is it possible to do a simulator based proof for every game based proof? For context: ...
1
vote
0answers
19 views

Shamir Secret Sharing: Using $a_0 \ldots a_k$ to store secret? [duplicate]

Let's assume I have a truly random secret $s$ that is 256 bits long, and I want to use SSS with e.g. $(k=4,n=8)$. The normal approach is to set $a_0=s$ and choose $a_1 \ldots a_{k-1}$ randomly, ...
0
votes
0answers
26 views

In an encryption scheme, why can we say that the Encryption and Decryption are PPAs?

In cryptography, a reasonable computational complexity definition for an encryption scheme, is 3 algorithms, (Generate, Encrypt, Decrypt) where encrypt and decrypt can be probabilistic polynomial ...
1
vote
1answer
87 views

Are there any classical proven secure cryptographic algorithms other than OTP? [duplicate]

Boiled down to the core as I understand it: A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time. If my understanding ...
9
votes
2answers
143 views

Are interactive proofs more secure their non-interactive counterpart?

Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure? Are there any new attack vectors that get introduced? Is there any reason to use the ...
1
vote
1answer
78 views

Are oracles needed in security proofs to prove that one problem is equivalent to the other?

I have seen a few security proofs where they show that solving one problem is equivalent to solving the other, via use of an oracle. For example, when proving that problem A is equivalent to problem ...
5
votes
2answers
212 views

Why ``adversary'' and ``challenger'' and what are typical roles of those?

I'm confused with words adversary and challenger, that are used in proof of security of some cryptosystems. For example, adversary and challenger appear in the formal definitions of IND-CPA, IND-CCA, ...
2
votes
1answer
65 views

What does “simulatable” mean in security proofs?

I am reading a security proof in a paper as follows. Regarding the data confidentiality of users, all related public transcripts are simply the ciphertexts $\mathcal{C}_1,\ldots,\mathcal{C}_n$. The ...
1
vote
2answers
137 views

What is the difference between the adversary and the algorithm?

I recently saw a sketch relating to provable security in a book, regarding the amount of time it takes to factor N where N = pq and p,q are primes. It says that "There is a trivial algorithm which ...
1
vote
0answers
127 views

Reduction to security of proof system for proving knowledge

I want to prove security of my system by reduction to the security of an underlying non-interactive proof system for proving knowledge. I know a game that captures the desired security property of my ...
0
votes
1answer
92 views

Can machine learning/AI lower the security existing cryptographic protocols similar to quantum computers? [duplicate]

Initial thinking would be not unless the protocol revealed sensitive local information that could then be analysed by an ML algorithm and applied globally. local meaning I see messages from Alice and ...
0
votes
1answer
74 views

Is the following non-interactive zero-knowledge set membership protocol provable secure?

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9). The Verifier -...
7
votes
1answer
252 views

Are DSA and ECDSA provably secure assuming DL security?

Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
59
votes
6answers
9k views

Soft question: Examples where lack of mathematical rigour cause security breaches?

Cryptographic tools can often become adopted even when their security proofs lack mathematical rigour - or altogether missing. Are there famous cases of security breaches in the industry, where the ...
1
vote
2answers
104 views

What is the Knowledge Of Secret Key Assumption (KOSK)

From what I've read it seems to be where an entity must prove that they own the secret key. Which is done by signing a message M using said secret key. Is this ...
2
votes
1answer
139 views

How does the random oracle model simplify proofs versus using the standard model?

If I use the standard model, then the proof must rely on mathematical assumptions. Will this security proof, generally be longer/more complex? Is there an example where the random oracle has been ...
9
votes
4answers
369 views

Signature security proof in the Random Oracle model

As a study case, I consider the BLS signature scheme, but the following question is relevant in the general context of security proofs in the Random Oracle model. Let us briefly recall BLS signature ...
2
votes
1answer
74 views

Variants of universal composability in security proofs

Universal composability (UC) framework seems to be a powerful framework for proving security of protocols, which guarantees security even in the presence of concurrent composition. Though, I see there ...

1
2 3 4 5
10