Ex Parte Macchetti et al

Board of Patent Appeals and Interferences

Feb 4, 2010

09974705 (B.P.A.I. Feb. 4, 2010)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________

Ex parte MARCO MACCHETTI, STEFANO MARCHESIN,
UMBERTO BONDI, LUCA BREVEGLIERI, GUIDO BERTONI,
and PASQUALINA FRAGNETO
____________

Appeal 2008-005061
Application 09/974,705
Technology Center 2400
____________

Decided: February 4, 2010
____________

Before LANCE LEONARD BARRY, JOHN A. JEFFERY, and
JAMES R. HUGHES, Administrative Patent Judges.

JEFFERY, Administrative Patent Judge.

DECISION ON APPEAL
Appellants appeal under 35 U.S.C. § 134(a) from the Examiner’s
rejection of claims 21-25, 27-43, and 48-51. Clams 1-20, 26, and 44-47
have been canceled. See Supp. Br. 2. We have jurisdiction under 35 U.S.C.
§ 6(b). We affirm.
Appeal 2008-005061
Application 09/974,705

2
STATEMENT OF THE CASE
Appellants invented a method and device that encrypts data through
several transformation rounds. The method uses a state array or matrix to
transform the data and includes a step of exchanging each row of the state
array for the columns of the state array during at least one of the
transformation rounds. This arrangement simplifies the system and
increases the system’s speed.1
Independent claim 21 is reproduced below with the key disputed
limitations emphasized:
A method of converting data between an unencrypted format and
an encrypted format, the data being organized in bit words, the method
comprising:
converting the data by at least performing a plurality of
transformation rounds comprising
applying at least one transformation to a two-dimensional
array of rows and columns of bit words defining a state array;
exchanging each of the rows with a respective column of the
state array to form a transposed state array for at least one of the
transformation rounds so that the at least one transformation is
applied to the transposed state array; and
applying at least one round key to the state array in at least
one of the transformation rounds.
The Examiner relies on the following as evidence of unpatentability:
Luther US 5,533,127 July 2, 1996
Ohkuma US 2001/0024502 A1 Sept. 27, 2001

1 See generally Spec 8-10; Figs. 5-6.
Appeal 2008-005061
Application 09/974,705

3
THE REJECTION
The Examiner rejected claims 21-25, 27-43, and 48-51 under
35 U.S.C. § 103(a) as unpatentable over Ohkuma and Luther. Ans. 3-11.2

CLAIM GROUPING
Appellants argue independent claims 21, 31, and 48 as a group. See
Br. 5-10. Appellants do not separately argue dependent claims 22-25, 27-30,
32-43, and 49-51. See id. Accordingly, we select claim 21 as
representative. See 37 C.F.R. § 41.37(c)(1)(vii).

CONTENTIONS
Regarding representative claim 21, the Examiner finds that Ohkuma
explicitly discloses all the limitations, except for exchanging each of the
rows with a respective column of the state array to form a transposed state
array. Ans. 3-4. The Examiner cites Luther to cure this deficiency, and
contends that a skilled artisan would have modified Ohkuma to exchange
each row with respective columns of a state array to confuse the data further.
Ans. 4.
Appellants argue that Luther fails to exchange rows with a respective
column of the state array to form a transposed state as claimed. Br. 5-10.
Appellants contend that the invert-bit function in Luther complements the

2 Throughout this opinion, we refer to (1) the Appeal Brief filed September
7, 2007 and supplemented October 11, 2007, and (2) the Examiner’s Answer
mailed November 28, 2007.
Appeal 2008-005061
Application 09/974,705

4
rows and columns rather than transposes them. Br. 8-9. Additionally,
Appellants contend that Luther does not complement each row and column,
but skips rows and columns. Br. 9.
The issue before us, then, is as follows:

ISSUE
Under § 103, have Appellants shown that the Examiner erred in
rejecting claim 21 by concluding that Ohkuma and Luther collectively teach
or suggest “exchanging each of the rows with a respective column of the
state array to form a transposed state array?”

FINDINGS OF FACT
The record supports the following findings of fact (FF) by a
preponderance of the evidence:
Ohkuma
1. Ohkuma discloses encrypting a data set in the form of a matrix
from one set of values to another set of values. ¶¶ 0062-65; Fig. 1.
2. This technique involves rounds of transformation using
transformation modules 2 and diffusion modules 3. The diffusion modules 3
include a Maximum Distance Separable (MDS) matrix or high-level MDS
matrix (e.g., MDSH shown in Fig. 1). ¶ 0062 and 0076; Fig. 1.
3. Ohkuma discloses an example of a high-level MDS matrix used in
encryption and a circuit used to transform data. ¶¶ 0261-63, 0273-74; Figs.
30 and 32.
Appeal 2008-005061
Application 09/974,705

5
4. Ohkuma discloses that “a matrix obtained by substituting rows,
substituting columns, and arbitrarily transposing in an arbitrary MDS matrix
may be used.” ¶ 0268.
Luther
5. Luther teaches an encryption system that involves a substitution of
a swap row/column end around function of an M row by N column two-
dimensional matrix of a data signal. Col. 1, ll. 35-39, col. 4, ll. 42-45, and
col. 6, ll. 12-16; Figs. 6 and 8.
6. Luther teaches the swap row/column end around function is
implemented when executing steps S211 and S215 in order to confuse the
data further. Col. 6, ll. 12-16.
7. Luther teaches one example of encrypting the data signal matrix’s
rows by selecting a value for S or “stripe height.” If S equals one, the third,
fourth, sixth, seventh, ninth, tenth, twelfth, and thirteenth rows are
encrypted. If S is selected to be two (i.e., S=2), the third through the
fourteenth rows are encrypted. Col. 4, ll. 42-54.
8. Luther teaches encrypting the data signal matrix’s columns by
selecting a value for S or “strip height.” If S equals one, the fourth, fifth,
eighth, ninth, twelfth, and thirteenth columns are encrypted.3 If S is selected
to be 2 (i.e., S=2), the fourth, fifth, sixth, eighth, ninth, tenth, twelfth,
thirteenth, and fourteenth columns are encrypted. Col. 4, l. 58 – col. 5, l. 3.

3 Luther states “rows” but we presume this was a typographical error
because the entire paragraph discusses encrypted columns of a data signal
matrix. See col. 4, l. 58 through col. 5, l. 3.
Appeal 2008-005061
Application 09/974,705

6
PRINCIPLES OF LAW
In rejecting claims under 35 U.S.C. § 103, it is incumbent upon the
Examiner to establish a factual basis to support the legal conclusion of
obviousness. See In re Fine, 837 F.2d 1071, 1073 (Fed. Cir. 1988). If the
Examiner’s burden is met, the burden then shifts to the Appellants to
overcome the prima facie case with argument and/or evidence. Obviousness
is then determined on the basis of the evidence as a whole and the relative
persuasiveness of the arguments. See In re Oetiker, 977 F.2d 1443, 1445
(Fed. Cir. 1992).

ANALYSIS
Based on the record before us, we find no error in the Examiner’s
obviousness rejection of representative claim 21 which calls for, in pertinent
part, exchanging each of the rows of a state array with a respective column
of the state array to form a transposed state array. Ohkuma discloses an
encryption technique that converts a data set described as a matrix from one
set of values to another set of values. FF 1. This technique involves several
transformation rounds using transformation modules 2 and diffusion
modules 3. FF 2. The diffusion modules 3 include a Maximum Distance
Separable (MDS) matrix or high-level MDS matrix (e.g., MDSH shown in
Fig. 1). Id. One such example of a high-level MDS matrix used in
encryption is shown in Figure 30 and transforms the data using the circuit
shown in Figure 32. FF 3. Ohkuma further discloses obtaining such a
matrix “by substituting rows, substituting columns, and arbitrarily
transposing in an arbitrary MDS matrix . . . .” FF 4 (emphasis added).
Appeal 2008-005061
Application 09/974,705

7
At a minimum, this portion of Ohkuma (id.) suggests using a
transposed matrix while converting data from an unencrypted format to an
encrypted format during transformation. See FF 1-4. Moreover, since
transposing a matrix involves exchanging its rows with respective columns,4
Ohkuma’s teaching of an arbitrarily transposing a matrix would do no more
than yield a predictable result of producing encrypted data by exchanging
each of the rows with a respective column of the state array to form a
transposed state array as recited in claim 21. See KSR Int’l Co. v. Teleflex
Inc., 550 U.S. 398, 416 (2007).
Additionally, Luther teaches an encryption technique that involves a
substitution of a swap row/column end around function of an M row by N
column two-dimensional matrix of a data signal. FF 5. In particular, Luther
teaches this swap row/column end around function is implemented during
the execution of steps S211 and S215 in order to confuse the data further.
FF 6. As explained above, swapping or exchanging rows and columns of a
matrix is a transposition and, thus, this portion of Luther suggests
exchanging each of the rows with a respective column of an array as recited
in claim 21 to confuse the data further.
Appellants argue that this section of Luther teaches complementation
and not transposition. Br. 8-9. We disagree. First, Luther states that the
encryption process involves a function that swaps the rows and columns
(i.e., transposes) the matrix of a data signal. Second, this portion discusses
an additional function (i.e., substitution of a swap row/column end around
function) can occur when executing steps S211 and S215 or during

4 “Transposition means exchange of rows and columns of a matrix.” Riaz A.
Usmani, Applied Linear Algebra 34 (1987).
Appeal 2008-005061
Application 09/974,705

8
complementing the data signals. See FF 6. Luther therefore teaches not
only complementing data signals, but also transposing a data signal matrix to
confuse the data further during encryption.
Appellants also contend that the Luther skips a number of rows and
columns during complementation based on random variables and, therefore,
the iterations do not match up for transposing each row and column of the
array. Br. 9. Luther teaches one example of encrypting a data signal that
involves selecting S or “stripe height” to be one. FF 7. In this scenario,
Appellants are correct that not all rows are encrypted, but only the third,
fourth, sixth, seventh, ninth, tenth, twelfth, and thirteenth rows are
encrypted. FF 7. But if S is selected to be two, more rows are encrypted.
Id. That is, by selecting S to be two, more columns of the data signal matrix
are encrypted than if S is one. FF 8. Ordinarily skilled artisans would have
readily understood from this teaching that selecting higher values of S will
encrypt more rows, and would predictably result in a value of S that will
encrypt all rows and columns of the data signal matrix such that no rows or
columns are skipped. Moreover, this teaching provides artisans with a finite
number of predictable solutions and ample reason to pursue these options
within their grasp. See KSR, 550 U.S. at 421. We therefore disagree with
Appellants (App. Br. 9) that the row and column iterations cannot match up
for transposition.
For the foregoing reasons, we find that the Examiner has not erred in
concluding that Ohkuma and Luther collectively teach or suggest
exchanging each row with a respective column of the state array to form a
Appeal 2008-005061
Application 09/974,705

9
transposed state array as recited in claim 21. We therefore sustain the
Examiner’s rejection of claim 21, and claims 22-25, 27-43, and 48-51 which
fall with claim 21.

CONCLUSION
Appellants have not shown that the Examiner erred in rejecting claims
21-25, 27-43, and 48-51 under § 103.

ORDER
The Examiner’s decision rejecting claims 21-25, 27-43, and 48-51 is
affirmed.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv).

AFFIRMED

pgc

ALLEN, DYER, DOPPELT, MILBRATH & GILCHRIST P.A.
1401 CITRUS CENTER 255 SOUTH ORANGE AVENUE
P.O. BOX 3791
ORLANDO FL 32802-3791

Appeal 2008-005061
Application 09/974,705

10
EVIDENCE APPENDIX

Riaz A. Usmani, Applied Linear Algebra 34-36 (1987).

Application/Control No.

09/974,705
Applicant(s)/Patent Under
Reexamination

Notice of References Cited
Examiner

Carl Colin
Art Unit

2400

Page 1 of 1
U.S. PATENT DOCUMENTS

* Document Number Country Code-Number-Kind Code Date MM-YYYY

Name

Classification

A US-

B US-

C US-

D US-

E US-

F US-

G US-

H US-

I US-

J US-

K US-

L US-

M US-
FOREIGN PATENT DOCUMENTS

* Document Number Country Code-Number-Kind Code Date MM-YYYY

Country

Name

Classification

N

O

P

Q

R

S

T
NON-PATENT DOCUMENTS
* Include as applicable: Author, Title Date, Publisher, Edition or Volume, Pertinent Pages)

U

Riaz A. Usmani, "Applied Lineaar Algebra" (1987) pp. 34-36

V

W

X

*A copy of this reference is not being furnished with this Office action. (See MPEP § 707.05(a).)
Dates in MM-YYYY format are publication dates. Classifications may be US or foreign.

U.S. Patent and Trademark Office
PTO-892 (Rev. 01-2001) Notice of References Cited Part of Paper No.
Delete Last PagelAdd A PageAuto-Fill