Questions tagged [cryptography]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-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 ...