Questions tagged [cr.crypto-security]
Theoretical aspects of cryptography and information security.
260
questions
2
votes
1
answer
171
views
Do pseudo-random number generator test batteries have any theoretical grounding?
There are a lot of PRNG test batteries, like DieHarder. They do check that some statistical tests expected for random sequence are indeed present.
But is there any theoretical motivation, why this ...
- 295
0
votes
0
answers
123
views
Could we build PSPACE-based cryptography - more secure post-quantum?
It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. 2WQC) - so maybe it is worth to start thinking of shifting the ...
- 325
-3
votes
1
answer
134
views
help me understand what semiprime factorizations are worth
Based on a response I received in another post, I would like to ask this question.
Are there semiprimes that are not very interesting in terms of research and are not worth factoring?
Are only the RSA ...
0
votes
0
answers
56
views
Restrictions on set of infinitely many n's for which an algorithm breaks distributional hardness
Say we want to capture the notion that an efficiently samplable distribution $D(1^n)$ is hard with respect to some boolean function $f$ for a decision problem or some efficient relation $R$ for a ...
- 117
1
vote
0
answers
72
views
One way analogues of Logspace
When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$.
Likewise we say a function is logspace one-way if the function is ...
- 12.8k
8
votes
1
answer
164
views
Q: Trusting program output from an untrusted machine
Let's suppose that we create a program P, that given input I, generates output O. We then want to run this program on an untrusted computer C that may either want to tamper with the program (run P' ...
- 183
8
votes
3
answers
508
views
What are some "must-read" papers for someone getting into Quantum Cryptography?
I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography.
I'm interested in Quantum Cryptography and would ...
- 219
0
votes
0
answers
190
views
"Fair" hash functions
Motivation. When I use a hash function, I would like my pre-images (original values) to a given output (hash) to be evenly distributed as it could be that an uneven distribution could make guessing / ...
3
votes
1
answer
147
views
Fast private computation of dot product
Consider two paranoid parties Alice and Bob. Say Alice owns a secret vector $x=(x_1,\ldots,x_n) \in \mathbb R^n$ and Bob owns a secret vector $y=(y_1,\ldots,y_n) \in \mathbb R^n$.
Question. How can ...
- 291
5
votes
0
answers
84
views
Chosen message attack on unhashed GGH signatures?
Background: I've been reading GGH's Public-Key Cryptosystems
from Lattice Reduction Problems, and have a question about a remark the authors make:
"It is important to remark at the outset, that ...
- 1,439
21
votes
2
answers
1k
views
PPAD and Quantum
Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
- 6,013
5
votes
0
answers
121
views
Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?
One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
- 387
1
vote
0
answers
53
views
Underlying codes in Niederreiter cryptosystems
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.
The minimum distance $d$ is given by
$d= min\lbrace k \text{ such that there are $k$ linearly ...
- 387
4
votes
2
answers
177
views
If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'
I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including ...
- 173
2
votes
1
answer
303
views
Would an NP-complete public key cryptosystem imply NP=co-NP?
Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP? My specialty is definitely not theoretical computer science, so this is somewhat of ...
- 131
1
vote
1
answer
107
views
Cryptography protocols using graph problem instances
I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
- 385
8
votes
2
answers
174
views
What is the state of the art in online voting?
Is there a cryptographic protocol which, at least in theory (and under standard cryptographic assumptions) enables people to securely vote from their homes? I could see how the various problems might ...
- 10.3k
16
votes
1
answer
1k
views
Password hashing using NP complete problems
Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
- 779
1
vote
2
answers
250
views
Which cryptographic protocols are secure against quantum computer attacks?
Are there any cryptosystems that we know that would be secure against an attack by a quantum computer?
Are there problems which are known or suspected to be hard for quantum computers, and can these ...
- 607
5
votes
0
answers
147
views
How hard is it to generate a set of relatively prime numbers between two given bounds?
Informal Question
How hard is it to generate a set of relatively prime numbers between two given bounds?
Decision Problem
Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
- 5,127
18
votes
2
answers
534
views
Is it possible to encrypt a CNF?
Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that
The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$.
$\Psi(\mathcal ...
- 13.9k
20
votes
2
answers
1k
views
Can any computational challenge be transformed to proof-of-work?
The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO.
I wonder whether there exists an algorithm that can convert ...
- 13.9k
4
votes
1
answer
141
views
Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise
There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we ...
- 1,141
6
votes
2
answers
288
views
Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?
I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $&...
- 261
7
votes
1
answer
328
views
Why is the security of lattice cryptosystems not provable from $P \neq NP$?
My understanding is that the Shortest Vector Problem ($\text{SVP}$) is $\text{NP}$-hard. Therefore, $\text{LWE}$ is also $\text{NP}$-hard. But $\text{LWE}$ is hard on average if it is hard in the ...
- 516
0
votes
1
answer
89
views
Problems equivalent to the existence of secure cryptosystems? [closed]
What are some necessary and sufficient conditions for the existence of following?
Symmetric encryption (defined here as satisfying $\text{IND-CPA}$ and $\text{INT_CTXT}$)
Asymmetric encryption
...
- 516
2
votes
1
answer
85
views
"Security Against Covert Adversaries" question
I was reading the paper Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries by Aumann and Lindell, and had some questions with the protocol for covert OT given errorless ...
- 918
5
votes
0
answers
82
views
Is [2-party d3-rolling with maximum probability 1/2] known to imply one-way functions?
Most things in complexity-based cryptography (for examples, see page 4) are known to imply
the existence of one-way functions, especially after this paper proved that implication for weak coin-...
user6973
-2
votes
1
answer
627
views
The factoring problem reduces to order finding or is it the other way around? [closed]
initially i was not at all equipped in theoretical computer science and knew only basics of number of theory.
I started working from scratch on the age old problem of primality testing which led me to ...
3
votes
4
answers
336
views
Is a theoretically secure key exchange possible?
During a discussion I was wondering if it would be possible to design a theoretically secure key exchange.
In other words: If it is possible to design a key exchange (like Diffie–Hellman) where the ...
- 139
9
votes
1
answer
287
views
Can a random oracle change which TFNP problems are strongly hard-on-average?
I've been thinking about the following question at
various times
since I saw this question on Cryptography.
Question
Let $R$ be a TFNP relation. Can a random oracle help P/poly
to break $R$ ...
user6973
2
votes
1
answer
108
views
Is a "complete" cipher possible?
Is a "complete" symmetric cipher possible? By this I mean a symmetric cipher that is provably secure under the assumption that a secure symmetric cipher exists.
- 516
4
votes
1
answer
74
views
Is it possible to MAC a quantum state with a classical key under reasonable assumption?
Assume that classical one-way functions secure against quantum adversaries exist. Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that:
...
- 516
2
votes
1
answer
134
views
Is it possible to encrypt quantum states under reasonable assumptions?
Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can ...
- 516
18
votes
0
answers
369
views
Does Factoring have a Statistical Zero Knowledge Proof?
The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
- 3,748
1
vote
0
answers
247
views
Quantum algorithms for generalizations of determinants
There are a wide variety of determent-like constructions. Some like the permanent or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like ...
- 1,206
6
votes
2
answers
319
views
How to find a non-zero point of a non-zero polynomial of low degree?
Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one ...
- 891
7
votes
1
answer
361
views
Quantum Hardness of Approximating Lattice Problems
A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum ...
- 5,961
16
votes
0
answers
537
views
Quantum Hardness of Finding Nash Equilibria
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.
Their main result is that the existence of ...
- 5,961
7
votes
2
answers
1k
views
Alternatives to Diffie Hellman
Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem ...
user34945
16
votes
1
answer
495
views
Complexity classes for proofs of knowledge
Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes ...
- 13.6k
23
votes
1
answer
2k
views
Knot Recognition as a Proof of Work
Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion.
Is it possible to use a Decision problem ...
- 1,641
1
vote
0
answers
113
views
Extractor with somewhat corrupted seeds
In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, ...
- 161
1
vote
2
answers
159
views
Factoring semiprimes whose factors very close to a power of two
Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ ...
2
votes
0
answers
107
views
Claw finding using quantum walk: superposition for Szegedy's framework
Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper:
Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
- 155
1
vote
2
answers
237
views
Information-theoretic Diffie-Hellman
The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand.
In Diffie-Hellman Alice and Bob ...
- 303
10
votes
1
answer
357
views
Can we construct a k-wise independent permutation on [n] using only constant time and space?
Let $k>0$ be a fixed constant.
Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:
The construction uses constant time and space (i.e. preprocessing takes constant ...
- 9,596
5
votes
1
answer
218
views
Simple candidates for pseudorandom permutations?
Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured ...
- 53
0
votes
1
answer
78
views
Question on cryptographic advantage
In Provably Secure Steganography by Hopper, et al, we have the following definition
Cryptographic notions
Let $F:\{0,1\}^k \times \{0,1\}^L \rightarrow \{0,1\}^l$ denote a family of functions. Let $...
4
votes
1
answer
324
views
Introductions to steganography from an information-theoretic standpoint
Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
- 143