Questions tagged [cryptography]

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

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
54 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u \...
4
votes
0answers
141 views

Optimal parallel-time repeated modular squaring circuit

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
3
votes
0answers
67 views

creating new PRF from existing one

I have encountered a problem in class, tried solving it and faced a problem, I will include my ideas, and the problems i faced. Assume F is a PRF, 1.denote $P_k(x) = F_k(x) ⊕ F_k(1^n)$ for any $n ∈ ...
3
votes
0answers
267 views

How is Chinese Remainder Theorem used in the proof of correctness for RSA

Question At the very end of (most) proofs of RSA's correctness we have something like $$m^{ed}\equiv m\pmod p$$ $$m^{ed}\equiv m\pmod q$$ Therefore by the Chinese Remainder Theorem (CRT) $$m^{ed}\...
3
votes
0answers
75 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 ...
2
votes
0answers
45 views

Permutation with stable partitions

I am searching a fast pseudo-random permutation function with the following requirements. Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset ...
2
votes
0answers
82 views

AKS primality test- Lemma 4.3, not following

I'm reading the AKS primality test paper as it is found here. I'm confused about a statement in Lemma 4.3: "Note that $(r, n)$ cannot be divisible by all the prime divisors of $r$ since otherwise $r$...
2
votes
0answers
45 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"?
1
vote
0answers
45 views

Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some ...
1
vote
0answers
76 views

Absolute limit in Huffman encoding

I have computed the average code length using the Huffman encoding. Now, I am asked to compare the average code length with Absolute limit but I ain't sure about the absolute limit here is :( Could ...
1
vote
0answers
20 views

equivalent sub-keys in DES encryption

i am trying to understand the DES cryptosystem and was wondering: what would've happened if all of the sub-keys were equal? does it reduce the security? can we actually find the keys if we know all ...
1
vote
0answers
71 views

A tree-like data structure with rights delegation for distributed computing

Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
1
vote
0answers
57 views

Is it possible to build a secure PRG from two functions one of them being a PRG?

Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG. Being $\alpha$ a constant, is it possible ...
1
vote
0answers
56 views

eVoting with Damgard-Jurik-Cryptosystem

I am trying to implement a secure elecetronic voting system. Therefore I found the Damgard and Jurik Cryptosystem. In their paper the authors describe a secure protocol for "A Length-Flexible ...
1
vote
0answers
65 views

On "practical" polynomial coefficients if P = NP

I got riddled by the following problem: Wikipedia states (without citation) Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution[Note 1] to an ...
1
vote
0answers
32 views

Generation of 11 bit random number

I need camera to sign one random line(there are something like 2000 lines) from the frame each second. At the beginning I have some 64 bits seed with high entropy from physical RNG and a secure ...
1
vote
0answers
29 views

Is there any knapsack-based cryptosystem that hasn't been broken?

I took part in the development of a knapsack-based asymmetric cryptosystem, and am currently planing to launch a campaign to promote it. Before we actually do, it occurred to me to research... what ...
0
votes
0answers
56 views

Books for learning Cryptocurrency

Please suggest a good for mathematical section of studying cryptocurrency.
0
votes
0answers
39 views

Asking for your help with LFSR, linear automaton

I am a software developer new to the site. I am currently learning about LFSR (linear feedback shift register). Every day I solve a question which is given to me, but today I am lost. I can not solve ...
0
votes
0answers
21 views

Extracting text from a hidden image

Say i have cropped an image and have hidden some part of it, like shown below Is it possible for anyone to download this image and able to decipher what the hidden text is?
0
votes
0answers
23 views

Abusing ElGamal in order to attack a known encrypted text

I saw a very interesting question regarding Elgamal cryptosystem that I don't know its answer. It is really interesting and I would be very happy if you could elaborate on it and explain the tricky ...
0
votes
0answers
41 views

Is 'the bombe' technically a computer?what is technically meant to be a computer?

Some say that 'the bombe' created by Alan Turing is technically not a computer despite decrypting the codes. Why is it so? Is 'the bombe' technically a computer? First of all what is technically ...
0
votes
0answers
33 views

Secrecy rate of eavesdropper channel?

I want to find secrecy rate of a main channel in case of Gaussian broadcast channel. e.g. I have a single transmitter and a receiver where eavesdropper wants to eavesdrop the communication over ...
0
votes
0answers
51 views

What are some data mining algoritms used in finance?

I want to test the applicability of homomorphic encryption in the financial domain, as suggested in Can homomorphic encryption be practical ?. Now, I want to know what algorithms are used for ...
-1
votes
1answer
17 views

Not CPA secure for CBC mode if some code are changed that is if we replaced a function $\pi(k,x)=k\oplus x$

Consider the CBC mode where the block cipher is replaced by a function $\pi$ where $\pi(k,x)=k\oplus x$. Show that the mode is not CPA secure. I am not got how to proceed to solve this question. ...