Muutke küpsiste eelistusi

E-raamat: Non-commutative Cryptography and Complexity of Group-theoretic Problems

, ,
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 145,86 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Non-commutative Cryptography and Complexity of Group-theoretic ProblemsSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

This book is about relations between three different areas of mathematics and theoretical computer science: combinatorial group theory, cryptography, and complexity theory. It explores how non-commutative (infinite) groups, which are typically studied in combinatorial group theory, can be used in public key cryptography. It also shows that there is remarkable feedback from cryptography to combinatorial group theory because some of the problems motivated by cryptography appear to be new to group theory, and they open many interesting research avenues within group theory. In particular, a lot of emphasis in the book is put on studying search problems, as compared to decision problems traditionally studied in combinatorial group theory. Then, complexity theory, notably generic-case complexity of algorithms, is employed for cryptanalysis of various cryptographic protocols based on infinite groups, and the ideas and machinery from the theory of generic-case complexity are used to study asymptotically dominant properties of some infinite groups that have been applied in public key cryptography so far. This book also describes new interesting developments in the algorithmic theory of solvable groups and another spectacular new development related to complexity of group-theoretic problems, which is based on the ideas of compressed words and straight-line programs coming from computer science.
Preface xiii
Introduction 1(6)
Part 1 Background on Groups, Complexity, and Cryptography
Chapter 1 Background on Public-Key Cryptography
7(6)
1.1 From key establishment to encryption
8(1)
1.2 The Diffie-Hellman key establishment
8(1)
1.3 The EIGamal cryptosystem
9(1)
1.4 The RSA cryptosystem
10(1)
1.5 Rabin's cryptosystem
11(1)
1.6 Authentication
11(2)
1.6.1 The Feige-Fiat-Shamir scheme
12(1)
Chapter 2 Background on Combinatorial Group Theory
13(12)
2.1 Basic definitions and notation
13(1)
2.2 Presentations of groups by generators and relators
14(1)
2.3 Algorithmic problems of group theory: decision, witness, search
15(5)
2.3.1 The word problem
15(1)
2.3.2 The conjugacy problem
16(1)
2.3.3 The decomposition and factorization problems
16(1)
2.3.4 The membership problem
17(1)
2.3.5 The isomorphism problem
17(1)
2.3.6 More on search/witness problems
18(2)
2.4 Nielsen's and Schreier's methods
20(1)
2.5 Tietze's method
21(1)
2.6 Normal forms
22(3)
Chapter 3 Background on Computational Complexity
25(16)
3.1 Algorithms
25(1)
3.1.1 Deterministic Turing machines
25(1)
3.1.2 Non-deterministic Turing machines
26(1)
3.1.3 Probabilistic Turing machines
26(1)
3.2 Computational problems
26(6)
3.2.1 Decision and search computational problems
27(1)
3.2.2 Size functions
28(2)
3.2.3 Stratification
30(1)
3.2.4 Reductions and complete problems
31(1)
3.2.5 Many-to-one reductions
31(1)
3.2.6 Turing reductions
31(1)
3.3 The worst case complexity
32(9)
3.3.1 Complexity classes
32(1)
3.3.2 Class NP
33(1)
3.3.3 Polynomial-time many-to-one reductions and class NP
34(1)
3.3.4 NP-complete problems
35(2)
3.3.5 Deficiency of the worst case complexity
37(4)
Part 2 Non-commutative Cryptography
Chapter 4 Canonical Non-commutative Cryptography
41(14)
4.1 Protocols based on the conjugacy search problem
41(2)
4.2 Protocols based on the decomposition problem
43(3)
4.2.1 "Twisted" protocol
44(1)
4.2.2 Hiding one of the subgroups
44(1)
4.2.3 Commutative subgroups
45(1)
4.2.4 Using matrices
45(1)
4.2.5 Using the triple decomposition problem
45(1)
4.3 A protocol based on the factorization search problem
46(1)
4.4 Stickel's key exchange protocol
47(3)
4.4.1 Linear algebra attack
48(2)
4.5 The Anshel-Anshel-Goldfeld protocol
50(1)
4.6 Relations between different problems
51(4)
Chapter 5 Platform Groups
55(18)
5.1 Braid groups
55(5)
5.1.1 A group of braids and its presentation
56(2)
5.1.2 Dehornoy handle free form
58(1)
5.1.3 Garside normal form
59(1)
5.2 Thompson's group
60(3)
5.3 Groups of matrices
63(2)
5.4 Small cancellation groups
65(1)
5.4.1 Dehn's algorithm
65(1)
5.5 Solvable groups
65(3)
5.5.1 Normal forms in free metabelian groups
66(2)
5.6 Artin groups
68(1)
5.7 Grigorchuk's group
69(4)
Chapter 6 More Protocols
73(6)
6.1 Using the subgroup membership search problem
73(3)
6.1.1 Groups of the form F/[ R, R]
76(1)
6.2 The MOR cryptosystem
76(3)
Chapter 7 Using Decision Problems in Public-Key Cryptography
79(12)
7.1 The Shpilrain-Zapata scheme
79(6)
7.1.1 The protocol
80(2)
7.1.2 Pool of group presentations
82(1)
7.1.3 Generating random elements in finitely presented groups
83(2)
7.2 Public-key encryption and encryption emulation attacks
85(6)
Chapter 8 Authentication
91(26)
8.1 A Diffie-Hellman-like scheme
91(1)
8.2 A Feige-Fiat-Shamir-like scheme
92(1)
8.3 Authentication based on the twisted conjugacy problem
93(1)
8.4 Authentication from matrix conjugation
94(3)
8.4.1 The protocol, beta version
94(1)
8.4.2 The protocol, full version
95(1)
8.4.3 Cryptanalysis
96(1)
8.5 Authentication from actions on graphs, groups, or rings
97(7)
8.5.1 When a composition of functions is hard-to-invert
97(1)
8.5.2 Three protocols
98(2)
8.5.3 Subgraph isomorphism
100(1)
8.5.4 Graph homomorphism
101(1)
8.5.5 Graph colorability
102(1)
8.5.6 Endomorphisms of groups or rings
103(1)
8.5.7 Platform: free metabelian group of rank 2
104(1)
8.5.8 Platform: Z*p
104(1)
8.6 No-leak authentication by the Sherlock Holmes method
104(13)
8.6.1 No-leak vs. zero-knowledge
105(1)
8.6.2 The meta-protocol for authentication
106(1)
8.6.3 Correctness of the protocol
107(1)
8.6.4 Questions and answers
108(1)
8.6.5 Why is the Graph ISO proof system not "no-leak"?
109(1)
8.6.6 A particular realization: subset sum
109(2)
8.6.7 A particular realization: polynomial equations
111(6)
Part 3 Generic Complexity and Cryptanalysis
Chapter 9 Distributional Problems and the Average Case Complexity
117(14)
9.1 Distributional computational problems
117(3)
9.1.1 Distributions and computational problems
117(2)
9.1.2 Stratified problems with ensembles of distributions
119(1)
9.1.3 Randomized many-to-one reductions
119(1)
9.2 Average case complexity
120(11)
9.2.1 Polynomial on average functions
121(4)
9.2.2 Average case behavior of functions
125(1)
9.2.3 Average case complexity of algorithms
125(1)
9.2.4 Average case vs. worst case
126(1)
9.2.5 Average case behavior as a trade-off
126(4)
9.2.6 Deficiency of the average case complexity
130(1)
Chapter 10 Generic Case Complexity
131(10)
10.1 Generic Complexity
131(5)
10.1.1 Generic sets
131(1)
10.1.2 Asymptotic density
132(1)
10.1.3 Convergence rates
133(1)
10.1.4 Generic complexity of algorithms and algorithmic problems
134(1)
10.1.5 Deficiency of the generic complexity
135(1)
10.2 Generic versus average case complexity
136(5)
10.2.1 Comparing generic and average case complexities
136(1)
10.2.2 When average polynomial time implies generic
136(2)
10.2.3 When generically easy implies easy on average
138(3)
Chapter 11 Generic Complexity of NP-complete Problems
141(6)
11.1 The linear generic time complexity of subset sum problem
141(1)
11.2 A practical algorithm for the subset sum problem
142(1)
11.3 3-Satisfiability
143(4)
Chapter 12 Generic Complexity of Undecidable Problems
147(8)
12.1 The halting problem
147(3)
12.2 The Post correspondence problem
150(1)
12.3 Finitely presented semigroups with undecidable word problem
150(5)
Chapter 13 Strongly, Super, and Absolutely Undecidable Problems
155(16)
13.1 Halting problem for Turing machines
157(1)
13.2 Strongly undecidable problems
158(2)
13.2.1 The halting problem is strongly undecidable
158(1)
13.2.2 Strongly undecidable analog of Rice's theorem
159(1)
13.3 Generic amplification of undecidable problems
160(3)
13.4 Semigroups with super-undecidable word problems
163(2)
13.5 Absolutely undecidable problems
165(6)
Part 4 Asymptotically Dominant Properties and Cryptanalysis
Chapter 14 Asymptotically Dominant Properties
171(8)
14.1 A brief description
171(1)
14.2 Random subgroups and generating tuples
172(1)
14.3 Asymptotic properties of subgroups
173(1)
14.4 Groups with generic free basis property
174(2)
14.5 Quasi-isometrically embedded subgroups
176(3)
Chapter 15 Length Based and Quotient Attacks
179(20)
15.1 Anshel-Anshel-Goldfeld scheme
179(2)
15.1.1 Description of the Anshel-Anshel-Goldfeld scheme
179(1)
15.1.2 Security assumptions of the AAG scheme
179(2)
15.2 Length based attacks
181(5)
15.2.1 A general description
181(3)
15.2.2 LBA in free groups
184(1)
15.2.3 LBA in groups from FBexp
185(1)
15.3 Computing the geodesic length in a subgroup
186(3)
15.3.1 Related algorithmic problems
186(2)
15.3.2 Geodesic length in braid groups
188(1)
15.4 Quotient attacks
189(10)
15.4.1 Membership problems in free groups
190(1)
15.4.2 Conjugacy problems in free groups
191(3)
15.4.3 The MSP and SCSP* in groups with "good" quotients
194(5)
Part 5 Word and Conjugacy Search Problems in Groups
Chapter 16 Word Search Problem
199(48)
16.1 Introduction
199(4)
16.2 Presentations of groups
203(1)
16.3 Approximating Cayley graphs of finitely presented groups
204(8)
16.3.1 Cayley graph approximations and singular sub complexes
204(4)
16.3.2 van Kampen diagrams
208(1)
16.3.3 Depth of diagrams and the canonical embeddings
209(3)
16.4 New algorithms for the word search problem in groups
212(6)
16.4.1 Search problems in groups
212(1)
16.4.2 The word search problem in groups. Algorithm A.
213(2)
16.4.3 The word search problem in groups. Algorithm B.
215(3)
16.5 Random van Kampen diagrams
218(6)
16.5.1 Basic random extensions and simple random walks
218(1)
16.5.2 Probability and asymptotic measure on diagrams
219(3)
16.5.3 Iterative random generator RGn
222(1)
16.5.4 Diagram complexity and random generator RGx
222(2)
16.6 Basic extension algorithm Bs and relative probability measures
224(13)
16.6.1 Basic extension Bs
224(2)
16.6.2 Completeness of the basic extension Bs
226(10)
16.6.3 Some properties of Bs
236(1)
16.7 Asymptotic properties of diagrams
237(5)
16.7.1 Properties related to RGx
237(5)
16.8 Generic properties of trivial words
242(3)
16.8.1 Random trivial words
242(1)
16.8.2 Generic properties of trivial words
243(2)
16.9 Comparison with standard techniques
245(2)
16.9.1 The Todd-Coxeter algorithm
245(1)
16.9.2 Total enumeration of gpF(R)
246(1)
Chapter 17 Conjugacy Search Problem
247(38)
17.1 Introduction
247(1)
17.2 Weighted graphs
248(2)
17.2.1 Definition
248(1)
17.2.2 Conjugacy and pseudo conjugacy graphs
249(1)
17.3 Transformations of weighted X-digraphs
250(9)
17.3.1 Shift operator
251(1)
17.3.2 Stallings' fold
252(2)
17.3.3 Stallings' procedure
254(2)
17.3.4 Basic extension
256(2)
17.3.5 R-extension algorithm
258(1)
17.4 Conjugacy graphs
259(3)
17.4.1 Existence of conjugacy graphs
260(1)
17.4.2 Conjugacy graph approximation
261(1)
17.5 Annular (Schupp) diagrams
262(2)
17.5.1 Depth of annular diagrams
263(1)
17.5.2 Annular diagrams as pseudo conjugacy graphs
264(1)
17.6 The conjugacy search problem
264(8)
17.6.1 Annular diagram bisection
264(5)
17.6.2 Conjugacy search algorithm
269(3)
17.7 Random annular diagrams
272(7)
17.7.1 Basic random extension of annular diagrams
274(4)
17.7.2 Completeness of Bs
278(1)
17.8 Asymptotic properties of random annular diagrams
279(1)
17.9 Asymptotic properties of conjugated words
280(5)
17.9.1 Random conjugated words
280(1)
17.9.2 Generic properties of random conjugated words
281(4)
Part 6 Word Problem in some Special Classes of Groups
Chapter 18 Free Solvable Groups
285(24)
18.1 Preliminaries
289(9)
18.1.1 The word problem
289(1)
18.1.2 Free solvable groups and the Magnus embedding
289(2)
18.1.3 Free Fox derivatives
291(1)
18.1.4 Flows on F/N
292(2)
18.1.5 Geometric interpretation of Fox derivatives
294(2)
18.1.6 Geometric circulations and the first homology group of Γ
296(1)
18.1.7 Geodesics in F/N'
296(2)
18.2 The word problem in free solvable groups
298(5)
18.2.1 The word problem in free metabelian groups
298(2)
18.2.2 The word problem in free solvable groups
300(3)
18.3 Geodesics in free metabelian groups
303(6)
18.3.1 Algorithmic problems about geodesics in groups
303(1)
18.3.2 Reduction to M2
304(1)
18.3.3 Rectilinear Steiner tree problem
305(1)
18.3.4 NP-completeness of BGLP in M2
305(4)
Chapter 19 Compressed Words
309(16)
19.1 Straight line programs
309(1)
19.2 Basic operations over SLPs
310(2)
19.2.1 Subwords
310(2)
19.2.2 Inversion
312(1)
19.3 Plandowski's algorithm
312(7)
19.3.1 Assertions
312(2)
19.3.2 Trimming
314(1)
19.3.3 Splitting
315(1)
19.3.4 Compactification
316(2)
19.3.5 Satisfiability of SLP
318(1)
19.3.6 Plandowski's algorithm
319(1)
19.4 Longest common initial segment
319(1)
19.5 Reduction
320(1)
19.6 The word problem in the automorphism group of a free group
321(4)
Appendix A Probabilistic Group-based Cryptanalysis
325(44)
A.1 Introduction
325(3)
A.2 Probability theory on groups
328(6)
A.2.1 Probabilities for various spaces - overview
328(3)
A.2.2 Mean (expectation) of a group-valued random element
331(2)
A.2.3 The mean set in a group
333(1)
A.2.4 Other possible definitions of E
334(1)
A.3 Strong law of large numbers
334(11)
A.3.1 Separation and inclusion lemmas
336(3)
A.3.2 Case of multi-vertex mean-sets
339(6)
A.4 Concentration of measure inequalities
345(4)
A.4.1 Chebyshev's inequality for graphs/groups
345(3)
A.4.2 Chernoff-Hoeffding-like bound for graphs/groups
348(1)
A.5 Configurations of mean-sets
349(3)
A.6 Computation of mean-sets in graphs
352(2)
A.6.1 Experiments
353(1)
A.7 Probabilistic cryptanalysis of Sibert type protocols
354(15)
A.7.1 Outline
355(1)
A.7.2 Zero-knowledge interactive proof systems
355(1)
A.7.3 Description of the protocol
356(1)
A.7.4 Security of the protocol
357(1)
A.7.5 The idea of mean-set attack: the shift search problem
358(1)
A.7.6 Effective computation of a mean-set
359(1)
A.7.7 The mean-set attack
360(3)
A.7.8 Experiments
363(3)
A.7.9 Defending against the attack
366(3)
Bibliography 369(12)
Abbreviations and Notation 381(2)
Index 383
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97814704140472e.html
Märksõnad: