Questions about the construction and analysis of protocols and algorithms for secure computation and communication (including authentication, integrity, and privacy aspects).

learn more… | top users | synonyms

7
votes
1answer
60 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
1
vote
2answers
38 views

In RSA, must $p$ and $q$ have the same number of bits?

Is it necessary to take the same bit size of "p" and "q" in case of RSA algorithm? i had read that bitsize of p and q must be same. BUT after calculating, i found that bit size could be different ...
-1
votes
0answers
12 views

SHA-1 Implementation In Java [on hold]

Can any one suggest an algorithm that takes in a string and outputs a 32 char hash using the SHA-1 hash function? Size of Hash must be 32 char or less.
8
votes
6answers
124 views

Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April: '"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a ...
5
votes
4answers
121 views

Can all NP-complete cryptosystems be broken if one is broken?

I was just reading something about NP-hard problems and cryptosystems. I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) ...
0
votes
1answer
28 views

Finding prime factors of non-random key generator

I have been working on a challenge i found on the internet. It is as follows: You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the ...
1
vote
1answer
50 views

Help in understanding exactly how lattices used as one way functions for hashing

(This question is related to homework) I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority ...
4
votes
1answer
44 views

If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument

I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is ...
0
votes
2answers
72 views

Decrypting transposition ciphers

How do I see if the following ciphertext eaeairtntrnaeemtve is a transposition cipher, using letter frequency? This article suggest how to detect by using letter ...
0
votes
1answer
43 views

Cryptography substitution frequency analysis

I am trying to find the plain text for the following cipher text using a frequency analysis vr pvst yqlp mq nvf But for the letters above this is really ...
3
votes
1answer
53 views

What is a protocol for determining which of two numbers is larger, without sharing those numbers?

Situation: Alice has selected a positive integer $a$, and Bob has selected a positive integer $b$. Alice and Bob want to know whether $a > b$, $a = b$, or $a < b$, but neither wishes to reveal ...
3
votes
2answers
80 views

Perfectly Secure Ciphers known other than the OTP

By Information-Theoretic definitions, the One Time Pad (OTP) is called/was proved to be a Perfectly Secure Cipher. For the sake of completeness, we define OTP: An enc/dec function, $f:\mathcal{P} ...
2
votes
1answer
73 views

Mealy machines to model ciphers [closed]

Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an ...
5
votes
1answer
62 views

Completeness of formal definition of 'hardness on the average'

While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
5
votes
2answers
156 views

What mathematics can be interesting for these CS areas?

For my CS degree I have had most of the "standard" mathematical background: Calculus: differential, integral, complex numbers Algebra: pretty much the concepts up until fields. Number Theory: XGCD ...
2
votes
1answer
39 views

Which areas in CS will be (or have been) most affected by fully homomorphic cryptography?

I'm in the middle of planning a 5000ish word essay on fully homomorphic cryptography, the current practical implementations and their limitations. Which areas of CS as a subject have been (or will ...
1
vote
1answer
59 views

Doubts on Definition of Indistinguishable Encryption in the Textbook

In the classic crypto textbook "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, there is a definition for indistinguishable encryption in the presence of an eavesdropper as ...
11
votes
2answers
195 views

How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
3
votes
2answers
85 views

Assumptions of One Way Functions

I try to get the intuition behind the notion of strong one way function and weak one way function by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of ...
7
votes
2answers
110 views

How hard is it to solve for $P$ in $A = PBP^{-1}$?

From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$ So, to solve the problem, if two graphs are ...
4
votes
1answer
467 views

Negligible Function in Cryptography

In the field of Cryptography and Computation Complexity there is a notion of negligible function. I have some difficulties in understanding intuition behind this notion. The following are some ...
2
votes
4answers
953 views

A good introductory book on cryptography

Can anyone suggest me some good books on cryptography? I have just starting studying cryptography but I know elementary number theory, abstract algebra and algorithms. Also please mention the ...
5
votes
1answer
200 views

Length-preserving one-way functions

Unfortunately my background in computational complexity is still weak, but I am working on it. As I understand, the question of existence of one-way functions is very important in the field. Assume ...
4
votes
2answers
261 views

If xor-ing a one way function with different input, is it still a one way function?

Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$? $\oplus$ is exclusive disjunction (xor) $||$ is ...
6
votes
2answers
115 views

Complexity of GF(2) and applications to cryptography

If I have a system of N polynomial equations with N unknowns in GF(2): What are some good methods to solve them? What are some software packages or libraries that implement this? What's the highest ...
6
votes
1answer
145 views

Quadratic residue and integer factoring

I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime). I am looking at the ...
2
votes
2answers
372 views

Collision resistant hash function

A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$. ...
6
votes
1answer
129 views

Mental poker: proving dealt hand is fair

I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman. Assuming I have a website, (TTP) how can I prove to the ...
3
votes
1answer
206 views

What will i obtain if i apply a xor-ing a one way function and it's input?

I know that a one-way function is informally a function that it's easy to compute but hard to invert. If f(x) is a one way function the function $g(x) = x\oplus f(x)$ is a one-way function? My ...
3
votes
1answer
393 views

How to show composition of one way function is not such?

I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function? Specifically: Say $f$ and ...
2
votes
2answers
73 views

Condition in Shamir Secret Sharing Scheme

For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$). The constant coefficient of this polynomial is ...
2
votes
1answer
570 views

One time pad, get plaintext using ciphers encoded with the same key

I'm trying to solve a problem: I have 11 ciphers encoded with the same key. My aim is to decode target cipher. If I do xor C1, C2 (ciphers encoded with the same key) I do get M1 xor M2 (where M1, M2 ...
5
votes
1answer
315 views

In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test: It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for ...
2
votes
0answers
32 views

Mersenne twister middle word

In some literature, as well as in Wikipedia, the middle term parameter m of Mersenne twister is called "number of parallel sequences". Why? What is meant here by "parallel sequences"?
3
votes
1answer
397 views

Rigorous proof against pseudo random function

I have the following problem: Define the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function. How do I ...
1
vote
2answers
151 views

Collisions of prefixes of MD5 hashes in some fixed interval

I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer ...
4
votes
1answer
85 views

LFSR sequence computation

I need to calculate the output of the sequence generated by this shift register but I cannot find anywhere how to do it. Everywhere the results are just given but there is no explanation how to do ...
5
votes
1answer
181 views

A hash function with predicted collisions

As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides ...
9
votes
1answer
294 views

Weak hashing function for memorable IPv6 addresses

IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been ...
1
vote
1answer
63 views

Are tamper attacks considered side-channel?

Wikipedia defines side-channel attacks as: any attack based on information gained from the physical implementation of a cryptosystem Usually in side channel attacks the implementations leak ...
6
votes
4answers
283 views

After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

Preface: This question was originally asked on Theoretical Computer Science, and the kind people there referred me to this web site. It is being repeated here in an attempt to find a satisfying ...
8
votes
5answers
210 views

How can encryption involve randomness?

If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness? Surely it has to be ...
8
votes
3answers
254 views

Key secrecy vs Algorithm secrecy

it's a well known statement that "Cryptographic security must rely on a secret key instead of a secret algorithm." I would like to ask about some details about it. And which are their differences? ...
8
votes
1answer
388 views

Is WPA2 with pre-shared key an example of a zero-knowledge proof?

When setting up an access point and selecting WPA2, one must manually enter a pre-shared key (a password), PSK, into both the AP and the STA. Both parties, AP and STA, must authenticate each other. ...
7
votes
2answers
310 views

What is the difference between classical crypto and post-quantum crypto?

Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be ...
9
votes
3answers
201 views

Is it possible to create a “Time Capsule” using encryption?

I want to create a digital time capsule which will remain unreadable for some period of time and then become readable. I do not want to rely on any outside service to, for instance, keep the key ...
13
votes
1answer
199 views

Are asymptotic lower bounds relevant to cryptography?

An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be ...
8
votes
1answer
170 views

Attack on hash functions that do not satisfy the one-way property

I am revising for a computer security course and I am stuck on one of the past questions. Here is it: Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to ...
9
votes
1answer
220 views

Choosing taps for Linear Feedback Shift Register

I am confused about how taps are chosen for Linear Feedback Shift Registers. I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, ...
9
votes
2answers
997 views

How does a wifi password encrypt data using WEP and WPA?

How does the password that we enter (to connect to a wireless network) encrypt the data on the wireless network? Through my reading I am not sure if the password that we enter is the same as the ...