Questions tagged [cryptography]
The cryptography tag has no usage guidance.
9
questions
-1
votes
0answers
65 views
Randomic sequence based on Kolmogorov complexity: why $K(h) ≥ |h| - ⌈log_2|h|⌉$?
I'm reading a textbook about cryptography where it is explained the concept of randomic sequence based on Kolmogorov complexity.
The textbook reports that a sequence $h$ can be considered randomic if $...
1
vote
0answers
45 views
Living in Minicrypt, but sampling hard instances without the solution
In Impagliazzo's worlds, Minicrypt is the one, where one way functions exist.
In other words, we can sample hard-on-average instances of NP complete problems.
Question:
Is living in Minicrypt, where ...
0
votes
0answers
11 views
Direct Diffie-Hellman by Shor's algorithm
Shor's algorithm appears to be capable of finding discrete logarithm even if the modulus is composite. Does the algorithm implicitly compute the Carmichael Lambda which goes in the exponent or somehow ...
5
votes
0answers
70 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 ...
0
votes
0answers
69 views
RSA as an Hidden Subgroup Problem
the Hidden Subset Problem (HSP) covers several known problems (e.g. Integer Factorization Problem, Discrete Logarithm Problem) as a special case:
Definition [Hidden Subgroup Problem (HSP)] Let $\...
0
votes
0answers
34 views
Must the cryptographic test for quantumness in [BCMVV18] use post-quantum Trapdoor Claw-Free Functions?
Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable computational quantumness based on a strengthening of trap-door claw-free functions (TCFs).
In the above scheme:
...
0
votes
0answers
26 views
Encrypt an explicit circuit
Suppose we are given a circuit that are promised to be in a fixed class $\mathcal{C}$ (say AC^0). We want to “encapsulate” the circuit such that the resulting circuit computes the same function, while ...
0
votes
0answers
41 views
Examples of inverse of trapdoor functions non-learnable with black-box query access?
The (informal) definition of trapdoor function is a one-way function with a trapdoor $t$ such that
given $f$, it is easy to compute $f(x)$ for any $x$, but hard to compute $f^{-1}(y)$ efficiently
...
3
votes
1answer
135 views
Is there a notion of indistinguishability obfuscation for almost equivalent circuits?
In the definition of indistinguishability obfuscation (iO), we have a probabilistic algorithm Obs that receives as input a circuit C, such that $i)$ the output Obs(C) is a circuit with the same ...
