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

0
votes
1answer
22 views
-2
votes
0answers
8 views

RSA Security Java [closed]

I need help getting this RSA program working, especially using these methods. I have gotten help with the layout of the program, but i need help implementing the methods: ...
-2
votes
1answer
29 views

Message size in Menezes–Vanstone elliptic curve cryptography [closed]

I ask about message size in Menezes–Vanstone elliptic curve cryptography (MVECC). In this presentation I not understand this point: One major drawback. — Due to point overhead, encrypted messages ...
2
votes
1answer
50 views

Is a very long plain text password harder to crack than a short complicated password? [closed]

Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters? ...
0
votes
1answer
50 views

How to explain the steps in the implementation of hashing functions like SHA1

I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia. I can see that there are a lot of mathematical ...
9
votes
2answers
28 views

How does an operating system create entropy for random seeds?

On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random ...
4
votes
1answer
46 views

Partially homomorphic encryption (on addition modulo N) not based on prime factorization

A cryptographic function is homomorphic on some operation if that operation is preserved in the encrypted data. Such a function is homomorphic on addition modulo if the following holds for some ...
3
votes
1answer
64 views

What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm (http://en.wikipedia.org/wiki/BB84) is based on the idea that by ...
3
votes
1answer
35 views

Iterative Byzantine consensus in directed graphs with unbounded malicious nodes

I've found many articles describing iterative procedures to reach Byzantine agreement on a graph (for instance http://www.crhc.illinois.edu/wireless/papers/icdcn14-vaidya.pdf or ...
5
votes
1answer
98 views

What is the complete version of the paper: “How to Generate and Exchange Secrets (extended abstract)” by Andrew Yao?

I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. ...
0
votes
1answer
24 views

Finding the private key in BB84 quantum cryptography

I'm trying to teach myself Quantum Cryptography for an exam I have soon, and I came across the following question: To establish a common key, Alice and Bob analyse a sequence of 20 photon pairs. ...
2
votes
0answers
14 views

Proof of correctness of the XL-algorithm for polynomial systems

Section 12.4 of G.V. Bard's Algebraic Cryptanalysis discusses the XL-algorithm (first reported by N.T. Courtois and A. Shamir in Efficient algorithms for solving overdefined systems of multivariate ...
1
vote
1answer
102 views

RSA encryption why does ed=1?

So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know: why the public key e and the private key d in the RSA encryption have to ...
7
votes
1answer
130 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
50 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 ...
8
votes
6answers
211 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
150 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
52 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
55 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
56 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
82 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
53 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
62 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
108 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
81 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
66 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 ...
6
votes
2answers
229 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
40 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
78 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
304 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
106 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
126 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
777 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
2k 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
231 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
313 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
133 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
205 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
468 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
130 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
245 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 ...
4
votes
1answer
506 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
82 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
721 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
416 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
34 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
490 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
195 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
104 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
184 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 ...