Knapsack Encryption Scheme Broken

Ernest Brickell, a graduate of Ohio State, has successfully broken the iterated knapsack encryption scheme. The achievement finishes a search begun in 1977 when Ralph Merkle, then at Stanford, and Martin Hellman first devised a cryptographic system based on the knapsack problem. Once a cryptographic scheme is announced, the immediate reaction is to attempt to show its insecurity. In early 1982, Adi Shamir, of the Weizmann Institute of Science in Israel, announced that he had broken one version of the code. Merkel was distressed by the media attention to this special case solution. Shamir had worked only with a one-step iteration. Merkel felt that multiply- iterated versions of the code would be secure, and offered a $1,000 prize to anyone who could show otherwise. Brickell has collected his check.

The knapsack problem can be summarized as follows: Given a set of positive integers and a target - sum, is there a subset of the set of integers that adds up exactly to the sum? In practice, the target is a number of 62 digits and the set may consist of a large supply of 60 digit numbers. To disguise the problem further, the numbers of the set may be altered using techniques of modular arithmetic. The process of modular multiplication may be repeated several times over, giving the iterated versions of the knapsack codes. The inventors of the code felt that 20 iterations would be sufficient to achieve a secure code. Brickell's work demonstrates that this is not the case. In fact, his procedure is essentially independent of the number of iterations that have taken place. He has found a way to use a single function to change the series of iterations into an easy version of the knapsack problem. The method uses results from the theory of lattices and produces a solution to the original problem without discovering the original set of integers used. His code breaking algorithm has successfully treated encrypted knapsacks that are 100 numbers in length and have undergone 20 iterations. That was done using less than 2 hours of computation time on a Cray 1S computer.

These knapsack systems are much faster to implement than the other most widely used crypto-system based on the factoring of very large numbers. Although these knapsack systems have been seriously considered for important applications, they are not currently in commercial use.

Brickell's current position is in the Applied Mathematics Division at Sandia National Laboratories. The people at Sandia have earned a reputation as being hard at work devising attacks on various public-key cryptographic systems.

While his work is impressive and unsuspected, Brickell is quick to point out that. his achievement applies only to the currently devised knapsack systems which employ modular arithmetic for disguising the process. It does not rule out the possibility that there could be secure systems based on other techniques.

(Brickell received his Ph.D. degree fron The Ohio State University in 1981 with specialization in combinatorics. His thesis, "The Incidence Structure of d and d + I Flats in the Direct Product of Projective and Affine Space," was directed by Dijen Ray-Chaudhuri.)

There have been many positive events in the department this year. Let me share some of them with you.

We have been encouraged by significant improvement in the scores incoming freshmen have achieved on the departmental placement tests. It is a clear sign that schools are preparing their students more effectively for a college education. The department remains ready to assist in any way it can. Bert Waits runs the Early Mathematics Testing Program, funded by the Board of Regents and operating statewide. Its success is well recognized and other states are planning to model the program. Joan Leitzel and Frank Demana are supported by the National Science Foundation and SOHIO in their articulation work with the schools.

Interest in our honors program has increased significantly this year. A total of 378 freshmen registered for mathematics honors courses last fall, 100 more than the year before. The need for special program activities for these capable students is quite important. Commons space and study areas continue to be a serious problem.

Graduate student enrollment totals 150, with roughly an equal split between domestic and foreign students. The quality of our students continues to rise. This year we extended offers of University Fellowships to 17 of our incoming students. The proposal by the Federal govemment to tax fee waivers is of serious concern. Out-of-state students would be particularly penalized. The Graduate School is presently considering several options that would offset the projected loss of student income.

Arnold Ross is preparing to offer his summer program for gifted high school children for the twenty-seventh consecutive year. The instructional side of the program is funded by the University. Thus far, however, we have been unable to fund student scholarships. This area has been forced to rely on private contributions.

There have also been changes in some of the support staff. Our head librarian for 16 years, Mrs. Janina Talat-Kielpzs retired last year. Her successor, Ms. Heidi Mercado, assumed the position this winter. Her previous post was at the University of Washington. We are looking forward to a long and profitable association.

If you were in the department during the last 17 years you will undoubtedly recall Mrs. Dorothy Whiteman, who ran our duplicating facility. Dorothy, also, retired this winter and similarly will be missed by everyone who knew her.

We have enjoyed a very successful recruitment season, attracting two workers in differential geometry, one in representation theory and one in logic. Twenty faculty from other institutions have already accepted visiting positions here for 1985-86. We are looking forward to another year full of exciting mathematics with research and discovery leading the way from faculty spending sleepless nights elated over their new results to even more vigorous discussions by the coffee pot.

Alan Woods Chairman

Special Thanks

In the last issue we presented an invitation and a challenge to those of you who have completed study at Ohio State to contribute to the support of special projects in the department. We thank all of you who responded to that request. It is with your help that we will be able to continue offering quality programs and special opportunities for students. A contribution of $25.00 or more will enroll you as a "Mathematics Motivator." Checks should be made payable to The Ohio State University Development Fund and mailed to James R. C. Leitzel, Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, Ohio 43210-1174. Any contribution you make, either generally or to an already established fund, is tax deductible.

Department News

The department maintains a strong reputation in the broad mathematics community. There are always several of our faculty on leave at universities across the country and around the world. The department also hosts visitors representing diverse fields of expertise. This year 22 visitors have spent time working within various research groups in the department. Our regular staff continues to grow as well. This year the department has hired 4 instructors, 2 research instructors, and 4 regular faculty. We welcome all these new individuals to the University. The four regular faculty are Ruth Charney, associate professor in the area of topology, and three assistant professors, Sheldon Kamienny, Karl Rubin and Alice Silverberg, in the area of number theory.

Harvey Friedman was among a group of distinguished scientists, mathematicians and engineers invited to a luncheon with President Ronald Reagan at the White House. Friedman, who has won the National Science Foundation's Waterman Award, was named one of America's top 100 young scientists by Science Digest magazine. The latter recognition was achieved through nomination by a panel of 55 highly respected members of the scientific community.

Hans Zassenhaus, professor emeritus, continues to receive honors. He was awarded a special grant from the Alexander von Humboldt Foundation, to visit the University of the Saarland, Saarbrucken, West Germany; a grant from Deutsche Forschungsgemeinschaft to participate in a project on Representation Theory at Essen University; and has received an Honorary Professorship at the Johannes Kepler University, Linz, Austria. The official investiture will take place during the International Conference on Symbol Manipulation to be held at Linz in April, 1985.

The department depends strongly on the good work of Graduate Teaching Associates in meeting its enormous and challenging teaching responsibilities. The department is pleased to extend congratulations to Agnes Babiera, Anthony DeGennaro, Eric Henderson and John Kernast who were nominated by their students for the 1985 Graduate School Award for classroom teaching.

Gerard M. Williger, an undergraduate majoring in astronomy, mathematics and physics, has been awarded the prestigious Marshall Scholarship. This award is given to an American student for study in Great Britain. The scholarship grant is $7,000 in addition to tuition, room and board for a two year period. He will study at the University of Cambridge. As well as maintaining a strong academic record, he has been active at the University in the OSU Marching Band and as a representative of Undergraduate Student Government on the University Senate. At the annual Honors Banquet of the Colleges of Arts and Sciences, he was named one of the two representatives from the College of Mathematical and Physical Sciences to receive the Excellence in Scholarship award.

Carl Phillips, an undergraduate with a double major in mathematics and political science, was a finalist in the National Truman Scholarship competition. The Scholarship is designed to provide financial support for students aspiring to a career in public service. After rounds of personal interviews, he has been named first alternate from the State of Ohio.

The Rasor-Bareis-Gordon Mathematics Contests are held each year. Cash awards to the winners of these contests come from the correspondingly named endowment funds honoring Grace M. Bareis, Kate Deterly Gordon and S.E. Rasor. The prizes are awarded in three divisions. The winners of the Rasor division were John C. Clifford, Kenneth C. Adkins, Thomas S. Boardman, Steven J. Decker, and Gregory M. Saunders. The Bareis division prizes were given to Thomas E. Barrett, Oliver P. King-Smith and Timothy A. Snyder. In the Gordon division awards went to Aviad Pundak-Muntz, Todd A. Miklos, and Charles D. Carlson, Jr. Congratulations to all these young people on their excellent performance.

Steve Beach and Bob Lowery, undergraduate students with majors in the department, are members of OSU's College Bowl Team. The team won the mid-western tournament at Eastern Michigan University and placed 4th in the national championship competition held during April at Emory University, Atlanta, Georgia.

In Memoriam

Richard Allen Bieberich, M.Sc. '67' Ph.D. '73 under the direction of Bogdan:Baishanski, died January 9, 1985 after a long illness. He joined the faculty of Ball State University, Muncie, Indiana in 1979. While there he organized several cross disciplinary seminars, encouraged good teaching and was an active member of the Indiana section of the MAA serving as Secretary-Treasurer since 1983. His research and working library has been donated to The Ohio State University Department of Mathematics.

Earl J. Mickle, professor emeritus, died April 11, 1985. Earl joined the Department of Mathematics as graduate student in 1937, received his Ph.D. in 1941, and retired as professor in 1980. He was the author of more than twenty-five research papers in the fields of real variables, measure theory, and topological groups. During his career he directed twelve doctoral dissertations and served on many influential committees of the department, college and university.

Additional responses from alumni have been received. Please take a minute, complete the form, and send it along to us. We are interested in what you are doing.

Neal B. Andregg B.Sc. '34, M.A. '37, Ed.D. '51 from Michigan State University, retired after 39 years of service with the Air Force and Army as Director of Education, Fort Gordon, Georgia.

Georgia Benkart B.Sc. '70, Ph.D. '74 from Yale University, currently Professor of Mathematics, University of Wisconsin, Madison.

Art Socian M.Sc. '78, currently Director, RAMIS Consulting with SOS Systems, Inc., East Brunswick, New Jersey.

Mark A. Chambers B.Sc. '82, currently a third year medical student at OSU going through clinical rotations.

Carol Taylor Del B.Sc. '70, currently Assistant Vice President and systems project manager at BancOhio (computer systems).

Al Giambrone M.Sc. '70, currently Professor of Mathematics, Sinclair Community Conege, Dayton, Ohio.

Thomm A. Hern M.Sc. '66, Ph.D. '69 just returned to his position at Bowling Green State University from a two year leave of absence spent at the University of North Carolina, Chapel Hill. Main current interests are mathematics of computer graphics, applications of graphics to the teaching of mathematics, geometric modeling and computer-aided design. In June, 1983 he was a member of an MAA delegation of undergraduate mathematics educators that visited the People's Republic of China.

Mack Hill M.Sc. '66, Ph.D. '71 from University of Cincinnati, currently Professor of Mathematics at Worcester State College, Worcester, Massachusetts.

Edwin R. Lassettre M.Sc. '63, currently Senior Technical Staff member at IBM, Los Gatos, California.

Albert Merkel B.Sc. '67, M.5c. '68 from University of Chicago, M.B.A. '83 from DePaul University, currently data planning coordinator and lead data base designer at Sargent & Lundy Engineers in Chicago.

Edward A. Molnar M.Sc. '70, Ph.D. '72, Major U.S. Army, after working at the Pentagon for seven years was transferred to West Point in '83 to serve as an Assistant Professor of Mathematics.

Barry Paul B.Sc. '76, M.Sc. '78 in Actuarial Science from University of Nebraska- Lincoln, Fellow of the Society of Actuaries and currently manager of the corporate Actuarial Department of All-State Life Insurance Company.

Dorothy Pavkov-Feucht M.A. '60, after 21 years with IBM's federal systems division in the Washington, D.C. area, married and moved to Oregon where she founded a computer software company. Product is an integrated electronic mail, computer conferencing, calendar management, word processing and file management package for computers.

Thomas H. Southard B.A. '32, M.A. '33, Ph.D. '36, retired as Professor Emeritus from California State University at Hayward.

Harold B. Weiland B.Sc. '66, currently a scaler at Bemoth Boat Yard, Psyht, Washington.

David M. Weiss M.Sc. '66, M.B.A. '76 from Baruch College, currently Chief Transportation Engineer with Gibbs and Hill, Inc., New York City. He serves as chair of the American Public Transit Association's Rail System Computer Design Subcommittee and a member of the IEEE safe headway standards working group.

Andrew Woldar M.Sc. '78, Ph.D. '84, currently lecturer at OSU, has accepted a tenure track position at Villanova University, Villanova, Pennsylvania beginning Autumn 1985.

Rubin Named Sloan Fellow

Karl Rubin, assistant professor, has been selected as a Sloan Research Fellow. Selection under this program, sponsored by the Alfred P. Sloan foundation, follows a well-developed procedure designed to identify young scholars who show great promise for doing original work in their field. The total number of awards made each year by the Foundation to individuals working in mathematics is 20. Over the years, the winners of these awards have made major contributions in their disciplines. Professor Rubin is a relatively new member of the department and specializes in algebraic number theory. He plans to use this award to visit the Mathematical Sciences Research Institute at Berkeley which will be conducting a program on "Number Theory and Connections with Algebraic Geometry." Another part of the academic year '86-'87 he will spend at the Institute for Advanced Study at Princeton.

Problem Corner

(Material for this column is prepared by Gerry Edgar)

Another chance to try your problem solving skills! Send your solutions to the Editor. The best (or most interesting) solutions will be included in the next issue of Math Matrix. You are encouraged to submit problems for inclusion in this corner. Problems with an applied flavor are especially welcome.

Problem 3. Does e^x/x have an indefinite integral of the form A(x)e^B(x), where A(x) and B(x) are rational functions?

Problem 4. A square cake with icing on the top and on the four sides is to be divided into seven pieces. Each piece should have the same volume of cake and the same area of icing. Is this possible?

Solutions to previous problems.

Problem 1. (from the Mathematical Magazine, January, 1882). Two men, A and B, hired a horse and carriage for $7, to go from Providence to Boston and back, the distance between the cities being 42 miles. At Attleboro', 12 miles from Providence, they took in C, agreeing to take him to Boston and Back to Attleboro' for his proportionate share of the expense. At Walpole, 24 miles from Providence they took in D, agreeing to take him to Boston and back to Walpole for his proportionate share of the expense. What ought each person to pay?

In this problem, there are two different ways to interpret the phrase "proportionate expense." We received four solutions. Two of them preferred the interpretation where A and B pay about $2.23: Zakaria A. El-Galamneh (OSU, Lima) and Sister Loretto Thoma (Chatfield College). One, from Patricia L Johnson, preferred the interpretation where A and B pay about $2.42. The fourth solution from A. Giambione (M.Sc '70) was the most interesting one. Here it is: There are two points of view that one might take as to the meaning of the phrase "proportionate share of the expense."

Under one interpretation we might say that the amount each man pays should be proportional to the ratio of the number of miles that he rides to the total number of man-miles that the carriage accrues. In this case, since the total number of man-miles is 264, we have:
A and B each pay (84/264)X$7 (about $2.23)
C pays (60/264)X$7 and (about $1.59)
D pays (36/264)X$7. (about $.95)

A second interpretation is that the $7 charge is for the number of miles that the carriage travels and that this nets out to a fixed cost per mile for use of the carriage regardless of the number of passengers. Then each man pays in inverse proportion to the number of men in the carriage during the miles that he rides. In this case we divide the trip into three segments. Since A and B are alone in the carriage for 24 miles they each pay (1/2)X(24/84)X$7 for this segment of the trip. A, B and C ride alone for 24 miles and thus each pays (1/3)X(24/84)X$7 for this segment. In the remaining segment A, B, C and D ride together for 36 miles and pay (1/4)X(36/84)X$7 each. The final talley gives:
A and B each pay about $2.42
C pays about $1.42 and
D pays about $.75.

Now A and B would prefer the first plan, C and D the second. But A and B are in the driver's seat, so, if they are clever, they will persuade C and D to accept the first interpretation. But if they are really clever ... well consider the following scenario: At the carriage shop A and B agree to split expenses evenly and so they pay the proprietor $3.50 apiece. Upon encountering C they suggest to him that the fare for an 84 mile trip is $7, which they can readily verify by exhibiting their bill. Since C will be traveling 60 miles and this is 5/7 of an 84 mile trip he should pay $5. This sounds reasonable to C so he pays them $2.50 each. Upon encountering D, C, having grown in business acumen from his association with A and B, joins with A and B in suggesting to D that since he will be travelling 36 miles, which is 3/7 of a $7 trip he should pay $3. He finds this logical and so pays A, B, and C $1 each. So D gets 3/7 of a $7 trip for $3. C gets 5/7 of a $7 trip for $4. And clever A and B ride free! But with a few more well placed passengers we could give C a free ride and eventually D as well. If we could get hold of an infinitely large carriage and an unlimited supply of hitchhikers maybe no one would have to pay! Shades of Zeno!

Changing Student Preparation

Colin B.B. Bull recently retired from the University. A geophysicist and glaciologist by training and interest, he first served as Director of the Institute of Polar Studies then as chair of the Department of Geology. For the past twelve years, he has been Dean of the College of Mathematical and Physical Sciences. During his tenure as Dean, many significant changes occurred in the College. The quality and quantity of research increased and many outstanding appointments were made. In the following article he speaks of another aspect of his work. Although he now signs his letters with the title "Expired Dean," he has far from completed his special agenda of future writing activities. We in the College will miss his wit and his support.

To some extent I find it odd that, as Dean for the last twelve years of what is clearly the strongest research College at The Ohio State University (my colleagues in other colleges will excuse me, I'm sure) the accomplishment in which I take most pride is the effect that the efforts of members of our College have had on the high-school preparation of our entering freshmen, particularly in mathematics.

The Ohio Revised Code, which controls our admissions policy, states, in part: "A graduate of the twelfth grade shall be entitled to admission without examination to any college or university which is supported wholly or in part by the state..." When the freshman arrives on campus, usually at Orientation before formal admission, we subject him or her to an advisory Math Placement Examination, that has remained of demonstrably constant standard since 1965. In 1965, about 11% of the entering freshmen on the Columbus Campus in the Autumn Quarter placed Level 1, ready for Calculus or better, and about 8% of them placed Level 5, very clearly needing some remedial mathematics before they were ready to take any College-level mathematics course. A few years later, when we had introduced Math 100 for these Level 5 students, a pretest, on the first day of the course, showed that only half of them could calculate correctly how much each student gained when three pizzas were divided equally among four of them.

The years following 1965 were academic disasters across the country. Every measure of academic achievement of high-school students showed continuing declines. At OSU this showed itself in the Math Placement Scores. By 1972, when I became Dean, the Level 1 percentage had decreased to 8% and the Level 5's were up to 22% of the incoming class. We tried to accommodate them to provide courses that would lead them into proper College level mathematics. In the following year John Riedl, our Associate Dean, and I tried for the first time to interest the University in the second part of that "Open Admission Statute," which continues, from the part quoted above, as: ". . . but for unconditional admission may be required to complete such units not included in his high school course as may be prescribed, not less than two years prior to his entrance, by the faculty of his institution." The date was too close to the stressful years of the late 1960's for the move to be acceptable, and the state of our entering freshmen continued to deteriorate. By 1979 about 29% of the entering freshmen in Autumn Quarter, on the Columbus Campus, placed Level 5, and on our other Campuses and in other quarters in Columbus the number approached, and often exceeded, 50%.

However, before the nadir, a group of our stalwart friends in the Math Department had decided that it was pointless to try to apportion blame for the decline, and better to do "something about it." In 1977-78 they agreed to give a modified Math Placement Test to the Junior year class at Westland High School. The result was outstanding: In the following year twice the historical average percentage of seniors took worthwhile math courses, and in 1979, on the regular Math Placement Test, the number of students placing Level 1 increased four-fold over the historical average for that school.

In the following years 7, 37 and 107 schools asked that we give an Early Placement Test, all of which we paid for from the College budget. Then, in response to our plea that we were performing a service for all of the Universities in the State, the Board of Regents helped us with funding. To abbreviate a long and successful story, in 1983-84 Bert Waits, in cooperation with all of the other state-assisted Universities, tested over 60,000 juniors in more than 600 schools state-wide, at a cost of $150,000 or so. We reckon that the program saves most of them at least one math course at the University, a bargain by anyone's standards. In the meantime we had persuaded the Board of Regents and the State Board of Education to convene a powerful "Advisory Commission on Articulation between Secondary Education and Ohio Colleges", the recommendations of which, published in 1981, included a college preparatory curriculum specifying 3 units of mathematics, fairly narrowly defined, and a distinction between conditional and unconditional admission, based on this college preparatory curriculum. Without too much trouble we persuaded the Board of Trustees and the University Senate to accept this new admission policy, to take effect in Autumn 1984.

The performance of our entering freshmen has shown a spectacular change, unmatched as far as I know in any other major state University: In Autumn 1984 the entering freshmen placing Level 1 had doubled to 11% from its 1979 percentage, and the remedial Level 5 had shrunk to 14%, half of the 1979 figure. From the early applicants for 1985 we see signs that the progress will continue.

Of course the credit for all of this really belongs to those aforementioned Math Department stalwarts, Joan and Jim Leitzel, John Riedl, Frank Demana and Bert Waits in particular, but it has been such a pleasure to be associated with them over the years that I'm not going to gainsay my part in encouraging them, providing support, and persuading the Board of Regents, the Trustees and the University Senate to do the "right thing" by the youth of Ohio. It's immodest to say so, but I really think that we can be moderately proud of ourselves.

[0]