Cryptography Question on subgroups in Elgamal/DH |
- Question on subgroups in Elgamal/DH
- Is a randomly selected permutation size (2^n)! the strongest possible symmetric crypto algorithm on n bits (ignoring efficiency)?
- Homomorphic npcomplete is a step below but could lead to homomorphic turingcomplete. Homomorphic crypto is on a process, not just the data it processes. Tor encrypts data and addresses but doesnt run custom software. Ethereum runs custom software reliably, though its computing state is public.
| Question on subgroups in Elgamal/DH Posted: 08 Aug 2018 07:51 PM PDT I'm reading about attacks on the Discrete Logarithm Problem, and one of them, the Pohlig-Hellman algorithm, does a prime factorization of the order of a group. You can't have a group in a multiplicative finite cyclic group with a prime order if your group is over a finite field, right? Since you modulo some prime, then the group order is p - 1, which isn't prime. So, do you need the subgroup to have a prime order in order to prevent this kind of attack? Is the subgroup just for faster encryption since the order of the subgroup is less than the order of the prime field? [link] [comments]  |
| Posted: 08 Aug 2018 04:24 AM PDT
There are (2n)! possible symmetric crypto algorithms on n bits, ignoring preprocessing and postprocessing. Such a permutation could impractically and inefficiently be written as a list of the first 2n nonnegative integers. There are more compressed ways to write a permutation, such as a sequence of permutations is a permutation. If the same permutation were used in multiple ways, it would be smaller. Finding the smallest compression of a certain bitstring, limited to any specific maximum compute cycles and memory, is npcomplete (too hard to find the best except for maybe up to 20 bits, but it means there are better ops for us to find). So it may be that we can randomly select from all possible permutation functions on 2n possibilities of n bits, by storing some of the permutation function in its behaviors depending on certain inputs/outputs (which must be reversible) instead of the algorithm itself needing 2n amount of storage to be 1 of those (2n)! possible permutation functions. Either way, is a randomly selected permutation function of 2n input and output the strongest possible symmetric crypto algorithm on n bits (ignoring efficiency)? [link] [comments]  |
| Posted: 08 Aug 2018 05:47 AM PDT Can a forest of nands (npcomplete) and the input bits, be encrypted, compute the values of the nands up to the output nand, and return the output without knowing the plaintext form of the nands? A nand is logic between 3 bits. 4 of their 8 possible states are allowed. Turingcomplete homomorphic crypto would be on operators such as lambda or turingMachine or rule110 or conwaysGameOfLife. rule110 is an npcomplete operator that when applied repeatedly without memory jumps (is a 1d cellular automata), or view time as a dimension so 2d timelessly, is turingComplete. For example. If a forest of nand or 2d grid of rule110 relating distant 2d cells, can be encrypted to maximum entropy, using subexponential time and memory after its found, even if it costs exponential compute cycles and memory to find that maximum entropy, then P!=NP. If it cant, then P=NP. [link] [comments]  |
| You are subscribed to email updates from Cryptography news and discussions. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment