一般論文

DBSJ Journal, Vol.7, No.4
March 2009

Oblivious CAPTCHA: A Fifth-Factor
Technology for Practical CAPTCHA
Use
Hiroaki OZEKI ♥The CAPTCHA (Completely Automated Public Turing
test to tell Computers and Humans Apart) idea is widelyused as a HIP (Human Interactive Proof) for
distinguishing between humans and computer programs.
These are automated tests that humans can pass, butthat current computer programs can’t handle. Breaking
a CAPTCHA generally involves solving a difficult
Artificial Intelligence problem. There are demands for
new technologies that are stronger against automatic
attacks by machines, without making it too hard forhumans to pass the tests. In this paper, we propose aconcept called the Oblivious CAPTCHA, as a fifth-factor
technology for a practical CAPTCHA. The Oblivious
CAPTCHA uses tasks such as identifying the English
alphabetic characters in a set of mixed alphabetic andnon-alphabetic characters, or counting the English
alphabetic characters in a string. In experiments wefound that the Oblivious CAPTCHA was easy for users,
because human beings can recognize images ofalphabetic characters quickly and accurately, but this isdifficult for computers, because OCR tech-niques tend tomisrecognize non-alphabetic characters as though they
were alphabetic. This shows our approach is practical.
We also describe novel algorithms for enhancing the skill
gap between humans and computers that can be usedwith many existing CAPTCHAs.

1. Introduction
1.1. Background
A CAPTCHA (Completely Automated Public Turing test
to tell Computers and Humans Apart) [1,2] is an
automated test that humans can pass, but that current
computer programs can’t satisfy. Most CAPTCHAs are
based on unsolved Artificial Intelligence (AI) problems, so
CAPTCHA breaking is regarded as an AI task. A
CAPTCHA is also regarded as a HIP (Human Interactive
Proof) that proves an active agent is a human rather thana machine.
A good CAPTCHA should satisfy several requirements.
First, a human being should be able to solve it quickly andwith little effort, but automated techniques, such assoftware bots should not be able to solve it easily.
Automated attacks are expected to produce many
incorrect answers.

Automatic
generation

Can you read this character string?
Display

Input Display

Input

Bot

Human
Figure 1: What is a CAPTCHA?

Figure 1 is a simple example of a CAPTCHA used toblock software bots (non-humans).
Here are some typical use cases of CAPTCHAs :¾ Registration for a new ID or user account (such as theIDs or accounts used for free email, blogs, or storage
services).
¾ Authenticating comments (such as in a blog, wiki, or
BBS (Bulletin Board System)).
¾ Validating online voting (to prevent automated ballot
stuffing).
Currently, there are four major CAPTCHA technologies:
Text identification (Text) [3-8], Logical puzzles (Puzzle) [9],Photograph identification (Photo) [10-13], and Sound
identification (Sound) [14] (Figure 2). Each existing
CAPTCHA technology has strengths and limitations.
Table 1 is a comparison table of CAPTCHAs.
At present, text identification is the most mature
CAPTCHA technology and the kind that is most widelyused. However, the attack technologies for text
identification have been developing rapidly simply
because it is also the biggest target [15-19]. Text
identification has improved its resistance to attacks byadding more processing to the character strings made ofalphanumericcharacters.
Typicalprocessing
transformations used with the character strings to help
disguise them are called Arc, Deform, Undividable, andSpecial effects (Figure 3).
Text identification faces two dilemmas, one for lengthand one for character distortion. Shorter strings are easierand more convenient for human beings, but shorter
strings are also easier to attack with automated methods.
Using more automated processing can add more
complexity to the characters and make it harder to attack
them with automatic methods, but that also makes thestrings harder and less convenient for people to recognize.
The goal is create new technologies that retain strength
against attacks from machines, but without making it
more difficult for humans to prove their humanity.

1.2. Our Contribution♥

Member. Tokyo Research Laboratory, IBM Japan,
Ltd. ozkmail@gmail.com

In this paper, we propose an Oblivious CAPTCHA(Figures 4, 5, 6), using fifth-factor technologies for

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009

practical CAPTCHAs. Our Oblivious CAPTCHA asks
users to answer questions like these:¾ Question: “Which of the characters in the 12-character
string ‘ＣＡЛＰＴЖЧＣ∀ＨИＡ’ are English letters?”(Correct answer: “CAPTCHA”.)¾ Question: “How many English letters appear in thatstring?” (Answer: “7”.)Our experiments showed the Oblivious CAPTCHA iseasy for users, because humans can quickly andaccurately distinguish between characters of their own
alphabet and non-alphabetic characters, while this is adifficult task for computers, because all OCR approaches
tend to misrecognize non-alphabetic characters as
belonging to the target alphabet. Therefore our approachseems simple and practical.
This paper is structured as follows. We describe related
work about CAPTCHAs in Section 2 and explain the
Oblivious CAPTCHA in Section 3. Section 4 evaluates ourapproach through actual experiments. Finally, we
conclude in Section 5 with a summary of our results andconsider issues that still remain to be addressed.

2. Related Works
Here are the four primary techniques now used for
CAPTCHAs [1,2][20-26]:¾ Text identification (Text) [3-9,15-18]: This method
involves recognizing and reading alphanumericcharacters within images.
¾ Logical puzzles (Puzzle) [9]: This method asks
questions about logical puzzles.
¾ Photograph identification (Photo) [10-13]: This method
calls for recognizing photographs, such as asking
whether a certain picture is a cat or a monkey.
¾ Sound identification (Sound) [14]: This involves asking
about sounds, usually synthesized voices orrecordings.
Figure 2 is an example of four variations of CAPTCHA.
Text

PuzzlePhoto

low quality images and small-screen devices such as
mobile phones. The questions are easy to understandand the cognitive loads for the users are small.
▼ Attacks based on improvements in OCR technologies
are becoming increasingly effective [15-19]. To respondto the increasingly sophisticated attacks, the images
are becoming more complicated, noisy, and distorted,so even human beings find it increasingly hard to see
the answers.
• Logical puzzles (Puzzle):△ There are automatic generation algorithms.
▼ There is limited variation in the automaticallygenerated questions or questions may take too long tosolve. It is difficult to design questions that are easily
understood, because some questions are not intuitive
for certain users. Also, some people find certain
problems hard to solve.
• Photograph identification (Photo):△ These tasks are especially challenging for artificial
intelligence, so the questions are especially resistantto machine attacks. Also, the questions are easily
understood, so the cognitive load is small.
▼ Larger images of higher quality are required, so thismethod is not suitable for many mobile devices (withsmall screens and low quality images). There are no
efficient algorithms to generate the images
automatically. It is difficult to prepare photographswith large numbers of elements. Also, the method
requires constructing a large and costly database ofphotographs.
• Sound identification (Sound):△ This is a method that visually handicapped people canalso use. There are several efficient automatic
generation algorithms. It works effectively even withlow quality images and small-screen devices such as
mobile phones.
▼ Listening to instructions and questions takes arelatively long time (perhaps 30 seconds). Also, attacks
based on improving in voice recognition technology
technologies are becoming increasingly effective.
Table 1: Comparison of CAPTCHA.
Present adoption (diffusion and share).

Sound

To which side does the blockon the bottom belong?

Humans can solve it quickly and easily.
The user selects each of the
12 images that depict cats.

Figure 2: Varieties of CAPTCHAs.
For all of these methods, humans are better thancomputers at answering the questions. Figure 2
illustrates these four CAPTCHAs.
Each existing CAPTCHA technology has strengths andweaknesses. (△: strengths, ▼: weaknesses)• Text identification (Text):△ This is currently the most commonly used method.
There are several efficient automatic generation
algorithms. Human can easily recognize the answers
in a few moments. The keyboard response method isquick and convenient. It works effectively even with

Bots cannot solve it.
Low cost of generating questions.
Effective for mobile devices.

Text

Puzzle

Photo

Sound

◎
◎
○
◎
◎

△
△
○
△
△

△
○
◎
×
×

△
△
○
◎
◎

Table 1 is a comparison table of the four types of
CAPTCHA. (Legend: ◎: Very good. ○: Good. △: Not
good. ×: Bad.) At present, text identification is the mostdeveloped and most widely used CAPTCHA technology.
Users have become accustomed to text CAPTCHAs, andthe competing methods are relatively less advantageous.
Puzzles and sounds are slow and can be difficult, andimages are expensive and have limited applicability.
Therefore it seems clear that text CAPTCHAs will remain
popular for the time being.
Preparing a text identification CAPTCHA involves
several steps. A string of characters is converted into asmall image, and then some operations such as those

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009

shown in Figure 3 are used on that image.
¾ arc: Thin lines and arcs are added on top of thecharacters.
¾ deform: The characters are deformed or warped.
¾ undividable: Characters are pushed together to makethem hard to separate.
¾ special effects: Decorations or borders are added
around the characters.
¾ combination: Various operations are combined.
[normal]CAPTCHA[normal][arc]

ＣＡＰＴＣＨＡＣＡЛＰＴЖЧＣ∀ＨИＡ

oblivious[dummy]ＣＡЛＰＴЖЧＣ∀ＨИＡ[deform]Ｃ a Лp ＴЖ Ч c∀ h ИＡ[undividable]

ＣＡЛＰＴЖЧＣ∀ＨИＡ[special effects]
ＣＡЛＰＴЖЧＣ∀ＨИＡ[arc]
CAPTCHA[deform]

C ap T c h A

CAPTCHA.

Figure 5: Combinations with Oblivious CAPTCHA.
[combination][undividable]

CAPTCHA[special effects]
CAPTCHA

Figure 3: Operations used for text identification images.

3. Oblivious CAPTCHA
3.1. Concept
In this paper, we propose the concept of Oblivious
CAPTCHA as an enhancement to the text identification
type of CAPTCHA.
Using Oblivious CAPTCHA involves three steps. First,
a character string that mixes dummy characters with thecharacters of the correct answer is prepared. Second, thehuman is asked to pick the characters of the correct
answer out of the mixed character string. Third theresults are checked to determine whether a human being
properly recognized the correct answer or a machine failed
to do so.
oblivious[normal][dummy]ＣＡＰＴＣＨＡＣＡЛＰＴЖЧＣ∀ＨИＡ
Figure 4: Oblivious CAPTCHA.
Figure 4 shows an example of Oblivious CAPTCHA. The
correct answer is written with letters of the English
alphabet, and the dummy characters are Russian letters(selected from those that do not appear in English). A
human being who reads English selects the correct letters,
while a machine using OCR techniques will include someRussian characters (misrecognized as the most similar
English letters). The Oblivious CAPTCHA can also be
combined with the existing arc, deform, undividable, andeffect operations for more strength.
There are two basic assumptions of the Oblivious
CAPTCHA approach. One is that literate human beings
can quickly and accurately recognize the written form of
their own language. The second assumption is that amachine using OCR techniques will tend to force foreign
characters into the target alphabet. These two
assumptions are described in more detail in the
Evaluation and Discussion.
Oblivious CAPTCHA can be combined with existing
techniques. Figure 5 shows combinations with Oblivious

Here are two examples of Oblivious CAPTCHAs,
showing that people can quickly and easily respond to thiskind of CAPTCHA. These are high-level questions thathumans can answer quickly, even on a mobile device.
¾ Question: “Select the English letters in the following
12-character string: ‘ Ｃ ＡЛ Ｐ Ｔ Ж Ч Ｃ ∀ Ｈ И Ａ ’. ”
(Answer: “CAPTCHA”.)¾ Question: “How many English letters appear in thestring?” (Answer: “7”.)[box]
ＣＡЛＰＴЖЧＣ∀ＨИＡ
ＣθＡЛ
Q. Pickup alphabets from Character string. A. “CAPTCHA”
Q. How many alphabets are there in this character string? A. “7”

ＰＴЖЧ
Ｃ∀ＨИ
Я↑∠Ａ

[Sound]Ｃ Ａ Ｐ Ｔ Ｃ Ｈ Ａ[sí:][éi][pí:][tí:][sí:][éitʃ][éi]oblivious

Ｃ Ａ βＰ Ｔ α ε Ｃ δ Ｈ γ Ａ[sí:] [éi] [beta][pí:] [tí:] [alpha] [epsilon] [sí:] [delta] [éitʃ] [gamma] [éi]Figure 6: Application of Oblivious CAPTCHA.
Figure 6 shows other examples of applying Oblivious
CAPTCHAs. An Oblivious CAPTCHA can be put into a
rectangle (see Figure 6 (top)). In addition, if it is aquestion answered with a number, it is not necessary to
specify the order in which the characters are read.
Oblivious CAPTCHA can even be used for Sound (seeFigure 6 (bottom)). The pronunciations of the names of thecharacters in the dummy string are read out loud.

3.2. Implementation

How many
Englishletters?:
2
Figure 7: Prototype Implementation of Oblivious
CAPTCHA. (Difficult Dummy)
Figure 7 is from a simple prototype implementation of
Oblivious CAPTCHA. This prototype was implemented

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009

with PHP 5.2.5, Apache 2.2.8, and related libraries.

Table 2: Experimental Questions.
Alphabet Dummy
Number of Alphabet
Characters : Dummy

3.3. Oblivious Transfer and Oblivious CAPTCHA

4. Evaluation and Discussion
4.1. Question composition and examples
For our experiments we prepared ten kinds of Oblivious
CAPTCHAs. The constraints were:¾ The characters used for the correct answers are the 26
uppercase letters of English: “ABCDEFGHIJKLMNOPQRSTUVWXYZ”.
¾ The easy dummy characters are these symbols: “◇◎△□☆”.
¾ The difficult dummy characters are 26 letters fromother languages and some special symbols: “Λβθδ∈ΓбЛ↑）ж∠ΣПΘρΦЯ＄ΨЦ∀ШЖЧИ”.
Ｑ．Fill in the number of alphabets on Ａ.___ column by the Character string. (30 sec)
Alphabet：ＡＢＣＤＥＦＧＨＩＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺDummy：◇◎△□☆ Λβθδ∈ΓбЛ↑）ж∠ΣПΘρΦЯ＄ΨЦ∀ШЖЧИ

Ｑ１

Ａ～Ｚ

◇

20

about 5 : 5

Ｑ２

Ａ～Ｚ

◇◎△□☆

20

about 5 : 5

Ｑ３

Ａ～Ｚ

◇◎△□☆

20

about 8 : 2

Ｑ４

Ａ～Ｚ

◇◎△□☆

20

about 2 : 8

Ｑ５

Ａ～Ｚ

◇◎△□☆

80

about 2 : 8

Ｑ６

Ａ～Ｚ

Λβθ～ЧИ

20

about 5 : 5

Ｑ７

Ａ～Ｚ

Λβθ～ЧИ

20

about 8 : 2

Ｑ８

Ａ～Ｚ

Λβθ～ЧИ

20

about 2 : 8

Ｑ９

Ａ～Ｚ

Λβθ～ЧИ

80

about 2 : 8

Ｑ１０

Ａ～Ｚ

Λβθ～ЧИ

20

about 5 : 5

4.2. Tests of human’s reading
4.2.1. Experimental procedures
The experimental environment was:
¾ Human subjects: 18 people (16 men and 2 women,from 20 – 49 years old, 17 Japanese and 1 Belgian).
¾ Each subject was shown the ten test patterns of
Q1-Q10. Each subject was shown each string for 30
seconds and asked to solve some problem involving thestring.
¾ The number of questions that could be solved in 30
seconds for each of the Q1-Q10 images was recorded.

4.2.2. Experiment Results
20
man, 40s
woman, 20s
woman, 20sman, 30s
man, 20s
man, 40s
man, 40s
man, 30s
man, 20s

18
Number of Correct Answers

An oblivious transfer [27] protocol is a protocol by which
a sender sends some information to the receiver, but
remains oblivious as to what was received. An example ofa k-out-of-n Oblivious Transfer would be a secure 2-party
protocol where Bob has secrets m1, m2, ..., mn out of npieces, and Alice has secrets a1, a2, ..., ak (k < n) out of of kpieces. After the protocol ends, Alice will have acquired
ma1, ma2, ..., mak. For this example, there are two
requirements:¾ (1) Alice attaches nothing besides ma1, ma2, ..., mak andis not understood at all.
¾ (2) Bob does not reveal anything about a1, a2, ..., ak.
Oblivious Transfer uses a function to conceal the true
data. The dummy data is mixed into the true data to
implement this function and cannot be distinguished fromthe valid data. The Oblivious CAPTCHA allows thecharacter of the dummy data to exist together as validcharacters and creates a state in which the dummy datacannot be recognized. The concept “It is made to do in thestate that cannot be distinguished” is a common feature of
Oblivious Transfer and Oblivious CAPTCHA.

16
14
12

man, 20s
man, 30s
man, 30s
man, 30s
man, 30s
man, 40s
man, 40s
man, 40s
man, 30s

108
6
4

Ｑ１．ＥＰＶ◇◇◇ＢＬ◇ＭＮ◇◇◇◇◇Ｇ◇ＡＧ

Ａ．１０.

Ｑ２．△Ｌ◇Ｈ☆Ｋ◎Ｍ☆☆☆Ｍ☆ＩＸＤＡＫＫＸ

Ａ．１２.

Ｑ３．ＫＮ◎ＳＴＥＣＵＰＦＴ☆Ｒ△ＱＱＶＮＢＶ

Ａ．１７.

Ｑ４．◇☆□Ｌ□☆◎□◎◎△◇◎Ｑ◇□△◇Ｚ☆

Ａ．

Ｑ５．Ｉ△ＸＨＰ◎△☆◇△△◎☆◎△◇□□Ｈ△◇◇◇□△□◎◇□Ｑ
Ｘ◎☆△◇△ＤＴＪ△◇◎□◎☆☆◇◇Ｗ◇△☆◇◇◇Ａ△◇◎□ＳＺ◎△Ｗ◇□△☆□◎△Ｙ□□☆◇☆☆☆

Ａ．１６.

Ｑ６．∀ΣＥＺＪ＄Ｍ↑ЦＪＡＷ∠↑ＦΨＵΣ）＄

Ａ．

Ｑ７．ＦＴＪＮＹＦＸＲΦＹＳПＳПＲＴＣＦＸＭ

Ａ．１７.

Ｑ８．ПＣＭＲЧρＣИΘＶЦ↑ＢΦδΛбβбЧ

Ａ．

2
0
1

３.

2

3

4

5
6
Question

7

8

9

10

Figure 9: Results of Human Tests.

９.

Ｑ９．∀θ∀Ｆ＄ИΨ∀Σ↑ЛΨＪρЯΨρΛΦжΨＡθ∈∈ΛＭЦ∀ЛＪΘЯЧЯбδΨ↑ΣΓбＱθΓИΓЯρЖΣΓ∠Λβ∈βＹЧШ＄бＹＹПЦΨЧＩδПβ↑∈ЖЛЯＢΛβ

Ａ．１０.

Ｑ１０．ＭＵＹＦＵ∀ＱЛΦρＹЧжρΦＰИＵΨПＡ．

９.

Figure 8: Example Questions.
Figure 8 shows the sample text strings as images. The
tests gradually become more difficult.
Table 2 is a summary of the questions.

80
Number of Characters Humans Recognized for
Each Ten Second Interval.

６.

70
60
50
40
30
20
10
0
1

2

3

4

5

6

7

8

9

10

Question

Figure 10: Number of Characters Humans Recognized for
Each Ten Second Interval.

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文
Ｑ１．ＥＰＶ◇◇◇ＢＬ◇ＭＮ◇◇◇◇◇Ｇ◇ＡＧ
Ｑ２．△Ｌ◇Ｈ☆Ｋ◎Ｍ☆☆☆Ｍ☆１ＸＤＡＫＫＸ
Ｑ３．ＫＮ◎ＳＴＥＣＵＰＦＴ☆Ｒ△ＱＱＶＮＢＶ
Ｑ４．◇☆□Ｌ□☆◎□◎◎△◇◎Ｑ◇□△◇Ｚ☆

Ｑ５．１△ＸＨＰ◎△☆◇△△◎☆◎△◇□□Ｈ△◇◇◇□△□◎◇□Ｑ
ＤＴ◇△
ＤＴＪ△◇◎□◎☆☆◇◇Ｗ◇△☆◇◇◇Ａ△◇◎□◇△ＤＴ
Ｘ◎☆△◇△ＳＺ◎△Ｗ◇□△☆□◎△Ｙ□□☆◇☆☆☆
Ｑ６．∀ΣＥＺＪＳＭＴｕＪＡＷ∠ＴＦＶＵΣ）Ｓ
Ｑ７．ＦＴＪＮＹＦＸＲ◎ＹＳＨＳＨＲＴＣＦＸＭ
П ＣＭＲｔρρＣИΘＶｕＴＢ◎ａＡ６β６ｔ
Ｑ８．П
ИΘ
ＣИΘ
Я ＶｐＡ◎ＩＸＶＡＯ∈∈ＡＭｕ∀ｎ
Ｑ９．∀０∀ＦＳＩＩＶ∀ΣＴｎＶＪｐЯ↑ΣΓбΘЯΣΓбＱＯｒＩｌｒｐ｝ＫΣｒ∠Ａβ∈βＹＬｉＩｌｌ
ΘЯｔｌ６６Ｖ↑ＪΘЯΣΓб＄６ＹＹＩｌｕＶｔｌｌａＩｌｕＶｔｌｌａＩｌβＴ∈｝ＫｎＴＢΣＡｒβ６
ρΦИ ＴｕＴΨ
ΨＲ
ρΦＰＩИ
Ｑ１０．ＭＴｕＴ￥ＦＴｕＴ￥Ｑｕｑ￥ＴжρΦ
Legend:
ＡＢＣ：Correct character selected.
ＡＢＣ：Different character selected.
ＸＹＺ
ＸＹＺ：Missing,
Do not scanned.
ＸＹＺ

Figure 11: Sample of OCR Scanning Test Result.
21
01

4.3.1. Experimental procedures-5

Figure 11 is a sample of the results of the OCR scanningtests. Figure 12 is a graph of the experiment results of thetests with an Acrobat OCR Scanner .Figure 13 is a graphof the experimental results with a Xero OCR scanner.
These results show:¾ Mixing in complex dummy characters is effective. The
mixing ratio of the correct answers and the dummy
characters increases the recognition failures as shownfor 2:8, 5:5, and 8:2.
¾ The higher the ratio of the dummy characters, themore recognition failures.
¾ For an analytical attack using OCR it would be more
effective to focus on increasing the incorrect
recognition rate rather than trying to lower the correct
recognition rate.

4

5

6

7

8

9

10

Correct recognition rate
Incorrect recognition rate-3-4

4.3.2. Experiment Results

3-2

4.3. Test of reading by machine (OCR)

Question

Figure 12: Result of OCR Scan Test (Correct/Wrongrate) (Acrobat OCR).
1.5
1
0.5
0
Rate

The experimental environment was:
¾ Each question was converted into an image, and thenconverted into a PDF image format with Acrobat.
¾ The OCR recognition processing was done by using the
OCR function of Adobe Acrobat (Acrobat 8 Professional
Japanese Edition), and Xero OCR (Yonde Koko 13.00),
liading Japanese OCR Software.
¾ The correct recognition rate (Correct recognition rate
for letters) and incorrect recognition rate (Rate at
which dummy characters were falsely recognized asvalid letters) were calculated as:¾
Correct recognition rate = (Number correctly
recognized letters) / (Total number of letters)¾
Incorrect recognition rate = (Number of dummy
letters falsely recognized as valid letters) / (Total
number of letters)

2

-1
Rate

Figure 9 is a graph of the experimental results of thehuman testing. Figure 10 is a graph where the median ofthe experiment results of the test for each person is
calculated, and the number of characters recognized forevery period of ten seconds is shown.
Here are the conclusions that can be drawn from thegraphs in Figures 9 and 10:¾ Mixing in a complex dummy slows recognition speeds
compared to mixing in a simple dummy. (From theresults for Q1, Q2, and Q6.)
¾ The mixing ratio of the correct answer and the dummy
increases and the recognition speed accelerates in theorder of 2:8, 8:2, and 5:5. (From the results of Q2-Q4
and Q6-Q8.)¾ When the correct answer exists with a complex dummy,
the recognition speed barely changes even if acancellation line is added. This shows that it ispossible to use Oblivious CAPTCHA and Arc together.
(From Q6 and Q10.)¾ The recognition speed does not increase when there
are more characters. (From Q1, Q5, Q6, and Q9.)
¾ Using the complex dummy characters does not prevent
sufficiently accurate answers in sufficiently short
response times, whether or not there is a cancellation
line. (From Q1, Q2, Q6, and Q10.)

DBSJ Journal, Vol.7, No.4
March 2009

1

2

3

4

5

6

7

8

9

10

-0.5
-1
-1.5

Correct recognition rate
Incorrect recognition rate-2
-2.5
Question

Figure 13: Result of OCR Scan Test (Correct/Wrong rate)(Xero OCR).

4.4. Combined method for Oblivious CAPTCHA
These results can be used together for a better system.
The combination would focus on using more charactersthat humans can read easily, and more characters thatmachines (OCR) cannot read easily.
¾ Humans can quickly distinguish between the lettersthey can read and the dummy (non-alphabetic)characters. They can make these distinctions quickly
even when the strings are longer.
¾ It is more effective to use Complex dummy characterssuch as “Λβθ～ЧИ” than simple dummy symbols
such as “◇◎△□☆”.
¾ Combining a small number of letters and a lot ofdummy characters is more effective.

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009

¾ Using the Oblivious CAPTCHA technique and Arc
together is effective. The reading speed of the humans
is barely affected when they are used together.

5. Summary
In this paper, we proposed Oblivious CAPTCHA as a
fifth-factor technology. Through experiments, we showedthat our approach is easy for users, because humans candistinguish between letters of their alphabet and othercharacters at high speed and with high accuracy, and thistask is difficult for computers, since OCR software
misrecognises many characters. We want to prove theutility of this technique through a larger scale experimentin the future.

Proceedings of the 9th International ACM SIGACCESS
Conference on Computers and Accessibility, ACM

SIGACCESS Conference on Assistive Technologies, pages
245-246 (2007).
[15] Jeff Yan and Ahmad Salah El Ahmad: “Breaking Visual
CAPTCHAs with Naive Pattern Recognition Algorithms”,
Computer Security Applications Conference (ACSAC 2007),
pages 279-291 (Dec. 2007).
[16] Kumar Chellapilla, Kevin Larson, Patrice Simard, and Mary
Czerwinski: “Designing human friendly human interaction
proofs (HIPs)”, In Proceedings of ACM CHI 2005 Conferenceon Human Factors in Computing Systems, Volume 1 of
Email and Security, pages 711-720 (2005).
[17] Greg Mori and Jitendra Malik: “Recognizing objects inadversarial clutter: Breaking a visual CAPTCHA”, In

Conference on Computer Vision and Pattern Recognition[References］[1] Luis von Ahn, Manuel Blum, and John Langford: “Tellinghumansandcomputers
apartautomatically”,
Communications of the ACM, pages 56-60 (2004).
[2] Luis von Ahn, Manuel Blum, Nicholas J. Hopper, and John
Langford: “CAPTCHA: Using Hard AI Problems For
Security”, Eurocrypt 2003 (2003).
[3] H.S. Baird, M.A. Moll, and S.Y. Wang: “ScatterType: A
Legiblebut
Hard-to-Segment
CAPTCHA”,
EighthInternational Conference on Document
Recognition, pages 935-939 (Aug. 2005).

[14] Jonathan Holman, Jonathan Lazar, Jinjuan Heidi Feng,John D’Arcy: “Developing usable CAPTCHAs for blind users”,

Analysisand[4] M. Chew and H.S. Baird: “BaffleText: a human interactive
proof”, Proceedings of 10th IS&T/SPIE Document
Recognition & Retrieval Conference 2003, San Jose; CA; USA(2003).
[5] A.L. Coates, H.S. Baird and R.J. Fateman: “PessimalPrint: A
Reverse Turing Test”, Int’l. J. on Document Analysis &Recognition, Vol. 5, pages 158-163 (2003).
[6] P. Simard, R. Szeliski, J. Benaloh, J. Couvreur, and I.
Calinov: “Using Character Recognition and Segmentation toTell Computers from Humans”, Int’l Conference on
Document Analysis and Recognition (ICDAR), (2003).
[7] Amalia Rusu and Venu Govindaraju: “Visual CAPTCHA
with Handwritten Image Analysis”, Lecture Notes in
Computer Science, Springer Berlin, Human Interactive
Proofs, Volume 3517/2005, pages 42-52 (2005).
[8] Henry S. Baird, Michael A. Moll, and Sui-Yu Wang: “AHighly Legible CAPTCHA That Resists Segmentation
Attacks”, Lecture Notes in Computer Science, Springer
Berlin, Volume 3517/2005, Human Interactive Proofs, pages
27-41 (2005).
[9] H.S. Baird and J.L. Bentley: “Implicit CAPTCHAs”, In

Proceedings of Document Recognition and Retrieval XII(IS&T/SPIE Electronic Imaging), volume 5676, pages

191-196, San Jose, CA (Jan. 2005).
[10] Jeremy Elson, John R. Douceur, Jon Howell, and Jared Saul:“Asirra: A CAPTCHA that Exploits Interest-Aligned Manual
Image Categorization”, Conference on Computer andCommunications Security (CCS’07), pages 366-374,

Proceedings of the 14th ACM Conference on Computer andCommunications Security (Oct. 2007).

[11] Monica Chew and J.D. Tygar: “Image recognition
CAPTCHAs”, In Proceedings of the 7th International
Information Security Conference (ISC 2004), pages 268-279.
Springer (Sep. 2004).
[12] Ralph Gross, Jianbo Shi, and Jeff Cohn: “Quovadis Face
Recognition?”, Technical Report CMU-RI-TR-01-17, Carnegie
Mellon University Robotics Institute (June 2001).
[13] Wen-Yi Zhao, Rama Chellappa, P.J. Phillips, and Azriel
Rosenfeld: “Face recognition: A literature survey”, ACM
Comput. Surv., 35(4):399-458 (2003).

(CVPR ’03), pages 134-144. IEEE Computer Society (2003).
[18] K. Chellapilla, and P. Simard: “Using Machine Learning to
Break Visual Human Interaction Proofs (HIPs)”, Advances in

Neural Information Processing Systems 17, Neural
Information Processing Systems (NIPS), MIT Press (2004).

[19] Gabriel Moy, Nathan Jones, Curt Harkless, and Randall
Potter: “Distortion Estimation Techniques in Solving Visual
CAPTCHAs”, IEEE Conference on Computer Vision and
Pattern Recognition (CVPR’04), Vol. 2, pages 23-28 (June
2004).
[20] J. Yan: “Bot, Cyborg and Automated Turing Test”, theFourteenth International Workshop on Security Protocols,
Cambridge, UK, (Mar 2006).
[21] Kolupaev, A. Ogijenko, J.: “CAPTCHAs: Humans vs. Bots”,
Security & Privacy, IEEE, Volume 6, Issue 1, pages 68-70(Jan.-Feb. 2008).
[22] Daniel Lopresti: “Leveraging the CAPTCHA Problem”,
Lecture Notes in Computer Science, Springer Berlin, Volume3517/2005, Human Interactive Proofs, pages 97-110 (2005).
[23] L. von Ahn, M. Blum, N.J. Hopper, and J. Langford: The
CAPTCHA webpage. http://www.captcha.net[24] Tim Converse: “CAPTCHA generation as a Web service”,

Proc. of Second Int’l Workshop on Human Interactive Proofs(HIP ’05), ed. by HS Baird and DP Lopresti, Springer-Verlag.
LNCS 3517, Bethlehem, PA, USA, 2005. pages 82-96 (2005).
[25] C. Pope and K. Kaur: “Is It Human or Computer? Defending
E-Commerce with CAPTCHA”, IEEE IT Professional, pages
43-49 (March 2005).
[26] S. Shirali-Shahreza and A. Movaghar: “A New Anti-Spam
Protocol Using CAPTCHA”, 2007 IEEE International
Conference on Networking, Sensing and Control, pages
234-238 (Apr. 2007).
[27] Moni Naor and Benny Pinksas: “Oblivious Transfer and
Polynomial Evaluation”, Proceedings of the Thirty-first
Annual ACM Symposium on the Theory of Computing, ACM,
pages 245-254 (1999).

Hiroaki OZEKI
Hiroaki Ozeki was born in Japan. He received B.E., M.E.,
and Ph.D. degrees from Tokyo University of Science in
2002, 2004, and 2007. He joined IBM Japan Ltd. in 2007.
He is currently a researcher at the IBM Tokyo ResearchLaboratory. He is a member of the Information Processing
Society of Japan (IPSJ).

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月