Questions tagged [cr.crypto-security]
Theoretical aspects of cryptography and information security.
257
questions
0
votes
0
answers
53
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
64
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.6k
8
votes
1
answer
155
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
7
votes
3
answers
451
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 ...
- 209
0
votes
0
answers
168
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
145
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 ...
- 227
5
votes
0
answers
79
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 ...
- 5,973
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
176
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
271
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
98
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 ...
- 395
8
votes
2
answers
171
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.1k
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
241
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 ...
- 577
5
votes
0
answers
145
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,005
18
votes
2
answers
526
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.8k
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.8k
4
votes
1
answer
137
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,131
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
312
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 ...
- 496
0
votes
1
answer
87
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
...
- 496
2
votes
1
answer
84
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 ...
- 778
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
-3
votes
1
answer
539
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
315
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
282
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
107
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.
- 496
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:
...
- 496
2
votes
1
answer
132
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 ...
- 496
18
votes
0
answers
355
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,718
1
vote
0
answers
226
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,196
6
votes
2
answers
310
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 ...
- 829
7
votes
1
answer
349
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,983
17
votes
0
answers
523
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,983
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
479
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.5k
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,631
1
vote
0
answers
112
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
2
votes
2
answers
151
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
106
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
233
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 ...
- 293
10
votes
1
answer
341
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,586
5
votes
1
answer
212
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
322
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
2
votes
1
answer
164
views
Cryptography with very small keys
Is anything known about doing cryptography with very small keys? In particular, is there any theory involving cryptosystems (based on whatever assumption you want) that can encrypt messages of length ...
- 11.9k
3
votes
0
answers
77
views
One kind of dependence relation between a pair of random variables
I have been working on privacy and come across a neat problem.
Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{...
- 425
4
votes
1
answer
205
views
Cryptographic systems that don't leak linear combinations of encrypted bits
Various encryption schemes would be considered broken if an adversary could have a non-negligible edge in predicting the first (or any) bit of an encrypted message. I am looking for a slightly ...
- 11.9k