Source: https://patents.google.com/patent/US7187769
Timestamp: 2018-02-25 04:11:33
Document Index: 651469156

Matched Legal Cases: ['art 11', 'art 12', 'art 2', 'art 11', 'art 13', 'art 13', 'art 14', 'art 14', 'art 14', 'art 14', 'art 14', 'art 14', 'art 14', 'art 15', 'art 16', 'art 17', 'art 11', 'arts 14', 'art 14', 'art 11']

US7187769B1 - Method and apparatus for evaluating the strength of an encryption - Google Patents
US7187769B1
US7187769B1 US09463907 US46390799A US7187769B1 US 7187769 B1 US7187769 B1 US 7187769B1 US 09463907 US09463907 US 09463907 US 46390799 A US46390799 A US 46390799A US 7187769 B1 US7187769 B1 US 7187769B1
US09463907
BEST MODE FOF CARRYING OUT THE INVENTION Embodiment According to a First Aspect of the Present Invention
In FIG. 1 there is depicted the functional configuration of an embodiment of each of the random function generating apparatus and the function randomness evaluating apparatus according to the present invention. An input part 11 inputs therethrough data and a parameter that are needed to generate a candidate function in a candidate function generating part 12. The candidate function generating part 2 generates a candidate function based on the input provided through the input part 11, and provides its parameter value, the input value and the calculation result (an output value) to a storage part 13. Various pieces of data thus stored in the storage part 13 are read out therefrom and fed to a differential-cryptanalysis resistance evaluating part 14 a, a linear-cryptanalysis resistance evaluating part 14 b, a higher-order-differential-attack resistance evaluating part 14 c, an interpolation-attack resistance evaluating part 14 d, a partitioning-attack resistance evaluating part 14 e, a differential-linear-attack resistance evaluating part 14 f, and a criteria evaluating part 14 g for evaluating other criteria. Based on the results of evaluations made in the respective evaluating parts, candidate functions of high resistance to the attacks are selected in a function select part 15 and stored in a storage part 16, from which a required one of the candidate functions is read out and provided to the outside via an output part 17.
In the function randomness evaluating apparatus according to the present invention, the functions to be evaluated are provided via the input part 11 to the respective evaluating parts 14 a to 14 g for the evaluation of their randomness.
λS(Γx,Γy)=|2×#{xε(2)n |x·Γx=S(x)·Γy}−22| (4)
y j =x 0 +x 1 x 3 +x 0 x 2 x 3 + . . . +x 1 x 4 x 5 x 6 . . . x N (6)
S-box S:GF(2)n →GF(2)m ;x
x=(x n−1 ,x n−2 , . . . ,x 0)εGF(2)n, (7b)
y=(y m−1 ,y m−2 , . . . ,y 0)εGF(2)m (7c)
Si :GF(2)n →GF(2);x
Si(x) (8)
y=fk(x)=cq−1 x q−1+cq−2 x q−2+ . . . +cj x j+ . . . +c1 x 1+c0 x 0 (10)
S:GF(2)n →GF(2)n :x→x 2k in GF(2n) (16a)
S:GF(2)n →GF(2)n :x→x 2k+1 in GF(2n) (16a)
S:GF(2)8 →GF(2)8 ;x
A((P(x,e)),a,b)
P(x,e)=x e in GF(28) (17)
Step S2: Evaluate whether candidate functions S are bijective or not. When the parameter a is an odd number and the parameter e is prime relative to 28−1 (which parameter is expressed by (e,255)=1), the functions S are bijective; select those of the parameters which satisfy these conditions, and discard candidates which do not satisfy them. This processing is performed in the criteria evaluating part 14 g in FIG. 1. Alternatively, the parameter a is obtained by inputting only an odd number in the input part 11.
(c) evaluating the resistance of each of said candidate functions to a cryptanalysis based on the output values stored in said storage means, and selectively outputting candidate function highly resistant to said cryptanalysis; and
wherein said step (c) comprising:
(c-2) a differential-linear cryptanalysis resistance evaluating step of: calculating, for every set of input difference value Δx and output mask value Γy of each candidate function S(x), a number of input values x for which the inner product of (S(x)+S(x+Δx)) and said output mask value Γy is 1; evaluating resistance of said candidate function to differential-linear cryptanalysis based on the result of said calculation; and leaving those of said candidate functions whose resistance is higher than a predetermined second reference and discarding the others;
(c-3) a partitioning-cryptanalysis resistance evaluating step of: dividing all input values of each candidate function and the corresponding output values into input subsets and output subsets; calculating an imbalance of the relationship between the input subset and the output subset with respect to their average corresponding relationship; evaluating the resistance of said each candidate function to said partitioning cryptanalysis based on the result of said calculation; and leaving those of said candidate functions whose resistance is higher than a predetermined third reference and discarding the others; and
(c-4) an interpolation-cryptanalysis resistance evaluating step of: expressing an output value y as y=fk(x) for an input value x and a fixed key k using a polynomial over Galois field which is composed of elements equal to a prime p or a power of said prime p; counting a number of terms of said polynomial; evaluating the resistance of said candidate function to interpolation cryptanalysis; and leaving those of said candidate functions whose resistance is higher than a predetermined fourth reference and discarding the others;
wherein said candidate functions are each a composite function composed of first and second functions of different algebraic structures, at least one of said first and second functions being resistant to said differential cryptanalysis and said linear cryptanalysis.
said differential-linear-cryptanalysis resistance evaluating step (c-2) includes a step of: calculating the following equation for every set of said input difference value Δx except 0 and said output mask value Γy except 0
ξS(Δx,Γy)=|2×#{xεGF(2)n|(S(x)+S(x+Δx))·Γy=1}−2n|;
said partitioning cryptanalysis resistance evaluating step (3) includes a step of dividing an input value set F and an output value set G of said candidate function into u input subsets {F0, F1, . . . , Fu−1} and v output subsets {G0, G1, . . . , Gv−1}; for each partition-pair (Fi, Gi) (i=0, . . . , u−1; j=0, 1, . . . , v−1), calculating a maximum one of probabilities that all output values y corresponding to all input values x of the input subset F1 belong to the respective output subsets Gj (j=0, . . . , v−1); calculating a measure IS(F, G) of an average imbalance of a partition-pair (F, G) based on all maximum values calculated for all partition pairs; and evaluating the resistance of said candidate function to said partitioning cryptanalysis based on said measure.
(c) evaluating resistance of each of said candidate functions to a cryptanalysis based on the output values stored in said storage means, and selectively outputting candidate function highly resistant to said cryptanalysis; and
(c-1) a higher-order cryptanalysis resistance evaluating step of calculating a minimum value of the degree of a Boolean polynomial for input bits of each of said candidate functions by which its output bits are expressed, evaluating the resistance of said each candidate function to higher order cryptanalysis based on the result of said calculation; and leaving those of said candidate functions whose resistance is higher than a predetermined first reference and discarding the others;
wherein said candidate functions are each a composite function composed of first and second functions of different algebraic structures, at least one of said first and second function being resistant to said differential cryptanalysis and said linear cryptanalysis.
said differential-linear-cryptanalysis resistance evaluating step (c-2) includes a step of: calculating the following equation for every set of said input difference Δx except 0 and said output mask value Γy except 0
said partitioning cryptanalysis resistance evaluating step (3) includes a step of dividing an input value set F and an output value set G of said candidate function into u input subsets {F0, F1, . . . , Fu−1} and v output subsets {G0, G1, . . . , Gv−1}; for each partition-pair (Fi, Gi) (i=0, . . . , u−1; j=0, 1, . . . , v−1), calculating a maximum one of probabilities that all output values y corresponding to all input values x of the input subset Fi belong to the respective output subsets Gj (j=0, . . . , v−1); calculating a measure IS(F, G) of an average imbalance of a partition-pair (F, G) based on all maximum values calculated for all partition pairs; and evaluating the resistance of said candidate function to said partitioning cryptanalysis based on said measure.
US09463907 1998-06-02 1999-06-01 Method and apparatus for evaluating the strength of an encryption Expired - Fee Related US7187769B1 (en)
US7187769B1 true US7187769B1 (en) 2007-03-06
US09463907 Expired - Fee Related US7187769B1 (en) 1998-06-02 1999-06-01 Method and apparatus for evaluating the strength of an encryption
JPH11212452A (en) * 1998-01-27 1999-08-06 Nec Corp Cryptographic robustness evaluation support device and machine readable record medium recorded with program
Bruce Schneier. Applied Cryptography. 1996. John Wiley & Sons, Inc. 2<SUP>nd </SUP>Edition. p. 349-351. *
Carlo Harpes. Partitioning Cryptanalysis. Mar. 23, 1995. p. 1-30. *
Francois-Xazier Standaert et al. Cyrptanalysis of Block Ciphers: A Survey. 2003. Universite catholique de Louvain. *
Hamade, Takeshi, et al., "On Partitioning Cryptanalysis of DES," Telecommunications Advancement Organization of Japan, SCIS '98, 2.2A, Jan. 1998, pp. 1-8.
Kaisa Nyberg. Differentially Uniform Mappings for Cryptography. Advances in Cryptology-Eurocrypt '93 Proceedings, Springer-Verlag. 1994. pp. 55-64. *
Kanda, Masayuki, et al., "A Round Function Structure Consisting of Few S-boxes (Part II)," Telecommunications Advancement Organization of Japan, SCIS '98, 2.2.D. Jan. 1998, pp. 1-8.
Langford, S.K., and Hellman, M.E., "Differential-Linear Cryptanalysis," Lecture Notes in Computer Science, Advances in Cryptology CRYPTO '94, vol. 839, 1994, pp. 17-25.
Lars R. Knudsen. Block Cipher-Analysis, Design and Application. Jul. 1, 1994. p. 53-143. *
Lars R. Kundsen. Block Cipher-A Survey. 1997. p. 18-45. *
Lars R. Kundsen. Block Cipher-Analysis, Design and Application. Jul. 1, 1994. p. 53-143. *
Moriai, Shiho, et al., "S-box Design Considering the Security Against Known Attacks on Block Ciphers," Technical Report of the IEICE, ISEC98-13, vol. 98, No. 227, Jul. 30, 1998, pp. 25-32.
Sakurai, Kouichi, "Angou riron no kiso," Kyoritsu Shuppan, pp. 69-72, 1996.
Shiho Moriai, "How to Design Secure S-boxes against Differential, Linear, Higher Order Differential, and Interpolation Attacks," Telecommunications Advancement Organization of Japan, SCIS '98, 2.2C, Jan. 1998, pp. 1-8.
Susan K. Langford et al. Differential-Linear Cryptanalysis. 1994. Springer-Verlag Berlin Heidelberg. p. 17-25. *
Thomas Jakobsen et al. the Interpolation Attack on Block Ciphers. *
Thomas Jakobsen et al. The Interpolation Attack on Block Ciphers. 1996. *
Vincent Rijmen et al. The Cipher Shark. Fast Software Encryption, LNCS 1039. 1996. p. 99-111. *
Xuejia Lai et al. Markov Ciphers and Differential Cryptanalysis. 1998. Springer-Verlag. p. 17-38. *
Yasuyoshi Kaneko et al. On Provable Security against Differential and Linear Cryptanalysis in Generalized Feistel Ciphers with Multiple Random Functions. 1997. p. 185-199. *
Yulian Zheng et al. On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypothesis. 1998. Springer-Verlag. *
Fujie et al. 1997 Semidefinite programming relaxation for nonconvex quadratic programs
Barak et al. 2001 On the (im) possibility of obfuscating programs
Shoup 2004 Sequences of games: a tool for taming complexity in security proofs.
Applebaum et al. 2010 Public-key cryptography from different assumptions
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MORIAI, SHIHO;AOKI, KAZUMARO;KANDA, MSAYUKI;AND OTHERS;REEL/FRAME:010634/0179