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
4
votes
2answers
147 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, ...
0
votes
0answers
14 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
59 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 ...
5
votes
1answer
69 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 ...
3
votes
0answers
52 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 ...
2
votes
1answer
226 views

Why is this voting system not secure?

Why not have each person simply treated as a counterparty to an off-the-record chat? People show up in groups and show an ID which is cross-referenced against a central database to prevent Sybil ...
2
votes
0answers
34 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
750 views

Uniform vs discrete Gaussian sampling in Ring learning with errors

The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
2
votes
0answers
422 views

Looking for a detailed example of proof by reduction

I'm looking for a very detailed example of proof by reduction. Say we have two or three protocols (that have been proven secure) and we construct a new protocol. We want to provide a proof of security ...
26
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
90 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.)
11
votes
1answer
1k views

CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm $Enc$ chooses ...
8
votes
1answer
519 views

Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

Assume that $f$ is a one-way function (OWF), and let $\mathbin\|$ denote string concatenation. Consider the function $g$ defined by $g(x) = f(x) \mathbin\| f(f(x))$. It is easy to prove that $g$ is a ...
8
votes
1answer
1k views

Difference between computational and statistical indistinguishabilities

What is the difference between the two notions of computational and statistical indistinguishability?
1
vote
0answers
21 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 ...
18
votes
4answers
3k views

Are encryption algorithms with fixed-point free permutations inherently flawed?

Flaw in Enigma One of the Enigma machine's flaw was the derangement (fixed-point free permutation) of the produced ciphertext, or simply put: No plaintext-letter can be enciphered to itself. See this ...
5
votes
0answers
163 views

Efficient proof of knowledge using Carter-Wegman 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 ...
19
votes
1answer
3k views

What do the signature security abbreviations like EUF-CMA mean?

From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes. The most common ones are the *UF-* ...
3
votes
2answers
111 views

modified substitution permutation networks

I have a model of substitution permutation networks, modified as follows: instead of iterating $n$ times a round(each of which is composed of the key mixing phase, substitution S-BOX) and ...
7
votes
2answers
2k 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 ...
1
vote
0answers
24 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
2answers
623 views

The security proof for Key Policy Attribute Based Encryption

My question relates to the original KP-ABE paper: http://research.microsoft.com/en-us/um/people/vipul/abe.pdf I'm having trouble understanding the proof (pages 10–13) that the scheme is secure in ...
7
votes
2answers
1k views

What is the definition of “security beyond the birthday paradox”?

I'm reading a paper about MACs and I would like to be sure about the meaning of a security beyond the birthday paradox. Is there a definition?
39
votes
1answer
16k 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. ...
0
votes
0answers
59 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 ...
3
votes
1answer
104 views

Relationship between the (provable) security and the size of the plaintext space

Motivation: An encryption scheme is used to encrypt the message which belongs to the plaintext space. The scheme designer does not know what kinds of message is valid (i.e. what the plaintext space is)...
2
votes
1answer
80 views

Maximum security strength in bits of ISAAC cipher?

Wikipedia claims key length can be very big in this cipher, so I assume it can offer a million bits of security provided entropy of key is the same? Of course I can SHA-256 hash the key to allow any ...
6
votes
2answers
410 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) ...
5
votes
2answers
551 views

What is the relation between computational security and provable security?

I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security. Let $...
2
votes
2answers
65 views

Sensitivity of probability measure in differential privacy

I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. ...
1
vote
0answers
60 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: ...
2
votes
0answers
70 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 ...
0
votes
1answer
110 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
votes
1answer
74 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, ...
4
votes
1answer
262 views

Formal Verification of DHKE protocol using ProVerif

I am new to ProVerif and trying to verify a simple DHKE protocol. The attacker is assumed as passive. The specifications are: The attacker cannot obtains the mutual key. Both participants obtain the ...
6
votes
2answers
309 views

Is this Sigma Protocol zero knowledge or is it just a proof of knowledge?

Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them ...
1
vote
1answer
31 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 ...
1
vote
1answer
338 views

What is purpose of a simulator and extractor in zero knowledge proof protocols?

I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat. The author proposed a zero knowledge ...
-2
votes
1answer
95 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 ...
9
votes
0answers
392 views

What level of security is provided when a Feistel Cipher is used as a round function of another Feistel Cipher?

Recently, I was reading: Are there any specific requirements for the function F in a Feistel cipher?, and the answer posted mentions a Feistel Cipher named Turtle, which uses a four-round Feistel ...
24
votes
2answers
3k 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?
3
votes
0answers
41 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? ...
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, ...
1
vote
0answers
122 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 ...
1
vote
1answer
80 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 ...
1
vote
1answer
18 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
2answers
220 views

Fiat-Shamir paradigm and the forking lemma

I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also ...
1
vote
1answer
72 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 ...
10
votes
2answers
133 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 ...
26
votes
3answers
4k views

Random oracle model proofs and programmability

Proving the security of a scheme with the random oracle model (ROM) involves two steps: first you prove that the scheme is secure in an idealized world where a random oracle exists, and then you ...