Reputation
5,962
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
1 8 22
Newest
 Informed
Impact
~66k people reached

Apr
18
answered State of the art low memory arbitrary-domain PRP?
Apr
18
comment State of the art low memory arbitrary-domain PRP?
If ​ 2^(2^128) < n ​ then encryption just outputs the plaintext and decryption just outputs the ciphertext. ​ ​ ​ If ​ n ≤ 2^(2^128) ​ then sometimes-recurse shuffle with 128 bits of security. ​ ​ ​ ​ ​ ​ ​ ​
Apr
18
comment State of the art low memory arbitrary-domain PRP?
If we take [b being fixed] completely seriously, then O(1) memory suffices - If ​ 2^(2^b) < n ​ then use the identity function on Zn, else use any PRP on Zn. ​ ​ ​ To avoid that, one must assume some relation between n and b. ​ ​ ​ I had initially been assuming log(n) was significantly less than b (making things more difficult), but it now seems like your interested in when log(n) is significantly greater than b. ​ ​ ​ ​ ​ ​ ​ ​
Apr
18
comment State of the art low memory arbitrary-domain PRP?
Oohh, is your space requirement for when log(n) is not significantly less than b? ​ (I was assuming the other way around.) ​ ​ ​ ​
Apr
18
comment State of the art low memory arbitrary-domain PRP?
Does it seem to have a security level significantly above 512 bits? ​ ​
Apr
18
comment Meaning of “random n/2 bit prime length prime p”
Your title has one more "prime" than your post's body. ​ ​
Apr
18
comment State of the art low memory arbitrary-domain PRP?
Is there even a PRF with such low space requirements? ​ ​
Apr
18
comment Is the following obfuscation weak in security or not?
Are {the operations on the line just above those} in {the q-element meadow}? ​ ​
Apr
18
comment Is the following obfuscation weak in security or not?
Is $\leftarrow$ supposed to denote setting the left variable to a random entry of the right tuple? ​ ​
Apr
18
comment Two-party equality computation
crossposted from mathoverflow after less than 5 minutes, without mentioning that on either site ​ ​
Apr
18
comment Differences between OWP and OWF and their IND-CPA security
The paper giving a more efficient construction of PRGs from OWFs is this one. ​ ​
Apr
17
comment How to Perform Computation on AES Encrypted Data
To answer your question: ​ Implement sufficiently homomorphic encryption and provide $\hspace{.8 in}$ [an encryption of the AES key with the homomorphic scheme]. ​ ​ ​ ​
Apr
13
comment Committing to a secret shared value
(continued ...) ​ ​ ​ (I might be able to prove that, for example, Shamir has no such way if I had a definition of what it means for a multi-party computation protocol internally "reconstruct the output value".) ​ The obvious alternative is having the initial multi-party computation protocol output encapsulations of the shares to everyone and give each party decapsulating info for its share. ​ ​ ​ ​ ​ ​ ​ ​
Apr
13
comment Committing to a secret shared value
If reconstruction takes everyone and the storage requirements are nearly minimal, then that's simply impossible. ​ (xor sharing satisfies those two conditions.) ​ If the secret sharing scheme instead merely doesn't provide a way to verify shares individually, then I don't see any way to avoid having the multi-party computation protocol internally "reconstruct the output value". ​ ​ ​ (... continued) ​ ​ ​ ​ ​ ​ ​ ​
Apr
12
revised How does Microsoft's BitLocker Recovery Code work?
improved grammar
Apr
12
comment Secret construction
edited answer ​ ​
Apr
12
revised Secret construction
modified to fit current question
Apr
12
answered Secret construction
Apr
12
comment Secret construction
Do you have particular security properties in mind? ​ ​
Apr
11
revised How are all necessary parameters shared between signer and verifier in ED25519 signature scheme?
improved title's grammr