Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)

4
votes
3answers
205 views

Is it possible to exactly reverse engineer an unknown cipher inside a black box?

Consider the following arrangement:- There is an unknown cipher algorithm operating inside the black box. You can enter infinite key /plain text pairs, and observe all of the outputs. The box might ...
1
vote
0answers
44 views

Key-space analysis of an algorithm

I have an algorithm that requires a set of keys to encrypt a text (image of size N x N). It is an image encryption algorithm for a project. The key can be thought of as a tuple $x_0, \lambda, d, i, ...
2
votes
2answers
170 views

Is the practice of “security through obscurity” violating Kerckhoffs's second principle?

Security through obscurity is the reliance on the secrecy of the design or implementation as the main method of providing security for a system or component of a system. Kerckhoffs's second principle:...
0
votes
1answer
79 views

What does $1^n$ mean? [duplicate]

I often see the notation of powers of 1 in cryptography papers. For example, let $n$ be security parameter, then what does $1^n$ mean?? From high school student perspective, powers of one is always ...
1
vote
0answers
39 views

Mersenne Twister's vulnerabilty with small-size distributions

C++ rookie here, trying to wrap his head around (CS)PRNGs. I (assume that I) already understand the concept of the Mersenne Twister being "broken" (i.e. not cryptographically secure) due to its ...
2
votes
1answer
71 views

How well is it understood mathematically why encryption schemes are hard to crack?

I have read some intro material into cryptography. It mainly goes into the current encryption schemes like AES, but not very deeply into the mathematics of why they are secure. I know that encryption ...
1
vote
0answers
26 views

Proofs of security for anonymity in a multi-party setting

I'm looking for material that proves the anonymity of parties in a non-interactive setting. I would like to know if there are simulation based proofs (UC) and property based proofs (game based) for ...
0
votes
1answer
36 views

Fairness and guaranteed output delivery

Why for achieving the fairness and guaranteed output delivery, less than a half of the parties should be corrupted? ($t < m/2$, where $t$ is the number of corrupted parties and $m$ is the total ...
1
vote
1answer
69 views

Any Arbitrary Function

According to the attached reference, does it mean that the adversary computes $PPT(initial~input)$, $PPT(z)$ and $PPT(f_i(x',y'))$? For example, suppose the corrupted party, in the malicious model, ...
-1
votes
1answer
31 views

Which of these deductions are true about the simulator and the adversary?

Which of these deductions make sense? The simulator is actually being run by the adversary. It makes sense that the adversary initializes the simulator (which is just a program) with the input that ...
0
votes
1answer
38 views

Is function Deterministic or Probabilistic in the malicious security definition?

As you see, according to the attached definitions from "Efficient Secure Two-Party Protocols", the definition of the security in the semi-honest world has two cases for $f=(f_1,f_2)$.(deterministic ...
3
votes
1answer
265 views

Strong One-Way Function

In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to ...
0
votes
0answers
149 views

Security proof in the semi-honest model

This protocol is designed in the semi-honest model. Two parties encrypt their input and send it to the cloud. Cloud will perform computation using a homomorphic encryption and send the result to P2. ...
2
votes
1answer
47 views

A problem exists with the security proof in the secure AND example in the malicious model [closed]

Imagine that the malicious adversary in the real world uses $Y = 0$ as its input, therefore he computes the output as ($X$ && $y=0$) = $0$. We can conclude that the real view in the real world ...
4
votes
1answer
61 views

The interaction between the malicious Adversary and the Simulator and Real-Ideal' views

This example is from “Efficient Secure Two-Party Protocols-Carmit Hazay-Yehuda Lindell”. And the security proof of the above example is this: I have drawn a picture that is deduced from the above ...
4
votes
1answer
69 views

Security proof in the Malicious Model

According to the above protocol(Efficient Secure Two-Pary Protocols-Hazay-Lindell-page 27), the authors proved the security of this protocol according to the two paragraphs below: We separately ...
1
vote
1answer
52 views

How to use Real-Ideal model in a specific scenario (two party with cloud)

I have designed a two-party protocol where two parties outsource their input to the cloud. For example, Alice and Bob have inputs $X$ and $Y$, respectively, after which Alice and Bob encrypt their ...
0
votes
1answer
31 views

Using the security definition in the malicious model to prove security in the semi honest model

Can I use the security definition in the malicious model in order to prove the security of a two-party protocol which is in the semi-honest model? (I am using IDEAL/REAL Model paradigm) Would you ...
1
vote
1answer
42 views

difference between the uniform and non-uniform probabilistic polynomial algorithms (ppt)

I am reading the book "Efficient Secure Two-Party Protocol". A question came to my mind. why has the author used a probabilistic polynomial time algorithm for security definition of ideal/real model ...
2
votes
1answer
116 views

Difference between semi-honest and malicious adversary using Ideal Real Model Paradigm

Would you please explain to me why in the security definition of ideal/real model paradigm which is described in the efficient secure two-party protocol book(Hazay, Lindell), the simulator tries to ...
0
votes
0answers
9 views

Difference between strongness and unverifiability properties in designated verifier signature

A strong verifier designated signature has the strongness and unverifiability properties but I don't really understand the strongness property. Is strongness related to unverifiability or are they ...
11
votes
3answers
1k views

How small is negligible?

When proving theorems in crypto we often make use of the concept of negligible functions or, more simply, negligible parameters. As a rule of thumb, given today (2018) computational power, what is ...
5
votes
1answer
119 views

“Power of one” as input to functions of a cryptosystem

What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this. I have been told it signifies the ...
1
vote
0answers
31 views

A qusetion about the security game of Certificateless signatures

Recently I read Certificateless Public Auditing for Data Integrity in the Cloud , I have a question about the security of proposed HOMOMORPHIC AUTHENTICABLE CLS. (Sec. IV). For the Type-I Adversary, ...
1
vote
1answer
65 views

In “Lecture Notes on Cryptography” what does “PTM” mean?

I came across a handbook named "Lecture Notes on Cryptography" from Shafi Goldwasser and Mihir Bellare and I read their definition 3.1 about poly-time indistinguishability: Let $X_n,Y_n$ be ...
0
votes
1answer
54 views

Maximum value of negligible probability?

We can see on many papers for cryptography that there are many uses of negligible probability to ensure something (security, correctness, etc). How can we say that some probability is negligible? I ...
4
votes
2answers
101 views

Is there a computational security of public-key encryption which is similar to the one of symmetric key encryption

We say a symmetric key encryption scheme $\Pi_{1} = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is computational security if for every PPT algorithm $A$ and every $x_{0}, x_{1}$ ($|x_{0}| = |x_{1}|$), ...
2
votes
2answers
94 views

Can the key-generation algorithm always be uniform?

Assume that the encryption uses $n$-bit keys to encrypt $l(n)$-length messages. If a symmetric key encryption scheme is defined as $\Pi_{1} = ( \mathrm{Enc}, \mathrm{Dec} )$, then for every $x_{0}, ...
3
votes
1answer
115 views

security against CPA attack?

Let $\mathcal{E} = (E,D)$ be a CPA secure cipher. Let's define $\mathcal{E'} = (E', D')$, where $E'(k,m) = E(k, E(k,m))$. How can I prove that $\mathcal{E'}$ will be CPA secure if $\mathcal{E}$ is? ...
1
vote
0answers
66 views

Design flaw in IND-CKA definition of Searchable Symmetric Encryption?

I am a graduate student interested in searchable encryption research. I carefully read the Secure Indexes paper published in 2004, and I was confused about the IND-CKA, the game-based security ...
4
votes
2answers
123 views

What is the relationship between entropy conditioning and final output bias in a TRNG?

This question concerns the conditioning and output of true random number generators. It refers to NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions. It ...
1
vote
1answer
93 views

Deterministic symmetric indistinguishable encryption

Are there any block-cipher modes (or symmetric encryption schemes in general) that are fully-deterministic, meaning same inputs lead to the same outputs (like for all modes with constant IV) and ...
-1
votes
2answers
128 views

Secure pseudo-random generator

Suppose that $G : \{0,1\}^k \rightarrow \{0,1\}^{2k}$ is a secure pseudo-random generator. Describe what is wrong with each of the following attempts to build a pseudo-random generator with $k$-bit ...
1
vote
1answer
146 views

Hash function composition - security level

When using two hash functions, g(x)=SHA-512 and f(x)=MD5 g(x) has 512 bit output (using salt) f(x) has 128 bit output. Let's say that z(x)=f(g(x)) meaning the output is 128 bit long. The Question: ...
0
votes
0answers
45 views

On computing probability of some cipher text

One presentation shows how one could compute probability of some cipher text occurring: Which I understand. However, also for computing probability that a plain text occurs given a ciphertext occured,...
1
vote
2answers
102 views

What does trust mean in cryptography?

Terms like "trustless protocol", "trusted third party", "trusted platform", "trusted server", etc. require a notion of trust. I already wrote The term trust when used in the context of cryptography ...
4
votes
1answer
97 views

How to determine the security in bits of a scheme?

This may be a stupid question. But how would we determine the security bit of a crypto scheme? For example, SHA2-256 offers 128 bit security due to birthday paradox, so do they measure the security ...
-5
votes
1answer
157 views

Client Puzzles and Amplification [closed]

Any hints or suggestion will be helpful.
1
vote
1answer
43 views

What does St denote?

I am reading a paper and notice that the term St is used without being defined. I suspect it is a common notation that I am not aware of. It is used in the following paper: https://eprint.iacr.org/...
1
vote
1answer
526 views

What exactly is a “security parameter”?

I often encounter the term “security parameter” when I read crypto related stuff. My basic understanding is that it just denotes some bit-length however, I'm not so sure. For example, when it says ...
2
votes
1answer
120 views

Encryption Scheme & Perfect Secrecy [Katz & Lindell]

An encryption scheme consists of the following data a plaintext space $\mathcal M$ a ciphertext space $\mathcal C$ a key space $\mathcal K$ a key generating algorithm Gen encryption and decryption ...
3
votes
2answers
779 views

Does information theoretical security definition imply DDH, RSA, QR does not hold?

Assuming we are in the information theoretical setting, whereby there is no bound on the computational power of an adversary. Does this mean that the standard definitions for DDH, RSA or QR do no hold ...
3
votes
0answers
86 views

How do adversary models and security types relate [from InfoSec SE]

I have been told to move the question to this forum in order to get a better insight, so here we go: Reading some questions in this forum I encountered this answer mentioning IND-CPA as a requirement ...
-4
votes
1answer
253 views

I am not convinced that SHA2/3 or AES256 is secure

I have been researching cryptography for the past few weeks to try and make sense of a few things, but is simply not making any sense for me. If I encrypt a message, send it to another computer, how ...
1
vote
0answers
48 views

RIsk mitigation: block cypher vs xor

It sort of looks like to me that there is a kind of risk mitigation in the architecture of block cyphers vs the xor cypher. In XOR, the risk is entirely in the random number generator. The XOR ...
-1
votes
1answer
265 views

What are the exceptions to Kerckhoffs's principle?

Kerckhoffs's principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge. Yet the following are three exceptions:- NSA Suite A cryptographic ...
2
votes
1answer
107 views

How is the zero-knowledge proof definition violated, here?

I'm confused about the definition of an interactive zero-knowledge proof (the simulator-transcript-thingy). Assume the following setup: $P$ and $V$ do a Diffie-Hellman key exchange to generate the ...
1
vote
1answer
285 views

What are the vulnerabilities of XOR in the following scenario?

What are the security vulnerabilities of the XOR operator in the following scenario: The Key, The Cyphertext and the Plaintext are the same size in bits. The Key is only used once and it's secret The ...
0
votes
1answer
42 views

Formal Information-Theoretic Key Expansion Definition

Is there a formal definition for a protocol that expands keys that are pre-shared among 2 or more parties? How about an informal definition? Example: Alice and Bob pre-share a $n$-bit string $k$. ...
1
vote
1answer
113 views

PPT vs NP problems

The common definition of security (for some cryptographic primitive) is to be secure against any PPT adversary (any probabilistic algorithm which runs in polynomial time). At the same time, we assume ...