On Public-key Steganography in the Presence of an Active Warden

The Book Review Column1by William GasarchDepartment of Computer ScienceUniversity of Maryland at College ParkCollege Park,MD,20742email:gasarch@In this column we review the following books.They are all in cryptography!1.Cryptological Mathematics by Robert Lewand.Reviewed by William Gasarch.Thebook is mostly about pre-RSA crypto.Is this topic worth covering?If so,is this the book to use?Alice and Bob debate his point.2.Data Privacy and Security by David Salomon.Reviewed by Nick Papanikolaou.De-spite the title this is also a textbook on cryptography.It covers pre-RSA,RSA,and also Steganography which is unusual.3.Cryptography:An Introduction by V.V.Yaschenko,Cryptanalysis of Number The-oretic Ciphers by S.S.Wagstaff,Jr.,RSA and Public-Key Cryptography by R.A.Mollin,and Foundations of Cryptography,Vol.1:Basic Tools,by O.Goldreich.Jointly reviewed by Jonathan Katz.If you want to be able to tell a good crypto book from a bad one then you must read this review.The most common faults are(1)not being rigorous enough,and(2)really being a number theory text in disguise.Books I want ReviewedIf you want a FREE copy of one of these books in exchange for a review,then email me at Reviews need to be in LaTeX,LaTeX2e,or Plaintext.Books on Algorithmsbinatorial Optimization:Packing and Covering by Cornuejols.2.Algorithms:Sequential,Parallel,and Distributed by Berman and Paul.3.Algorithms:Design Techniques and Analysis by Alsuwaiyel.Books on Complexity,Cryptography,and Combinatoricsplexity of Classification of Boolean Constraint Satisfaction Problems by Creignou,Khanna,and Sudan.2.Elliptic Curves:Number Theory and Cryptography by Larry Washington.3.Block Error-Correcting Codes:A Computational Primer by Xambo-Descamps.binatorial Designs:Constructions and Analysis by Stinson.5.Aspects of Combinatorics and Combinatorial Number Theory by S.D.Adhikari.1c William Gasarch,2005.Misc Books1.Algorithmic Learning in a Random World by Vovk,Gammerman,Shafer.2.Domain Decomposition Methods–Algorithms and Theory by Toseli and Widlund.3.Dynamic Reconfiguration:Architectures and Algorithms by Vaidyanathan and Trahan.4.Semantic Integration of Heterogenous Software Specifications by Martin Groβe-Rhode.5.Handbook of Computational Methods of Integration by Kyther and Schaferkotter.Review of2Cryptological MathematicsAuthor:Robert LewandMAA,2000,$33.95,SoftcoverReviewer:William GasarchAlice has taught a course in crypto.Bob is going to teach one soon.Bob:Alice,how much pre-RSA crypto do you do when you teach Crypto?Alice:I go over Monoalphabetic substitutions(for example the Caeser Cipher where every letter is replaced by the letter shifted3places,mod26),Polyalphabetic substitutions(for example,every odd placed letter is shifted by1,every even placed letter is shifted by5),Polygraphic substitutions (for example,there is a3×3matrix that is multiplied mod26by every block of3letters),the enigma code from WW II,and the1-time pad.Bob:Why do all that?Alice:There are several reasons1.They get good and motivated review of modular arithmetic,number theory,probability,statistics,and linear algebra.2.They see the fallacy of thinking that just because your code was hard to come up with doesnot mean its hard to break(e.g.,a random permutation of{a,...,z}can be easily broken with frequencey analysis).3.They see that many codes that were thought unbreakable were eventually broken;this breedsa heathly skepticisim about current claims.4.They see that historically crypto has been a tradeoffbetween how much information youmust exchange over a secure line and how secure the code is.For example,the shift cipher requires very little information exchange ahead of time(just a number between1and26), but is not secure,whereas the1-time pad is unbreakable but needs massive amounts of data to be exchanged over a secure line.5.(Continuing the above point.)Since the beginning of Crypto,perhaps4000years ago,therehas been the need for a secure channel or a private meeting to exchange information initially.Public Key crypto offers a way to do crypto and not have this meeting.Hence it can be seen as the solution of a4000-year old problem.Seeing it in this light really impresses the students about its importance.2copyright2005,William Gasarch6.If you know the pre-RSA material then the introduction of complexity(e.g.how much timeit takes to crack a code)as a formal object of study is more striking in its importance and originality.Bob:You speak in lists!But more importantly,yes,you’ve sold me.I will do lots of PRE-RSA crypto.Do you have a book to recommend?Alice:Many crypto books have some of this material.But be warned of books written by people who understand the mathematics but don’t quite get the computer science.Bob:Do you have a book to warn me to stay away from.Alice:Yes and No.I have just read Cryptological Mathematics by Robert Edward Lewand.There are some PROS and CONS.The table of contents is available at/blewand/cryptomath/description.htmThefirst chapter is entitled Monoalphabetic Substitution Ciphers.This is when you(say)replace a by b,b by c,...,y by z,and z by a.More complicated bijections are also allowed;however,you want to be able to describe them briefly.Sections1.1,1.2,1.3,and1.4are on proof techniques and simple number theory.Section1.5is on additive ciphers,multiplicative ciphers,affine ciphers,and keyword ciphers.It is well written and interesting.Bob:Is the fact that they spend most of the chapter on topics not in the title-is that a bad thing? Alice:Itsfine.Its hard to weave the needed math into the book as you’re doing it.One can view this as teaching math of interest in a motivated way.Bob:So,you recommend the book?Alice:Not so fast.There are several problems with this chapter.1)(Page27)The cast of characters is introduced,and its not Alice and Bob and Eve!!Its Beth and Stephanie and Molly!!This was very disconcerting since they are replacing us!Bob:They don’t use Alice and Bob?But that is why we exist!!Alice:Calm down Bob!Most books use Alice and Bob,so we’ll be employed for a while.Now back to the book.2)(Page32)The discussion of Multiplicative Inverses mod26suggests trying all possibilities.This isfine for mod26but is bad for larger values of n.The author misses an oppurtunity to introduce the reader to issues of complexity.3)(No particular page)A person who makes up a random permuation of{a,...,z}for his cipher may think that nobody can possibly crack it since the original permuation is random.But frequency attacks can easily crack such ciphers.There is a valuable lesson in this—a cipher may be able to be cracked by ways its creator never imagined.Hence statements about the security of a cipher have to made very carefully.This is an excellent point to make,which the author does not.The second chapter is on Polyalphabetic Substitution ciphers.One example of this would be to use the cipher that shifts a letter by2on all letters in even places,and use ciphers that shift a letter3places on all letters in odd places.More complicated ones are described and used.This is useful in that it hides the frequency of letters(the author makes this point nicely).Sections2.1, 2.2,2.3,and2.4are on probability and combinatorics,which is needed for this chapter.Again this is a nice way to motivate these topics.This chapter only has one problem.On page96it describes the index of Coincidence which can be used to tell if a code is monoalphabetic or polyalphabetic.If this index is close to0.064then the code is probabably monoalphabetic.If this index is close to0.038then the code is probably not monoalphabetic.Bob:What if the index is much bigger than0.064?Inbetween the two numbers?Can that happen?What if the index is much smaller than0.038?Alice:Anyone reading the book would ask those questions.Yet the author does not address this point.Bob:What’s in the third chapter?Alice:The third chapter is on Polygraphic Substitution ciphers.This is where you replace a block of text for another block of text.Section3.1introduces the idea.Section3.2is about matrices and linear algebra,which the student needs for this chapter.The rest of the chapter describes some systems and also how to crack them.There is a nice summary of how to crack them on page133.There is a problem with the summary.Again he uses the Index of Coincidence.The claim is that if it is close to0.65then the code is monoalphabetic(this is true)and that one should “try attacking the message using monoalphabetic(additive,multiplicative,keyword,and affine transformation)”This is misleading.Frequency attacks are the best against monoalphabetic ciphers.Bob:This is all fairly interesting pre-RSA crypto.But do they do RSA?Alice:Yes.The fourth chapter is on RSA.Its a good exposition with many examples but has two very serious problems.1.On page155they talk about how to calculate powers like(78390)91025(mod180577).Theymention the sequential method and Mathematica routines,but they never mention repeated squaring!2.On page157they state“So the RSA algorithm is as secure as the unfactorability of n”This is not known to be true.It is known that if factoring was easy then RSA would be breakable.The converse is not known.It is possible that some clever other method may emerge that cracks RSA without factoring.Note that we can test for primality without being able to factor,which would seem counter-intuitive except that we are all used to it.Bob:Does he mention that there are attacks on the implementation of RSA,such as timing attacks?Alice:Ah,good question.No he does not.Bob:Well...how important is that for an undergraduate text?Alice:I think its very important!When Ifirst read about timing attacks it blew my mind!It showed the limits to mathematical proofs of security when dealing with the real world.Bob:What else is in the book?Alice:The book has short biographies of four prominent people involved with the origin of crypto: Herbert Yardley,William Friedman,Agnes Meyer Driscoll,and Frank Rowlett.The book also has a very nice Taxonomy of terms used in Crypto.Bob:What else do they leave out?Alice:They do not discuss the1-time pad or issues of key length in general.This is a bad omission since it sets the stage for RSA.They also do not discuss Kerchhoffs’s law,which is that you should assume the enemy knows what system you are using.Bob:At the end of the day,do you recommend this book?Alice:That is a more profound question than you realize.On the one hand,the book is well written and introduces math of interest in a motivated and fun way.On the other hand,its wrong on some points(though not that many)and misses opportunities at other points.How important is that?Do the PROS outweight the CONS?Bob:What is the intended audience and what audience do you think it’s good for?Alice:It’s intended for a liberal-arts course on math.It could also be used as a supplement in a course for majors.If the teacher knows all the problems with it and points them out then this can be good and has the advantage of teaching students that textbooks can be wrong.Bob:Lets revisit your list of reasons to teach PRE-RSA and see how this book does.Alice:Gladly.1.They get good and motivated review of modular arithmetic,number theory,probability,statistics,and linear algebra.This book does very well on these topics.2.They see the fallacy of thinking that just because your code was hard to come up with doesnot mean its hard to break(e.g.,a random permutation of{a,...,z}can be easily broken with frequencey analysis).The book does talk about frequencey analysis,but doesn’t really make this point.3.They see that many codes that were thought unbreakable were eventually broken;this breedsa heathly skepticisim about current claims.The book does not make this point.4.They see that historically crypto has been a tradeoffbetween how much information youmust exchange over a secure line and how secure the code is.For example,the shift cipher requires very little information exchange ahead of time(just a number between1and26), but is not secure,whereas the1-time pad is unbreakable but needs massive amounts of data to be exchanged over a secure line.The book does not make this point;in fact,the book does not even cover the1-time pad.5.(Continuing the above point.)When they see that tradeoffthey are impressed with PublicKey Crypto in that it solves a4000-year old problem.The book does not make this point.6.If you know the pre-RSA material then the introduction of complexity(e.g.how much timeit takes to crack a code)as a formal object of study is more striking in its importance and originality.The book does not make this point.Bob:You still speak in lists!You seem to be writing a negative review.Alice:I view this more as(1)a warning to people who do use the book as to what to look out for, and(2)advice for the author if he writes a second edition.I want to stress that the points I raise can be addressed without a radical rewrite,and I urge the author to make those changes.Review of3Data Privacy and SecurityAuthor:David SalomonPublisher:Springer–Verlag,2003$51.48,HardcoverReviewer:Nick Papanikolaou(Dept.of Computer Science,University of Warwick,U.K.)1IntroductionThefield of cryptology and data security hardly needs any introduction;numerous popular accounts of the subject have appeared over the years,and it is already a core topic in undergraduate computer science.The very term“cryptology”is testimony to the long history of thefield;the term is derived from the wordsκρυπτ´oς(meaning hidden),andλ´oγoς(meaning speech),which have retained their meaning in the Greek language for many centuries.Cryptology is the study of codes and ciphers,mechanisms through which data can be trans-formed so as to make their content unreadable to anyone but specially authorized persons.It is traditionally divided into cryptography,the development of new codes and ciphers,and cryptanal-ysis,the art of subverting existing ones.While cryptanalysis is regarded as a sort of‘black magic’that has always required special skill(in Alan Turing’s days)or extremely fast computers(today), the study of cryptography is of interest to everyone and is becoming increasingly accessible to a wider public.Formally,the purpose of cryptography is to accomplish one or more of the following objectives:•confidentiality,or secrecy of given data;•integrity,or assurance that data has not been tampered with;•non–repudiation,or definitive proof that data was exchanged between parties;•authentication,or proof of the origin of given data.David Salomon’s recent textbook ventures to survey classical cryptography and steganography in an accessible manner.While there already exist several volumes covering these topics e.g.[7,8,9], Salomon’s book is a practical and readable reference that has much to commend it.Interestingly, it is one of few books to treat steganography on a par with classical cryptographic techniques.2CoverageSalomon starts with a fascinating account of the Zimmermann telegram,which famously contained a plot to discourage the United States from entering the First World War.The telegram was decrypted in England and this,as the author points out,changed the course of history.This highlights the significance of cryptanalysis,and is followed in the book by a definition of all the relevant terminology.Some basic terms of interest are:3c Nick Papanikolaou,2005Code:A code is a direct transformation of a word,a phrase,or even an entire message. Cipher:A cipher is a transformation defined over each symbol in a particular alphabet. Nomenclator:A nomenclator is a combination of code and cipher.Encryption:Encryption is the process of applying a code or cipher to a message,called the plaintext.Decryption:Decryption is the process of recovering the plaintext from an encrypted message, known as the ciphertext.The book’s introduction goes on to discuss some simple ciphers,including the Caesar cipher and the one–time pad.The Caesar cipher is no more than letter shifting;a message is encrypted by replacing each letter with the letter n positions ahead of it.A fashionable version of this cipher is known as ROT13,and has n=13,i.e.half the length of the English alphabet.For example, ROT13transforms the message SIGACT NEWS into FVTNPG ARJF.The one–time pad is a rare example of a perfect cryptosystem;a perfect,or unconditionally secure cryptosystem,cannot be broken even if the enemy has unlimited time and computational power.To encrypt a message m with the one–time pad,one must generate a key,k,which is at least as long as m.The same key must be used to encrypt and decrypt the message;the ciphertext is the exclusive-or of k and m.As long as a different key is used for every message,this system provides perfect secrecy—in other words,an enemy cannot obtain any information about the key given only the ciphertext.The one–time pad cryptosystem suffers from the need to distribute the key to all legitimate receivers of a message;the key itself must be exchanged in secrecy.This so–called key distribution problem is addressed in public–key cryptography,and also by using quantum key distribution techniques,described later.2.1Chapters1–3:Substitution and Transposition CiphersThefirst three chapters of the book deal with all the traditional ciphers.In a substitution cipher, each letter in a message is replaced with another letter from one or more alphabets.When all letters are drawn from a single alphabet,we have a monoalphabetic substitution cipher;these are covered in Chapter1.When the letters in a message are replaced with letters from several alphabets, we have a polyalphabetic substitution cipher,and these are discussed in Chapter3.Transposition ciphers replace a message by a permutation of itself,as explained in Chapter2of Salomon’s book.The ciphers discussed in Chapter1include Polybius’cipher,the Playfair cipher,fractionation, and homophonic ciphers.Of these,we will discuss only the Playfair cipher here.In the Playfair cipher,all messages are encrypted with the help of a5×5square,which contains all the letters of the alphabet except J,which is rarely used in messages anyway.The square serves as an encryption key,and is constructed by choosing a long word with relatively few or no repeating letters.The unique letters of this word are placed,in sequence,into the square,followed by all the other letters in the alphabet.Take,for example,the word COMPUTATION;the corresponding square becomes:C O M P UT A I N BD E F G HK L Q R SV W X Y ZNow,suppose we wish to encrypt the plaintext FOLLOW ME EARLY.To do this,we divide the plaintext into pairs of letters(we remove duplicate letters,and pad out with an X):FO,LO,WM, EA,RL,YX.Then,for each pair of letters(x,y),we locate x and y in the square and draw the rectangle which has x and y as opposite corners.Next x and y are replaced by the letters in the other two corners of this rectangle.When x and y do not form a rectangle,they are replaced with the letters immediately below(that’s when x and y are in the same column)or immediately to the right(that’s when x and y are in the same row).Using these rules,we obtain for the pairs in our example plaintext:EM,WA,XO,WL,SQ,VZ.If you would like to know why YX maps to VZ,and what happens in more complicated cases,you should buy the book!Chapter2deals with transposition ciphers:the turning template,the columnar transposition cipher and the variations due to Myzkowsky and Scott.The author explains how such ciphers can be decrypted,as he does also in Chapter1.Breaking both substitution and transposition ciphers is actually done by taking advantage of the relative frequency of letters in the English alphabet. Did you know that the probability offinding an‘E’in Shakespeare’s plays is0.1196?It should be added that Matlab code for some of these ciphers is provided in the text.Chapter3discusses a great variety of ciphers,including those due to Beaufort,Trithemius, Vigen`e re,Gronsfeld,Eyraud,Hill and Jefferson.Let’s consider the Hill cipher briefly.In the Hill cipher,all the letters in the alphabet are numbered0to25;a number n<26is chosen,and the key is formed by generating a n×n matrix K whose elements are integers in the range0to25. Thefirst n letters of a given plaintext are converted to a column vector,P,and the ciphertext is obtained by computingC=K·P(mod m)Decryption in the Hill cipher consists of computing a matrix inverse modulo an integer;in particular, P=K−1·C(mod m).Unfortunately,the Hill cipher has limited power and can be subverted using a so–called chosen–plaintext attack,in which the enemy knows afinite number of ciphertexts,C i,and their corresponding plaintexts,P i.2.2Chapters4and5:Random Numbers and The EnigmaChapter4of Data Privacy and Security is devoted to random numbers,which are of primordial importance in cryptography.In practice,pseudorandom number generators are used,and algo-rithms for this purpose are discussed in the text.Also,the author describes the main statistical tests that can be performed to gauge the degree of randomness of a given number sequence.These various topics are covered in extensis in Don Knuth’s seminal work[2],which is aimed at a more advanced reader.One of the most attractive features of this book is the material in Chapter5,which details the Enigma machine,used by the Germans in World War II.The historical background is discussed,and the workings of the machine are carefully explained by means of numerous diagrams and pictures.2.3Chapters6–8:Stream Ciphers,Block Ciphers,Public Key Cryptography Chapters6–8of the book cover the more fashionable aspects of cryptography,though no differently from most of the other books[7,8,9]on the subject.Stream ciphers(Chapter6)and block ciphers(Chapter7)are the two principal classes of cipher used on modern–day computers.Since all messages are now ultimately reduced to strings of zeros and ones,secure ciphers have to be based on the manipulation of bits.Stream ciphers encrypt a string of bits by treating each bit individually,while block ciphers divide a bit string into blocks and transform each block.Chapter6points out the distinction between symmetric–key and public–key cryptosystems. Symmetric key cryptosystems use the same key for encryption and decryption,while public–key systems use two distinct keys.Linear and nonlinear shift registers are discussed,along with cellular automata,SEAL and the RC4cipher.Chapter7describes substitution–permutation ciphers,Lucifer and the Data Encryption Stan-dard(DES).This leads on to a presentation of Blowfish,IDEA,RC5and Rijndael.Rijndael is also known as the Advanced Encryption Standard,or NIST standard FIPS-197.Rijndael involves several rounds and consists of the following operations:byte substitution,row shifting,column mixing,and adding a subkey(or‘round key’).It is not yet known how secure Rijndael is;Salomon states that its security‘can be demonstrated only with time.’Chapter8presents Diffie–Hellman–Merkle key exchange,RSA(the Rivest–Shamir–Adleman public–key cryptosystem),Rabin’s system and the El–Gamal scheme.All of these are discussed briefly,with an emphasis on RSA.Threshold schemes and authentication are then covered.Elliptic curve cryptography,now quite en vogue,is then described at length.We cannot do justice to the many topics covered,in the framework of this brief review;let us at least reproduce,from page200 of the book,a two–line implementation of RSA in Perl:print pack"C*",split/\D+/,‘echo"16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc‘2.4Chapter9:Quantum CryptographyOf the cryptographic techniques described in this book,none is more exciting than quantum cryp-tography,which relies for its security on the laws of quantum physics;the BB84protocol for quantum key distribution is presented in Chapter9.It has been proven that this protocol is unconditionally secure against all possible attacks and therefore solves,at least in principle,the age–old problem of key bined with an unconditionally secure cryptosystem,such as the one–time pad,quantum key distribution paves the way for truly unbreakable cryptography.While public–key cryptosystems,such as RSA,resolve the problem of distributing keys in a mathematical way,their security remains largely dependent on the complexity of certain computa-tional problems,such as prime factoring,which can be performed efficiently on a quantum computer. Quantum computers are still mostly objects of theoretical speculation,but small–scale ones have been built in experimental physics labs.Peter Shor famously devised efficient quantum algorithms for factoring and the discrete logarithm;a full–scale quantum computer could run these algorithms and efficiently break several cryptosystems in current use.The security of quantum cryptography, or more specifically,quantum key distribution,is not threatened by the computational power of quantum computers.Gilles Brassard ran a‘Cryptology’column in SIGACT News for years;before I describe quantum cryptography in more detail,let me quote his words on the tie between this newsletter and the subject:“The fates of SIGACT News and Quantum Cryptography are inseparably entangled.The exact date of Stephen Wiesner’s invention of‘conjugate coding’is unknown but it cannot be far from April1969,when the premier issue of SIGACT News[...]came out.Much later,it was in SIGACT Newsthat Wiesner’s paperfinally appeared[Vol.15,No.1,1983]in the wake of thefirst author’s[GillesBrassard’s]early collaboration with Charles Bennett[...].It was also in SIGACT News that the originalexperimental demonstration for quantum key distribution was announced for thefirst time[Vol.20,No.4,1989]and that a thorough bibliography was published[Vol.24,No.3,1993].Finally,it was inSIGACT News that Doug Wiedemann chose to publish his discovery when he reinvented quantum keydistribution in1987,unaware of all previous work but Wiesner’s[Vol.18,No.2,1987].Quantum key distribution protocol BB84allows two parties,‘Alice’and‘Bob,’to establish a secret binary key.The idea is to represent each bit in a given string by either a rectilinearly or diagonally polarized photon.In the rectilinear basis,a0is represented by a photon polarized at0◦, and a1by a90◦–polarized photon.In the diagonal basis,a45◦–polarized photon stands for0and a135◦–polarized photon stands for1.In brief,the protocol proceeds as follows.Alice generates a random bit string,and a random string of encoding bases.Each bit is mapped to a polarized photon using the corresponding basis and then transmitted to Bob.Bob does not know which basis has been used to encode each photon,and so chooses one of the two bases at random in order to make a measurement.Due to the laws of quantum physics,the result of Bob’s measurement is only guaranteed to be correct for a given photon if his choice of measurement basis matches the one used by Alice for encoding.When the entire binary string has been transmitted in this way, Bob will have obtained a subset of Alice’s bit ing a classical—possibly even public—communications channel,Alice tells Bob which of his basis choices were correct.There is much more to quantum cryptography than we can say here,and the interested reader is referred to[4]for a recent introduction to the subject.It should be added that commercial quantum cryptographic devices do exist already(see and http:// ).Quantum protocols such as BB84are of special interest to computer scientists today;for example,[3]discusses modelling and analysing the security of these schemes using automated tools.Salomon’s presentation of quantum cryptography in Data Privacy and Security is very readable, and is innovative in the sense that not many crypto textbooks deal with this subject.On a lighter note,Schneier[7]exclaims:“this would still be on the lunatic fringe of cryptography,but Bennett and Brassard actually went and built a working model of the thing[...].”2.5Chapters10–12:SteganographyThe threefinal chapters of the book are devoted to steganography,or data hiding.The goal of steganography is to hide a message in another item of data,known as the cover.If the original message is to be embedded in a text,referred to as covertext,the product of the steganographic pro-cedure is termed a‘stegotext.’Messages can also be embedded in images,sounds and video,leading respectively to the use of the terms‘coverimage’and‘stegoimage,’‘coveraudio’and‘stegoaudio,’‘covervideo’and‘stegovideo.’Word-smithing will never go out of style!The basic ingredients of a data hiding system are:(1)the data to be embedded;(2)the cover, in which embedding will occur;(3)a stego–key;(4)an embedding algorithm;and(5)a decoder. The embedding algorithm produces a stego–cover given thefirst three items above.To recover the data hidden in it,the stego–cover is fed into a decoder along with the stego–key.Chapter10 of the book elaborates on these fundamentals and focuses on data hiding in text.The principal characteristics of a data hiding algorithm are identified and explained;these are embedding capacity (how much data can be hidden in a given cover),invisibility(how much distortion is caused to the cover),undetectability(a statistical measure of the distortion),robustness(the degree of immunity of the stego–cover to subsequent alterations,such as compression),tamper resistance(the degree of immunity of the stego–cover to direct tampering)and the signal–to–noise ratio.Watermarking is introduced.As an example of data hiding in text,that merely modifying the spaces in a textfile is a means of conveying a message.This particular idea is extended in an interesting manner on page256:。

Sino-US English Teaching, ISSN 1539-8072June 2012, Vol. 9, No. 6, 1246-1252On the Translation of Public Signs From theFunctional Perspective *ZHU Ji-fengNingbo Dahongying University, Ningbo, ChinaWith the rapid development of Chinese economy, more and more foreigners have been attracted to China to invest,work, study, and travel. To help the foreigners better understand China and facilitate cross-cultural communication,bilingual or even trilingual public signs spring up in every part of China. As is known that public signs, usually in theform of a few words, pictures, or words accompanied with a picture, function not only as a “face” of a city and a nation,but also as a first calling card given to the foreigners. Moreover, public signs have definite functions—informing,warning, or directing. However, to our disappointment, mistranslations of the public signs are often presented in someplaces. As a special text whose function is strong and communicative purpose is quite clear, the translation of publicsigns should be based on the text’s functions and the translator’s purpose. This paper classifies public signs, comparesChinese signs with English ones, and comes up with the principle for its Chinese-English translation, namely, anA-B-C approach (Adapt-Borrow-Create approach) which is based on the Skopostheorie.Keywords: public signs, translation, principle, functionalism IntroductionIn recent years, frequent communication has been intensified both in business and culture between China and the West. More and more foreigners come to China. They want to know more about Chinese culture, customs, economy, and so on. Therefore, the Chinese-English translation becomes a significant way of communicating with foreigners. Besides, to build an international metropolis, we need good international language environment. Since the reform and opening, the international language environment has been improved greatly in such large cities as Beijing. There is no doubt that good language environment is the key point to hold the 2008 Olympic games in Beijing successfully to some extent. Public signs in English mean a lot to alien tourists. Translators should carry an in-depth study of functional features and language style of public signs in order to reproduce the profiles in light of functionalism. However, at present, many translators or translation researchers mainly focus on how to reproduce the public signs in a faithful way, hence fail to take the functions of the placards into consideration while offering their own way of sign translation. Furthermore, most of the examples cited by the researchers are restricted to a certain region.*This paper is one of the research results from the program “On the Problems in the Translation of Chinese Public Signs in Tourist Attractions” (No. CF112415).ZHU Ji-feng, lecturer at School of Foreign Languages, Ningbo Dahongying University.Rights Reserved.TRANSLATION OF PUBLIC SIGNS FROM THE FUNCTIONAL PERSPECTIVE1247Definition and Classification of Public SignsPublic signs are generally referred as “signs” in English, and have been defined in various ways. It is defined in Webster’s New Collegiate Dictionary (1977) as “a posted command, warning, or direction”. According to Macquarie Dictionary (Butler, 1987), a sign is “an inscribed board, space, etc., serving for information, advertisement, warning, etc., on a building, along a street, or the like”. The Longman Dictionary of Contemporary English (1997) defines a sign as “a piece of paper, metal, etc. in a public place, with words or drawings on it that give people information, warn them not to do something, etc.”. Or according to OxfordAdvanced Learners’ Dictionary (2010), it is defined as “a piece of paper, wood or metal that has writing or a picture on it that gives you information, instructions, a warning, etc.”. According to these definitions, signs cancontain words, pictures, or drawings used for giving information, warning, etc.. With regard to our Chinese, “signs” are often referred as “public signs”, for such signs generally appear in public places.Sign is a broad term, widely used in public facilities, ranging from traveling, catering, accommodation, recreation, shopping to medical service, educational institution, and financial service. It includes words of caution, public notices, bills, posters, slogans, outdoor advertisements, traffic notices, and so on. Specifically speaking, it covers street signs, road signs, road markers, parking signs, school signs, construction signs, non-smoking signs, signs at scenic spots, slogans, etc.Practical Functions of Public SignsSigns perform the following four basic functions: indicating, promoting, restricting, and compelling.As its meaning suggests, indicating is to indicate or guide readers. Signs as such are also called Rights Reserved.instructive/directive/guiding notices which give readers detailed information with no prohibition and restriction.Indicating is the most basic function performed in sign language. Indicating signs generally give readers relevantinformation about what it is and what service it provides.Prompting has no striking difference from indicating except that the former carries the tone of warning. It aims at reminding readers of paying considerable attention to signs.Unlike the two functions mentioned above, signs that perform restricting function put restrictions and constraints to readers, who are expected to abide by certain rules in the interest of public. Restricting signs are tokeep or confine within limits.To put it simple, compelling signs have great power and potency to induce action or brief. With its tough tone, negative words, and comparatively uniform sentence structures, there is slight possibility of any alternatives.Comparison Between the Chinese and English Public SignsBoth share similarities, of which, the language styles are concise, convenient, and conspicuous; moreover, the figures of speech are often adopted. Yet, a series of differences still exist. Such stylistic analysis focuses moreon its functional significance in the sign translation than on the formal features of texts for its own sake.Word OrderAs thinking modes vary in two cultures, the centre of power reflected in Chinese and English is strikingly different. The Chinese sign is highly implicit by placing the focus at the end of a phrase; on the contrary, the English1248TRANSLATION OF PUBLIC SIGNS FROM THE FUNCTIONAL PERSPECTIVE sign emphasizing the point at the beginning. For instance, “油漆未干Wet Paint”; “无汞(电池) Mercury-Free”.Diction PracticeDifferences are also seen in diction practice. Verbs are usually employed in Chinese to perform such functions as warning, restricting, and compelling, whereas the nouns and gerunds are quite common in English.For instance, “严禁穿行No Trespassing”; “不收手续费No Commission Charge”.Mood UnlikeEnglish signs which sound euphemistic and implicative, Chinese signs are more direct and straightforward, even with a touch of authority. English signs often display the allowable aspect instead of aiming at the prohibited audience. For instance, “闲人免进Staff Only”; “送客止步 Passengers Only”.VoiceEnglish signs generally use passive voice; Chinese signs, however, are more of active voice. Hence, sign translators should take into account the target reader’s acceptability and identification. For example, “禁止携带犬只入内Dogs Not Allowed”; “戴好防护镜和安全帽Safety Glasses & Hard Hats Required”.The Translation of Public Signs Under the Framework of Functionalism In 1970s, there was a new theory named functional translation theory in Germany. Skopos theory, as the most important theory in the field of Functionalist Approaches, is proposed by Catharina Rice and Hans Vermeer in 1970s. It is “a technical term for the aim or purpose of a translation” (Vermeer, 1996, p. 221). Skopos theorists assert that any action has an aim and a purpose. From their standpoint, translation is considered not as a process ofRights Reserved.transcoding, which usually adopted by earlier non-functionalist approaches, but as a form of human action which has its own purpose basically decided on by the translator. The skopos of a translation, Vermeer explains, is the goal or purpose, defined by the commission and if necessary adjusted by the translator. Vermeer (1996) defined commission as “the instruction, given by oneself or by someone else, to carry out a given action (which could be translation)” (p. 201).According to the skopos theory, all the translation works should obey three rules: the skopos rule, the coherence rule, and the fidelity rule.The skopos rule is the primary one of the three above. It suggests that human action (and its subcategory: translation) is determined by its purpose (skopos), and therefore it is a function of its purpose. The rule is formalized using the formula: IA(Trl) = f(Sk). The main point of this functional approach is the following: It is not the source text as such, or its effects on the source-text recipient, or the function assigned to it by the author, that determines the translation process, as is postulated by equivalence-based translation theories, but the prospective function or skopos of the target text as determined by the initiator’s, i.e., client’s needs. Consequently, the skopos is largely constrained by the target text user (reader/listener) and his/her situation and cultural background.The coherence rule stipulates that the target text must be sufficiently coherent to allow the intended users to comprehend it, given their assumed background knowledge and situational circumstances; the starting point for a translation is a text as part of a world continuum, written in the source language. It has to be translated into a target language in such a way that it becomes part of a world continuum which can be interpreted by the recipients as coherent with their situation.TRANSLATION OF PUBLIC SIGNS FROM THE FUNCTIONAL PERSPECTIVE1249The fidelity rule concerns intertextual coherence between translatum and source text, and stipulates merely that some relationship must remain between the two, once the overriding principle of skopos and the rule of (intratextual) coherence have been satisfied (Vermeer, 1996, p. 100).As has been mentioned, the informative function of a text is to inform the reader about objects and phenomena in the real world. “The choice of linguistic and stylistic forms is subordinate to this function. In translation where both the ST (source translation) and TT (target translation) are of the informative type, the translator should attempt to give a correct and complete representation of the ST’s content and should be guided,in terms of stylistic choices, by the dominant norms of the ST and TT”. So the truthfulness is the core of this kindof public signs. Translators only stand in the position of trying to be anonymous. When they translate public signs, they should pay more attention to the readers’ understanding and reaction. That is to say, they should concern theeffect of information transmitting.On the relationship between form and content, he thinks that translation should have the original text’s meaning and spirit in mind, but not be stickler for the language form to pursue the equality between original and target text. Nevertheless, on the other hand, the translations of informative public signs also stress the arrangement and words choosing, because the format of an informative text is often standard. In the process of translation, because of different structure and custom, we should pay more attention to choosing the suitable word.Now, there is a new tendency to translate the public signs.On the relationship between original and translated text, the original must obey the translated text’s form.The original text is just the source of information. Frequently, we change the translation into a kind of mechanicaloperation with explicit purpose, and it just follows the standard of target text, which is beneficial for Rights Reserved.disseminating the information. From this aspect, the Skopostheorie, which stresses the principle of translation’s function, is fit for the informative public signs. There are some signs in every street and publics, which have the function to keep the crime on guard. For example: “窃贼当心，本区域所有物品都经智能液处理，伸手必擒。

Chapter 1: Introduction (5)Chapter 2: Classical Encryption Techniques (7)Chapter 3: Block Ciphers and the Date Encryption Standard (13)Chapter 4: Finite Fields (21)Chapter 5: Advanced Encryption Standard (28)Chapter 6: More on Symmetric Ciphers (33)Chapter 7: Confidentiality Using Symmetric Encryption (38)Chapter 8: Introduction to Number Theory (42)Chapter 9: Public-Key Cryptography and RSA (46)Chapter 10: Key Management; Other Public-Key Cryptosystems (55)Chapter 11: Message Authentication and Hash Functions (59)Chapter 12: Hash and MAC Algorithms (62)Chapter 13: Digital Signatures and Authentication Protocols (66)Chapter 14: Authentication Applications (71)Chapter 15: Electronic Mail Security (73)Chapter 16: IP Security (76)Chapter 17: Web Security (80)Chapter 18: Intruders (83)Chapter 19: Malicious Software (87)Chapter 20: Firewalls (89)A NSWERS TO Q UESTIONS1.1The OSI Security Architecture is a framework that provides a systematic way of definingthe requirements for security and characterizing the approaches to satisfying thoserequirements. The document defines security attacks, mechanisms, and services, and the relationships among these categories.1.2 Passive attacks have to do with eavesdropping on, or monitoring, transmissions.Electronic mail, file transfers, and client/server exchanges are examples oftransmissions that can be monitored. Active attacks include the modification of transmitted data and attempts to gain unauthorized access to computer systems.1.3 Passive attacks: release of message contents and traffic analysis. Active attacks:masquerade, replay, modification of messages, and denial of service.1.4 Authentication: The assurance that the communicating entity is the one that it claims to be.Access control: The prevention of unauthorized use of a resource (i.e., this service controls who can have access to a resource, under what conditions access can occur, and what those accessing the resource are allowed to do).Data confidentiality: The protection of data from unauthorized disclosure.Data integrity: The assurance that data received are exactly as sent by an authorized entity(i.e., contain no modification, insertion, deletion, or replay).Nonrepudiation: Provides protection against denial by one of the entities involved in a communication of having participated in all or part of the communication.Availability service: The property of a system or a system resource being accessible and usable upon demand by an authorized system entity, according to performancespecifications for the system (i.e., a system is available if it provides services according to the system design whenever users request them).1.5 See Table 1.3.C HAPTER 2C LASSICAL E NCRYPTION T ECHNIQUESR2.1 Plaintext, encryption algorithm, secret key, ciphertext, decryption algorithm.2.2 Permutation and substitution.2.3 One key for symmetric ciphers, two keys for asymmetric ciphers.2.4 A stream cipher is one that encrypts a digital data stream one bit or one byte at atime. A block cipher is one in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length.2.5 Cryptanalysis and brute force.2.6 Ciphertext only. One possible attack under these circumstances is the brute-forceapproach of trying all possible keys. If the key space is very large, this becomesimpractical. Thus, the opponent must rely on an analysis of the ciphertext itself, generally applying various statistical tests to it. Known plaintext. The analyst may be able to capture one or more plaintext messages as well as their encryptions.With this knowledge, the analyst may be able to deduce the key on the basis of the way in which the known plaintext is transformed. Chosen plaintext. If the analyst is able to choose the messages to encrypt, the analyst may deliberately pickpatterns that can be expected to reveal the structure of the key.2.7 An encryption scheme is unconditionally secure if the ciphertext generated by thescheme does not contain enough information to determine uniquely thecorresponding plaintext, no matter how much ciphertext is available. Anencryption scheme is said to be computationally secure if: (1) the cost of breaking the cipher exceeds the value of the encrypted information, and (2) the timerequired to break the cipher exceeds the useful lifetime of the information.2.8 The Caesar cipher involves replacing each letter of the alphabet with the letterstanding k places further down the alphabet, for k in the range 1 through 25.2.9 A monoalphabetic substitution cipher maps a plaintext alphabet to a ciphertextalphabet, so that each letter of the plaintext alphabet maps to a single unique letter of the ciphertext alphabet.2.10 The Playfair algorithm is based on the use of a 5 5 matrix of letters constructedusing a keyword. Plaintext is encrypted two letters at a time using this matrix.2.11 A polyalphabetic substitution cipher uses a separate monoalphabetic substitutioncipher for each successive letter of plaintext, depending on a key.2.12 1. There is the practical problem of making large quantities of random keys. Anyheavily used system might require millions of random characters on a regularbasis. Supplying truly random characters in this volume is a significant task.2. Even more daunting is the problem of key distribution and protection. For everymessage to be sent, a key of equal length is needed by both sender and receiver.Thus, a mammoth key distribution problem exists.2.13 A transposition cipher involves a permutation of the plaintext letters.2.14 Steganography involves concealing the existence of a message.2.1 a. No. A change in the value of b shifts the relationship between plaintext lettersand ciphertext letters to the left or right uniformly, so that if the mapping isone-to-one it remains one-to-one.b. 2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, 24. Any value of a larger than 25 isequivalent to a mod 26.c. The values of a and 26 must have no common positive integer factor other than1. This is equivalent to saying that a and 26 are relatively prime, or that thegreatest common divisor of a and 26 is 1. To see this, first note that E(a, p) = E(a,q) (0 ≤ p≤ q < 26) if and only if a(p–q) is divisible by 26. 1. Suppose that a and26 are relatively prime. Then, a(p–q) is not divisible by 26, because there is noway to reduce the fraction a/26 and (p–q) is less than 26. 2. Suppose that a and26 have a common factor k > 1. Then E(a, p) = E(a, q), if q = p + m/k≠ p.2.2 There are 12 allowable values of a (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25). There are 26allowable values of b, from 0 through 25). Thus the total number of distinct affine Caesar ciphers is 12 26 = 312.2.3 Assume that the most frequent plaintext letter is e and the second most frequentletter is t. Note that the numerical values are e = 4; B = 1; t = 19; U = 20. Then we have the following equations:1 = (4a + b) mod 2620 = (19a + b) mod 26Thus, 19 = 15a mod 26. By trial and error, we solve: a = 3.Then 1 = (12 + b) mod 26. By observation, b = 15.2.4 A good glass in the Bishop's hostel in the Devil's seat—twenty-one degrees andthirteen minutes—northeast and by north—main branch seventh limb east side—shoot from the left eye of the death's head— a bee line from the tree through the shot fifty feet out. (from The Gold Bug, by Edgar Allan Poe)2.5 a.The first letter t corresponds to A, the second letter h corresponds to B, e is C, sis D, and so on. Second and subsequent occurrences of a letter in the keysentence are ignored. The resultciphertext: SIDKHKDM AF HCRKIABIE SHIMC KD LFEAILAplaintext: basilisk to leviathan blake is contactb.It is a monalphabetic cipher and so easily breakable.c.The last sentence may not contain all the letters of the alphabet. If the firstsentence is used, the second and subsequent sentences may also be used untilall 26 letters are encountered.2.6The cipher refers to the words in the page of a book. The first entry, 534, refers topage 534. The second entry, C2, refers to column two. The remaining numbers are words in that column. The names DOUGLAS and BIRLSTONE are simply words that do not appear on that page. Elementary! (from The Valley of Fear, by Sir Arthur Conan Doyle)2.7 a.2 8 10 7 9 63 14 54 2 8 1056 37 1 9ISRNG BUTLF RRAFR LIDLP FTIYO NVSEE TBEHI HTETAEYHAT TUCME HRGTA IOENT TUSRU IEADR FOETO LHMETNTEDS IFWRO HUTEL EITDSb.The two matrices are used in reverse order. First, the ciphertext is laid out incolumns in the second matrix, taking into account the order dictated by thesecond memory word. Then, the contents of the second matrix are read left toright, top to bottom and laid out in columns in the first matrix, taking intoaccount the order dictated by the first memory word. The plaintext is then read left to right, top to bottom.c.Although this is a weak method, it may have use with time-sensitiveinformation and an adversary without immediate access to good cryptanalysis(e.g., tactical use). Plus it doesn't require anything more than paper and pencil,and can be easily remembered.2.8 SPUTNIK2.9 PT BOAT ONE OWE NINE LOST IN ACTION IN BLACKETT STRAIT TWOMILES SW MERESU COVE X CREW OF TWELVE X REQUEST ANYINFORMATION2.10 a.b.2.11 a. UZTBDLGZPNNWLGTGTUEROVLDBDUHFPERHWQSRZb.UZTBDLGZPNNWLGTGTUEROVLDBDUHFPERHWQSRZc. A cyclic rotation of rows and/or columns leads to equivalent substitutions. Inthis case, the matrix for part a of this problem is obtained from the matrix ofProblem 2.10a, by rotating the columns by one step and the rows by three steps.2.12 a. 25! ≈ 284b. Given any 5x5 configuration, any of the four row rotations is equivalent, for atotal of five equivalent configurations. For each of these five configurations,any of the four column rotations is equivalent. So each configuration in factrepresents 25 equivalent configurations. Thus, the total number of unique keysis 25!/25 = 24!2.13 A mixed Caesar cipher. The amount of shift is determined by the keyword, whichdetermines the placement of letters in the matrix.2.14 a. Difficulties are things that show what men are.b. Irrationally held truths may be more harmful than reasoned errors.2.15 a. We need an even number of letters, so append a "q" to the end of the message.Then convert the letters into the corresponding alphabetic positions:The calculations proceed two letters at a time. The first pair:The first two ciphertext characters are alphabetic positions 7 and 22, whichcorrespond to GV. The complete ciphertext:GVUIGVKODZYPUHEKJHUZWFZFWSJSDZMUDZMYCJQMFWWUQRKRb. We first perform a matrix inversion. Note that the determinate of theencryption matrix is (9 ⨯ 7) – (4 ⨯ 5) = 43. Using the matrix inversion formulafrom the book:Here we used the fact that (43)–1 = 23 in Z26. Once the inverse matrix has beendetermined, decryption can proceed. Source: [LEWA00].2.16 Consider the matrix K with elements k ij to consist of the set of column vectors K j,where:andThe ciphertext of the following chosen plaintext n-grams reveals the columns of K:(B, A, A, …, A, A) ↔ K1(A, B, A, …, A, A) ↔ K2:(A, A, A, …, A, B) ↔ K n2.17 a.7 ⨯ 134b.7 ⨯ 134c.134d.10 ⨯ 134e.24⨯ 132f.24⨯(132– 1) ⨯ 13g. 37648h.23530i.1572482.18 key: legleglegleplaintext: explanationciphertext: PBVWETLXOZR2.19 a.b.2.20your package ready Friday 21st room three Please destroy this immediately.2.21 y the message out in a matrix 8 letters across. Each integer in the key tellsyou which letter to choose in the corresponding row. Result:He sitteth between the cherubims. The isles may be gladthereof. As the rivers in the south.b.Quite secure. In each row there is one of eight possibilities. So if the ciphertextis 8n letters in length, then the number of possible plaintexts is 8n.c. Not very secure. Lord Peter figured it out. (from The Nine Tailors)3.1 Most symmetric block encryption algorithms in current use are based on the Feistelblock cipher structure. Therefore, a study of the Feistel structure reveals theprinciples behind these more recent ciphers.3.2 A stream cipher is one that encrypts a digital data stream one bit or one byte at atime. A block cipher is one in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length.3.3 If a small block size, such as n = 4, is used, then the system is equivalent to aclassical substitution cipher. For small n, such systems are vulnerable to a statistical analysis of the plaintext. For a large block size, the size of the key, which is on the order of n 2n, makes the system impractical.3.4 In a product cipher, two or more basic ciphers are performed in sequence in such away that the final result or product is cryptographically stronger than any of the component ciphers.3.5 In diffusion, the statistical structure of the plaintext is dissipated into long-rangestatistics of the ciphertext. This is achieved by having each plaintext digit affect thevalue of many ciphertext digits, which is equivalent to saying that each ciphertext digit is affected by many plaintext digits. Confusion seeks to make the relationship between the statistics of the ciphertext and the value of the encryption key ascomplex as possible, again to thwart attempts to discover the key. Thus, even if the attacker can get some handle on the statistics of the ciphertext, the way in which the key was used to produce that ciphertext is so complex as to make it difficult todeduce the key. This is achieved by the use of a complex substitution algorithm. 3.6 Block size: Larger block sizes mean greater security (all other things being equal)but reduced encryption/decryption speed. Key size: Larger key size means greater security but may decrease encryption/decryption speed. Number of rounds: The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security. Subkey generation algorithm:Greater complexity in this algorithm should lead to greater difficulty ofcryptanalysis. Round function: Again, greater complexity generally means greater resistance to cryptanalysis. Fast software encryption/decryption: In many cases, encryption is embedded in applications or utility functions in such a way as topreclude a hardware implementation. Accordingly, the speed of execution of the algorithm becomes a concern. Ease of analysis: Although we would like to make our algorithm as difficult as possible to cryptanalyze, there is great benefit inmaking the algorithm easy to analyze. That is, if the algorithm can be concisely and clearly explained, it is easier to analyze that algorithm for cryptanalyticvulnerabilities and therefore develop a higher level of assurance as to its strength.3.7 The S-box is a substitution function that introduces nonlinearity and adds to thecomplexity of the transformation.3.8 The avalanche effect is a property of any encryption algorithm such that a smallchange in either the plaintext or the key produces a significant change in theciphertext.3.9 Differential cryptanalysis is a technique in which chosen plaintexts with particularXOR difference patterns are encrypted. The difference patterns of the resultingciphertext provide information that can be used to determine the encryption key.Linear cryptanalysis is based on finding linear approximations to describe thetransformations performed in a block cipher.3.1 a. For an n-bit block size are 2n possible different plaintext blocks and 2n possibledifferent ciphertext blocks. For both the plaintext and ciphertext, if we treat theblock as an unsigned integer, the values are in the range 0 through 2n– 1. For amapping to be reversible, each plaintext block must map into a uniqueciphertext block. Thus, to enumerate all possible reversible mappings, the blockwith value 0 can map into anyone of 2n possible ciphertext blocks. For anygiven mapping of the block with value 0, the block with value 1 can map intoany one of 2n– 1 possible ciphertext blocks, and so on. Thus, the total numberof reversible mappings is (2n)!.b. In theory, the key length could be log2(2n)! bits. For example, assign eachmapping a number, from 1 through (2n)! and maintain a table that shows themapping for each such number. Then, the key would only require log2(2n)! bits, but we would also require this huge table. A more straightforward way todefine the key is to have the key consist of the ciphertext value for eachplaintext block, listed in sequence for plaintext blocks 0 through 2n– 1. This iswhat is suggested by Table 3.1. In this case the key size is n⨯ 2n and the hugetable is not required.3.2 Because of the key schedule, the round functions used in rounds 9 through 16 aremirror images of the round functions used in rounds 1 through 8. From this fact we see that encryption and decryption are identical. We are given a ciphertext c.Let m' = c. Ask the encryption oracle to encrypt m'. The ciphertext returned by the oracle will be the decryption of c.3.3 a.We need only determine the probability that for the remaining N – t plaintextsP i, we have E[K, P i] ≠ E[K', P i]. But E[K, P i] = E[K', P i] for all the remaining P iwith probability 1 – 1/(N–t)!.b.Without loss of generality we may assume the E[K, P i] = P i since E K(•) is takenover all permutations. It then follows that we seek the probability that apermutation on N–t objects has exactly t' fixed points, which would be theadditional t' points of agreement between E(K, •) and E(K', •). But apermutation on N–t objects with t' fixed points is equal to the number of wayst' out of N–t objects can be fixed, while the remaining N–t–t' are not fixed.Then using Problem 3.4 we have thatPr(t' additional fixed points) = ⨯Pr(no fixed points in N – t – t' objects)=We see that this reduces to the solution to part (a) when t' = N–t.3.4Let be the set of permutations on [0, 1, . . ., 2n– 1], which is referredto as the symmetric group on 2n objects, and let N = 2n. For 0 ≤ i≤ N, let A i be all mappings for which π(i) = i. It follows that |A i| = (N– 1)! and= (N–k)!. The inclusion-exclusion principle states thatPr(no fixed points in π)=== 1 – 1 + 1/2! – 1/3! + . . . + (–1)N⨯ 1/N!= e–1 +Then since e–1≈ 0.368, we find that for even small values of N, approximately37% of permutations contain no fixed points.3.53.6 Main key K = 111…111 (56 bits)Round keys K1 = K2=…= K16 = 1111..111 (48 bits)Ciphertext C = 1111…111 (64 bits)Input to the first round of decryption =LD0RD0 = RE16LE16 = IP(C) = 1111...111 (64 bits)LD0 = RD0 = 1111...111 (32 bits)Output of the first round of decryption = LD1RD1LD1 = RD0= 1111…111 (32 bits)Thus, the bits no. 1 and 16 of the output are equal to ‘1’.RD1 = LD0 F(RD0, K16)We are looking for bits no. 1 and 16 of RD1 (33 and 48 of the entire output).Based on the analysis of the permutation P, bit 1 of F(RD0, K16) comes from thefourth output of the S-box S4, and bit 16 of F(RD0, K16) comes from the second output of the S-box S3. These bits are XOR-ed with 1’s from the correspondingpositions of LD0.Inside of the function F,E(RD0) ≈ K16= 0000…000 (48 bits),and thus inputs to all eight S-boxes are equal to “000000”.Output from the S-box S4 = “0111”, and thus the fourth output is equal to ‘1’,Output from the S-box S3 = “1010”, and thus the second output is equal to ‘0’.From here, after the XOR, the bit no. 33 of the first round output is equal to ‘0’, and the bit no. 48 is equal to ‘1’.3.7 In the solution given below the following general properties of the XOR functionare used:A ⊕ 1 = A'(A ⊕ B)' = A' ⊕ B = A ⊕ B'A' ⊕ B' = A ⊕ BWhere A' = the bitwise complement of A.a. F (R n, K n+1) = 1We haveL n+1 = R n; R n+1 = L n⊕ F (R n, K n+1) = L n⊕ 1 = L n'ThusL n+2 = R n+1 = L n' ; R n+2 = L n+1 = R n'i.e., after each two rounds we obtain the bit complement of the original input,and every four rounds we obtain back the original input:L n+4 = L n+2' = L n ; R n+2 = R n+2' = R nTherefore,L16 = L0; R16 = R0An input to the inverse initial permutation is R16 L16.Therefore, the transformation computed by the modified DES can berepresented as follows:C = IP–1(SWAP(IP(M))), where SWAP is a permutation exchanging the positionof two halves of the input: SWAP(A, B) = (B, A).This function is linear (and thus also affine). Actually, this is a permutation, the product of three permutations IP, SWAP, and IP–1. This permutation ishowever different from the identity permutation.b. F (R n, K n+1) = R n'We haveL n+1 = R n; R n+1 = L n⊕ F(R n, K n+1) = L n⊕ R n'L n+2 = R n+1 = L n⊕ R n'R n+2 = L n+1⊕ F(R n+1, K n+2) = R n≈ (L n⊕ R n')' = R n⊕ L n⊕ R n'' = L nL n+3 = R n+2 = L nR n+3 = L n+2⊕ F (R n+2, K n+3) = (L n≈ R n') ⊕ L n' = R n' ⊕1 = R ni.e., after each three rounds we come back to the original input.L15 = L0; R15 = R0andL16 = R0(1)R16 = L0⊕ R0' (2)An input to the inverse initial permutation is R16 L16.A function described by (1) and (2) is affine, as bitwise complement is affine,and the other transformations are linear.The transformation computed by the modified DES can be represented asfollows:C = IP–1(FUN2(IP(M))), where FUN2(A, B) = (A ⊕ B', B).This function is affine as a product of three affine functions.In all cases decryption looks exactly the same as encryption.3.8 a. First, pass the 64-bit input through PC-1 (Table 3.4a) to produce a 56-bit result.Then perform a left circular shift separately on the two 28-bit halves. Finally,pass the 56-bit result through PC-2 (Table 3.4b) to produce the 48-bit K1.:in binary notation: 0000 1011 0000 0010 0110 01111001 1011 0100 1001 1010 0101in hexadecimal notation: 0 B 0 2 6 7 9 B 4 9 A 5b. L0, R0 are derived by passing the 64-plaintext through IP (Table 3.2a):L0 = 1100 1100 0000 0000 1100 1100 1111 1111R0 = 1111 0000 1010 1010 1111 0000 1010 1010c. The E table (Table 3.2c) expands R0 to 48 bits:E(R0) = 01110 100001 010101 010101 011110 100001 010101 010101d. A = 011100 010001 011100 110010 111000 010101 110011 110000e. (1110) = (14) = 0 (base 10) = 0000 (base 2)(1000) = (8) = 12 (base 10) = 1100 (base 2)(1110) = (14) = 2 (base 10) = 0010 (base 2)(1001) = (9) = 1 (base 10) = 0001 (base 2)(1100) = (12) = 6 (base 10) = 0110 (base 2)(1010) = (10) = 13 (base 10) = 1101 (base 2)(1001) = (9) = 5 (base 10) = 0101 (base 2)(1000) = (8) = 0 (base 10) = 0000 (base 2)f. B = 0000 1100 0010 0001 0110 1101 0101 0000g. Using Table 3.2d, P(B) = 1001 0010 0001 1100 0010 0000 1001 1100h. R1 = 0101 1110 0001 1100 1110 1100 0110 0011i. L1 = R0. The ciphertext is the concatenation of L1 and R1. Source: [MEYE82]3.9The reasoning for the Feistel cipher, as shown in Figure 3.6 applies in the case ofDES. We only have to show the effect of the IP and IP–1 functions. For encryption, the input to the final IP–1 is RE16|| LE16. The output of that stage is the ciphertext.On decryption, the first step is to take the ciphertext and pass it through IP. Because IP is the inverse of IP–1, the result of this operation is just RE16|| LE16, which isequivalent to LD0|| RD0. Then, we follow the same reasoning as with the Feistel cipher to reach a point where LE0 = RD16 and RE0 = LD16. Decryption is completed by passing LD0|| RD0 through IP–1. Again, because IP is the inverse of IP–1, passing the plaintext through IP as the first step of encryption yields LD0|| RD0, thusshowing that decryption is the inverse of encryption.3.10a.Let us work this from the inside out.T16(L15|| R15) = L16|| R16T17(L16|| R16) = R16|| L16IP [IP–1 (R16|| L16)] = R16|| L16TD1(R16|| L16) = R15|| L15b.T16(L15|| R15) = L16|| R16IP [IP–1 (L16|| R16)] = L16|| R16TD1(R16 || L16) = R16|| L16 f(R16, K16)≠ L15|| R153.11PC-1 is essentially the same as IP with every eighth bit eliminated. This wouldenable a similar type of implementation. Beyond that, there does not appear to be any particular cryptographic significance.3.13a.The equality in the hint can be shown by listing all 1-bit possibilities:We also need the equality A ⊕ B = A' ⊕ B', which is easily seen to be true. Now, consider the two XOR operations in Figure 3.8. If the plaintext and key for anencryption are complemented, then the inputs to the first XOR are alsocomplemented. The output, then, is the same as for the uncomplementedinputs. Further down, we see that only one of the two inputs to the secondXOR is complemented, therefore, the output is the complement of the outputthat would be generated by uncomplemented inputs.b.In a chosen plaintext attack, if for chosen plaintext X, the analyst can obtain Y1= E[K, X] and Y2 = E[K, X'], then an exhaustive key search requires only 255rather than 256 encryptions. To see this, note that (Y2)' = E[K', X]. Now, pick atest value of the key T and perform E[T, X]. If the result is Y1, then we knowthat T is the correct key. If the result is (Y2)', then we know that T' is the correctkey. If neither result appears, then we have eliminated two possible keys withone encryption.3.14 The result can be demonstrated by tracing through the way in which the bits areused. An easy, but not necessary, way to see this is to number the 64 bits of the key as follows (read each vertical column of 2 digits as a number):2113355-1025554-0214434-1123334-0012343-2021453-0202435-0110454- 1031975-1176107-2423401-7632789-7452553-0858846-6836043-9495226-The first bit of the key is identified as 21, the second as 10, the third as 13, and so on.The eight bits that are not used in the calculation are unnumbered. The numbers 01 through 28 and 30 through 57 are used. The reason for this assignment is to clarify the way in which the subkeys are chosen. With this assignment, the subkey for the first iteration contains 48 bits, 01 through 24 and 30 through 53, in their naturalnumerical order. It is easy at this point to see that the first 24 bits of each subkey will always be from the bits designated 01 through 28, and the second 24 bits of each subkey will always be from the bits designated 30 through 57.3.15 For 1 ≤ i ≤ 128, take c i∈ {0, 1}128 to be the string containing a 1 in position i andthen zeros elsewhere. Obtain the decryption of these 128 ciphertexts. Let m1,m2, . . . , m128 be the corresponding plaintexts. Now, given any ciphertext c which does not consist of all zeros, there is a unique nonempty subset of the c i’s which we can XOR together to obtain c. Let I(c) ⊆ {1, 2, . . . , 128} denote this subset.ObserveThus, we obtain the plaintext of c by computing . Let 0 be the all-zerostring. Note that 0 = 0⊕0. From this we obtain E(0) = E(0⊕0) = E(0) ⊕ E(0) = 0.Thus, the plaintext of c = 0 is m = 0. Hence we can decrypt every c ∈ {0, 1}128.3.16a. This adds nothing to the security of the algorithm. There is a one-to-onereversible relationship between the 10-bit key and the output of the P10function. If we consider the output of the P10 function as a new key, then thereare still 210 different unique keys.b. By the same reasoning as (a), this adds nothing to the security of the algorithm.3.17s = wxyz + wxy + wyz + wy + wz + yz + w + x + zt = wxz + wyz + wz + xz + yz + w + y3.18OK4.1 A group is a set of elements that is closed under a binary operation and that isassociative and that includes an identity element and an inverse element.4.2 A ring is a set of elements that is closed under two binary operations, addition andsubtraction, with the following: the addition operation is a group that iscommutative; the multiplication operation is associative and is distributive over the addition operation.C HAPTER 4F INITE F IELDS。

CAPTCHA:Using Hard AI Problems For SecurityLuis von Ahn1,Manuel Blum1,Nicholas J.Hopper1,and John Langford21Computer Science Dept.,Carnegie Mellon University,Pittsburgh PA15213,USA 2IBM T.J.Watson Research Center,Yorktown Heights NY10598,USAAbstract.We introduce captcha,an automated test that humans canpass,but current computer programs can’t pass:any program that hashigh success over a captcha can be used to solve an unsolved Artifi-cial Intelligence(AI)problem.We provide several novel constructions ofcaptcha s.Since captcha s have many applications in practical secu-rity,our approach introduces a new class of hard problems that can beexploited for security purposes.Much like research in cryptography hashad a positive impact on algorithms for factoring and discrete log,wehope that the use of hard AI problems for security purposes allows usto advance thefield of Artificial Intelligence.We introduce two familiesof AI problems that can be used to construct captcha s and we showthat solutions to such problems can be used for steganographic commu-nication.captcha s based on these AI problem families,then,imply awin-win situation:either the problems remain unsolved and there is away to differentiate humans from computers,or the problems are solvedand there is a way to communicate covertly on some channels.1IntroductionA captcha is a program that can generate and grade tests that:(A)most humans can pass,but(B)current computer programs can’t pass.Such a program can be used to differentiate humans from computers and has many applications for practical security,including(but not limited to):–Online Polls.In November1999, released an online poll ask-ing which was the best graduate school in computer science(a dangerous question to ask over the web!).As is the case with most online polls,IP addresses of voters were recorded in order to prevent single users from vot-ing more than once.However,students at Carnegie Mellon found a way to stuffthe ballots by using programs that voted for CMU thousands of times.CMU’s score started growing rapidly.The next day,students at MIT wrote their own voting program and the poll became a contest between voting “bots”.MITfinished with21,156votes,Carnegie Mellon with21,032and every other school with less than1,000.Can the result of any online poll be trusted?Not unless the poll requires that only humans can vote.–Free Email Services.Several companies(Yahoo!,Microsoft,etc.)offer free email services,most of which suffer from a specific type of attack:“bots”that sign up for thousands of email accounts every minute.This situation can be improved by requiring users to prove they are human before they can get a free email account.Yahoo!,for instance,uses a captcha of our design to prevent bots from registering for accounts.Their captcha asks users to read a distorted word such as the one shown below(current computer programs are not as good as humans at reading distorted text).Fig.1.The Yahoo!captcha.–Search Engine Bots.Some web sites don’t want to be indexed by search engines.There is an html tag to prevent search engine bots from reading web pages,but the tag doesn’t guarantee that bots won’t read the pages;it only serves to say“no bots,please”.Search engine bots,since they usually belong to large companies,respect web pages that don’t want to allow them in.However,in order to truly guarantee that bots won’t enter a web site, captcha s are needed.–Worms and Spam.captcha s also offer a plausible solution against email worms and spam:only accept an email if you know there is a human be-hind the other computer.A few companies,such as are already marketing this idea.–Preventing Dictionary Attacks.Pinkas and Sander[11]have suggested using captcha s to prevent dictionary attacks in password systems.The idea is simple:prevent a computer from being able to iterate through the entire space of passwords by requiring a human to type the passwords.The goals of this paper are to lay a solid theoretical foundation for captcha s, to introduce the concept to the cryptography community,and to present several novel constructions.Lazy Cryptographers Doing AINote that from a mechanistic point of view,there is no way to prove that a program cannot pass a test which a human can pass,since there is a program—the human brain—which passes the test.All we can do is to present evidence that it’s hard to write a program that can pass the test.In this paper,we take an approach familiar to cryptographers:investigate state-of-the-art algorithmic developments having to do with some problem,assume that the adversary doesnot have algorithms for that problem that are are much better than the state-of-the-art algorithms,and then prove a reduction between passing a test and exceeding the performance of state-of-the-art algorithms.In the case of ordi-nary cryptography,it is assumed(for example)that the adversary cannot factor 1024-bit integers in any reasonable amount of time.In our case,we assume that the adversary cannot solve an Artificial Intelligence problem with higher accu-racy than what’s currently known to the AI community.This approach,if it achieves widespread adoption,has the beneficial side effect of inducing security researchers,as well as otherwise malicious programmers,to advance thefield of AI(much like computational number theory has been advanced since the advent of modern cryptography).A captcha is a cryptographic protocol whose underlying hardness as-sumption is based on an AI problem.An important component of the success of modern cryptography is the practice of stating,very precisely and clearly,the assumptions under which cryptographic protocols are secure.This allows the rest of the community to evaluate the as-sumptions and to attempt to break them.In the case of Artificial Intelligence,it’s rare for problems to be precisely stated,but using them for security purposes forces protocol designers to do so.We believe that precisely stating unsolved AI problems can accelerate the development of Artificial Intelligence:most AI problems that have been precisely stated and publicized have eventually been solved(take chess as an example).For this reason it makes practical sense for AI problems that are used for security purposes to also be useful.If the under-lying AI problem is useful,a captcha implies a win-win situation:either the captcha is not broken and there is a way to differentiate humans from comput-ers,or the captcha is broken and a useful AI problem is solved.Such is not the case for most other cryptographic assumptions:the primary reason algorithms for factoring large numbers are useful is because factoring has applications in cryptanalysis.In this paper we will present constructions of captcha s based on certain AI problems and we will show that solving the captcha s implies solving the AI problems.The AI problems we chose have several applications,and we will show that solutions to them can be used,among other things,for steganographic communication(see Section5).Related WorkThefirst mention of ideas related to“Automated Turing Tests”seems to appear in an unpublished manuscript by Moni Naor[10].This excellent manuscript contains some of the crucial notions and intuitions,but gives no proposal for an Automated Turing Test,nor a formal definition.Thefirst practical example of an Automated Turing Test was the system developed by Altavista[8]to prevent “bots”from automatically registering web pages.Their system was based on the difficulty of reading slightly distorted characters and worked well in practice,but was only meant to defeat off-the-shelf Optical Character Recognition(OCR) technology.(Coates et al[5],inspired by our work,and Xu et al[14]developed similar systems and provided more concrete analyses.)In2000[1],we introduced the notion of a captcha as well as several practical proposals for Automated Turing Tests.This paper is thefirst to conduct a rigorous investigation of Automated Turing Tests and to address the issue of proving that it is difficult to write a computer program that can pass the tests.This,in turn,leads to a discussion of using AI problems for security purposes,which has never appeared in the literature.We also introduce thefirst Automated Turing Tests not based on the difficulty of Optical Character Recognition.A related general interest paper[2] has been accepted by Communications of the ACM.That paper reports on our work,without formalizing the notions or providing security guarantees.2Definitions and NotationLet C be a probability distribution.We use[C]to denote the support of C.If P(·)is a probabilistic program,we will denote by P r(·)the deterministic program that results when P uses random coins r.Let(P,V)be a pair of probabilistic interacting programs.We denote the output of V after the interaction between P and V with random coins u1and u2,assuming this interaction terminates,by P u1,V u2(the subscripts are omittedin case the programs are deterministic).A program V is called a test if for allP and u1,u2,the interaction between P u1and V u2terminates and P u1,V u2∈{accept,reject}.We call V the verifier or tester and any P which interacts with V the prover.Definition1.Define the success of an entity A over a test V bySucc V A=Prr,r[ A r,V r =accept].We assume that A can have precise knowledge of how V works;the only piece of information that A can’t know is r ,the internal randomness of V.CAPTCHAIntuitively,a captcha is a test V over which most humans have success close to1,and for which it is hard to write a computer program that has high success over V.We will say that it is hard to write a computer program that has high success over V if any program that has high success over V can be used to solve a hard AI problem.Definition2.A test V is said to be(α,β)-human executable if at least anαportion of the human population has success greater thanβover V.Notice that a statement of the form“V is(α,β)-human executable”can only be proven empirically.Also,the success of different groups of humans might depend on their origin language or sensory disabilities:color-blind individuals, for instance,might have low success on tests that require the differentiation of colors.Definition3.An AI problem is a triple P=(S,D,f),where S is a set of problem instances,D is a probability distribution over the problem set S,and f:S→{0,1}∗answers the instances.Letδ∈(0,1].We require that for an α>0fraction of the humans H,Pr x←D[H(x)=f(x)]>δ.Definition4.An AI problem P is said to be(δ,τ)-solved if there exists a pro-gram A,running in time at mostτon any input from S,such that[A r(x)=f(x)]≥δ.Prx←D,r(A is said to be a(δ,τ)solution to P.)P is said to be a(δ,τ)-hard AI problem if no current program is a(δ,τ)solution to P,and the AI community agrees it is hard tofind such a solution.Definition5.A(α,β,η)-captcha is a test V that is(α,β)-human executable, and which has the following property:There exists a(δ,τ)-hard AI problem P and a program A,such that ifB has success greater thanηover V then A B is a(δ,τ)solution to P.(Here A B is defined to take into account B’s running time too.)We stress that V should be a program whose code is publicly available. Remarks1.The definition of an AI problem as a triple(S,D,f)should not be inspectedwith a philosophical eye.We are not trying to capture all the problems that fall under the umbrella of Artificial Intelligence.We want the definition to be easy to understand,we want some AI problems to be captured by it,and we want the AI community to agree that these are indeed hard AI problems.More complex definitions can be substituted for Definition3and the rest of the paper remains unaffected.2.A crucial characteristic of an AI problem is that a certain fraction of thehuman population be able to solve it.Notice that we don’t impose a limit on how long it would take humans to solve the problem.All that we require is that some humans be able to solve it(even if we have to assume they will live hundreds of years to do so).The case is not the same for captcha s.Although our definition says nothing about how long it should take a human to solve a captcha,it is preferable for humans to be able to solve captcha s in a very short time.captcha s which take a long time for humans to solve are probably useless for all practical purposes.AI Problems as Security PrimitivesNotice that we define hard in terms of the consensus of a community:an AI problem is said to be hard if the people working on it agree that it’s hard. This notion should not be surprising to cryptographers:the security of most modern cryptosystems is based on assumptions agreed upon by the community (e.g.,we assume that1024-bit integers can’t be factored).The concept of a hard AI problem as a foundational assumption,of course,is more questionable than P=NP,since many people in the AI community agree that all hard AI problems are eventually going to be solved.However,hard AI problems may be a more reasonable assumption than the hardness of factoring,given the possibility of constructing a quantum computer.Moreover,even if factoring is shown to be hard in an asymptotic sense,picking a concrete value for the security parameter usually means making an assumption about current factoring algorithms:we only assume that current factoring algorithms that run in current computers can’t factor1024-bit integers.In the same way that AI researchers believe that all AI problems will be solved eventually,we believe that at some point we will have the computational power and algorithmic ability to factor1024-bit integers. (Shamir and Tromer[13],for instance,have proposed a machine that could factor 1024-bit integers;the machine would cost about ten million dollars in materials.) An important difference between popular cryptographic primitives and AI problems is the notion of a security parameter.If we believe that an adversary can factor1024-bit integers,we can use2048-bit integers instead.No such concept exists in hard AI problems.AI problems,as we have defined them,do not deal with asymptotics.However,as long as there is a small gap between human and computer ability with respect to some problem,this problem can potentially be used as a primitive for security:rather than asking the prover to solve the problem once,we can ask it to solve the problem twice.If the prover gets good at solving the problem twice,we can ask it to solve the problem three times,etc.There is an additional factor that simplifies the use of hard AI problems as security primitives.Most applications of captcha s require the tests to be answered within a short time after they are presented.If a new program solves the hard AI problems that are currently used,then a different set of problems can be used,and the new program cannot affect the security of applications that were run before it was pare this to encryption schemes:in many applications the information that is encrypted must remain confidential for years,and therefore the underlying problem must be hard against programs that run for a long time,and against programs that will be developed in the future.1We also note that not all hard AI problems can be used to construct a captcha.In order for an AI problem to be useful for security purposes,there needs to be an automated way to generate problem instances along with their solution.The case is similar for computational problems:not all hard computa-tional problems yield cryptographic primitives.Who Knows What?Our definitions imply that an adversary attempting to write a program that has high success over a captcha knows exactly how the captcha works.The only piece of information that is hidden from the adversary is a small amount of randomness that the verifier uses in each interaction.This choice greatly affects the nature of our definitions and makes the prob-lem of creating captcha s more challenging.Imagine an Automated Turing Test that owns a large secret book written in English and to test an entity A it ei-ther picks a paragraph from its secret book or generates a paragraph using the best known text-generation algorithm,and then asks A whether the paragraph makes sense(the best text-generation algorithms cannot produce an entire para-graph that would make sense to a human being).Such an Automated Turing Test might be able to distinguish humans from computers(it is usually the case that the best text-generation algorithms and the best algorithms that try to de-termine whether something makes sense are tightly related).However,this test cannot be a captcha:an adversary with knowledge of the secret book could achieve high success against this test without advancing the algorithmic state of the art.We do not allow captcha s to base their security in the secrecy of a database or a piece of code.Gap AmplificationWe stress that any positive gap between the success of humans and current computer programs against a captcha can be amplified to a gap arbitrarily close to1by serial repetition.The case for parallel repetition is more complicated and is addressed by Bellare,Impagliazzo and Naor in[3].Let V be an(α,β,η)-captcha,and let V m k be the test that results by repeat-ing V m times in series(with fresh new randomness each time)and accepting only if the prover passes V more than k times.Then for any >0there exist m and k with0≤k≤m such that V m k is an(α,1− , )-captcha.In gen-eral,we will have m=O(1/(β−η)2ln(1/ ))and sometimes much smaller.Since captcha s involve human use,it is desirable tofind the smallest m possible. This can be done by solving the following optimization problem:minm ∃k:m i=k+1 m i βi(1−β)m−i≥1− &k i=0 m i ηi(1−η)m−i≤Notice that amplifying a gap can roughly be thought of as increasing the security parameter of a captcha:if the best computer program now has success 0.10against a given captcha(for example),then we can ask the prover to pass the captcha twice(in series)to reduce the best computer program’s success probability to0.01.3Two AI Problem FamiliesIn this section we introduce two families of AI problems that can be used to construct captcha s.The section can be viewed as a precise statement of the kind of hardness assumptions that our cryptographic protocols are based on.We stress that solutions to the problems will also be shown to be useful.For the purposes of this paper,we define an image as an h×w matrix(h for height and w for width)whose entries are pixels.A pixel is defined as a triple of integers(R,G,B),where0≤R,G,B≤M for some constant M.An image transformation is a function that takes as input an image and outputs another image(not necessarily of the same width and height).Examples of image transformations include:turning an image into its black-and-white version, changing its size,etc.Let I be a distribution on images and T be a distribution on image transfor-mations.We assume for simplicity that if i,i ∈[I]and i=i then T(i)=T (i ) for any T,T ∈[T].(Recall that[I]denotes the support of I.)Problem Family(P1).Consider the following experiment:choose an image i←I and choose a transformation t←T;output t(i).P1I,T consists of writing a program that takes t(i)as input and outputs i(we assume that the program has precise knowledge of T and I).More formally,let S I,T={t(i):t∈[T] and i∈[I]},D I,T be the distribution on S I,T that results from performing the above experiment and f I,T:S I,T→[I]be such that f I,T(t(i))=i.Then P1I,T=(S I,T,D I,T,f I,T).Problem Family(P2).In addition to the distributions I and T,let L be a finite set of“labels”.Letλ:[I]→L compute the label of an image.The set of problem instances is S I,T={t(i):t∈[T]and i∈[I]},and the distribution on instances D I,T is the one induced by choosing i←I and t←T.Define g I,T,λso that g I,T,λ(t(i))=λ(i).Then P2I,T,λ=(S I,T,D I,T,g I,T,λ)consists of writing a program that takes t(i)as input and outputsλ(i).Remarks1.Note that a(δ,τ)solution A to an instance of P1also yields a(δ ,τ+τ )solution to an instance of P2(whereδ ≥δandτ ≤log|[I]|is the time that it takes to computeλ),specifically,computingλ(A(x)).However,this may be unsatisfactory for smallδ,and we might hope to do better by restricting to a smaller set of labels.Conversely,P1can be seen as a special case of P2withλthe identity function and L=[I].Formally,problem families P1 and P2can be shown to be isomorphic.Nonetheless,it is useful to make a distinction here because in some applications it appears unnatural to talk about labels.2.We stress that in all the instantiations of P1and P2that we consider,I,Tand,in the case of P2,λ,will be such that humans have no problem solving P1I,T and P2I,T,λ.That is,[T]is a set of transformations that humanscan easily undo in[I].Additionally,it has to be possible to perform all the transformations in[T]using current computer programs.3.There is nothing specific to images about these problem definitions;any otherspace of objects which humans recognize under reasonable transformations(e.g.,organized sounds such as music or speech,animations,et cetera)couldbe substituted without changing our results.4.It is easy to build a(δI,τI)-solution to P1I,T,whereδI=max{Pr j←I[j=i]:i∈[I]}andτI is the time that it takes to describe an element of[I],by always guessing the image with the highest probability in I.Sim-ilarly,it is easy to build a(δI,λ,τI,λ)-solution to P2I,T,λ,whereδI,λ= max{Pr j←I[λ(j)=λ(i)]:i∈[I]}andτI,λis the time that it takes to de-scribe a label in L.Therefore,we restrict our attention tofinding solutions to P1I,T whereδ>δI and solutions to P2I,T,λwhereδ>δI,λ.Hard Problems in P1and P2We believe that P1and P2contain several hard problems.For example,the captcha shown in Section1(and other captcha s based on the difficulty of reading slightly distorted text)could be defeated using solutions to P2.To see this,let W be a set of images of words in different fonts.All the images in W should be undistorted and contain exactly one word each.Let I W be a distri-bution on W,let T W be a distribution on image transformations,and letλWmap an image to the word that is contained in it.A solution to P2IW ,T W,λWis aprogram that can defeat a captcha such as the one that Yahoo!uses(assuming T W is the same set of transformations they use).So the problem of determining the word in a distorted image is an instantiation of P2(it can be easily seen to be an instantiation of P1too).Reading slightly distorted text has been an open problem in machine vision for quite some time.(For a good overview of the difficulties of reading slightly distorted text,see[12].)But P1and P2are much more general,and reading slightly distorted text is a somewhat easy instance of these problems.In general it will not be the case that the problem is reduced to matching26∗2+10different characters(upper and lowercase letters plus the digits).The hardness of problems in P1and P2mostly relies on T.In particular,it should be computationally infeasible to enumerate all of the elements of[T],since I will normally be such that enumeration of[I]is feasible.Thus we are mainly interested in(δ,τ)solutions whereτ |[T]|,whileτ>|[I]|may sometimes be acceptable.In addition to the size of the transformation set,the character of the transformations is also important:it is necessary to defeat many simple checks such as color histogram comparisons,frequency domain checks,etc.Since instantiations of P1and P2have never been precisely stated and pub-lished as challenges to the AI and security communities,there is no way to tell if they will withstand the test of time.For now we refer the reader to for examples of I’s and T’s which are believed to be good candidates.Any instantiation of P1and P2for security purposes requires that the precise I and T be published and thoroughly described.4Two Families of captcha sWe now describe two families of captcha s whose security is based on the hard-ness of problems in P1and P2.Notice that if P1I,T is(δ,τ)-hard then P1I,T can be used to construct a captcha trivially:the verifier simply gives the prover t(i)and asks the prover to output i.According to our definition,this would be a perfectly valid captcha.However,it would also be a very impractical one: if[I]is large,then humans would take a long time to answer.The captcha s we present in this section can be quickly answered by humans.Thefirst family of captcha s,matcha,is somewhat impractical,but the second family,pix,is very practical and in fact several instantiations of it are already in use.4.1MATCHAA matcha instance is described by a triple M=(I,T,τ),where I is a distri-bution on images and T is a distribution on image transformations that can be easily computed using current computer programs.matcha is a captcha with the following property:any program that has high success over M=(I,T)can be used to solve P1I,T.The matcha verifier starts by choosing a transformation t←T.It thenflips a fair unbiased coin.If the result is heads,it picks k←I and sets(i,j)=(k,k). If the result is tails,it sets j←I and i←U([I]−{j})where U(S)is the uniform distribution on the set S.The matcha verifier sends the prover(i,t(j))and sets a timer to expire in timeτ;the prover responds with res∈{0,1}.Informally, res=1means that i=j,while res=0means that i=j.If the verifier’s timer expires before the prover responds,the verifier rejects.Otherwise,the verifier makes a decision based on the prover’s response res and whether i is equal to j:–If i=j and res=1,then matcha accepts.–If i=j and res=0,then matcha rejects.–If i=j and res=1,then matcha rejects.–If i=j and res=0,then matcha plays another round.In the last case,matcha starts over(with a fresh new set of random coins):it flips another fair unbiased coin,picks another pair of images(i,j)depending on the outcome of the coin,etc.Remarks1.It is quite easy to write a computer program that has success probability1/2over matcha by simply answering with res=1.For most applications,a distinguishing probability of1/2is unacceptable.In order for matcha tobe of practical use,the test has to be repeated several times.2.Our description of matcha contains an obvious asymmetry:when i=j,matcha presents the prover with(i,t(i))for i←I,and when i=j matcha presents(i,t(j)),where i is chosen uniformly from the set[I]−{j}.This gives the prover a simple strategy to gain advantage over M:if i seems tocome from I,guess that t(j)is a transformation of i;otherwise guess that it isn’t.The reason for the asymmetry is to make the proof of Lemma1easier to follow.We note that a stronger captcha can be built by choosing i from the distribution I restricted to the set[I]−{j}.3.The intuition for why matcha plays another round when i=j and res=0isthat we are trying to convert high success against matcha into high success in solving P1;a program that solves P1by comparing t(j)to every image in[I]will encounter that most of the images in[I]are different from t(j).4.In the following Lemma we assume that a program with high success overM always terminates with a response in time at mostτ.Any program which does not satisfy this requirement can be rewritten into one which does,by stopping afterτtime and sending the response1,which never decreases the success probability.We also assume that the unit of time that matcha uses is the same as one computational step.Lemma1.Any program that has success greater thanηover M=(I,T,τ)can be used to(δ,τ|[I]|)-solve P1I,T,whereδ≥η2+p1+(1−p1)(1−σB)1+p1,which givesσB≤1−p0and p1≤2(1−σB).Hence:Pr T,I,r [A B r(t(j))=j]≥ns=1Pr T,I,r[A B r(t(j))=j||S|=s]Pr T,I[|S|=s](1)=ns=11−p0E T,I[|S|](3)≥1−p01+2|[I]|(1−σB)(5)(2)follows by the definition of the procedure A B,(3)follows by Jensen’s in-equality and the fact that f(x)=1/x is concave,(4)follows becauseE T,I[|S|]≤1+ i=j Pr I,r(B(i,t(j))=1)and(5)follows by the inequalities for p0,p1andσB given above.This completes the proof.Theorem1.If P1I,T is(δ,τ|[I]|)-hard and M=(I,T,τ)is(α,β)-human executable,then M is a(α,β,(2−|[I]|)δ。

STEGANOGRAPHY WITH TWO JPEGS OF THE SAME SCENE TomášDenemark,Student Member,IEEE,and Jessica Fridrich,Fellow,IEEEBinghamton UniversityDepartment of ECEBinghamton,NYABSTRACTIt is widely recognized that incorporating side-information at the sender can significantly improve steganographic security in practice.Currently,most side-informed schemes for digital images utilize a high quality“precover”image that is subsequently processed and then jointly quantized and embedded with a secret. In this paper,we investigate an alternative form of side-information in the form of two JPEG images of the same scene.The second JPEG image is used to determine the preferred polarity of embedding changes and to modu-late their costs.Tests on real imagery show a very sig-nificant improvement in empirical security with respect to steganography utilizing a single JPEG image.Index Terms—Steganography,side-information, precover,security,steganalysis,JPEG,UNIWARD1.INTRODUCTION Steganography is a private communication tool in which secrets are embedded in cover objects to hide the pres-ence of the message itself.In side-informed steganogra-phy,the sender utilizes information that is unavailable to the steganalyst(and the recipient)to improve secu-rity.For example,the embedding can take place while processing(compressing)a higher quality representation of the cover image called precover[1].The most common example of this type of steganography uses non-rounded DCT coefficients when saving an uncompressed image as JPEG[2,3,4,5,6,7,8].Most consumer-end electronic devices,such as cell phones,tablets,and low-end digital cameras,however, can save images only in the JPEG format and thus do not The work on this paper was partially supported by NSF grant No.1561446and by Air Force Office of Scientific Research under the research grant number FA9950-12-1-0124.The ern-ment is authorized to reproduce and distribute reprints for Gov-ernmental purposes notwithstanding any copyright notation there on.The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies,either expressed or implied of AFOSR or the ernment.give the user access to the uncompressed image.In this case,one can utilize a different type of side-information –multiple JPEG images of the same scene.This re-search direction has not been developed much mostly due to the difficulty of acquiring the required imagery and modeling the differences between acquisitions.The first work on this topic includes[9,10,11]where the au-thors made multiple scans of the same printed image and then modeled the differences between scans and among neighboring pixels.Unfortunately,this requires acquir-ing a potentially large number of scans,which makes this approach rather labor intensive.Moreover,differences in the movement of the scanner head between scans lead to misalignment that complicates using this type of side-information properly.In this paper,we work with multiple images acquired in the JPEG format as we expect quantized DCT coef-ficients to be naturally more robust to small imperfec-tions during acquisition.Since our intention is to design a practical method,we avoid the difficult and poten-tially extremely time consuming task of modeling the differences between acquisitions[9,10,11]and make the approach work well even when mere two images are avail-able to the sender.In particular,we modulate the em-bedding costs of J-UNIWARD[7]based on the preferred direction inferred from two JPEG images of the same scene.The method is tested on real-life multiple expo-sures obtained using a tripod-mounted digital camera. The proposed embedding with two JPEG images is sub-stantially more secure than when only a single JPEG is available to the steganographer.In the next section,we review existing side-informed steganography with a high quality precover.The new steganographic method for embedding with two JPEGs is detailed in Section3.In Section4,we describe and analyze the image source used for experiments in Sec-tion5.The same section contains a comparison with J-UNIWARD and SI-UNIWARD as well as a study of how the security gain due to the second JPEG changes with differences between exposures.The paper is con-cluded in Section6.1020Burst index kM S EFig.1.MSE between z (1)and z (k ),k =2,...,7from each burst averaged over all 9,310bursts from BURST-base.See the main text for notation.2.STEGANOGRAPHY WITH PRECOVER Virtually all modern embedding schemes for JPEG im-ages,whether or not they use side-information,are im-plemented within the paradigm of distortion minimiza-tion.The sender first defines the cost of modifying each cover element (DCT coefficient)and then embeds the payload so that the expected value of the total cost is as small as possible.Syndrome-trellis codes[12]can be used to implement the embedding in practice.For simplicity,we work with 8-bit M ×N grayscale images with M and N multiples of 8.The non-rounded and rounded values of DCT coefficients from (u,v )th8×8block will be denoted c (u,v )ij ∈R and x (u,v )ij ∈{−1023,...,1024},1≤i,j ≤8,1≤u ≤M/8,1≤v ≤N/8,respectively.The cost of changing x (u,v )ij by 1and −1is ρ(u,v )ij (1)and ρ(u,v )ij (−1),respectively.When the symbols x ij ,c ij ,ρij are used without super-scripts,the range of i,j spans the entire M ×N image.The total cost (distortion)of embedding is D (x ,y )= x ij =y ij ρij (y ij −x ij ),where y ij ∈{x ij −1,x ij ,x ij +1}is the stego image.An embedding scheme operating at the rate–distortion bound (with minimal D )would embed a payload of R bits by modifying the DCT coefficients with probabilities:β±ij=P {y ij =x ij ±1}=e −λρij (±1)1+e −λρij (1)+e −λρij (−1),(1)where λis determined from the payload constraint R = ij h 3(β+ij ,β−ij ),with h 3(x,y )=−x log 2x −y log 2y −(1−x −y )log 2(1−x −y )the ternary entropy func-tion.One of the most secure schemes for JPEG im-ages called J-UNIWARD [7]computes the costs from the decompressed JPEG image.The costs are symmetric ρij (1)=ρij (−1)for all i,j .While it is currently an open problem how to use side-information (c ij )in an optimal fashion for embed-ding [13],numerous heuristic schemes have been pro-0.20.40.6Quality factor QM o d u l a t i o n m (Q )Fig.2.Modulation factor m (Q )as a function of the JPEG quality factor Q for images from BURSTbase.posed in the past [3,5,6,7,8,4].In a nut shell,these schemes use the rounding error e ij =c ij −x ij ,−1/2≤e ij ≤1/2,to modulate the embedding costs ρij by 1−2|e ij |∈[0,1].In SI-UNIWARD [7],for example,the costs are:ρij (sign(e ij ))=(1−2|e ij |)ρ(J)ij (2)ρij (−sign(e ij ))=C wet ,(3)where ρ(J)ij are J-UNIWARD costs and C wet is some large number (“wet cost”).In [8],a ternary version of SI-UNIWARD was studied where the authors argued that,as the rounding error e ij becomes small,the embed-ding rule should be allowed to change the coefficient both ways.This ternary version of SI-UNIWARD usesρij (−sign(e ij ))=ρ(J)ij instead of (3).3.STEGANOGRAPHY WITH TWO JPEGS Let us consider a situation when the sender acquires twoJPEG images of the same scene,x (1)ij and x (2)ij ,while pro-nouncing,e.g.,the first image as cover JPEG and consid-ering x (2)ij as side-information.The value x (2)ij can only be useful to the sender when x (2)ij =x (1)ij ,which happens increasingly more often with smaller quantization steps (larger JPEG quality).This type of side-information isdifferent from the non-rounded values c (1)ij .In particu-lar,it informs the sender more about the direction along which the costs should be modulated and less about themagnitude of the rounding error e (1)ij =c (1)ij −x (1)ij .The proposed embedding scheme,which we call J2-UNIWARD,uses J-UNIWARD costs [7]when x (1)ij =x (2)ij and modulated costs otherwise:ρij (sign(x (2)ij −x (1)ij ))= ρ(J)ij if x (1)ij =x (2)ij m (Q )ρ(J)ij if x (1)ij =x (2)ij ,(4)with the modulation factors m (Q )∈[0,1]to be de-termined experimentally for each JPEG quality factor 1≤Q ≤100.0.10.20.30.40.5Quality factor QD e t e c t i o n e r r o r P E0.10.20.30.40.5Quality factor QD e t e c t i o n e r r o r P EFig.3.Empirical security of J2-UNIWARD as a function of the JPEG quality factor Q with the merger of GFR,SRM,and ccJRM features.Left:Comparison with previous art for R =0.2bpnzac.Right:P E for R ∈{0.1,0.2,0.3,0.4,0.5}bpnzac,embedding simulated at rate–distortion bound.4.THE BURSTBASE DATASETIt is generally difficult to acquire two images of the ex-act same scene because the camera position may slightly change between the exposures even when mounted on a tripod due to vibrations caused by the shutter.Another potential source of differences is slightly varying exposure time and changing light conditions between exposures.To eliminate possible impact of flicker of artificial lights,all images were acquired in daylight,both indoor and outdoor,and without a flash.Canon 6D,a DSLR camera with a full-frame 20MP CMOS sensor,set to a fixed ISO of 200was used in a burst mode.The shutter was operated using a cable release with a two-second self-timer to further minimize vibrations due to operating the camera.To prevent the camera from changing the set-tings during the burst,it was used in manual mode.All images were acquired in the RAW CR2format and then exported from Lightroom 5.7to 24-bit TIFF format with no other processing applied.A total of 133bursts were acquired,each containing 7images.To increase the number of images for experi-ments,the 5472×3648TIFF images were cropped into 10×7equidistantly positioned tiles with 512×512pixels.This required a slight overlap between neighboring tiles (7pixels horizontally and 35pixels vertically).These 70×133=9,310smaller images were then converted to grayscale in Matlab using ’rgb2gray ’and saved in a lossless raster format to facilitate experiments with a range of JPEG quality factors.We call this database of 7×9,310uncompressed grayscale images ’BURST-base’.The images were further JPEG compressed with different quality factors for all experiments in this paper.For each pair of different images from each burst,we computed the mean square error (MSE)between them and then selected the pair with the smallest MSE,ran-domly denoting one as z (1)ij and the other z (2)ij .The re-maining five images from the burst were denoted z (k )ij ,k =3,...,7,so that the MSE between z (1)ij and z (k )ij forms a non-decreasing sequence in k .Next,we ana-lyzed images from BURSTbase sorted in this manner to determine how much the differences between the imagesare due to acquisition noise.The MSE between z (1)ij and z (k )ij ,k =2,...,7,averaged over the BURSTbase is plot-ted in Figure 1.For the closest pair,MSE(z (1),z (2))≈5,which would correspond to σ2a =5if the differences weresolely due to AWG noise with variance σ2a .This closely matches the variance estimated from a single image of content-less scenes,such as blue sky.This reasoning in-dicates that z (2)and z (3)are on average reasonably well aligned with z (1)while z (k ),k ≥4,are affected by small spatial shifts.5.EXPERIMENTSIn this section,the security of J2-UNIWARD is studied across a range of quality factors and payloads and con-trasted with the same scheme utilizing a single JPEG im-age and a scheme utilizing a single high-quality precover.We also investigate the security boost of the second ex-posure with increased differences between exposures.The modulation factor m (Q )(4)was determined for each quality factor Q to minimize P E =min P F A (P MD +P F A )/2,the minimal total probability of error on the training set,where P MD ,P F A are missed-detection and false-alarm rates of a detector implemented using the0.20.4Quality factor QP EFig.4.Security of J2-UNIWARD when k th closest image from each burst is used as side-information,0.4bpnzac.ensemble classifier [14]with GFR (Gabor Filter Resid-ual)features [15]when splitting BURSTbase into equally sized training and testing set.The GFR features were selected because they are known to be highly effec-tive against modern JPEG steganography,including J-UNIWARD and SI-UNIWARD.The optimal modulation factor determined experimentally and shown in Figure 2can be well approximated by a ramp function:m (Q )=max {0.075,0.02167×Q −1.55}.(5)The ramp function can be justified when adopting a generalized Gaussian model of precover JPEG DCT co-efficients and an AWG model of the acquisition noise.This argument is omitted here due to space limitations and will appear in the journal version of this paper [16].The largest observed loss in P E due to replacing optimal values of m (Q )with the ramp function was about 0.01.Because the feedback from detection with GFR fea-tures was used to design the embedding scheme,all detectors in this section were implemented with a diverse feature set that is a merger of the spatial rich model (SRM)[17],Cartesian-calibrate JPEG Rich Model (ccJRM)[18],and GFR to make sure the em-bedding does not have a fatal weakness with respect to older features.Figure 3left shows P E averaged over ten splits of BURSTbase into training and testing sets (denoted P E )as a function of the JPEG quality fac-tor for payload 0.2bpnzac together with the results forJ-UNIWARD (with x (1)k as covers)and SI-UNIWARD(with c (1)k as side-information).The side-information in the form of two JPEG images significantly increases em-pirical security w.r.t.embedding with a single JPEG (J-UNIWARD)especially for large payloads and small qual-ity factors.The empirical security is however not bet-ter than when non-rounded DCT coefficients are used as side-information (SI-UNIWARD).Figure 3right shows the detection error as a function of the quality factor for five payloads.Since the statistical spread of P E over the splits ranged between 0.0010−0.0075,we do not show the error bars in the figure as it would be hard to discern them visually.To assess how sensitive J2-UNIWARD is w.r.t.smalldifferences between exposures,we implemented thescheme with x (1)ij as cover and x (k )ij ,k =3,...,7as side-information,essentially using the second closest (k =3),the third closest (k =4),etc.,image instead of the clos-est image.As apparent from Figure 1,with increasing k ,the boost should start decreasing.Figure 4shows P E as a function of the quality factor across k =2,...,7to-gether with the value of J-UNIWARD (JUNI).While the gain of the second image indeed decreases with increased MSE,this decrease is gradual and rather small for higher quality factors.This experiment proves that the sec-ond exposure provides useful side-information even when small spatial shifts are present opening thus the possibil-ity to improve steganography even when the multiple exposures are acquired with a hand-held camera rather than mounted on a tripod.This possibility is left as part of future research.6.CONCLUSIONSWe study steganography with side-information at the sender in the form of a second JPEG image of the same scene that is used to infer the preferred direction of steganographic embedding changes.This information is incorporated into the embedding algorithm by decreas-ing (modulating)the embedding costs of such preferred changes.Experiments with real multiple acquisitions show a quite significant increase in empirical security of with respect to steganography with a single cover image (J-UNIWARD).The boost in empirical security appears fairly insensitive to small differences between the two ac-quisitions,which makes the proposed method practical and opens up the possibility to use multiple exposures obtained using a hand-held camera or acquiring multiple exposures from short video clips.Further improvement is likely possible by optimizing the embedding cost modulation for each DCT mode,quantization step,and the average grayscale of the DCT block because the acquisition noise amplitude depends on luminance.Finally,we plan to study how to utilize more than two (quantized and unquantized)acquisitions.7.REFERENCES[1]A.D.Ker,“A fusion of maximal likelihood andstructural steganalysis,”in Information Hiding, 9th International Workshop,T.Furon, F.Cayre,G.Doërr,and P.Bas,Eds.,Saint Malo,France,June11–13,2007,vol.4567of LNCS,pp.204–219, Springer-Verlag,Berlin.[2]J.Fridrich,M.Goljan,and D.Soukal,“Perturbedquantization steganography using wet paper codes,”in Proceedings of the6th ACM Multimedia&Secu-rity Workshop,J.Dittmann and J.Fridrich,Eds., Magdeburg,Germany,September20–21,2004,pp.4–15.[3]Y.Kim,Z.Duric,and D.Richards,“Modifiedmatrix encoding technique for minimal distortion steganography,”in Information Hiding,8th Inter-national Workshop,J.L.Camenisch,C.S.Collberg, N.F.Johnson,and P.Sallee,Eds.,Alexandria,VA, July10–12,2006,vol.4437of LNCS,pp.314–327, Springer-Verlag,New York.[4]V.Sachnev,H.J.Kim,and R.Zhang,“Lessdetectable JPEG steganography method based on heuristic optimization and BCH syndrome cod-ing,”in Proceedings of the11th ACM Multimedia &Security Workshop,J.Dittmann,S.Craver,and J.Fridrich,Eds.,Princeton,NJ,September7–8, 2009,pp.131–140.[5]F.Huang,J.Huang,and Y.-Q.Shi,“New chan-nel selection rule for JPEG steganography,”IEEE Transactions on Information Forensics and Secu-rity,vol.7,no.4,pp.1181–1191,August2012. [6]L.Guo,J.Ni,and Y.Q.Shi,“Uniform embeddingfor efficient JPEG steganography,”IEEE Transac-tions on Information Forensics and Security,vol.9, no.5,pp.814–825,May2014.[7]V.Holub,J.Fridrich,and T.Denemark,“Universaldistortion design for steganography in an arbitrary domain,”EURASIP Journal on Information Secu-rity,Special Issue on Revised Selected Papers of the 1st ACM IH and MMS Workshop,vol.2014:1,2014.[8]T.Denemark and J.Fridrich,“Side-informedsteganography with additive distortion,”in IEEE International Workshop on Information Forensics and Security,Rome,Italy,November16–192015.[9]E.Franz,“Steganography preserving statisticalproperties,”in Information Hiding,5th Interna-tional Workshop,F.A.P.Petitcolas,Ed.,Noordwi-jkerhout,The Netherlands,October7–9,2002,vol.2578of LNCS,pp.278–294,Springer-Verlag,New York.[10]E.Franz and A.Schneidewind,“Pre-processing foradding noise steganography,”in Information Hid-ing,7th International Workshop,M.Barni,J.Her-rera,S.Katzenbeisser,and F.Pérez-González,Eds., Barcelona,Spain,June6–8,2005,vol.3727of LNCS,pp.189–203,Springer-Verlag,Berlin. [11]E.Franz,“Embedding considering dependenciesbetween pixels,”in Proceedings SPIE,Electronic Imaging,Security,Forensics,Steganography,and Watermarking of Multimedia Contents X, E.J.Delp,P.W.Wong,J.Dittmann,and N.D.Memon, Eds.,San Jose,CA,January27–31,2008,vol.6819, pp.D1–12.[12]T.Filler,J.Judas,and J.Fridrich,“Minimizing ad-ditive distortion in steganography using syndrome-trellis codes,”IEEE Transactions on Information Forensics and Security,vol.6,no.3,pp.920–935, September2011.[13]J.Fridrich,“On the role of side-information insteganography in empirical covers,”in Proceed-ings SPIE,Electronic Imaging,Media Watermark-ing,Security,and Forensics2013,A.Alattar,N.D.Memon,and C.Heitzenrater,Eds.,San Francisco, CA,February5–7,2013,vol.8665,pp.0I1–11. [14]J.Kodovský,J.Fridrich,and V.Holub,“Ensembleclassifiers for steganalysis of digital media,”IEEE Transactions on Information Forensics and Secu-rity,vol.7,no.2,pp.432–444,April2012.[15]X.Song,F.Liu,C.Yang,X.Luo,and Y.Zhang,“Steganalysis of adaptive JPEG steganography us-ing2D Gaborfilters,”in3rd ACM IH&MMSec.Workshop,esana,J.Fridrich,and A.Alat-tar,Eds.,Portland,Oregon,June17–19,2015. [16]T.Denemark and J.Fridrich,“Steganography withmultiple JPEG images of the same scene,”IEEE Transactions on Information Forensics and Secu-rity,2016,in preparation.[17]J.Fridrich and J.Kodovský,“Rich models for ste-ganalysis of digital images,”IEEE Transactions on Information Forensics and Security,vol.7,no.3, pp.868–882,June2011.[18]J.Kodovskýand J.Fridrich,“Steganalysis of JPEGimages using rich models,”in Proceedings SPIE, Electronic Imaging,Media Watermarking,Security, and Forensics2012,A.Alattar,N.D.Memon,andE.J.Delp,Eds.,San Francisco,CA,January23–26,2012,vol.8303,pp.0A1–13.。

论弗罗斯特《摘苹果之后》中的死亡隐喻发布时间：2022-07-21T08:53:03.876Z 来源：《时代教育》2022年5期作者：刘沛婷[导读] 乔治·莱考夫和马克?约翰逊于《我们赖以生存的隐喻》一书中指出隐喻不仅仅是一种修辞手法，更是一种思维方式刘沛婷湖南师范大学，湖南长沙 410006摘要：乔治·莱考夫和马克?约翰逊于《我们赖以生存的隐喻》一书中指出隐喻不仅仅是一种修辞手法，更是一种思维方式，在人们的日常语言和活动中无所不在。

诗歌是高度隐喻化的体裁，本文就将以弗罗斯特的短诗——《摘苹果之后》为例，通过挖掘诗歌中的结构隐喻、方位隐喻和本体隐喻，深刻剖析弗罗斯特的死亡观建构，为该诗的解读提供新的维度，也有助于丰富该理论的应用范畴。

关键词:《摘苹果之后》；结构隐喻；方位隐喻；本体隐喻；死亡On death metaphors in Frost’s “After Apple-Picking”Peiting LiuHunan Normal University, Hunan Changsha 410006Abstract: George Lakoff and Mark Johnson put forward in their book Metaphors We Live By that metaphor is not only a figure of speech but a way of thinking, pervasive in everyday language and action. Since poetry is highly metaphorical, this thesis is to explore how Robert Lee Frost construct his insight of death through structural metaphors, orientational metaphors as well as ontological metaphors in his short poem “After Apple-Picking”, with the hope to provide a new dimension for the interpretation of the poem and to expand the application scope of the theory. Key words: “After Apple-Picking”; structural metaphors; orientational metaphors; ontological metaphors; death 1.IntroductionLakoff and Johnson in their monograph Metaphors We Live Вy, point out that metaphor not only can be understood from the figurative perspective, but is the thinking way.[1] Ungerer and Schmid hold that conceptual metaphor, as a cognitive instrument, is not just a stylistically dramatic way of expressing thoughts by means of literary language, but a way of thinking.[2] K?vecses has put that conceptual metaphor is defined as understanding one conceptual domain in terms of another conceptual domain.[3] On the basis of the cognitive approach to the understanding of conceptual metaphor, it can be divided into structural metaphor, orientational metaphor and ontological metaphor. The development of conceptual metaphor theory has brought advance to Linguistics, Anthology, Literature and so on.Robert Lee Frost commands an important place in any list of outstanding poets in the twentieth century. His poem “After Apple-picking” is written in the first person. The speaker is an orchard worker who has picked apples long and hard but is now on the verge of being overwhelmed by fatigue and the depth of the experience. On the edge of falling sleep, he remembers not only the ripe apples successfully picked but also those that fell and were considered damaged and had to be sent to the cider mill. He knows that his sleep will be troubled by the failures more than by the successes. He is not sure about the nature of the sleep he is about to drop into—whether it will be ordinary sleep, more like a hibernation, or more like death.The entire poem is a kind of extended metaphor, in which the activity of harvesting apples represents people’ life and the speaker’s falling asleep suggests human death.As a classical literary work, the study of this poem mostly focuses on its rhythm and writing devices. The analysis of multiple themes and symbols has always been the research hotspot of literature works. Li Yingxue discussed the fuzziness of the meaning of poetry from the perspective of deconstruction, and there are many scholars who explore metaphors in Frost’s other poems.[4] Few people applied it to analyze “After Apple-Picking”. Therefore, this paper is to discuss how Frost structures his thoughts on death metaphorically by describing a laborer’s picking apples. The first three chapters of this thesis illustrate Frost’s views of death through the construction of structural metaphors, orientational metaphors and ontological metaphors in “After Apple-Picking” respectively. At last it is followed by a logical conclusion of this thesis.2.Structural MetaphorsIn structural metaphor, one greatly structured and explicitly delineated concept is applied to structure another. As Lakoff and Johnson point out that one domain of conceptual metaphor is metaphorically structured in light of another. Structural metaphor allows its source domain to offer a comparatively rich knowledge structure for the target domain, that is to say, the cognitive function of structural metaphor is to enable audiences to understand the target domain by the structure of the source domain. The poem “After Apple-Picking” include two key conceptual metaphors: DEATH IS SLEEP and PEOPLE ARE PLANTS.2.1 DEATH IS SLEEPFrost chooses a laborer who is overtired with apple-picking and falls asleep to reflect his insight of death. Hence the poem can be understood as a mapping from a source domain (sleep) to a target domain (death). The mapping is tightly structured. There are ontological correspondences. The dead correspond to those who have a sound sleep. The retrospection before death corresponds to the unconscious state near sleep. The darkness corresponds to the night. The cease of life corresponds to the stillness and motionlessness of sleep. As Lakoff puts it, “people use a concrete source domain to describe an abstract target domain.”[5] Death is an abstract concept, which can be understood vividly through the concept of sleep. The word “sleep”has been repeated five times. “Winter sleep” suggests the emotion of being decayed, forlorn and silent triggered by death because winter, in the metaphoric meanings, has strong associations with death.[6] Another euphemistic expression of death is “long sleep”, which is indicative of its permanence. “Human sleep” is the most evident reflection of conceptualization of death as sleep, showing that human death is what Frost has discussed. In the light of sleep, Frost’s “After Apple-Picking” is no longer a lyrical poem of a worker’s experience on the orchard farm and fatigue aftera day’s labor, but a profound thought on life and death through an extended conceptual metaphor of death as sleep.2.2 PEOPLE ARE PLANTSBoth man and tree are living beings that go through birth and wither, and the achievements of man are kin to the fruits of plants. “Apples I didn’t pick upon some bough” correspond to those unfilled dreams while apples that “struck the earth/ No matter if not bruised or spilled with stubble”correspond to people’s failed pursuits. The scent of apples refers to delight and satisfaction brought by success. In Frost’s poem, the act of apple-picking is a metaphor for the fruits the speaker has achieved in life.[7] It is universally acknowledged that success is what people desire and is something enjoyable. However, the speaker is overtired of the great harvest and wished to rest, which illustrates that the speaker has been bored with worldly sense of accomplishment and hopes to simple have a dream and a “long sleep”. Due to the sweet smell of the apple, the narrator actually falls asleep after fatigue and he enters into “long sleep”(death) with a sense of emptiness resulted from the excessive fruits he has gathered. The speaker’s experience reveals the poet’s meditation on life that it is futile people achieve a great deal of success but eventually own nothing after death. Therefore, the poet don’t ponder on human sleep for no reason but he penetrates the meaninglessness of long tough life struggles.The two root metaphors are carefully chosen to reflect Frost’s philosophy on death. This also confirms the cognitive value of metaphor, that is, vehicles(such as sleep) are usually well known to readers, and their features and structures will be mapped to relatively unfamiliar things when they interact with tenor (such as death) to help readers understand the characteristics and structures of ontology. The characteristics of sleep are mapped to the characteristics of death. Frost’ poem “After Apple-Picking” is not only a pastoral work of rural world in orchard farm but also a thought-provoking poem on death. The end of labor leaves the speaker with a sense of completion and fulfillment yet finds him blocked from success by winter’s approach and physical weariness. The futility that what people achieved as a result resembles fallen apples of no worth leads to fatigue and wish to seek relief in sleep, that is death. Therefore, this seemingly idyllic poem is in fact the ultimate exploration of human destiny through the metaphors of death as sleep and people as plants.3.Orientational MetaphorsOrientational metaphors do not structure one concept in terms of another but instead organize a whole system of concepts with respect to one another.[1] Most of them have to do with spatial orientation: up-down, in-out, front-back, on-off, deep-shallow, central-peripheral. These spatial orientations arise from the fact that we have bodies of the sort we have and that they function as they do in our physical environment. As Lakoff points out that CONSCIOUS IS UP; UNCONSCIOUS IS DOWN. HEALTH SND LIFE ARE UP; SICKNESS AND DEATH ARE DOWN. This poem employs spatial antagonism to construct death metaphor. “The Apple-Picking” involves a development from consciousness to unconsciousness. At the very beginning, the farmer is sober enough on the long two-pointed ladder sticking toward heaven. The spacial position is rather high. After the speaker has been done with apple-picking, rest is badly needed after the arduous labour. He is drowsed off and no longer in his conscious state. Frost adopts simple past tense from line8 to line17, serving as a beginning of the speaker’s dream. In the half unconsciousness of the farmer, the autumn evening bursting with the aroma of the apples has for a moment changed into a winter morning with hoary glass. In farmer’s dream, things “melted”, “fall and break”, which suggests a downward trend. Finally both woodchuck and the farmer fall asleep on the ground. The perspective of the whole poem shifts from heaven to earth, that is from top to bottom, revealing the opposition of space. A pane of glass divides the world into two parts: reality and dream. The transition from reality to dream is the manifestation of change of the speaker’s consciousness. The higher position represents reality and consciousness while the lower dream and unconsciousnessWhat’s more, the positional contrast reveals the opposition of life and death. In the first line of “After Apple-Picking”, the ladder occupies a central position in the whole picture of the poem, acting as a bridge between heaven and earth, life and death. The imagery of heaven and apples evokes the garden of Eden. The act of ascending the ladder symbolized a re-approach to heaven and eternal life while the movement down the ladder symbolizes the descent from heaven to earth, also from life to death[4]. According to Bible, picking apples is considered as corruption and degradation. As baskets of apples fall down and are spiked, they become worthless. This is true of human beings. After the farmer has finished apple-picking, fatigue and emptiness has wrapped him. His vigorous life reaches a pause, which actually means the farmer’s death. Most of fundamental concepts are organized in terms of one or more spatialization metaphors. In Frost’s “After Apple-Picking”, the poet shows the transition from consciousness to unconsciousness as well as from life to death in virtue of the binary opposition of space. The physical basis of such division is that humans sleep and die lying down and stand up when they are awaken. Therefore, the antagonism of life and death is constructed through the opposition of up and down positions, which contributes to the further construction of the root metaphors.4.Ontological MetaphorsOntological metaphor helps us understand those abstract entities through conceptualizing them as these entities and substances which are related to human’s experience. As Lakoff and Johnson point out: “our experience of physical objects and substances provides a further basis for understanding.” Ontological metaphor could be classified into three types, which are entity and substance metaphor, container metaphor and personification.Firstly, an invisible abstract concept, in entity and substance metaphor, is considered as a visible concrete object. Human being expresses abstract concepts as these entities and substances which are related to human’s experience. Death is an abstract concept, which can be understood thanks to another common concept—sleep. The dark and bleak state of death is implied by night in winter. The poet also tries to clarify the hibernation of hamsters and the long sleep of human beings: one is short seasonal rest and the other is an eternal stop of motion. In this way, the characteristics of death are no longer vague. The first root metaphor of death as sleep receives deeper and more detailed illustrations. Similarly, human achievements becomes a measurable entity like apples in “ After Apple-Picking”. Through these well-known common things, the original abstract concept can be elucidated. The essence of metaphor lies in the comparison between two entities.Secondly, container metaphor is a kind of ontological metaphor in which an invisible abstract concept is regarded as a container which has a surface owning scope and range with an in-out orientation. In Frost’s poem, the farmer’s dream and sleep is a container, where he can see “magnified apples”, feel “the pressure of ladder-round”. The farmer’s falling into dreams shows the motion from one space to another space. The state of farmer can be classified into “in sleep” and “out of sleep”, which symbolize death and life respectively.Lastly, personification specifies the physical object as being a man, which can make people to comprehend these different physical objects in light of human characteristics, motivations and activities. In Frost’s poem, apple “struck the earth” and long sleep can “come on” are all personification. They are extensions of ontological metaphors and that they allow us to make sense of phenomena in the world on the basis of our own goals. It is carefully chosen to endow this poem a dynamic effect so that the theme of this poem can be effectively conveyed. All in all, the understanding of a poetic metaphor is a cognitive process.[8] Ontological metaphor makes us understand abstract concepts by use of concrete concepts. The poet uses sleep to explain death, making the abstract concept simplified and concrete. In the poem, the dream not only reflects the structural metaphor, but also reflects the container metaphor. It forms a contrast between “in dream” and “out of dream” so as to further strengthen the difference between life and death. Apple has bruises, and Death actively does come in. These anthropomorphic expressions embody the metaphorical nature of language and the symbolic nature of death. As a result, metaphor of death in this poem has been justified.5.ConclusionThe exploration of the relationship between Frost’s view of death and Lakoff’s cognitive metaphors will undoubtedly help readers to guard against deceptive surface meanings when interpreting and appreciating Frost’s poems, and to explore the profound life philosophy reflected in his poems through metaphorical thinking and active participation.Through dividing metaphors in Frost’s “After Apple-Picking” according to Lakoff’s classification, the way of constructing poem’s theme is evidently revealed. At the first glance, it seems to be a lyrical poem, but it actually a poem of death after further analysis. Frost implicitly depicts life actions as apple picking activities, apples are symbols of human achievements, and death is similar to long sleep, which are structural metaphors, through which the characteristics of abstract concept death can be easily understood. Moreover, the orientational metaphors constitute to the body of this poem. The up-down spatial position divides the farmer’s state into consciousness and unconsciousness, also a reflection of human’s state of life and death. The contrast between in-out categories reflects the whole poem’s structure: it shifts from reality to dream. Since the farmer’s dream is explained as a container, the state of dreaming metaphorically stands for death. Therefore the whole poem is based on structural metaphors of death is sleep and people are plants, which are illustrated with orientational metaphors and ontological metaphors.However, the thesis still has some limitations due to the author’s slim analysis. It can be better with more logical illustrations and evidences. But it is no doubt that the thesis provides a new perspective of discussing Frost’s poem. It expands the application scope of Lakoff’s conceptual metaphor and enriches its practice, and produces referential meaning to literature appreciation. References[1]Lakoff, G & M. Johnson. Metaphors We Live By[M]. Chicago: The University of Chicago Press.1980.[2]Ungerer, F & H. J. Schmid. An Introduction to Cognitive Linguistics.[M]. Beijing: Foreign Language Teaching and Research Press. 2008.[3]K?vecses, Z. Metaphor: A practical introduction[M]. New York: Oxford University Press.2002.[4]李应雪. 一个解构批评的范本——析罗伯特·弗洛斯特诗歌《摘苹果之后》意义的模糊性[J]. 宁夏大学学报(人文社会科学版), 2007(04): 78-81.[5]Lakoff, G. The Invariance Hypothesis: is abstract reason based on image-schemas?[J]. Cognitive Linguistics, 1990(01): 39-47.[6]Huo, Lirong. Comments on “After Apple-Picking”[J]. Overseas English, 2012(01): 196-197.[7]赵志宇. 罗伯特·弗洛斯特的《摘罢苹果》[J]. 文学语言学研究, 2007(02):70-71.[8]胡壮麟. 诗性隐喻[J]. 山东外语教学, 2001(03): 3-8.。

A Secure Data Hiding Scheme for Two-Color ImagesYu-Yuan Chen,Hsiang-Kuang Pan,and Yu-Chee TsengDepartment of Computer Science and Information EngineeringNational Central UniversityChung-Li,32054,TaiwanEmail:yctseng@.tw(corresponding author)AbstractIn this paper,we propose a new steganography scheme forhiding a piece of critical information in a host binary image(such as facsimiles).A secret key and a weight matrix are usedto protect the hidden data.Given an image block of size,our scheme can hide as many as bits of datain the image by changing at most2bits in the image.Thisscheme,as compared to an existing scheme[18],can providehigher security,embed more data,and maintain higher qualityof the host image.1IntroductionAs digital media are getting wider popularity,theirsecurity-related issues are becoming a greater concern.Onecentral issue is confidentiality,which is typically achieved byencryption.However,as an encrypted message usuallyflagsthe importance of the message,it also attracts cryptanalysts’interests.The sometimes confusing terminology stagenogra-phy has a differentflavor from encryption;its purpose is toembed a piece of critical information in a non-critical hostmessage(e.g.,webpages,advertisements,etc.)to distractopponents’attention[7,12].One less confusing name forsteganography would be data hiding.It should be understoodthat steganography is orthogonal to encryption,and it may becombined with encryption to achieve a higher level of security.The study of this subject may be traced to[9],where thePrisoners’Problem was proposed.In this scenario,Alice andBob are in jail,and wish to hatch an escape plan.All theircommunications must go through the warden,Willie,and ifWillie detects any encrypted messages,he will frustrate theirplan by throwing them into solitary confinement.So theymustfind some way to hide their plaintext(or ciphertext)inan innocuous-looking covertext.The history and bandwidthconcerns of the subliminarl channel are discussed in[11,10].A nice clarification on steganography is in[2].Data hiding is usually achieved by alternating somenonessential information in the host message.Given a colorimage,one simple approach is to use the least-significant bitsented in Section3.Analysis and experimental results are in Section4.Section5draws our conclusions.2Reviews and MotivationsBelow,we review the data hiding scheme proposed by[18], through which we will identify problems and motivate our work.Wefirst define some notations.We treat a bitmap as an integer matrix,and thus the terms“bitmap”and“matrix”will be used interchangeably.Given two bitmaps andof the same size,we denote by the bitwise AND of these two bitmaps.Similarly,we denote by the bit-wise exclusive-OR of and.Given an integer matrix, we denote by the element of at row and column, and by the sum of all elements in.The data hiding scheme of[18]works as follows.We are given a host binary image,a secret key,and some critical data bits to be embedded in.The secret key is a bitmap of size.For simplicity,it is assumed that the size of is a multiple of.In the embedding is achieved by modifying some bits of.S1.Partition into blocks,each of size.S2.For each block obtained in step S1,check whether the condition“”holds true.If so,go to step S3to embed one data bit in;otherwise,no data will be embedded in and will be kept intact.S3.Let the bit to be embedded in be.Then do the fol-lowing to modify:if()thenKeep intact;else if()thenRandomly pick a bit such thatand change to1;else if()thenRandomly pick a bit such thatand change to0;elseRandomly pick a bit such thatand complement;end if;In summary,the above scheme tries to embed as many as one data bit in each block.A block can hide one data bit if(the reason will become clear later).Suppose is changed to.The scheme maintains the following invariant:I1.It is not hard to verify that step S3guarantees this invariant. Thus,when the receiverfinds thatFig.1.An example of hiding3bits in abitmap.,he/she can derive the embedded data bit by com-puting.As an opponent does not know the secret key,the embedded data is secure.At most one bit in will be modified if some data is embedded.So the outlook of will not be changed significantly if block size is large enough.Consider the example in Fig.1,where is a bitmap and is a bitmap.First,is partitioned into four blocks and.Since, no data is embedded in.Since,one data bit can be embedded.As thefirst bit to be embedded is 0,is changed to to preserve the above invariant(the changed bit is marked by gray).For,sincebut the next embedded bit is1,is kept intact. Similarly,is modified to hide a data bit of1.Below,we discuss some properties and weaknesses of this scheme.First,since the binary AND operator is used to com-pute,the maximal value of can not exceed.Second,by the nature of binary AND,if a block has to be modified,it must occur in the locations in which the secret has a value of1.Thus,when a completely blank is transmitted(or a large part of is so),an opponent can easily notice the modified locations and thus derive the secret key.This is why the scheme excludes out the possi-bility of using an such that to hide data. For a similar reason,the case ofis excluded out from embedding data to prevent the attack of being completely black or a large part of being so(for instance,when is completely black,any modification on its bit will imply that the corresponding bit in is1).However, even with these constraints,the value of may still be com-promised.A pixel location that has ever been changed must imply a1in corresponding location in;a pixel location that is never changed may imply a0in the corresponding location in.Also,must be chosen with a lot of care.A with too few1’s will suffer from low data hiding rate and may be easily compromised.A with too many1’s will suffer from a brute-force attack.Similarly,the host bitmap should be chosen with care.An with too many0’s is not a good host image because the data hiding rate may be low.3A Secure Data Hiding Scheme for2-Color ImagesIn this section,we propose a new data hiding scheme that can greatly improve over[18].The basic ideas are:(i)to useFig.2.Block diagram of the proposed data hid-ing scheme.a different binary operator XOR to protect the secret key from being compromised,and(ii)to use a weight matrix to increase the data hiding rate while maintaining high quality of the host image.The block diagram of our scheme is depicted in Fig.2.The inputs to our scheme are::a host bitmap,which is to be modified to embed data.(We will partition into blocks of size.For simplicity,we assume that the size of is a multiple of .):a secret key shared by the sender and the receiver.It is a randomly selected bitmap of size.:a secret weight matrix shared by the sender and the receiver.It is an integer matrix of size whose content satisfies some requirements(to be stated later).:the number of bits to be embedded in each block of.The value of satisfies.:some critical information consisting of bits to be embedded in,where is the number of blocks in.3.1Weight ManagementOur scheme heavily relies on the weight matrix to rep-resent the embedded data.This section shows how this works through an example.The complete scheme will be presented in the next section.Suppose the size of and is.Below,we consider a block of the host image.We will show how to embed bits of data in.Let’s assume the following inputs:First,we will perform a bitwise exclusive-OR on and:Next,let be the pairwise multiplication operator on two equal-size integer matrices.We compute:Summing all elements in above result,we have.Next,we will embed two data bits,say,into.Sup-pose that is changed to.Regarding as a binary number,our scheme will ensure the following invariant:I2.,With this invariant,the receiver can derive by computing.Note that there are two ma-jor differences when comparing I2to I1.First,the modular equation is generalized for embedding two bits.Second,there is a precondition on the value of in I1,whereas there is no such a precondition in I2,implying that any block can carry two bits of hidden data.Next,we show how to modify to ensure I2.We intend to change as few bits in as possible.Since,if fortunately,then there is no need to modify.Otherwise,some bit(s)has to be modified.Ob-serve that if we complement bit,then will be complemented.If is swapped from0to1,then the modular sum will be increased by;otherwise,the sum will be decreased by.For instances,if we swap, the sum will be decreased by,and if we swap, the sum will be increased by.It is not hard to verify that we need to complement only one bit in to increase or decrease the sum by1,2,or3in this example.3.2The Hiding StepsDefinition1An matrix can serve as a weight matrix if each element of appears at least once in ,i.e.,.The rationale of this definition will become clear later. Note that it is trivialfind a legal because at the very be-ginning we have imposed that.Also,there are many choices for.We canfirst pick elements in and assign to them.The remainingelements can be assigned randomly.Thus,the number of choices for is:For instance,if and,there arepossible’s.This number should be large enough to forbid a brute-force attack.Let be a legal weight matrix and be a block of. Below,we show how to embed bits of data,say, into by changing at most2bits in.Our goal is to modify into to ensure the following invariant:I3:.Below,we derive the embedding scheme in4steps.pute.pute.S3.From the matrix,compute for eachthe following set:Intuitively,is the set containing every matrix indexsuch that if we complement,we can increase the sum in step S2by.There are actually two possibilities to achieve this:(i)if and,then complementing will increase the weight by,and(ii) if and,then complement-ing will decrease the weight by,or equivalently increase the sum by(under).The following lemmas reveal some important properties of these sets.Lemma1For each such that,the following statement is true:Proof.Suppose that.By Definition1,there is at least one element.It must be that;otherwise,complementing will increase the sum by ,making nonempty.If we complement,the sum will be decreased by,or equivalently increased by.So,the set is nonempty.Note that this is with the exception that,in which case.Lemma2The set.Proof.By Definition1,there is at least one element .Since,no matteris0or1,if we complement,the sum will be increased/decreased by,hence proving this lemma.S4.Define a weight differenceWe have to increase the sum in step S2by to satisfy I3.If,there is no need to change.Otherwise, we run the following program to transform to.For ease of presentation,let’s define for any.a)Randomly pick an such thatand.b)Randomly pick a and complement thebit;c)Randomly pick a and comple-ment the bit;Intuitively,to increase the sum by,we can pick two nonempty sets and.Since these sets indicate thelocations where we can complement to increase the weightby and,respectively.The overall effect is an increase of the weight by.However,there are logicalflawsin the above program,which we left intentionally for ease of presentation.First,the set(and similarly,,, etc.)is not yet defined.Like other’s,we can regardas the set of indices such that complementing these locations in will result in an increase of weight by.Since this can be achieved by doing nothing on,we can always regard as nonempty and whenever the statement“complement the bit ”is encountered,we simply skip this step.This amend-ment will make the program complete.The next problem is to prove that in step a,we can alwaysfind a qualified,which is shown below.Lemma3Step S4will always succeed,and at most two bitsof will be modified to embed bits of data.Proof.We test a series of values for and show that eventu-ally a qualified can be found.First,we test.If, then is a solution.Otherwise,,which im-plies by Lemma1.Then,we test.If, then is a solution.Otherwise,,which im-plies by Lemma1.Next,we test.If, then is a solution.Otherwise,,which implies .We can repeat this process to test,,etc.If the tests keep on failing,we claim that eventually will be tested.If so,Lemma2guarantees that is nonempty and thus we are done.The claim can be proved by a simple rule in num-ber theory,which says thatmust contain all and only the numbers that are a mul-tiple of under[5].As is a multiple of ,will eventually be tested.Finally,it is easy to see that at most2bits of will bemodified.Below,we demonstrate an example.Let the host image ,secret key,and weight matrix be as shown in Fig.3. First,is partitioned into four blocks.Let, so we can embed12bits,say into.The exclusive-OR result of each block and is inFig.4(a).For,.Since the embedded data is,we have to increase the weight by .Since and,we can comple-ment.For,.Since the embedded data is,there is no need to modify.For,.Since the embedded data is, we have to increase the weight by,which can be done by complementing.For,. Since the embedded data is,we have to increase the weight by5.There is no single point in by comple-menting which we can do so.So changing two bits ofFig.3.An example of host image ,secret key,and weight matrix.Fig.4.(a),and (b)the modified host im-age.is necessary.One possibility isand.In this example,we choose to complement and .The final mod-ified image is shown in Fig.4(b).4Vulnerability Analysis and Experimental Re-sults4.1Possible Attacks and CostsIn the following discussion,we assume that an opponent already knows the data hiding algorithm,the host image ,the value of ,and the block size.Also,the opponent captures a copy of the modified image .A brute-force attackis quite impossible,since there areand combinations for and ,respectively.Next,we consider a chosen-plaintext attack,which uses a differential technique to reduce the search range of .Sup-pose part of is available to the opponent.If the opponentcan find a block which is translated toafter embedding bits ,and a block which is translated to after embed-ding bits ,then the attack may proceed in several ways.If,then the difference of and will somehow re-flect the relation of weights in the locations where differsfrom and where differs from .If we further assumethatand that there is only one location,say ,in being changed,then the value of must be or ().If each entry of can be so compro-mised,then the possible combinations of can e reduced to about .If unfortunately the weight matrix has been compro-mised,then the keycan be compromised easier.For in-stance,if anddiffer from at only onelocation,say,then can be derived as follows.If,then ,imply-ing that .On the contrary,if,then ,implying thatis the complement of .The attack will succeed if each entry of can be so compromised.As can be seen,the above attack has a very high cost,as long as the block size ()is reasonably large and the secrecy of and is maintained.4.2Experimental ResultsTo visualize the data hiding effect,we have implementedthe WL scheme [18]and our scheme.Below,we present our experimental results on the two host images in Fig.5(a),and Fig.6(a).We make comparison from three aspects:A)Equal Block Size:We use the same block size and com-pare images’quality after data hiding.The results are in parts(b)and (c)of Fig.5,and Fig.6,where the block size is.Our results have more “noises”since as many as 2bits in each block will be modified compared to 1bit of the WL’s.In this case,we trade image quality for higher data hiding ratio.In general,our scheme can hide about 4to 10times more data than that of WL’s.B)Equal Image Quality:In this experiment,we try to equalize the image quality by adjusting the block size.It is easy to see that the WL scheme will modify in average 0.5bit in each block hidden with data.To maintain the same image quality,we can use a block size that is 4times larger than that in WL scheme.Thus,in the worst case,2bits will be modified in each of our blocks,or equivalently 2/4=0.5bit in each of WL’s blocks.Based on this assumption,we show the experi-mental results in parts (d)and (e)of Fig.5,and Fig.6,wherethe block size isfor WL’s scheme and for our scheme.Note that in this case the WL scheme can embed at most 1bit in each block,and ours unconditionallybits in each block.Our datahiding ratio is at least 10/4higher than WL’s.C)Equal Amount of Embedded Data:Here we further equalize the amount of embedded data (by adjusting the block sizes)so as the compare the image quality after data hiding.The results are in parts (f)and (g)of Fig.5,and Fig.6.Note that since the data hiding ratio of the WL scheme will depend on the nature of the host image,we have to choose the block sizes that deliver approximately the same amount of hidden data to make the comparison.Specifically,the block sizesused in Fig.5(f),Fig.5(g),Fig.6(f),and Fig.6(g)are,,,,,and ,respectively.Clearly,our results deliver much better image quality.Finally,we comment that in both WL and our schemes,the security will depend on the block size used.In both items B and C of the above experiments,larger block sizes are used in our scheme,thus providing another advantage of higher secu-rity.5ConclusionWe have presented a new steganography scheme for hiding data in a binary image.The main idea is to use a secret key andFig. 6.Embedding effect on image “Micky”(obtained from the Disney World):(a)the original host image,(b)after embedding338bytes by our scheme with block size,(c)after embedding83bytes by WL schemewith block size,(d)after embedding103 bytes by our scheme with block size,(e) after embedding34bytes by WL scheme with block size,(f)after embedding180bytes by our scheme with block size,and(g) after embedding180bytes by WL scheme with block size.[9]G.J.Simmons.The Prisoners’Problem and the SubliminalChannel.In CRYPTO’83,pages51–67.[10]G.J.Simmons.Results Concerning the Bandwidth of Sublim-inal Channels.IEEE J.on Selected Areas in Communications, 16(4):463–473,May1998.[11]G.J.Simmons.The History of Subliminal Channels.IEEEJ.on Selected Areas in Communications,16(4):452–462,May 1998.[12]W.Stallings.Cryptography and Network Security.PrenticeHall,New Jersey,1999.[13]R.G.van Schyndel,A.Z.Tirkel,and C.F.Osborne.A DigitalWatermark.In IEEE Int.Conf.Image Processing,volume2, pages86–90,1994.[14]R.Z.Wang,C.F.Lin,and J.C.Lin.Image Hiding by LSB Sub-stitution and Genetic Algorithm.In Proceedings of International Symposium on Multimedia Information Processing,Chung-Li, Taiwan,R.O.C,December1998.[15]P.Wayner.Should encryption be regulated.Byte,May1993.[16]P.W.Wong.A Public key Watermark for Image Verificationand Authentication.In Proceedings of International Conference on Image Processing,Chicago,Illinois,USA,October1998. [17]P.W.Wong.A Watermark for Image Integrity and OwnershipVerification.In Proceedings of IS T PIC Conference,Portland, Oregon,USA,May1998.[18]M.Y.Wu and J.H.Lee.A Novel Data Embedding Method forTwo-Color Facsimile Images.In Proceedings of International Symposium on Multimedia Information Processing,Chung-Li, Taiwan,R.O.C,December1998.。

Translation of Public Signs from the Perspective of SkoposTheoryAbstractPublic signs are widely used and play an increasingly important role in our daily life. This paper analyzes the main functions of public signs—instruction, restriction and compulsion, and briefly introduces the skopos theory as well as its three translation principles: skopos rule, fidelity rule and coherence rule. Meanwhile, on the basis of practical functions of skopos theory, several translation strategies are proposed, including zero translation, borrowing, imitating and creating. Except for several commonly used strategies, this paper proposes a novel one, which is rewording, such as using non-discriminal words, common words and humorous words.Key WordsPublic Signs; Skopos Theory; Translation Principles摘要公示语在现代生活中的应用越来越广泛，作用也越来越明显。