The Status of the P Versus NP Problem

[gasparosoft]

When editor-in-chief Moshe Vardi asked me to write this piece for Communications, my first reaction was the article could be written in two words:

Still open.

When I started graduate school in the mid-1980s, many believed that the quickly developing area of circuit complexity would soon settle the P versus NP problem, whether every algorithmic problem with efficiently verifiable solutions have efficiently computable solutions. But circuit complexity and other approaches to the problem have stalled and we have little reason to believe we will see a proof separating P from NP in the near future.

Nevertheless, the computer science landscape has dramatically changed in the nearly four decades since Steve Cook presented his seminal NP-completeness paper "The Complexity of Theorem-Proving Procedures"10 in Shaker Heights, OH in early May, 1971. Computational power has dramatically increased, the cost of computing has dramatically decreased, not to mention the power of the Internet. Computation has become a standard tool in just about every academic field. Whole subfields of biology, chemistry, physics, economics and others are devoted to large-scale computational modeling, simulations, and problem solving....

More

[enum21]

...if P = NP then public-key cryptography becomes impossible. True, but what we will gain from P = NP will make the whole Internet look like a footnote in history.

Και πιο κάτω

In "What If P = NP?" we saw the nice world that arises when we assume P = NP. But we expect P ≠ NP to hold in very strong ways. We can use strong hardness assumptions as a positive tool, particularly to create cryptographic protocols and to reduce or even eliminate the need of random bits in probabilistic algorithms.

Cryptography. We take it for granted these days, the little key or lock on our Web page that tells us that someone listening to the network won't get the credit card number I just sent to an online store or the password to the bank that controls my money. But public-key cryptography, the ability to send secure messages between two parties that have never privately exchanged keys, is a relatively new development based on hardness assumptions of computational problems.

If P = NP then public-key cryptography is impossible. Assuming P ≠ NP is not enough to get public-key protocols, instead we need strong average-case assumptions about the difficulty of factoring or related problems.

Πώς λειτουργεί η public-key cryptography?

[gasparosoft]

Η ιδέα είναι η εξής: Έχεις 2 keys στην κατοχή σου. Ένα private κι ένα public. Το public μπορεί να το δει ο καθένας ενώ το private το ξέρεις μόνο εσύ(για αυτό άλλωστε ονομάζονται και public , private αντίστοιχα).
Αν θέλει κάποιος να σου στείλει ένα message , τότε το κάνει encrypt με το public key σου. Μόνο ο κάτοχος του private key μπορεί να το κάνει decrypt(ο οποίος είσαι εσύ φυσικά. Αυτό γίνεται με την βοήθεια μαθηματικών , βλέπε discrete logarithm problem ,Integer factorization and rsa problem κτλ).
Πέρα όμως από την χρήση του για encryption/decryption μηνυμάτων , μπορεί να χρησιμοποιηθεί και στα digital signatures. Εκεί η διαδικασία είναι αντίστροφη. Για να ταυτοποιήσεις το μήνυμά σου(κάτι σαν την υπογραφή στην πραγματικότητα) το κάνεις encrypt με το private key. Ε οποιοσδήποτε τώρα μπορεί να το κάνει decrypt με το public key σου και να πάρει πίσω το κανονικό μήνυμα.

Φυσικά δεν είναι αποδοτική η public cryptography λόγω των πολύπλοκων μαθηματικών και των πολύ μεγάλων κλειδιών(κάνοντας έτσι τον αλγόριθμο αργό για μεγάλη είσοδο) για αυτό χρησιμοποιείται σε συνδυασμό με symmetric key cryptography. (Ουσιαστικά κάνεις encrypt το symmetric key και στέλνεις αυτό το οποίο είναι συνήθως 256 bits.)
Eπίσης ούτε τα digital signatures λειτουργούν έτσι. Πρώτα κάνεις την διαδικασία που σου περιέγραψα παραπάνω και μετά hash το message με έναν secure hash algorithm έτσι ώστε να μικρύνεις το μέγεθος του(256-512 bits) και να το στείλεις μαζί με το encrypted message.

Edit: Ελπίζω να έγινα κατανοητός , γιατί δεν είναι ένα από τα προσόντα μου(δυστυχώς). Αν θέλεις παραπάνω πες μου

[enum21]

Ναι έγινες απόλυτα κατανοητός και σ' ευχαριστώ!!

Τώρα, όσον αφορά τη symmetric-key cryptography αν κατάλαβα καλά από την περιγραφή που έκανες θα πρέπει να είναι πιο γρήγορη και ίσως πιο απλή από τη public,σωστά? Είναι όμως το ίδιο ασφαλής ή λιγότερο? Γιατί όσο να' ναι στη δεύτερη υπάρχει το private key, εδώ? Θέλω να πω με ποιον τρόπο θα γίνει το αντίστοιχο decrypt του μηνύματος?

[gasparosoft]

Στην symmetric key cryptography υπάρχει ένα κοινό key. Πρέπει να το ξέρει και ο sender και ο receiver. H δυσκολία ήταν πριν ανακαλυφθεί η public key cryptography να στείλεις το key στον παραλήπτη(έπρεπε να τον συναντήσεις από κοντά ή να βρεις κάποιον άλλο ασφαλή τρόπο , πράγμα που ήταν μεγάλη σπατάλη χρόνου και χρημάτων ίσως). Με την public key cryptography αυτό λύθηκε όπως σου περιέγραψα.
Τώρα υπάρχουν 2 είδη από symmetric ciphers: Stream ciphers και block ciphers(οι πρώτοι χρησιμοποιούνται πιο πολύ στην Ευρώπη).Ο stream cipher κάνει encrypt το message bit by bit με ένα pseudorandom keystream(εντελώς random δεν γίνεται δυστυχώς , τα παράπονα στον turing ).
Από την άλλη ένας block cipher κάνει encrypt το message ανά blocks(128 bits ο ΑΕS(128-192-256 bits το key) και 64 bits ο ξεπερασμένος DES(56 bits το key)). Τώρα υπάρχουν διάφοροι τρόποι σπασίματος των αλγορίθμων αυτών. Ο DES παρότι παλιός η πιο πρακτική επίθεση είναι με brute force attack(δοκιμάζει όλα τα keys που είναι 2^56 - πλέον λόγο του μικρού κλειδιού σπάει πολύ γρήγορα (για αυτό μετά χρησιμοποίησαν τον 2DES ,3DES)). Νομίζω και για τον ΑΕS ισχύει το ίδιο(αλλά λόγω μεγαλύτερου κλειδιού θέλει εκατομμύρια χρόνια για να το βρεις). Υπάρχουν και άλλα κόλπα , βλέπε related key attacks , linear and differential cryptanalysis κτλ.
Ουσιαστικά παρότι το key ενός public key algorithm είναι πάνω από 2048 bits , η ασφάλεια που προσφέρουν είναι πάνω κάτω η ίδια. Απλώς χρησιμοποιούμε ένα hybrid cryptosystem (αυτό που περιέγραψα στο προηγούμενο ποστ) λόγω ταχύτητας και αποτελεσματικό key-exchange(βέβαια κι εδώ έχουμε προβλήματα αλλά υπάρχουν πάρα πολλά protocols).
Γενικά η public key cryptography βασίζεται σε μαθηματικά προβλήματα. Οπότε ένα λάθος implementation τα κάνει όλα άνω κάτω ενώ οι symmetric key algorithms βασίζονται στο confusion and diffusion.

[enum21]

Αρκετά ενδιαφέροντα πράγματα!! Υπάρχουν άλλα είδη εκτός από τη public & symmetric-key cryptography? Δεν θέλω να σε κουράσω άλλο,παίζει και η Ελλάδα τώρα...

Επίσης με βάση το άρθρο που postαρες στάθηκα και εδώ

Approaches to Showing P ≠ NP
Here, I present a number of ways we have tried and failed to prove P ≠ NP...

Και θεώρησα αρκετά χρήσιμο να ψάξω γιατί οι περισσότεροι επιστήμονες προσπαθούν να αποδείξουν αυτό -> P ≠ NP και αν υπάρχουν άλλοι που δρουν προς την άλλη πλευρά.

Μερικές απαντήσεις:

According to a poll,[5] many computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems, no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.

It is also intuitively argued that the existence of problems that are hard to solve but for which the solutions are easy to verify matches real-world experience.[10]

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...
— Scott Aaronson, MIT

On the other hand, some researchers believe that we are overconfident in P ≠ NP and should explore proofs of P = NP as well. For example, in 2002 these statements were made:[5]

The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. [. . .] The resolution of Fermat's Last Theorem also shows that very simply [sic] questions may be settled only by very deep theories.
—Moshe Y. Vardi, Rice University

Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.
—Anil Nerode, Cornell University

από wiki

[proskopos]

Ναι έγινες απόλυτα κατανοητός και σ' ευχαριστώ!!

Τώρα, όσον αφορά τη symmetric-key cryptography αν κατάλαβα καλά από την περιγραφή που έκανες θα πρέπει να είναι πιο γρήγορη και ίσως πιο απλή από τη public,σωστά? Είναι όμως το ίδιο ασφαλής ή λιγότερο? Γιατί όσο να' ναι στη δεύτερη υπάρχει το private key, εδώ? Θέλω να πω με ποιον τρόπο θα γίνει το αντίστοιχο decrypt του μηνύματος?

Όπως θα έλεγε,νομιζω και ο κ. Γκρίτζαλης, δεν υπάρχει λιγότερο ή περισσότερο ασφαλείς τρόπος κρυπτογράφησης, αλλα λιγότερο ή περισσότερο αποτελεσματικός αλγόριθμος... Και οι 2 τρόποι ειναι ασφαλής, αρκεί να τους χρησιμοποιείς σωστά...
Κάτι που συγκράτησα απο το μάθημα της ασφάλειας, σχετικά με το θέμα μας είναι το εξης:

Tα συμμετρικά συστήματα έχουν σαν πλεονέκτημα (περιληπτικά):
1)Δύσκολη Κρυπτανάλυση
2)Χρησιμοποιούν εύκολες μαθηματικές μεθόδους
3)Η κρυπτογράφηση και η αποκρυπτογράφηση είναι γρήγορες διαδικασίες
Μειονεκτήματα:
1)Ανάγκη για ασφαλή φύλαξη κλειδιών
2)Ανάγκη για ασφαλή διανομή του δημοσίου κλειδιού

Αντίστοιχα τα ασύμετρα έχουν:
1)Έυκολη διανομή δημοσίων κλειδιών
2)Οποιοσδήποτε μπορεί να στείλει κρυπτογραφημένο ένα μήνυμα που μόνο ο σωστός παραλήπτης θα μπορέσει να το διαβάσει.
Μειονεκτήματα:
1)Μεγάλος χρόνος για κρυπτογράφηση+αποκρυπτογράφηση
2)Μαθηματικά απαιτητικές διαδικασίες
3)Κίνδυνος παραγοντοποίησης δημοσίου κλειδιού και αποκάλυψης ιδιωτικού.

Για να δούμε τις δυνατότητες που θα προκύψουν από τον συνδυασμό των συστημάτων πρέπει να δούμε πως θα τα συνδέσουμε
Ιδέα:Να χρησιμοποιήσουμε τους αλγόριθμους δημοσίων κλειδιών(ασύμετρα) για την μετάδοση των κλειδιών των αλγορίθμων ιδιωτικού κλειδιού(συμμετρικά).

Έτσι θα έχουμε τα εξής πλεονεκτήματα:
1)Ασφαλή-Έυκολη διανομη του κλειδιού(ασύμετρα συστήματα)
2)Η διαδικασία θα είναι ταχύτατη.(όπως στην περίπτωση των συμμετρικών συστημάτων)
3)Δύσκολη κρυπτανάλυση(συμμετρικά συστήματα)
4)Έχουμε χρήση ενός μόνο κλειδιού για κρυπτογράφηση-αποκρυπτογράφηση(συνεπώς γλυτώνουμε το κίνδυνο αποκάλυψης του κλειδιού μέσω παραγοντοποίησης)
5)Μαθηματικά εύκολες διαδικασίες.
Τα μειονεκτήματα είναι αυτά που κληρονομούμε λόγω του συνδυασμού:
1)Εξακολουθεί να υπάρχει ανάγκη για ασφαλή φύλαξη του κλειδιού
2)Πλεόν δεν μπορεί οποιοσδήποτε μπορεί να στείλει κρυπτογραφημένο ένα μήνυμα που μόνο ο σωστός παραλήπτης θα μπορέσει να τα διαβάσει.

[enum21]

Ναι ίσως δεν ήμουν και τόσο καλή στη διατύπωση του μειονεκτήματος των συμμετρικών κλειδιών, άλλωστε δεν έχω κάνει ασφάλεια (ακόμα ).

Όπως ανέφερε και ο gasparosoft πιο πάνω

H δυσκολία ήταν πριν ανακαλυφθεί η public key cryptography να στείλεις το key στον παραλήπτη(έπρεπε να τον συναντήσεις από κοντά ή να βρεις κάποιον άλλο ασφαλή τρόπο , πράγμα που ήταν μεγάλη σπατάλη χρόνου και χρημάτων ίσως).

Αυτό μου φάνηκε ότι δεν είναι ασφαλής διαδικασία

Όσον αφορά το πλεονέκτημα 4

4)Έχουμε χρήση ενός μόνο κλειδιού για κρυπτογράφηση-αποκρυπτογράφηση(συνεπώς γλυτώνουμε το κίνδυνο αποκάλυψης του κλειδιού μέσω παραγοντοποίησης)

δεν αναιρεί τον κανόνα 1?

1)Ασφαλή-Έυκολη διανομη του κλειδιού(ασύμετρα συστήματα)

Ή κάτι δεν έχω καταλάβει σωστά?

[gasparosoft]

Αυτό αποτελεί το hybrid cryptosystem.
Το 1 αφορά την μεταφορά του κλειδιού(που χρησιμοποιείται από τον symmetric algorithm) encrypted με έναν asymmetric algorithm.
Το 4 αφορά το symmetric key το οποίο είχες κρυπτογραφήσει με τον asymmetric algorithm.
Ουσιαστικά είναι τα πλεονεκτήματα των asymmetric και symmetric algorithms αντίστοιχα.

[adam98]

Enum21 πάρε το μάθημα της Ασφάλειας ΠΣ φέτος και θα δεις αυτά που ρωτάς και πολλά άλλα.