4
$\begingroup$

I'm a student of Masters in Cyber Security. I have a habit to understand things from their first principles (at the very beginning). Kindly use any simple mathematical example to answer because I have read plenty of technical answers but they aren't clear to me. For example, we use primes because we know factoring them is extremely hard. Furthermore, we use injectives because we don't want one to many relations in encryption because it will be a disaster on the decryption side. Same like my examples can you provide me an example of using groups that makes sense as primes and injective do?Kindly, let me know what was the actual problem which leads us to use groups in cryptography?

I know what a group is and its properties, I know about abstract algebra, but I don't know why we use them and what happens if we don't use them.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ This is a too broad. The simple answer their hard properties. RSA factoring ( RSA problem). EC forms an additive group where most of the time the DLOG is hard. Multiplicative groups, too. Lattice groups have hard problems that enables us to form encryption, signatures, etc... $\endgroup$ – kelalaka Apr 4 at 22:40
  • $\begingroup$ sorry, I didn't get you properly, I just need a simple math example about why we use groups. $\endgroup$ – Zain Apr 4 at 23:09
  • 2
    $\begingroup$ You did not provide what is not clear to you! Here Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y? $\endgroup$ – kelalaka Apr 4 at 23:11
  • 2
    $\begingroup$ @Zain: 1) "which doesn't let the number go beyond our imaginations" - 2^256 is definitely beyond our imagination. And RSA operates also with bigger numbers, e.g. modulo of the order 2^8192. It is definitely beyond our imagination. The reasons to use groups and fields have nothing to do with human cognitive capabilities. 2) Please tell us why the link provided by kelalaka and the mentioned problems like RSA factoring or DLOG do not answer your question. $\endgroup$ – mentallurg Apr 5 at 0:00
  • 1
    $\begingroup$ Your question might be easier to answer if you mention what sorts of things you expect to be used. You mentioned something about a system "which doesn't let the number go beyond our imaginations." If you're talking about the real numbers, you should note that they are also a field (and hence a ring and a group as well). $\endgroup$ – Aman Grewal Apr 5 at 0:47
15
$\begingroup$

Kindly, let me know what was the actual problem which leads us to use groups in cyptogrpahy?

Well, we use groups and other similar mathematical constructs because:

  • We found there are problems that appeared to be difficult to solve with those groups

  • We found ways to translate the difficulty of solving those problems into the cryptographical strength of some object (such as an RSA public key encryption, or a signature), that is, you can't break the cryptographical object (e.g. decrypt the encrypted ciphertext without the key) unless you can solve the hard problem.

The second part is crucial; we know problems that are much harder to solve than the ones we use in cryptography; however we don't know how to exploit those.

That's pretty much the answer; the answer to "why do we use groups" is pretty much the same as Willy Sutton supposedly gave to the question "why do you rob banks" - "because that's where the money is" - that is, we do it because it provides the cryptographical security we're looking for.

I believe if I don't know "why" then everything is useless.

Then you're in trouble with cryptography - one of the things we do not know is why these hard problems are actually hard (if, in fact, they are) - the most we know is that a number of fairly bright people have tried to do a number of rather clever tricks to solve them, and none of them worked.

Improve this answer
$\endgroup$
3
  • $\begingroup$ For example, we use primes because we know factoring them is extremely hard. furthermore, we use injectives because we don't want one to many relations in encryption because it will be a disaster on the decryption side. Same like my examples can you provide me any example of using groups which makes sense as primes and injectives does? $\endgroup$ – Zain Apr 5 at 20:37
  • 1
    $\begingroup$ @Zain: Do you care why factoring primes is hard? $\endgroup$ – MSalters Apr 6 at 8:00
  • $\begingroup$ @Zain -- We actually don't actually know if factoring primes is hard. We think it is, and many smart people have tried and failed to find efficient ways to do factor primes, but there is no proof of such. In fact, there has been progress at finding more efficient ways to factor primes, but so far not enough to render prime-factoring-based cryptosystems useless (you just have to use really big primes). $\endgroup$ – Gavin S. Yancey Apr 6 at 11:27
8
$\begingroup$

Groups have properties which are useful for many cryptographic operations

  • When you multiply 2 numbers in a cryptographic operation you want the result of the multiplication also to be in the same set. For e.g. if you are multiplying something which fits in a byte (or n bytes) by something similar, you also want the result also to fit in a byte (or n bytes). Groups have the closure property which ensures this

  • When you want to decrypt something which is encrypt, many a times the decryption is an inverse of the encryption. Elements of a Group are invertible so again that is needed.

There are other properties of Groups which are useful in other specific cases. For e.g. in AES's MixColumn operation, the associativity property is needed. Like this you will find a lot of cryptographic operations which require many of the properties.

Rings & Finite Fields are also Groups, so they also have the same properties. Groups have Closure, Associativity & Inverse under only one Arithmetic operation. However, Finite Fields have Closure, Associativity, Identity, Inverse, Commutativity under both 2 Arithmetic operations (for e.g. Addition & Multiplication).

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I agree with the compact representation, although it's not very precisely stated. $(\mathbb{Z},+)$ is a group but results are not compact. $\endgroup$ – Fractalice Apr 5 at 8:44
  • 1
    $\begingroup$ @user93353 integers with addition form a group but they don't have the property that adding elements preserves size (200 fits in a byte but 200+200 does not). $\endgroup$ – Fractalice Apr 5 at 13:00
  • 1
    $\begingroup$ @Fractalice - you could define a group such that they fit. I am not saying all groups will result in byte + byte = byte $\endgroup$ – user93353 Apr 5 at 13:09
  • 2
    $\begingroup$ I don't find this argument very convincing; it appears to just take "Why do we like groups?" and expand the definition of group but keep the same question. For example, you say, "When you multiply 2 numbers in a cryptographic operation you want the result of the multiplication to be in the same set", but why do you want that? For that matter, why do you want to multiply 2 numbers? That's not what I want; what I want is to keep my information secret from somebody else. $\endgroup$ – Daniel Wagner Apr 5 at 17:27
  • 1
    $\begingroup$ @DanielWagner not OP, but variable length encodings tend to lead to timing side-channels. This is an argument for cryptographic operations where elements come from finite sets though (which is a reason why the group $(\mathbb{Z}, +)$ is perhaps not useful for cryptography). $\endgroup$ – Mark Apr 5 at 19:17
4
$\begingroup$

The problem with "why"

"Why" is generally an unfortunate question. It is often very hard or impossible to answer. The reasoning goes like this: if you ask "why" a (reasonably complex) thing is like it is, any meaningful answer usually breaks the issue down into subcomponents. Then, you can and need to ask "why" for each of those. This goes on and on ad nauseam. Either you end up with more and more ever more complex answers and questions; or you eventually lose the semantics along the convoluted path, or you end up with subquestions that simply have no meaningful "why" answer at all.

A popular example would be children asking why the sky is blue. With a "nerd" child, you can spend a lot of time on that. It's not uninteresting, and not futile, and being inquisitive is great, but it's often frustrating.

There is a nice video from Feynman himself explaining this: https://www.youtube.com/watch?v=36GT2zI8lVA

Why do we use rings, groups, fields in cryptography

We use these structures in cryptography because in modern times, cryptography inevitably works on natural numbers as their base domain, and nothing else. Why is that the case? Because in our current computer architecture, all data is represented as natural numbers sooner or later, and therefore it only makes sense to focus all our efforts on this common denominator, instead of having different cryptography for images, text, sound etc..

Rings, groups, fields and other structures are literally what makes up numbers (or rather the semantics on numbers). There is no magic to this. Every child is working with these structures even when learning to count to 100, they just don't know it yet. It's not like mathematicians saw all the problems of cryptography, tried 10 alternatives, until someone said "hey, let's take rings", but whenever you are working with numbers, you inevitable end up with some of these structures.

It's not like we invented all these structures (people have been multiplying and adding long before these terms or the strict understanding of their structure were around); we just use them to label some very restrictive sets with their operations. Other labels or definitions could probably have been arrived at.

A direct example is the RSA public key algorithm. It is a conceptionally simple set of operations in modular arithmetic (i.e. $\mathbb N_n$ with $n$ being a very large integer with the property $n = pq$, with $p$ and $q$ being large primes). When working with these things, the only way we know how is to work with operators (multiplication...) which form a group structure. Ignoring key generation, the actual encryption and decryption is a single operation: exponentiation in modular algebra. Understanding why it works is easy even if someone only had a few first lessons in algebra, to define the terms. Hence we are using groups here (or rather some practical proofs from group theory) because they are the correct tool, they make it easy to reason about the algorithm and prove the correctness, and very easy to implement.

As a side point, not directly related to the question: Here, it just so happens that this operation also is very simple for a computer to perform. The inverse (which would be equivalent to cracking the code) is very hard. "Why" that is (on a philosophical level) is impossible to tell, except we didn't find a way to do yet. Nobody knows if it is fundamentally impossible to ever find an efficient algorithm to invert this.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is a scary thought that there may not be an objective reality to which we have access and there may not be an objective cause for an effect. Rather this cause may be the result of debate and consensus among a group of people. A group of people with similar background will tend to agree easier on something as opposed to an engineer and a medic. Once you work in crypto for 5 years you will probably agree with a lot of things posted here. But in doing this you might also loose some perspective. Embrace crypto but do not loose critical thinking. Good luck @Zain $\endgroup$ – Roman Gherta Apr 6 at 22:46
4
$\begingroup$

I think you got it backwards:

Algebraic structures like rings and groups and fields are the underlying concept of all commonly used types of numbers like the integers, rationals, reals and complex numbers. In algebra it is quite common to do theorems and proofs in the structure with the minimum requirements - so they are valid in a wide range of structures, and not just in the integers for example.

School math and possibly university courses intended for non-mathematicians are simplified versions of that: The numbers are just there, they skipped the basics of explaining where the numbers come from and what axioms and definitions have been made.

When it comes to cryptography, you already mentioned one relevant example: Factorization of large numbers is difficult. But that is just a problem - on its own this is not enough to create an encryption scheme. If we look at RSA, then everything happens inside a specific finite ring: all calculations happen modulo N.

Another example: ElGamal is a cryptosystem, which is based on the discrete logarithm - which is also a difficult problem like factorization. But the discrete logarithm problem is defined inside a finite group. And it has very little to do with logarithms on real numbers besides the name. And this finite group can be all integers modulo a prime number - or it can be an elliptic curve, which is another type of finite group.

I know what a group is and its properties, I know about abstract algebra, but I don't know why we use them and what happens if we don't use them.

How do you want to "not use them"? If you think about integers, they are a ring, which is a group (for addition) and a semi group (for multiplication). Or more generally: From what do you want to build an encryption scheme, signature scheme, etc? Cryptography has to build on some structure. And for most public key cryptography, this structure is finite groups, rings and fields.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ I would disagree with this; one can certainly define mathematical objects that do not fit within the group/ring/field paradigms (e.g. latin squares); we generally don't, because the standard solutions appear to give better (that is, more useful) answers $\endgroup$ – poncho Apr 5 at 19:17
  • $\begingroup$ may be you are rigth but i know the basics, but i don't know the use of them in cryptography. for example, we use primes because we know factoring them is extremely hard. furthermore, we use injectives becasue we dont want one to many relation in encryption becasue it will be a disaster on the decryption side. Same like my examples can you provide me any example of using groups which makes sense as primes and injectives does? $\endgroup$ – Zain Apr 5 at 20:35
  • $\begingroup$ @poncho I did not state they are the only structures that exist. But you're right, I should have specified that statement more precisely. $\endgroup$ – tylo Apr 13 at 13:25
  • $\begingroup$ @tylo: "The only thing more basic would be set theory"; that certainly sounds like you are claiming we don't know of any object that has more structure than a set which is not a group... $\endgroup$ – poncho Apr 13 at 13:31
  • $\begingroup$ @poncho I am already editing the answer. But you misunderstood what my point was. It was meant exactly the opposite way: groups build upon sets by adding structure. $\endgroup$ – tylo Apr 13 at 13:38
3
$\begingroup$

Maybe I can give another answer from the perspective of Multiparty Computation (MPC), which studies the problem of enabling multiple parties to securely compute a function on sensitive data while revealing only the outputs.

A very important tool for solving the problem stated above is secret-sharing, which enables distribution of a secret $s$ into $n$ shares $s_1,\ldots,s_n$, in such a way that any set of at most $t$ shares does not leak anything about the secret, but any set of $t+1$ shares can completely reconstruct it. One of the most popular secret-sharing constructions is Shamir Secret Sharing, in which a secret $s$ is distributed by choosing a random polynomial $f$ of degree at most $t$, subject to $f(0)=s$, and letting the $i$-th share be $s_i:=f(i)$.

The idea why this construction works is that, due to the interpolation theorem, any set of $t+1$ points $(i,f(i))$ completely determine a unique polynomial of degree at most $t$, so in particular they determine $s=f(0)$, but only $t$ such points can be consistent with too many polynomials of degree at most $t+1$ as to be able to determine $s$. Now, for all of this to make sense, the elements need to belong to some algebraic structure (in particular a ring, since we're talking about polynomials). Furthermore, as stated, this structure has to be a field, since otherwise the interpolation theorem does not hold.¹

So, to sum up, there are some contexts where we benefit a lot from the additional properties that certain structures have. In the case of fields, the fact that there are no zero divisors really makes life easier.

¹The interpolation theorem also works for more general rings, but you they still need to have certain properties, like a long-enough exceptional sequence.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.