Yuval Hachtarian (i), Shira Gilat (-1)
Email Boris (Remove 777 from kun777yav@gmail.com) to be included in the mailing list.
Place:
Seminar Room, Mathematics&CS building (Building #216 in the campus), Bar-Ilan University.
Arrival instructions: Press the "-" zoom button twice, to see the campus on the right of the map.
Car permit: If you arrive by car and need a car entrance permit, call Rivka or Tamar at 03-5317875.
General description:
Few public-key schemes are considered secure.
Nearly all of them are based on commutative groups, and can be broken in subexponential time using standard computers,
and in polynomial time using quantum computers.
About 10 years ago, an investigation began of the potential of basing a public-key scheme on a noncommutative algebraic structure. This approach has potential for solving the
mentioned problems. But it has been locked into a cycle of ad hoc approaches, which fall to equally ad hoc cryptanalyses, or ill specified schemes which lack the vital details
for implementation and security testing. Standard computational group theory is not currently ideally suited for cryptanalysis, as the theory tends to emphasize pure
mathematical applications: parameters for cryptography tend to be larger, and the approach is allowed to be more heuristic. On the other side, proposals for cryptosystems come
from pure mathematicians who often do not understand the practical constraints of a modern public-key scheme.
This colloquium is intended to bring together mathematicians, computer scientists, and scientists working in the industry, who are interested in this emerging field of
mathematics and computer science, for the purpose of learning from one another, and discussing new ideas and directions.
15.5.14 (Thu), 14:00: Ran Cohen (BIU), Arithmetic codices III.
8.5.14 (Thu), 14:00: Ran Cohen (BIU), Arithmetic codices II.
1.5.14 (Thu), 14:00: Ran Cohen (BIU),
Arithmetic codices.
This notion generalizes the notions of arithmetic secret sharing schemes as well as some notions from algebraic complexity theory.
The first talk will provide a review of some arithmetic secret sharing schemes and the second talk will discuss the definition of
codices.
https://eprint.iacr.org/2012/388
27.3.14 (Thu), 14:00: Arkadius Kalka (BIU),
Introduction to non-commutative and non-associative public-key cryptography.
We give an elementary introduction to non-commutative public-key cryptography. We focus on key establishment protocols (KEP).
We introduced the first KEPs which use non-associative algebraic structures, and we explain how they work and discuss their base problems.
6.3.14 (Thu), 14:00: Arkadius Kalka (BIU),
Secure information transmission based on
physical principles (after D. Grigoriev and V. Shpilrain).
The abstract of their paper:
"We employ physical properties of the real world to design
a protocol for secure information transmission where one of the parties
is able to transmit secret information to another party over an insecure
channel, without any prior secret arrangements between the parties. The
distinctive feature of this protocol, compared to all known public-key
cryptographic protocols, is that neither party uses a one-way function.
In particular, our protocol is secure against (passive) computationally
unbounded adversary.".
Their second paper we discussed: Yao's Millionaires' problem and decoy-based
public key encryption by classical physics [paper]
15.1.13 (Tue), 14:00: Ran Cohen (BIU), Pairing-based encryption IV
1.1.13 (Tue), 14:00: Ran Cohen (BIU), Pairing-based encryption III
27.11.12 (Tue), 14:00: Ran Cohen (BIU), Pairing-based encryption II
20.11.12 (Tue), 14:00: Ran Cohen (BIU), Pairing-based encryption
13.11.12 (Tue), 14:00: Ran Cohen (BIU), Identity-based cryptography (continued)
30.10.12 (Tue), 14:00: Ran Cohen (BIU), Identity-based cryptography
16.5.12 (Wed), 19:30-20:30: David Garber (HIT), An introduction to Garside groups, with an eye towards the Conjugacy Problem, XIII.
15.5.12 (Tue), 12:10-13:10: Ran Cohen (BIU), The Paillier PKC.
8.5.12 - two talks:
12:10-13:10: Ran Cohen (BIU), Identity based encryption, III
19:30-20:30: David Garber (HIT), An introduction to Garside groups, with an eye towards the Conjugacy Problem, XII.
2.5.12 (Wed), 19:30-20:30: David Garber (HIT), The Conjugacy Problem in Garside groups, XI.
1.5.12 (Tue), 12:00-13:00: Ran Cohen (BIU), Identity based encryption, II
17.4.12 - two talks:
12:00-13:00: Ran Cohen (BIU), Identity based encryption
(This is the first, introduction lecture. It will be followed by several talks on the topic below.)
Constructions of identity based encryption (IBE) in the standard model are known based on bi-linear maps assumptions and lattices assumptions. In the random oracle (RO) model there is also a construction based on the quadratic residuosity (QR) assumption. An open problem is to construct an IBE scheme in the standard model based on classic number-theoretic assumptions (DDH, QR, etc.).
We will review the random oracle methodology and present some IBE constructions along with their security proofs.
19:30-20:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, X.
28.3.12, 19:30-20:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, IX. Lectures 8-9.
Special announcement: Pariticipants of the CGC Seminar win first place in BIU's Gravity Challenge.
|
|
| Contest winners:
Adi Lugassi (e), Uzi Harush (pi),
Yuval Hachtarian (i), Shira Gilat (-1) |
The challenge, met. |
21.3.12, 19:30-20:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, VIII.
Participants who missed the previous talks can catch up using the following lecture notes: Lecture 1 , Lecture 2 , Lectures 3-5 , Lectures 6-7.
1.3.12, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, VII. Lecture notes for lectures 6-7
26.1.12, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, VI.
19.1.12, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, V. Lecture notes for lectures 3-5
12.1.12, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, V. Lecture notes for lectures 3-5
29.12.11, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, IV.
21.12.11, 12:00-13:30 (Joint with ENI Seminar - note special day & time): Arkadius Kalka (BIU), On the Simultaneous Conjugacy Problem in Garside groups. (In English)
15.12.11, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, III.
8.12.11, 17:00-18:30: Arkadius Kalka (BIU), An introduction to Garside groups. (In English) [relevant paper]
8.12.11, 19:00: Chris Peikert (Georgia Institute of Technology), Pseudorandom Functions and Lattices, SCPQWebinar (info).
Pseudorandom function (PRF) families are a workhorse of symmetric cryptography,
implying efficient solutions to most encryption and authentication problems.
Existing constructions of PRFs fall into two broad classes:
(1) heuristic designs like AES that withstand known cryptanalytic attacks and
(2) theoretically sound ones where security is rigorously provable under simple
assumptions, like the existence of one-way functions or the hardness of
numbertheoretic problems (e.g., factoring or computing discrete logs).
All known constructions of the latter type, however, are either inherently
sequential with large circuit depth, or have huge circuits and are breakable
with quantum algorithms.
In this work we give "direct" constructions of pseudorandom function (PRF)
families based on conjectured hard *lattice* problems and *learning* problems.
Our constructions are asymptotically efficient and highly parallelizable in a
practical sense, i.e., they can be computed by simple, relatively *small*
low-depth arithmetic or boolean circuits (e.g., in NC$^{1}$ or even TC$^{0}$).
In addition, they are the first (theoretically sound) low-depth PRFs that have
no known attack by efficient quantum algorithms. Central to our results is a
new ``derandomization'' technique for the learning with errors (LWE) problem
which, in effect, generates the error terms deterministically.
This is recent joint work with Abhishek Banerjee (Georgia Tech) and
Alon Rosen (IDC Herzliya)
1.12.11, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, II. [Lecture notes]
24.11.11, 17:00-18:30: David Garber (Holon Institute of Technology), An introduction to Garside groups, with an eye towards the Conjugacy Problem, I. [Lecture notes]
Note: This lecture is at the level of new Master's students and third year undergraduates. A Hebrew Lecture.
17.11.11, 12:00-13:30: Boaz Tsaban (BIU), Challenges in modern cryptology: An introduction to noncommutative cryptography.
Note: This lecture is aimed at new Master's students (third year undergraduates are also welcome).
10.11.11, 18:00-19:00: Zvika Brakerski (Stanford University), Fully Homomorphic Encryption from LWE, SCPQWebinar (info).
In fully homomorphic encryption, it is possible to transform an encryption of a message, $m$, into an encryption of any (efficient) function of that message, $f(m)$, without knowing the secret key. This property makes it into a very useful cryptographic building block.
In the talk, we will show how to construct fully homomorphic encryption from the learning with errors (LWE) assumption. Thus, by known reductions, our scheme is based on the worst case hardness of short vector problems in arbitrary lattices.
We introduce two novel techniques: re-linearization and dimension-modulus reduction, which enable us to deviate from two fundamental concepts that ruled the design of all previous candidate schemes:
1. We show that the ``squashing paradigm'' is not needed to achieve full homomorphism.
2. We show that Gentry's bootstrapping theorem is not necessary for achieving ``leveled'' fully homomorphic encryption (a variant where the parameters of the scheme grow with the depth of the circuit to be evaluated). Nevertheless, using the bootstrapping theorem is still necessary to get a non-leveled scheme, it also improves efficiency and considerably weakens the underlying hardness assumption. Specifically, our scheme (using bootstrapping) can be based on the hardness of quasi-polynomial approximation to short vector problems.
The talk is based on two works: a joint work with Vinod Vaikuntanathan, and a joint work with Craig Gentry and Vinod Vaikuntanathan.
3.11.11, 11:00-13:00: Bill Gasarch (Univ. Maryland), Ramsey Theory - Theorems and “Applications”, Lecture VI.
2.11.11, 11:00-13:00: Bill Gasarch (Univ. Maryland), Ramsey Theory - Theorems and “Applications”, Lecture V.
1.11.11, 14:15-16:00: Bill Gasarch (Univ. Maryland), Ramsey Theory - Theorems and “Applications”, Lecture IV.
1.11.11, 11:00-13:00: Bill Gasarch (Univ. Maryland), Ramsey Theory - Theorems and “Applications”, Lecture III.
31.10.11, 11:00-13:00: Bill Gasarch (Univ. Maryland), Ramsey Theory - Theorems and “Applications”, Lecture II.
30.10.11, 12:00-13:30: Bill Gasarch (Univ. Maryland), Ramsey Theory - Theorems and “Applications”, Lecture I.
Note: At 13:15, we will schedule an extra hour for this lecture series, probably on Wednesday.
27.10.11, 18:00-19:00: Ludovic Perret (Laboratoire d'Informatique de Paris 6), Algebraic Attacks in Code-based cryptography, SCPQWebinarn (info).
In this talk, we present a new approach to investigate the security of the McEliece cryptosystem. Since its invention thirty years ago, no efficient attack had been devised that managed to recover the private key. Faugère-Otmani- Perret-Tillich (FOPT) show at Eurocrypt 2010 that the private key of such cryptosystem can be recovered by solving a highly structured system of algebraic equations (the system is bilinear). This property is due to the particular class of codes considered which are alternant codes. These highly structured algebraic equations allowed to mount a efficient key-recovery attack against two recent variants of the McEliece cryptosystems that aim at reducing public key sizes by using quasi-cyclic or quasi-dyadic structures. In the first part of the talk, we present this attack and an improved complexity analysis. Indeed, thanks to a recent development due to Faugère-Safey el Din-Spaenlehauer on the solving of bilinear systems, we can estimate the complexity of the FOPT algebraic attack. This is a first step toward providing a concrete criterion for evaluating the security of future compact McEliece variants.
In the second part of the talk, we will study the difficulty of the Goppa Code Distinguishing (GD) problem, which is the problem of distinguishing the public matrix in McEliece's cryptosystem from a random matrix. It was widely believed that this problem is computationally hard as proved by the increasing number of papers using this hardness assumption. We present an efficient distinguisher for alternant and Goppa codes over binary/non binary fields. The distinguisher is based on the FOPT attack.
(joint work with Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, and Jean-Pierre Tillich)
13.7.11: (Wednesday), 15:00 - 16:15: Arkadius Kalka (BIU), Non-associative Cryptography II: Anshel-Anshel-Goldfeld KAP for multi-LD-systems
12.7.11: (Tuesday), 14:00 - 15:15: Arkadius Kalka (BIU), Non-associative Cryptography
We introduce a generalized Anshel-Anshel-Goldfeld (AAG)
public key agreement scheme for magmas, i.e. algebraic structures with a non-associative operation.
This might lead to the foundation of non-associative public-key cryptography, generalizing the concept of noncommutative PKC.
We show that left selfdistributive systems appear in a natural special case of a generalized AAG public key agreement scheme for
magmas, and we propose a concrete realization using shifted conjugacy in braid groups and discuss the advantages compared with the classical
AAG public-key system based on conjugacy in braid groups.
14.6.11: (Tuesday), 12:00 - 13:00 (Special Mathematics Colloquium):
Oleg Bogopolski (Düsseldorf Univ.), On residual properties of groups
8.6.11: No seminar (Shavuot).
1.6.11: No seminar (Yom Yerushalayim).
25.5.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Martin Albrecht (Université Pierre et Marie Curie), Polly Cracker Revisited.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
In this talk, we introduce the provable-security treatment of cryptographic constructions based on the hardness of computing a Groebner basis. We formalise
and study the relation between various computational problems associated with Groebner bases, and revisit the (symmetric) polly cracker encryption scheme, proving
that it achieves only bounded IND-CPA security under the ideal membership problem. Next, using results from computational commutative algebra, we show that no
simple generic transformation can lead to a fully secure polly-cracker-type scheme. This then leads us to noisy variants of Groebner bases and related problems.
After formalizing and justifying the hardness of the noisy assumptions we show that noisy encoding of messages results in a secure homomorphic scheme. Finally,
through a symmetric-to-asymmetric conversion, we provide a positive answer to the long standing open problem proposed by Barkee et al. of using multivariate
polynomials in public-key cryptography.
Joint work with C. Cid, P. Farshim, J-C. Faugere and L. Perret
22.5.11: (Sunday), 16:00 pm (joint with the BIU Combinatorics seminar):
Arkadius Kalka (BIU), On the diameter of the Tits graph of the longest element in Coxeter groups of classical type
Consider the Tits graph of the longest element of a finite type Coxeter group. Its vertices are reduced words representing the longest element, and edges
correspond to one application of a relation. By counting appropriate inversions Reiner and Roichman
[RR09]
computed lower bounds for the diameter of this Tits graph for all finite type Coxeter groups. Using methods from the theory of hyperplane arrangements they proved
for the families of A and B-type that these lower bounds are exact.
We give elementary proofs for the A and B-type by showing that the Tits posets (poset structure given by inclusion of these inversions) have unique maximal and
minimal elements. For the D-type Coxeter group, we show for several ''natural'' candidate bottom words that there exist other local minimal elements in the Tits poset.
18.5.11: (Wednesday), 10:00 am promptly (joint with the BIU Algebra seminar):
Daniel Lenz (Jena), Order based constructions of groupoids from inverse semigroups
We discuss how the universal groupoid of an inverse semigroup
introduced by Paterson can be obtained by a simple order based
construction. Along the way one obtains canonically a reduction of
this groupoid. In the case of inverse semigroups arising from graphs
(respectively, tilings) this reduction is the graph groupoid
introduced by Kumjian et al. (respectively, the tiling groupoid of
Kellendonk). We discuss some topological features of this reduction
as well as the structure of its open invariant sets. This can be used
to investigate the ideal structure of an associated reduced
$C^*t$-algebra.
11.5.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Rong Ge (Princeton University), New Algorithms for Learning in Presence of Errors.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
We give new algorithms for a variety of randomly-generated instances of computational problems using a linearization technique that reduces to solving a system of
linear equations.
These algorithms are derived in the context of learning with structured noise, a notion introduced in this paper. This notion is best illustrated with the
learning parities with noise (LPN) problem - well-studied in learning theory and cryptography. In the standard version, we have access to an oracle that, each time
we press a button, returns a random vector $ a \in GF(2)^n$ together with a bit $b \in GF(2)$ that was computed as $a\cdot u +\eta$, where $u\in GF(2)^n$ is a secret
vector, and $\eta \in GF(2)$ is a noise bit that is $1$ with some probability $p$. Say $p=1/3$. The goal is to recover $u$. This task is conjectured to be intractable.
In the structured noise setting we introduce a slight (?) variation of the model: upon pressing a button, we receive (say) $10$ random vectors
$a_1, a_2, \ldots, a_{10} \in GF(2)^n$, and corresponding bits $b_1, b_2, \ldots, b_{10}$, of which at most $3$ are noisy. The oracle may arbitrarily decide
which of the $10$ bits to make noisy. We exhibit a polynomial-time algorithm to recover the secret vector $u$ given such an oracle. We think this structured
noise model may be of independent interest in machine learning.
We discuss generalizations of our result, including learning with more general noise patterns. We also give the first nontrivial algorithms for two problems, which
we show fit in our structured noise framework.
We give a slightly subexponential algorithm for the well-known learning with errors (LWE) problem over $GF(q)$ introduced by Regev for cryptographic uses.
Our algorithm works for the case when the gaussian noise is small; which was an open problem.
We also give polynomial-time algorithms for learning the MAJORITY OF PARITIES function of Applebaum et al. for certain parameter values. This function is a special
case of Goldreich's pseudorandom generator.
The talk will mainly focus on LPN and LWE.
11.5.11: (Wednesday), 10:30 am promptly (joint with the BIU Algebra seminar):
Luda Markus-Epstein (Technion), The word problem for inverse monoids presented by a single relator
Since Magnus it has been well known that one-relator groups have a decidable word problem. However, solvability of the word problem in one- relator monoids is
far from being completely studied. Only a few examples of inverse monoids with solvable word problem are known. Recently, the solvability of the word problem in
inverse monoids with a single sparse relator has been announced by Hermiller, Lindblad and Meakin.
We consider certain one-relator inverse monoids. In our attempt to solve the word problem, we rely on the result of Ivanov, Margolis and Meakin which states that
the word problem for the inverse one-relator monoid is decidable if the membership problem for the corresponding prefix monoid is decidable. Thus, we first solve
the membership problem for the prefix monoid and then apply the theorem to solve the word problem. Our methods involve van Kampen diagrams and word combinatorics
27.4.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
William Skeith (The City College of New York),
New Learning Problem with Applications to Cryptography.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
27.4.11: (Wednesday), 14:00--15:00 (joint with the Emmy Noether Seminar):
Arkadius Kalka (BIU), Tropical Cryptography
[Relevant paper]
We present the recent idea of "Tropical Cryptography" by Dima Grigoriev and Vladimir Shpilrain.
They employ tropical algebras as platforms for several cryptographic schemes that would be vulnerable to
linear algebra attacks were they based on "usual" algebras as platforms.
In particular they propose "tropical variants" of slight generalisations of a key establishment protocol by Stickel and
of a public key cryptosystem by Tzuong-Tsieng Moh.
They make a case for using tropical algebras as platforms by using, among other things, the fact that in the "tropical" case, even solving systems
of linear equations is computationally infeasible in general.
20.4.11: Pessach break
13.4.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Martin Kreuzer (Universitat Passau),
Groebner bases for non-commutative polynomials and applications to cryptography.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
One of the most active areas of research in Post-Quantum Cryptography is based on the idea to use non-commutative algebraic structures in order to build
cryptographic primitives. For this, it is clearly necessary to compute effectively in such structures and to assess the feasability and efficiency of such
computations. Groebner bases are a fundamental tool to perform effective computations. We outline the basic theory of Gr"obner bases for two-sided ideals in
non-commutative polynomial rings, explain the Buchberger procedure to enumerate them, and present some first ways of applying them to perform fundamental
operations such as ideal membership, elimination, kernels and images of algebra homomorphisms, etc. Then we treat more advanced techniques such as Hilbert
functions, finiteness checks, Gelfand-Kirillov dimension, and syzygies. Finally we apply the Gr"obner basis method to important questions in group-based
cryptography.
6.4.11: (Wednesday), 14:00--15:00: Gary Vinokur (BIU), The Conjugacy Problem in the braid group V [Notes]
30.3.11: (Wednesday), 18:00--19:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Ludovic Perret (Laboratoire d'Informatique de Paris 6),
Groebner bases techniques in Cryptography.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
30.3.11: (Wednesday), 14:00--15:30: Ran Cohen (BIU), Algebraic-geometric secret sharing II
[Notes (in Hebrew)]
16.3.11: (Wednesday), 18:00--19:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Vadim Lyubashevsky (École Normale Supérieure, Paris),
Efficient cryptography from generalized compact knapsacks.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
I will first give a brief survey on the role of the knapsack problem in lattice-based cryptography and its relationship to all the problems upon which
lattice-based protocols are based. Then I will describe a new lattice-based signature scheme which is based on the conjectured hardness of a natural average-case
problem which can be seen as a hybrid between the Ring-LWE and the NTRU assumptions. The assumption roughly states that if we pick a polynomial r uniformly at
random from a particular polynomial ring R, and polynomials s_1,s_2 at random from a small subset of R, then the pair (r,rs_1+s_2) is computationally
indistinguishable from a uniformly random element in R x R. The resulting signature length of the signature scheme is under 9000 bits, which is a factor of six
shorter than any previous lattice-based scheme of comparable security that also possesses a security reduction.
16.3.11: (Wednesday), 14:00--15:30: Ran Cohen (BIU), Algebraic-geometric secret sharing
[Notes (in Hebrew)]
The purpose of the series of talks is to understand the algebraic-geometric secret sharing scheme of Cramer & Chen.
The main advantage of this secret sharing scheme is that the number of players does not depend on the size of the underlying field.
The talks will be self-contained, and no prior knowledge in secret sharing schemes and/or algebraic geometry is required.
The first part will include some background on secret sharing in general.
The focus will be on Shamir's secret sharing scheme, the homomorphic nature of this construction (the notions of multiplication and strong multiplication),
the relation to Reed-Solomon error correcting codes, and Feldman's VSS (verifiable secret sharing).
The second part will include background on algebraic curves and algebraic-geometric codes.
The third part will cover the Cramer & Chen secret sharing construction.
9.3.11: (Wednesday), 14:00--15:30: Gary Vinokur (BIU), The Conjugacy Problem in the braid group IV
[Notes (in Hebrew)]
Lecture in Hebrew
2.3.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Chris Peikert (Georgia Institute of Technology),
Trapdoors for Lattices: Signatures, Identity-Based Encryption, and Beyond.
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
2.3.11: (Wednesday), 14:00--15:30: Gary Vinokur (BIU), The Conjugacy Problem in the braid group III
[Notes (in Hebrew)]
Lecture in Hebrew
27.2.11: (Sunday), 14:00 - 15:00 (joint with the BIU Combinatorics seminar):
Boaz Tsaban (BIU), The Algebraic Eraser and short expressions of permutations as
products [relevant paper]
On March 2004, Anshel, Anshel, Goldfeld, and Lemieux introduced
the Algebraic Eraser scheme for key agreement over an insecure channel,
using a novel hybrid of infinite and finite noncommutative groups. They
also introduced the Colored Burau Key Agreement Protocol (CBKAP), a
concrete realization of this scheme.
We present general, efficient heuristic algorithms, which extract the
shared key out of the public information provided by CBKAP. These
algorithms are, according to heuristic reasoning and according to massive
experiments, successful for all sizes of the security parameters,
assuming that the keys are chosen with standard distributions.
Our methods come from probabilistic group theory and expander graphs.
In particular, we provide a simple and efficient heuristic algorithm for
finding short expressions of permutations in S_n, as products of given
random permutations.
Our algorithm gives (heuristically and experimentally) expressions of
length roughly n^2\log n, in time roughly n^3\log n and space roughly
n^2\log n, and is the first practical one for n>128.
The talk is designed to be accessible also to undergraduate students.
So, students are welcome.
Disclaimer: Our work does not make any claim concerning the security of
the actual distributions used in the Algebraic Eraser (TM). These
distributions are are proprietary and are not available to the authors.
Joint work with Arkadius Kalka and Mina Teicher (BIU).
17.2.11: (Thursday), 12:15--13:45: Gary Vinokur (BIU), The Conjugacy Problem in the braid group II
[Notes (in Hebrew)]
We finish the first solution to CSP, and proceed to a better solution and possibly also to the multiple CSP.
Lecture in Hebrew.
16.2.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Ciaran Mullan (Royal Holloway, University of London) ,
Cryptanalysis of two matrix-based key establishment protocols
[talk slides]
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
In this talk we will discuss two recent key establishment protocols.
The first is due to Baumslag, Camps, Fine,
Rosenberger and Xu (2006), and the second due to Habeeb, Kahrobaei and
Shpilrain (2010).
For the first scheme, we offer a cryptanalysis when the platform group
is SL_4(Z). And we cryptanalyze
the second scheme when GL_n(F_p) is used as a platform.
For both schemes we will see some effective linear algebra tricks to
efficiently derive the key,
assuming only the passive adversary model.
Joint work with S.R. Blackburn and C. Cid.
10.2.11: (Thursday), 12:15--13:45: Gary Vinokur (BIU), The Conjugacy Problem in the braid group
[Notes (in Hebrew)]
Lecture in Hebrew.
2.2.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Jintai Ding (University of Cincinnati) , Post-quantum cryptography -- multivariate public key cryptography
[talk slides]
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
30.1-1.2.11 (Sunday-Tuesday): Winter School on Secure Computation and Efficiency
Where: Feldman International Conference Center (Building 301), Bar Ilan University
(Do not forget to register by emailing name and affiliation to mpcschool.biu@gmail.com)
20.1.11: (Thursday), 12:10--13:40: Gary Vinokur (BIU), Introduction to Artin's braid groups, part I.
[Notes (in Hebrew)]
Lecture in Hebrew.
19.1.11: (Wednesday), 19:00--20:00 (joint with the Symbolic Computation and Post-Quantum Cryptography Seminar):
Alexei Miasnikov (Stevens Institute of Technology), Compression and Complexity.
[talk slides]
Place: Your PC. This is a webinar. For more Information click here.
You have to install a free software on your PC, in advance.
Also, read here.
10.1.11: (Monday), 12:10 - 13:00: Gary Vinokur (BIU), Public key cryptography based on variants of the conjugacy
problem III
We show a reduction of the Key-Decomposition Problem to Simultaneous CSP.
Lecture in Hebrew.
3.1.11: (Monday), 12:10 - 13:00: Gary Vinokur (BIU), Public key cryptography based on variants of the conjugacy
problem II
[Notes (in Hebrew)]
Lecture in Hebrew.
26.12.10: (Sunday), 14:00 - 15:30 (joint with the BIU Combinatorics seminar):
Lev Shneerson (CUNY), On the growth functions of semigroups
We study the asymptotic behavior of the growth functions in some classes of finitely generated and
finitely presented semigroups and investigate conditions under which these semigroups have polynomial growth.
In particular, we find new criteria for polynomial growth in finitely presented Rees quotients of free inverse
semigroups.
Most of the results of the talk are joint work with David Easdown (School of Mathematics and Statistics,
The University of Sydney, Australia).
13.12.10: (Monday), 12:15 - 13:30: Gary Vinokur (BIU), Public key cryptography based on variants of the conjugacy
problem
[Notes (in Hebrew)]
Lecture in Hebrew.
12.12.10: (Sunday), 14:00 - 15:30 (joint with the BIU Combinatorics seminar):
Ori Gurel-Gurevich (U. British Columbia), The unlikeliness of being covered
We will show that the probability that a simple random walk will cover a finite, bounded degree graph in
linear time is exponentially small. More precisely, for every D and C, there exists a=a(D,C)>0 such that for
any graph G, with n vertices and maximal degree D, the probability that a simple random walk, started
anywhere in G, will visit every vertex of G in its first Cn steps is at most $exp(-an)$.
Joint work with Itai Benjamini and Ben Morris.
28.11.10: (Sunday), 14:00 - 15:30 (joint with the BIU Combinatorics seminar):
Moshe Cohen (Bar-Ilan University), A dimer model for the Jones polynomial of pretzel knots or
Everything you ever wanted to know about Tutte's acitivity but
were afraid to ask
The Tutte polynomial gives remarkable insight into the structure of a
graph, especially in terms of its bulky and computationally expensive
definition using "activity". By narrowing our focus to a specific
class of graphs coming from pretzel knots, we can recover these
activity words easily as the determinant of a matrix.
This determinant encodes information about the spanning tree expansion
of the graph, something that has proved useful in this context. When
viewed a different way, however, this determinant encodes information
about perfect matchings of a different bipartite graph. This "dimer
model" arises from statistical mechanics and has been studied
extensively in different contexts.
The Jones polynomial of a knot is a specialization of the Tutte
polynomial of a graph obtained from a knot. No background in Knot
Theory will be expected. This talk is accessible to anyone with a
basic understanding of graph theory and matrix determinants.
18.11.10: (Thursday), beginning at 14:15 (joint with the CS Colloquium):
Roni Stern (Ben-Gurion University), Using Lookaheads with Optimal Best-First Search
We present an algorithm that exploits the complimentary benefits of
best-first search (BFS) and depth-first search (DFS) by performing
limited DFS lookaheads from the frontier of BFS. We show that this
continuum requires significantly less memory than BFS. In addition, a
time speedup is also achieved when choosing the lookahead depth
correctly. We demonstrate this idea for breadth-first search and for
A*. Additionally, we show that when using inconsistent heuristics,
Bidirectional Pathmax (BPMX), can be implemented very easily on top of
the lookahead phase. Experimental results on several domains
demonstrate the benefits of all our ideas.
Joint work with Tamar Kulberis, Ariel Felner, Rob Holte
7.11.10: (Sunday), 14:00 - 15:30 (joint with the BIU Combinatorics seminar):
Gady Kozma (Weizmann Institute), Random walks on the symmetric group
The group of all permutations of n elements is perhaps the most studied finite non-abelian group, in terms of random walks on it. An exciting aspect of the field is that every question can be approached probabilistically or algebraically, and people reached impressive results both using and not using its theory of representations. We will survey old and new results, and connections to the quantum Heisenberg ferromagnet. No prior knowledge of representation theory (or physics) will be assumed.
2.11.10: (Tuesday), 12:00 (joint with the BIU Combinatorics seminar):
Eli Bagno (Jerusalem College of Technology), Permutation statistics in the affine Coxeter group of type A
[Talk Slides]
The theory of permutation statistics on infinite groups is still not well developed. One of the main problems is that
many of the classical combinatorial parameters used in the finite case have a finite range. A choice of such a parameter
on an infinite group would yield no reasonable generating function. Hence many of the nice and elegant identities known,
for example, for the classical Weyl groups, do not exist for the affine case.
In this work we present a combinatorial parameter with an infinite range on the affine Coxeter group of type A, which
equidistributes with the length function over this group. The nice behavior is only over the 'positive part' of the group,
but here the idea of Hilbert's Hotel comes to our aid. Our parameter also has an algebraic meaning. In previous works it
has been shown that the coinvariant algebra of the symmetric group, which is isomorphic to its regular representation,
can be decomposed into sub representations corresponding to combinatorial parameters such as the descent functions and
the major index. These results were extended to all classical finite Coxeter groups and also to the colored permutation
groups.
This idea is implemented in the case of the affine Coxeter group of type A, using our new parameter.
24.10.10: (Sunday), 14:00 - 15:30 (joint with the BIU Combinatorics seminar):
Gidi Amir (Bar-Ilan University), The speed process of TASEP (Totally ASymmetric Exclusion Process)
We study an exclusion process on Z where each particle is assigned a class (number in Z) and each particle tries to swap
places with its right neighbor with rate 1 if that neighbor has a higher class number. (Alternatively, each edge of Z is
"sorted" with rate 1.) With the right starting conditions, the position of each particle (normalized by time) converges
to a constant speed. The speed of each particle is uniform in [-1,1], but there are strong dependencies between the
behaviors of different particles. We study the joint distribution of these speeds - the TASEP speed process.
We prove that the TASEP speed process is stationary with respect to the multi-type TASEP dynamics, where speeds
are considered as the classes of the particles. Consequently, every ergodic stationary measure is given as a projection
of the speed process measure. This allows us to utilize known results on the stationary measure for the multi-type TASEP
to deduce various marginals of the speed process, such as the joint distribution of the speeds for 3 successive particles.
Another surprising consequence is the existence of infinite "convoys" - particles (with different classes) all converging
to the same speed. Some of our results apply also to the partially asymmetric case as well.
No prior knowledge on exclusion processes is assumed, and all definitions will be given within the lecture.
This is joint work with Omer Angel and Benedek Valko.
20.10.10: (Wednesday), 10:30 am promptly (joint with the BIU Algebra seminar):
Alexei J. Kanel-Belov (Bar-Ilan University), Construction of finitely presented infinite nil-semigroup
We use geometric methods for the construction.
We assign elements of the semigroup by paths on a special metric space.
This space can be considered as aperiodic tiling by finite number of tiles.
The relations in the semigroup can be assigned by flips on this tiling. Using these
assignments we can transform
a given word and obtain some area in which this word's path can be situated. Using some monomial
relations we obtain that all words with big powers can be reduced to nil.
Unlike the classical group situation, our complex is non-planar.
27.05.10: Elette Boyle (MIT, Weizmann), Fully Homomorphic Encryption over the Integers
This talk will present the recent work of Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan designing a simple fully homomorphic encryption scheme using only modular arithmetic. The presentation will include a brief introduction to fully homomorphic encryption, an exposition of their construction and security reduction, and a brief discussion of their underlying hardness assumption (the approximate integer gcd problem). [relevant paper]
17+31.05.10: (Monday), 14:00, informal meetings:
Arkadius Kalka (BIU), The subword reversing method and its applications
[relevant paper]
13.05.10: Benny Applebaum (Weizmann), Public-Key Cryptography from Different Assumptions
This work attempts to broaden the foundations of public-key cryptography. We construct new public key encryption schemes based on new
hardness-on-average assumptions for natural *combinatorial* NP-hard optimization problems. We consider the following assumptions:
(1) It is infeasible to solve a random set of sparse linear equations mod 2, of which a small fraction is noisy.
(2) It is infeasible to distinguish between a random unbalanced bipartite graph, and such a graph in which we ``plant'' at
random in the large side a set S with only |S|/3 neighbors.
(3) There is a pseudorandom generator where every output bit depends on a random constant-size subset of the inputs.
We obtain semantically secure public key encryption schemes based on several combinations of these assumptions, including a scheme
which is based solely on Assumption 1, and a scheme which is based on a combination of Assumptions 2 and 3. These are arguably of
more ``combinatorial''/``private-key'' nature than any assumptions used before for public key cryptography. We also give some evidence
for our assumptions by showing that they resist certain classes of natural algorithms (i.e., semi-definite programs, AC0 circuits,
low-degree polynomials, and cycle counting), and by relating these assumptions to other problems such as planted clique and learning
juntas.
Joint work with Boaz Barak and Avi Wigderson. No background in cryptography is assumed.
[relevant paper],
[talk slides]
5.05.10: (Wednesday), 10:30 am, in the Algebra Seminar:
Tali Kaufman (BIU), Symmetric LDPC codes and local testing
Local computation tasks (as local testing, correcting, decoding) is
possible in codes based on polynomials. This is related to the fact that
such codes are highly symmetric, yet they are defined by short linear
equations. Codes defined by short linear equations are called LDPC.
In the heart of this work is the following question: Could we have
high rate codes which are highly symmetric, yet are defined by short
linear equations? In this work we construct codes with rate better than
polynomial codes that are defined by short equations. Moreover we
obtain bounds on the best rate of such symmetric codes.
Joint work with Avi Wigderson
28.04.10: (Wednesday), 12:00, joint with ENI seminar:
Arkadius Kalka (BIU), Parabolic subgroups and Garside subgroups of a Garside group
The well-known notion of a parabolic subgroup of an Artin-Tits group can be extended to the framework of Garside groups so that most of the
standard properties known in the Artin-Tits groups case are preserved. The extension is not trivial. Further, we consider the more general notion of a Garside subgroup
of a Garside group that nicely extends the notion of an LCM-homomorphism between Artin-Tits groups. Both, the notions of parabolic subgroup
and of Garside subgroup of a Garside group have been introduced by E. Godelle.
The conjugacy problem in Garside groups has been solved by M. Picantin, generalizing Garside's seminal approach. A slightly modified
approach, using fractional normal forms, leads to a solution for the subgroup conjugacy problem for all (conjugates of) Garside subgroups of
Garside groups.
26.04.10: (Monday), 14:00, informal meeting:
Arkadius Kalka (BIU), Gaussian and Garside monoids
21.04.10: (Wednesday), 12:00, Eran Liberman (BIU), Subgroup conjugacy problem in braid groups and similar groups
In the lecture we will give methods of solving the subgroup conjugacy problem for special type of subgroups for braid group and similar groups. We explain the importance of the problem and prove the solution.
8.04.10: Arkadius Kalka (BIU), Introduction to Quantum Computing V
Outline: Factoring, period finding, discrete logarithms, and the hidden subgroup problem
21.12.09: Arkadius Kalka (BIU), Introduction to Quantum Computing IV [Lecture Notes pp. 15-17]
Outline: The quantum Fourier transform, phase estimation, and order finding.
14.12.09: Ran Cohen (BIU), DLP on the critical group of finite graphs II
7.12.09: Itai Dinur (Weizmann), How to Solve it: New Techniques in Algebraic Cryptanalysis [related paper]
In this talk I will introduce a new kind of attack (called Cube Attack) on cryptographic schemes which can be represented by an (unknown) low degree polynomial with tweakable public variables such as a plaintext or IV and fixed secret variables such as a key. Its complexity is exponential in the degree but only polynomial in the key size, and it was successfully applied to several concrete cryptographic schemes. It is joint work with Adi Shamir.
30.11.09: Ran Cohen (BIU), DLP on the critical group of finite graphs
I plan to talk about a group that was suggested as a basis of DLP based cryptosystems in 2006 by Norman Biggs. This is the critical group of finite graphs (a.k.a Jacobian group of finite graphs). During 2007 and 2008 there were publications of two attacks against the DLP in this group. This group may be interesting for future research because it has many analogies with elliptic curves.
29.11.09 (Sunday), 12:00, special guest of the CGC Colloq, hosted by the Math Colloq:
Enric Ventura (Universitat Poli\`ecnica de Catalunya), Algebraic extensions in free groups with two applications
[Talk Slides]
In this talk, I'll introduce the concept of algebraic
extension of free groups, which appeared in the literature under
different contexts and by independent authors (I'll follow a unified
version due to Miasnikov-Ventura-Weil, and using Stallings graphs in
an essential way). This is a modern development trying to mimic the
theory of field extensions, among subgroups of a given free group.
Some results are totally analog while some other aspects behave in a
considerably more complicated way.
The talk will continue with two applications:
1) an algorithm to compute closures of subgroups with respect to certain topologies, and
2) a result about fixed subgroups of endomorphisms of free groups.
16.11.09: Arkadius Kalka (BIU), Introduction to Quantum Computing III [Lecture Notes pp. 11-14]
Outline: The first quantum algorithms: Deutsch, Deutsch-Jozsa, Simon's algorithm.
10.11.09 (Wednesday), 12:00, in the Bar-Ilan Combinatorics Seminar:
Arkadius Kalka (BIU), Complexity of relations in the braid group
We describe a new method to give lower bounds on the complexity of word
problems in certain groups. As an application, we show that for each $n$
there is a sequence of words of length $n$ in the generators of the braid
group $B_n$ that represent the identity element of $B_n$ and such that the
number of braid relations of the form
$\sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}$ needed
to pass from these words to the empty word is quadratic with respect to
the length of the word. Thus we exhibit a quadratic lower bound even
without counting the commutativity relations.
This is a joint work with Joel Hass and Tahl Nowik.
9.11.09: Arkadius Kalka (BIU), Introduction to Quantum Computing II [Lecture Notes pp. 6-10]
Outline: Reversible computation, quantum cicuits, universal quantum gates, quantum complexity.
4.11.09 (Wednesday), 10:30 am promptly, joint with BIU Algebra Seminar: John Meakin (University of Nebraska), Subgroups of monoids
One obtains significant information about the structure of large classes of monoids by studying their embedded subgroups. For example, a great deal of information about the full linear monoid of n by n matrices over a field (or more generally of a linear algebraic monoid) is determined by the subgroup structure of its group of units. As another example, Bass-Serre theory may be used to study the subgroup structure of certain amalgams of inverse monoids and this may be exploited to understand the structure of amalgams of some well known C*-algebras. The set of idempotents of a monoid carries the structure of a biordered set, first elucidated by Nambooripad in the 1970's. Topological techniques may be used to study the subgroup structure of monoids freely generated by biordered sets. In this talk, I will discuss some recent work and unsolved problems.
26.10.09: Arkadius Kalka (BIU), Introduction to Quantum Computing [Lecture Notes pp. 1-5]
This is the first lecture of a course:
We will give an elementary introduction to quantum computation starting from
the scratch. The emphasis of this course will be on quantum algorithms. The
most famous example is the celebrated Shor's quantum algorithm for integer
factorization which, once a quantum computer with sufficiently many qubits
will be build, may break the RSA public key encryption. But we're going to
cover also other quantum algorithms and topics of quantum complexity, quantum
information, and quantum communication.
The conclusive topic list will be decided during the semester - may be
depending on the preferences of the audience.
Everyone who wants to join me learning a fascinating new subject lying on the
border of mathematics, computer science and physics is welcome.
Outline: Brief introduction to quantum mechanics and its principles: superposition, measurement, unitary transformations.
Basics of computation: Boolean circuits, P, BPP, reversible computation.
23.06.09: Ari Belenkiy (BIU), Shor's factorization algorithm for quantum computers
Retelling the old (1994) story.
9.06.09: Peter Storm (University of Pennsylvania and HU), Hash functions using SL2
The talk is about an idea of Tillich and Zémor for using 2x2 matrices to produce hash functions.
(2 and 16).6.09: Ran Cohen (BIU), Nonstandard discrete log and Diffie-Hellman problems
This is a survey of a recent paper by Neal Koblitz and Alfred Menezes.
(19 and 26).5.09: Boris Kunyavskii (BIU), Digest of elliptic curve cryptography
This is a brief overview of ECC conceived as an introduction to the forthcoming talks by Ran Cohen on nonstandard discrete log problems.
(5 and 12).5.09: Boris Kunyavskii (BIU), Public key cryptosystems arising from algebraic surfaces over finite fields
We shall discuss several versions of public key cryptosystems based on the following principle: it is easy to draw a plane curve through two given rational points but it is hard to find even one rational point on a given curve. Most protocols can easily be broken (by finding a point lying in a finite extension of the ground field) but there are still no known attacks against other ones.
28.4.09 No meeting (Remembrance Day)
21.4.09: David Garber (HIT), Length-based attack on the shifted conjugacy search problem
Dehornoy (2006) has suggested an authentication scheme which is based on the shifted conjugacy search problem. Longrigg and Ushakov (2007) cryptanalyze the suggestion of Dehornoy, and they show that they can break the scheme, by reducing the shifted conjugacy search problem to the well-studied conjugacy search problem. Despite this fact, it is still very interesting to check if the length-based approach is applicable for this problem. Based on previous results, this attack with some modifications (like the use of memory) should be applicable in this case too. In the talk, we will present Dehornoy's scheme, Longrigg-Ushakovs cryptanalysis, and our results on the length-based cryptanalysis of this scheme. Joint work with David Hai Gootvilig.
(9 and 16).4.09 No meeting (Passover vacation)
(19 and 26).3.09 + 2.4.09: Robert Schwartz (BIU), Computational aspects of nilpotent groups.
4.2.09, 12:00 (joint with ENI Seminar): Arkadius Kalka (BIU), Solution to the subgroup conjugacy problem for $B_m\le B_n$.
21.1.09, 12:00 (joint with ENI Seminar): Arkadius Kalka (BIU), The shifted conjugacy decision problem in braid groups and its generalizations.
Shifted conjugacy defines a left-selfdistributive operation on the braid
group B_{\infty } with infinitely many strands, introduced by P. Dehornoy.
It is connected with the discovery of a left-invariant total order on braid
groups. Dehornoy also proposed an authentication scheme based on shifted
conjugacy.
It is an open problem whether the shifted conjugacy decision problem (CDP) in
B_{\infty } is decidable. This problem
can be reduced to a subgroup CDP of B_{n-1}\le B_n for some n\in
\mathbb{N}. We settle this problem by reduction to an instance of a
simultaneous CDP in B_n.
More general, it is an open problem whether the subgroup CDP for B_m \le B_n
with m < n is solvable. We also solve this problem without making a detour via
the simultaneous CDP by a variation of Garside's approach, and we present a
deterministic algorithm. We improve this algorithm using minimal simple
elements a la Franco and Gonzalez-Meneses.
This also provides solutions to shifted CDP's for some generalized shifted
conjugacy operations.
20.1.09, 12:00 (joint with Combinatorics Seminar): Moshe Newman (BGU), Combinatorics and algebra of homogeneous one-relator semigroups: An elementary discussion.
We will consider a semigroup on a finite set of generators, which is
described by one relation, that equates two words of equal length.
That is, we have an equation
u = v where u and v are words of the same length on some alphabet.
Since our equivalence can only equate words of the same length, we can talk about the size of an equivalence class, or of an element in the semigroup. For a combinatorist, there is an obvious question: how many different equivalence classes are there of length n?
Equivalently, how many semigroup elements are there of length n?
We will take the usual route for an enumerative combinatorics:
Call this number f(n), and let F(x) be the generating function
F(x) = Sum f(n) x^n, n = 0 to infinity.
Instead of asking about f(n) directly, we ask what can be said about F(x)?
We make the following conjecture and give a number of elementary
and illuminating examples in the talk to back it up. The conjecture is that given a semigroup equivalence corresponding to one relator of the form u = v with u and v of equal length,
one can take a set of unique representatives for the equivalence
classes, such that the set is a regular language. This would imply an
elementary proof that F(x) is always a rational function.
14.1.09 (Wednesday), 10:30 am promptly, joint with BIU Algebra Seminar: Daniel Wise (McGill University), The W-cycle conjecture.
I will describe an elementary problem which arises from consideration of a one-relator group < a, b | W >. The problem is about bounds on the number of cycles of a certain type in a labeled oriented graph. The problem seems destined for a few puzzlists in a Putnam competition. But while it wouldn't surprise me if someone came up with a gem of a proof, after 5 years, I've given up on finding a (direct) solution. I will present some partial results, and seek help from the audience towards a resolution or a counterexample...
7.1.09 (Wednesday - note special day and time!): Two talks, joint with BIU Algebra Seminar:
10:00-11:00: Mark Lawson (Heriot-Watt University), Representations of the polycyclic monoids
The polycyclic (or Cuntz) inverse monoids are amongst the most interesting classes of inverse monoids. They arise in settings as diverse as the syntactic monoids of correct bracketing languages in formal language theory and in the construction of the Cuntz C*-algebras. In this talk, I shall introduce these monoids from scratch and discuss their representations by means of partial permutations. This work has connections with papers by Bratteli and Jorgensen and of Kawamura on iterated function systems and representations of the Cuntz C*-algebras, and with constructions of certain of the Thompson groups.
11:00-12:00: Stephen Miller (Rutgers University), Rounding in matrix groups
I will describe the problem of rounding elements of Lie groups to finitely generated subgroups, which is a nonabelian generalization of lattice rounding in Euclidean space. Unlike that situation, one can prove results which rule out approximation algorithms as uniformly effective as LLL (unless P=NP).
(joint work with Evgeni Begelfor and Ramarathnam Venkatesan)
1.1.09: Michael Lifliand (Cisco Israel), Cryptanalysis of LUT.
This work describes cryptanalysis of the shared key LUT encryption. The goal of the work is evaluation of this method of encryption as an attempt to create a proven security solution. There are two main features of the LUT encryption that are elaborated for this goal. Simplicity of the processing logic gives an opportunity of combinatorial estimation of hypothetic attack against such cipher. Absence of an inverse functional conversion prevents most of known types of cryptographic attacks including linear and differential cryptanalysis. Described cryptanalysis of the LUT encryption estimates minimal number of tests that should be executed for any possible attack.
13+20+27.11.08: Arkadius Kalka (BIU), Introduction to the Braid group and cryptography
6.11.08: Brad Young, The Math That Saved the World: A Mathematical Analysis of the Rejewski and Turing Cryptographic Cracks of the Nazi Enigma Machine
The Allied forces in World War II were victorious in part due to the success of top-secret cryptographic analysis of German communications, which were encrypted using the "Enigma Machine". Despite its seemingly unbreakable cryptographic strength, the Enigma Machine eventually fell to a series of brilliant mathematical analyses, at first in Poland by Marian Rejewski, and later in England by Alan Turing. This presentation will delve into the mathematical nature of these cracks and will also note their historical impact, both in terms of impact on WWII as well as resulting advances in computational devices and applied mathematics.
10.6.08, 19.6.08: Karin Forkosh, Congugacy in Thompson's group F, after Kassabov and Matucci
13.5.08: Doron Zeilberger (Rutgers), Older Mathematicians Make Beautiful Provers
Jointly with Combinatorics Colloquium
G. H. Hardy famously (and stupidly!) said that "mathematics is a young man's game". This "meta-theorem" has been already refuted many times [both the "young" part and the "man" part, but in this talk I will focus on the former]. Notable counterexamples include
2.3.08 Haya Shulman (BIU), Cryptography and Complexity [presentation]
We give an overview of complexity theory and present one of its main
goals: proving lower bounds on resources. We then introduce
some of the basic (uniform) complexity classes, e.g. P, NP, NPC.
We explore the relation between complexity and cryptography, focusing
on the basic concepts of randomness and knowledge.
We further discuss worst versus average case complexity and consider
the interest in average case complexity for use in security.
When discussing efficiency, we present the difference
between what theoreticians and practitioners refer to as efficient.
We conclude by presenting an important goal of cryptography, which is
to understand and to identify the minimal assumptions necessary for
obtaining security.
24.2.08 Fabienne Chouraqui (Technion), Rewriting systems and embedding of monoids in groups.
Joint with Algebra Colloquium
A connection between rewriting systems and embedding of monoids in groups is presented. We consider monoids and groups with the same presentation and we show that if the group admits a complete rewriting system, which satisfies the condition that each rule with positive left-hand side has a positive right-hand side, then the monoid admits also a complete rewriting system and it embeds in the group. As an example, we give a very simple proof that right angled Artin monoids, embed in the corresponding right angled Artin groups. This is a special case of a celebrated result of Paris that Artin monoids embed in their groups.
12.2.08+19.2.08 (Tuesdays, 12:00--13:30): Stuart Margulis (BIU), Introduction to Computational Group Theory, parts II+III
Joint with Combinatorics Colloquium - note special day and time!
Outline:
A. Algorithms and decidability
1. The Word, Isomorphism and Conjugacy Problem for Groups.
2. The Membership Problem for Subgroups.
3. Everything is undecidable (almost).
B. Algorithms for Computing with Finitely Presented Groups
1. Coset Enumeration.
2. The Knuth Bendix Procedure.
3. Automatic and Hyperbolic Groups: Example- The Braid Group.
4. Garside Monoids and Groups: Example- The Braid Group.
3.2.08 Michael Lifliand (Cisco Israel), New proposals for fast encryption
This work describes a new approach to creation of fast encryption
methods with symmetric (shared) key. The result solutions are
intermediate between block and stream ciphers. The main advantages of
both types of ciphers are realized and most of disadvantages are
eliminated. The new approach combines built-in calculation of the hash
for data integrity, pseudo-random generator, and option for dual shared
keys, all important properties for secure applications. The new methods
may be designed for different size of shared key. Both software and
hardware implementations of the new methods are fast and simple even in
any 8-bit controller and may be used in various applications. The work
presents the basic cryptanalysis of suggested methods. It proves basic
features and gives an option to claim the strength of suggested
encryption.
For more details, contact x@cisco.com where x=mliflian
27.1.08 Stuart Margulis (BIU), Introduction to Computational Group Theory, part I
Outline:
1. Turing Machines and the Halting Problem.
2. Finitely presented semigroups and undecidablility of the Word Problem.
20.1.08 No meeting (lecture postponed).
13.1.08 Arkadius Kalka (BIU), The Algebraic Eraser(TM): Details and and example
The main example of the general scheme presented by Prof. Goldfeld would be introduced, with an explanation of its connnection to the simultaneous conjugacy search problem in the braid group, and some additional details. Based on their paper on the topic.
6.1.08: Dorian Goldfeld (Columbia University), Actions, commutator identities, and the Algebraic Eraser(TM)
Special Mathematics Colloquium
An algebraic structure arising in formulation of a lightweight key agreement protocol yields a new concept of commutator whose identities are quite traditional. This is joint work with Iris and Michael Anshel.
30.12.07: No meeting (Representation Theory Conference)
16+23.12.07: Haya Shulman (BIU), Asymmetric Cryptography [presentation]
We initiate this series of talks with the preliminaries and discuss a rigorous approach to cryptography and security, present the definition of encryption scheme and the definitions of the required security specifications for asymmetric and symmetric encryption schemes and consider the distinctions thereof. We show that there does not exist information theoretically secure or deterministic public key encryption scheme, as opposed to private key encryption scheme. We then proceed to the discussion of the efficiency considerations and present the construction and the proof of a hybrid encryption scheme.
9.12.07: No meeting (Hanukkah).
18+25.11.07; 2.12.07: Luda Markus (BIU), Generic-Case Complexity, Decision Problems in Group Theory, Applications in Cryptography
The general idea of generic behavior in the context of group theory was introduced by M. Gromov when he defined the class of word-hyperbolic groups. This was made precise by Olshanskii and Champetier. The aim of this talk is to discuss a recent paper (? 2002) of I.Kapovich, Myasnikov, Schupp and Shpilrain concerning "generic-case complexity", which deals with the performance of an algorithm on "most" inputs. It turns out that for a very large class of finitely generated groups the classical decision problems of group theory -the word problem, conjugacy and membership problems;-all have linear generic-case complexity. This explains why LBA (length based attacks) give surprisingly good results in breaking the AAG scheme. Moreover, this cryptoanalysis provides a good method to choose strong keys (groups, subgroups or elements) for various realizations of the AAG-type schemes that would prevent some of the known attacks.
11.11.07: Boaz Tsaban (BIU), An introduction to CGC
We give some motivation for the topic, and then (since time permits) explain a major obstacle that has to be overcome in order to obtain a good public key scheme based on noncommutative groups. This obstacle can be viewed as a useful "generic" heuristic algorithm for solving equations in noncommutative groups. This win/win situation is typical to the field of CGC.