Questions about the construction and analysis of protocols and algorithms for secure computation and communication (including authentication, integrity, and privacy aspects).
2
votes
1answer
37 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 ...
4
votes
1answer
50 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 ...
0
votes
4answers
84 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
59 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
138 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 ...
4
votes
1answer
47 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
53 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 ...
0
votes
0answers
32 views
Trapdoor implementation [closed]
X-posting from SO
Please refer to this secure index paper. On page#6, a trapdoor is defined as
...
2
votes
2answers
107 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
125 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
103 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
123 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
43 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
180 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 ...
0
votes
0answers
68 views
difference between stream cipher and block cipher [closed]
A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher may be designed to operate on one bit at a time or on units larger than a byte at a time.
A block cipher ...
