2015
7
2
2
0
Computationally secure multiple secret sharing: models, schemes, and formal security analysis
2
2
A multisecret sharing scheme (MSS) allows a dealer to share multiple secrets among a set of participants. in such a way a multisecret sharing scheme (MSS) allows a dealer to share multiple secrets among a set of participants, such that any authorized subset of participants can reconstruct the secrets. Up to now, existing MSSs either require too long shares for participants to be perfect secure, or do not have a formal security analysis/proof. In 2013, Herranz et al. provided the first formal definition of computational security for multistage secret sharing scheme (MSSS) in the standard model and proposed a practical and secure scheme. As far as we know, their scheme is the only computationally secure MSS in the standard model, and there is no formal definition of the computational security for other categories of MSSs. Based on this motivation, in this paper, we define the first formal model of indistinguishability against the chosen secret attacks (CSA) for other types of MSSs in the standard model. Furthermore, we present two practical CSAsecure MSSs, belonging to different types of MSSs and enjoying the advantage of short shares. They are also provably secure in the standard model. Based on the semantic security of the underlying encryption schemes, we prove the security of our schemes.
1

91
99


S.
Mashhadi
Iran
smashhadi@iust.ac.ir
Multisecret Sharing Scheme
Multistage Secret Sharing Scheme
Provable Security
Privatekey Cryptosystem
Standard Model
[[1] M. Bellare, A. Boldyreva, S. Micali, Publickey encryption in a multiuser setting: Security proofs and improvements, in: Proceeding of Eurocrypt'00, in: LNCS, 1807, SpringerVerlag, 2000, pp. 259274. ##[2] M. Bellare, A. Desai, E. Jokipii, P. Rogaway, A concrete security treatment of symmetric encryption, in: FOCS'97, IEEE Society Press, 1997, pp. 394403. ##[3] M. Bellare, P. Rogaway, Introduction to modern cryptography, Notes for the course CSE207 of the University of California, San Diego, available at http://cseweb.ucsd.edu/classes/sp99/cse207/index.html, visited at November 2012. ##[4] C. Cachin, Online secret sharing, in Proceedings of IMA Conference'95, in: LNCS, 1025, SpringerVerlag, 1995, pp. 190198. ##[5] T.Y. Chang, M. S. Hwang, W. P.Yang, A new multistage secret sharing scheme using oneway function, ACM SIGOPS Operating Systems, 39, 2005, pp. 4855. ##[6] H.Y. Chien, J.K. Jan, Y.M. Tseng, A practical (t, n) multisecret sharing scheme, IEICE Transactions on Fundamentals of Electronics, Communications and Computer 83A, 12, 2000, pp. 27622765. ##[7] M. H. Dehkordi, S. Mashhadi, New efficient and practical verifiable multisecret sharing schemes, Information Sciences 178, 9, 2008, pp. 22622274. ##[8] J. He, E. Dawson, Multistage secret sharing based on oneway function, Electronics Letters 30, 19, 1994, pp. 15911592. ##[9] J. Herranz, A. Ruiz, G. Sáez, Sharing many secrets with computational provable security, Information Processing Letters 113, 2013, pp. 572579. ##[10] C. Hu, X. Liao, X. Cheng, Verifiable multisecret sharing based on LFSR sequences, Theoret. Commun. Sci. 445, 2012, pp. 5262. ##[11] M. Karchmer, A. Wigderson, On Span Programs, in: Proceeding of SCTC'93, IEEE Computer Society Press, 1993, pp. 102111. ##[12] J. Katz, Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC, New York, 2008. ##[13] J. Katz, M. Yung, Characterization of security notions for probabilistic privatekey encryption, Journal of Cryptology, 19, 2006, pp. 6795. ##[14] H. Krawczyk, Secret sharing made short, in: Proceedings of Crypto'93, in LNCS, 773, SpringerVerlag, 1993, pp. 136146. ##[15] H. X. Li, C. T. Cheng, L. J. Pang, An improved Multistage (t, n)threshold secret sharing scheme, LNCS 3739, 2005, pp. 267274. ##[16] H. Y. Lin, Y. S. Yeh, Dynamic multisecret sharing scheme, Int. J. Contemp. Math. Sciences, 3, 2008, pp. 3742. ##[17] S. Mashhadi, M. Hadian Dehkordi, Two verifiable multi secret sharing schemes based on nonhomogeneous linear recursion and LFSR publickey cryptosystem, Information Sciences 294, 2015, pp. 3140. ##[18] B. Masucci, Sharing multiple secret: Models, schemes and analysis, Designs, Codes and Cryptography, 39, 2006, pp. 89111. ##[19] A. Shamir, How to share a secret, Communications of the ACM. 22, 1979, pp. 612613. ##[20] C.C. Yang, T.Y. Chang, M.S. Hwang, A (t, n) multisecret sharing scheme, Applied Mathematics and Computation 151, 2004, pp. 483490.##]
Efficient implementation of low time complexity and pipelined bitparallel polynomial basis multiplier over binary finite fields
2
2
This paper presents two efficient implementations of fast and pipelined bitparallel polynomial basis multipliers over GF (2m) by irreducible pentanomials and trinomials. The architecture of the first multiplier is based on a parallel and independent computation of powers of the polynomial variable. In the second structure only even powers of the polynomial variable are used. The parallel computation provides regular and lowcost structure with low critical path delay. In addition, the pipelining technique is applied to the proposed structures to shorten the critical path and to perform the computation in two clock cycles. The implementations of the proposed methods over the binary extension fields GF (2163) and GF (2233) have been successfully verified and synthesized using Xilinx ISE 11 by Virtex4, XC4VLX200 FPGA.
1

101
114


B.
Rashidi
Iran
b.rashidi@ec.iut.ac.ir


R.
Rezaeian Farashahi
Iran
farashahi@cc.iut.ac.ir


S. M.
Sayedi
Iran
m_sayedi@cc.iut.ac.ir
Bitparallel Multiplier
Elliptic Curve Cryptography
Trinomials
Pentanomials
Pipelining
[[1] Arash ReyhaniMasoleh, "A New BitSerial Architecture for Field Multiplication Using Polynomial Bases", Cryptographic Hardware and Embedded SystemsCHES 2008, Vol. 5154, pp. 300314. ##[2] CheWun Chiou and HueyLin Jeng, "Parallel Algorithm for Polynomial Basis Multiplier in GF(2m) Fields", Tamkang Journal of Science and Engineering, Vol. 11, No. 2, 2008, pp. 211218. ##[3] XIE Jiafeng, HE Jianjun, GUI Weihua, "Low latency systolic multipliers for finite field GF(2m) based on irreducible polynomials", Journal of Central South University, Vol. 19, Iss. 5, 2012, pp. 12831289. ##[4] Huapeng Wu, "BitParallel Finite Field Multiplier and Squarer Using Polynomial Basis", IEEE Transactions on Computers, Vol. 51, No. 7, July 2002, pp. 750758. ##[5] Eduardo CuevasFarfan, Miguel MoralesSandoval, Alicia MoralesReyes, Claudia FeregrinoUribe, Ignacio AlgredoBadillo, Paris Kitsos, René Cumplido, "KaratsubaOfman Multiplier with Integrated Modular Reduction for GF(2m)", Advances in Electrical and Computer Engineering, Vol. 13, No. 2, 2013, pp. 310. ##[6] M. Elia, M. Leone and C. Visentin, "Low complexity bitparallel multipliers for GF (2m) with generator polynomial P(x) = xm + xk + 1", Electronics Leters 1st April 1999 Vol. 35 No. 7, pp. 551552. ##[7] Nam Su Chang, Chang Han Kim, YoungHo Park, and Jongin Lim, "A Nonredundant and Efficient Architecture for KaratsubaOfman Algorithm", Proceedings of the 8th International Conference on Information Security (ISC), Singapore, September 2023, SpringerVerlag Berlin Heidelberg, Vol. 3650, 2005, pp. 288299. ##[8] Mario Alberto GarcíaMartínez, Rubén Posada Gómez, Guillermo MoralesLuna and Francisco RodríguezHenríquez, "FPGA Implementation of an Efficient Multiplier over Finite Fields GF(2m)", Proceedings of the IEEE International Conference on Reconfigurable Computing and FPGAs, 2005, pp.2126. ##[9] Chester Rebeiro and Debdeep Mukhopadhyay, "Hybrid Masked Karatsuba Multiplier for GF (2233)", 11th IEEE VLSI Design and Test Symposium, Kolkata, August 2007. ##[10] Che Wun Chiou and Liuh Chii Lin, "Fast Array Multiplications over GF (2m) Fields with Multiple Speeds", Tamkang Journal of Science and Engineering, Vol. 7, No 3, 2004 , pp. 139144. ##[11] Junfeng Fan and Ingrid Verbauwhede, "A DigitSerial Architecture for Inversion and Multiplication in GF(2m)", IEEE Workshop on Signal Processing Systems, 810 Oct. 2008, pp. 712. ##[12] Lejla Batina, Nele Mentens, Sıddıka Berna Ors, Bart Preneel, "Serial Multiplier Architectures over GF(2m) for Elliptic Curve Cryptosystems", 12th IEEE Electro technical Conference, Vol.2 2004, pp. 779782. ##[13] JengShyang Pan, ChiouYng Lee and Pramod Kumar Meher, "LowLatency DigitSerial and DigitParallel Systolic Multipliers for Large Binary Extension Fields", IEEE Transactions on Circuits and Systems I: Regular Papers, Dec. 2013, pp. 31953204. ##[14] Nazar A. Saqib, Francisco RodriguezHenriquez and Arturo DiazPerez, "A Parallel Architecture for Fast Computation of Elliptic Curve Scalar Multiplication over GF (2m)" 18th International Parallel and Distributed Processing Symposium, 2630 April 2004. ##[15] George N. Selimis, Apostolos P. Fournaris, Harris E. Michail, Odysseas Koufopavlou, "Improved throughput bitserial multiplier for GF(2m) fields", Integration, the VLSI Journal 42, 2009, pp. 217226. ##[16] CheWun Chiou, ChiouYng Lee and JimMin Lin, "Finite Field Polynomial Multiplier with Linear Feedback Shift Register", Tamkang Journal of Science and Engineering, Vol. 10, No. 3, 2007, pp. 253264. ##[17] ChiouYng Lee, Che Wun Chiou , JimMin Lin, "Lowcomplexity bitparallel dual basis multipliers using the modified Booths algorithm", Computers and Electrical Engineering Vol. 31, 2005, pp. 444459. ##[18] Ali Zakerolhosseini, Morteza Nikooghadam, "Lowpower and highspeed design of a versatile bitserial multiplier in finite fields GF (2m)", Integration, the VLSI Journal Vol. 46, 2013, pp. 211217. ##[19] C. Grabbe, M. Bednara, J. Teich, J. von zur Gathen, J. Shokrollahi "FPGA Designs of Parallel High Performance GF(2233) Multipliers" International Symposium on Circuits and Systems, 2003, Vol. 2, pp. 268271. ##[20] Yin Li, Gongliang Chen, Xiaoning Xie: "Low complexity bitparallel GF (2m) multiplier for allone polynomials", IACR Cryptology ePrint Archive 2012: 414 (2012). ##[21] Haining Fan, Jiaguang Sun, Ming Gu and KwokYan Lam, "Overlapfree KaratsubaOfman Polynomial Multiplication Algorithms", IET Information security, Vol. 4, No. 1, 2010, pp. 814. ##[22] Sameh M. Shohdy, Ashraf B. ElSisi, and Nabil Ismail, "Hardware Implementation of Efficient Modified Karatsuba Multiplier Used in Elliptic Curves", International Journal of Network Security, Vol. 11, No. 3, Nov. 2010, pp.155162. ##[23] Mohammed Benaissa and Wei Ming Lim, "Design of Flexible GF(2m) Elliptic Curve Cryptography Processors", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 14, No. 6, June 2006, pp. 659662. ##[24] Arash ReyhaniMasoleh, and M. Anwar Hasan, "Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF (2m)", IEEE Transactions on Computers, Vol. 53, No. 8, August 2004, pp. 945959. ##[25] ChiouYng Lee, ChinChin Chen,YuanHo Chen and ErlHuei Lu, "LowComplexity BitParallel Systolic Multipliers over GF(2m)", IEEE International Conference on Systems, Man, and Cybernetics, 2006, pp. 16. ##[26] Gang Zhou, Harald Michalik, and László Hinsenkamp, "Complexity Analysis and Efficient Implementations of Bit Parallel Finite Field Multipliers Based on KaratsubaOfman Algorithm on FPGAs", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 18, No. 7, July 2010, pp. 10571066. ##[27] Haining Fan and M. Anwar Hasan, "A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields", IEEE Transactions on Computers, Vol. 56, No. 2, February 2007, pp. 224233. ##[28] Miguel MoralesSandoval, Claudia FeregrinoUribe, René Cumplido, Ignacio AlgredoBadillo, "An area/performance tradeoff analysis of a GF(2m) multiplier architecture for elliptic curve cryptography", Computers and Electrical Engineering, Vol. 35, 2009, pp. 5458. ##[29] Huapeng Wu, "BitParallel Finite Field Multiplier and Square Using Polynomial Basis", IEEE Transactions Computers, Vol. 51, 2002, pp. 750758. ##[30] Lee, C. Y., Lu, E. H. and Lee, J. Y., "BitParallel Systolic Multipliers for GF (2m) Fields Defined by AllOne and EquallySpaced Polynomials," IEEE Transactions Computers, Vol. 50, 2001, pp. 385393. ##[31] Lee, C. Y., "Low Complexity BitParallel Systolic Multiplier Over GF (2m) Using Irreducible Trinomials," IEE Proc. Comput. Digit. Tech., Vol. 150, 2003, pp. 3942. ##[32] Bahram Rashidi, Reza Rezaeian Farashahi, Sayed Masoud Sayedi, "Highspeed and Pipelined Finite Field BitParallel Multiplier over GF(2m) for Elliptic Curve Cryptosystems", Proceedings of the 11th International ISC Conference on Information Security and Cryptology (ISCISC), 34 Sept. 2014, pp. 1520. ##[33] G. Zhou, L. Li, and H. Michalik, "Area optimization of bit parallel finite field multipliers with fast carry logic on FPGAs", Proceedings of the International Conference on Field Program. Logic and Applications (ICFPL), Sep. 2008, pp. 671674. ##[34] W. N. Chelton and M. Benaissa, "Fast elliptic curve cryptography on FPGA," IEEE Transactions Very Large Scale Integration (VLSI) System, Vol. 16, No. 2, Feb. 2008, pp. 198205. ##[35] F. RodríguezHenríquez, N. A. Saqib, and N. CruzCortés, "A fast implementation of multiplicative inversion over GF(2m)", in Proceedings of the International Conference on Inf. Technol.: Coding Computer, 2005, pp. 574579. ##[36] Reza Azarderakhsh, Arash ReyhaniMasoleh, "LowComplexity Multiplier Architectures for Single and HybridDouble Multiplications in Gaussian Normal Bases", IEEE Transactions on Computers, Vol. 62, No. 4, April 2013, pp. 744757. ##[37] Arash ReyhaniMasoleh, "Efficient Algorithms and Architectures for Field Multiplication Using Gaussian Normal Bases," IEEE Transactions Computers, Vol. 55, No. 1, Jan. 2006, pp. 3447. ##[38] A.H. Namin, H. Wu, and M. Ahmadi, "A WordLevel Finite Field Multiplier Using Normal Basis," IEEE Transactions Computers, Vol. 60, No. 6, June 2010, pp. 890895. ##[39] Arash ReyhaniMasoleh and M.A. Hasan, "A New Construction of MasseyOmura Parallel Multiplier over GF (2m)" IEEE Transactions Computers, Vol. 51, No. 5, May 2002, pp. 511520. ##[40] C. K. Koç and B. Sunar, "An Efficient Optimal Normal Basis Type II Multiplier over GF (2m)" IEEE Transactions Computers, Vol. 50, No. 1, Jan. 2001, pp. 8387. ##[41] Arash ReyhaniMasoleh, M. Anwar Hasan, "Low Complexity WordLevel Sequential Normal Basis Multipliers", IEEE Transactions on Computers, Vol. 54, No. 2, Feb. 2005, pp.98110. ##[42] Arash ReyhaniMasoleh, M. Anwar Hasan, "Efficient DigitSerial Normal Basis Multipliers over Binary Extension Fields", ACM Transactions on Embedded Computing Systems, Vol. 3, No. 3, August 2004, pp. 575592. ##[43] JennShyong Horng, IChang Jou, ChiouYng Lee, "Lowcomplexity multiplexerbased normal basis multiplier over GF(2m)", Journal of Zhejiang University Science A, 2009 Vol. 10, No.6, pp. 834842. ##[44] Huapeng Wu, "BitParallel Polynomial Basis Multiplier for New Classes of Finite Fields", IEEE Transactions on Computers, Vol. 57, No. 8, August 2008, pp. 10231031. ##[45] M. Nikooghadam, A. Zakerolhosseini, "Utilization of Pipeline Technique in AOP Based Multipliers with Parallel Inputs", Journal of Signal Processing Systems, Vol. 72, No. 1, pp. 5762. ##]
EEH: AGGHlike public key cryptosystem over the eisenstein integers using polynomial representations
2
2
GGH class of publickey cryptosystems relies on computational problems based on the closest vector problem (CVP) in lattices for their security. The subject of lattice based cryptography is very active and there have recently been new ideas that revolutionized the field. We present EEH, a GGHLike public key cryptosystem based on the Eisenstein integers Z [ζ3] where ζ3 is a primitive cube root of unity. EEH applies representations of polynomials to the GGH encryption scheme and we discuss its key size and parameters selection. We also provide theoretical and experimental data to compare the security and efficiency of EEH to GGH with comparable parameter sets and show that EEH is an improvement over GGH in terms of security and efficiency.
1

115
126


R.
Ebrahimi Atani
Iran
rebrahimi@guilan.ac.ir


Sh.
Ebrahimi Atani
Iran
ebrahimi@guilan.ac.ir


A.
Hassani Karbasi
Iran
amirhassanikarbasi@gmail.com
Latticebased Cryptography
Publickey Cryptosystem
GGH
Dedekind Domain
Polynomial Representation
[[1] V. Lyubashevsky, and D. Micciancio, Generalized compact knapsacks are collision resistant, In Proceedings of ICALP, (2006), Vol. 4052 of LNCS, pages 144155. ##[2] C. Peikert, and A. Rosen, Lattices that admit logarithmic worstcase to averagecase connection factors, In Proceedings of STOC, ACM, (2007), pages 478487. ##[3] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of ACM, (2009), Vol. 56, pages 634. ##[4] C. Peikert, and B. Waters, Lossy trapdoor functions and their applications, In Proceedings of STOC, (2008), pages 187196. ##[5] V. Lyubashevsky, A. Palacio, and G. Segev, Publickey cryptographic primitives provably as secure as subset sum, In D. Micciancio, editor, Proceedings of TCC, (2010), Vol. 5978 of LNCS, pages 382400. ##[6] C. Gentry, C. Peikert, and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, In Proceedings of STOC, (2008), pages 197206. ##[7] V. Lyubashevsky, and D. Micciancio, Asymptotically efficient latticebased digital signatures, In Proceedings of TCC, (2008), Vol. 4948 of LNCS, pages 3754. ##[8] D. Gordon, J. Katz, and V. Vaikuntanathan, A group signature scheme from lattice assumptions, Advances in CryptologyASIACRYPT, (2010), Springer Berlin Heidelberg, pages 395412. ##[9] S. Agrawal, D. Boneh, and X. Boyen, Lattice basis delegation in fixed dimension and shorterciphertext hierarchical ibe, Advances in Cryptology CRYPTO, (2010), Springer Berlin Heidelberg, pages 98115. ##[10] C. Gentry, S. Halevi, and V. Vaikuntanathan, A simple bgntype cryptosystem from lwe, In H. Gilbert, editor, Advances in Cryptology EUROCRYPT, (2010), Vol. 6110 of Lecture Notes in Computer Science, pages 506522. ##[11] C. Gentry, Fully homomorphic encryption using ideal lattices, In Proceedings of STOC, ACM, (2009), pages 169178. ##[12] D. Stehle, and R. Steinfeld, Faster fully homomorphic encryption, In M. Abe, editor, ASIACRYPT, (2010), Vol. 6477 of Lecture Notes in Computer Science, pages 377394. ##[13] N. Ogura, G. Yamamoto, T. Kobayashi, and S. Uchiyama, An improvement of key generation algorithm for gentrys homomorphic encryption scheme, In IWSEC, (2010), Vol. 6434 of LNCS, pages 7083. ##[14] P. Cayrel, R. Lindner, M. Ruckert, and R. Silva, Improved zeroknowledge identification with lattices, Tatra Mountains Mathematical Publications 53.1 (2012), pages 3363. ##[15] V. Lyubashevsky, Latticebased identification schemes secure under active attacks, In Proceedings of PKC, (2008), No. 4939 in LNCS, pages 162179. ##[16] P. Gaborit, J. Ohler, and P. Sole, CTRU, a polynomial analogue of NTRU, Technical report, INRIA, France, 2002. Available at ftp://ftp.inria.fr/INRIA/publication/ publipdf/RR/RR4621.pdf. ##[17] M. Coglianese, and B.M. Goi, MaTRU: A New NTRUBased Cryptosystem, In Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT), (2005), pages 232243. ##[18] N. Vats, NNRU, a Noncommutative Analogue of NTRU, The Computing Research Repository (CoRR), abs/0902.1891, (2009). Available at; http://arxiv.org/abs/0902.1891. ##[19] R. Kouzmenko, Generalizations of the NTRU Cryptosystem, Master's thesis, Polytechnique Montreal, Canada, (2006). ##[20] C. Karimianpour, LatticeBased Cryptosystems, Master's thesis, University of Ottawa, Canada, (2007). ##[21] M. Nevins, C. Karimianpour, and A. Miri, NTRU over rings beyond Z, Designs, Codes and Cryptography, (2010), vol. 56, no. 1, pages 6578. ##[22] E. Malekian, A. Zakerolhosseini, and A. Mashatan, QTRU: Quaternionic Version of the NTRU PublicKey Cryptosystems, The int'l Journal of information Security (ISeCure), (2011), vol. 3, no. 1, pages 2942. ##[23] A.H. Karbasi and R.E. Atani, ILTRU: An NTRULike Public Key Cryptosystem Over Ideal Lattices, The 7th International IEEE Symposium on Telecommunications (IST2014), Tehran, Iran, (2014). ##[24] O. Goldreich, Sh. Goldwasser, and Sh. Halevi, Publickey cryptosystems from lattice reduction problems, In CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, London, UK, (1997), pages 112131. ##[25] R.J. McEliece, A publickey cryptosystem based on algebraic coding theory, Deep Space Network Progress Report, (1978), No. 44, pages 114116. ##[26] P. Nguyen, Cryptanalysis of the GoldreichGoldwasserHalevi Cryptosystem from Crypto '97, Advances in CryptologyCrypto '99, LNCS 1666, (1999), pages 288304. ##[27] D. Micciancio, Improving lattice based cryptosystems using the Hermite normal form, In Cryptography and Lattices Conference (CaLC), (2001), pages 126145. ##[28] M. Ajtai, and C. Dwork, A PublicKey Cryptosystem with WorstCase/AverageCase Equivalence, In 29th ACM Symposium on Theory of Computing, (1997), pages 284293. ##[29] C.P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci., (1987), No. 53(23), pages 201224. ##[30] S. Paeng, B. Jung, and K. Ha, A Lattice Based Public Key Cryptosystem Using Polynomial Representations, In Y.G. Desmedt (Ed.), PKC, (2003), Vol. 2567 of LNCS, Springer, pages 292308. ##[31] K. Jarvis, and M. Nevins, ETRU: NTRU over the Eisenstein Integers, Designs, Codes and Cryptography 74.1, (2015), pages 219242. ##[32] K. Ireland, and M. Rosen, A Classical Introduction to Modern Number Theory, Second Edition. New York: SpringerVerlag, (1990). ##[33] J. Hoffstein, J. Pipher, and J.H. Silverman, An Introduction to Mathematical Cryptography, SpringerVerlag, 1st edition, (2008). ##[34] J. Hoffstein, N. HowgraveGraham, J. Pipher, J.H. Silverman, and W. Whyte, NTRU Sign: digital signatures using the NTRU lattice, In Topics in cryptology CTRSA, (2003), Vol. 2612 of Lecture Notes in Comput. Sci., Springer, pages 122140. ##[35] J.H. Silverman, HighSpeed Multiplication of (Truncated) Polynomial Rings, NTRU Cryptosystems Technical Report 11, (1999), Available from: http://www.ntru.com. Accessed: Dec 2010. ##[36] G. Bourgeois, and J. Faugere, Algebraic attack on NTRU using Witt vectors and Grobner bases, In Journal of Math. Crypt., (2009), Vol. 3, pages 205214. ##[37] V. Shoup, NTL: A Library for doing Number Theory, http://www.shoup.net/ntl/. Accessed: Aug. (2010). ##[38] J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU: a ringbased public key cryptosystem, In Algorithmic Number Theory, Portland OR, (1998), Vol. 1423 of Lecture Notes in Comput. Sci., pages 267288. ##[39] A.H. Karbasi and R.E. Atani, "PSTRU: A provably secure variant of NTRU Encrypt over extended ideal lattices," The 2nd National Industrial Mathematics Conference, Tabriz, Iran, (2015). ##]
Cryptanalysis of some first round CAESAR candidates
2
2
ΑΕS _ CMCCv₁, ΑVΑLΑNCHEv₁, CLΟCv₁, and SILCv₁ are four candidates of the first round of CAESAR. CLΟCv₁ is presented in FSE 2014 and SILCv₁ is designed upon it with the aim of optimizing the hardware implementation cost. In this paper, structural weaknesses of these candidates are studied. We present distinguishing attacks against ΑES _ CMCCv₁ with the complexity of two queries and the success probability of almost 1, and distinguishing attacks on CLΟCv₁ and SILCv₁ with the complexity of Ο (2n/2) queries and the success probability of 0.63, in which n is bit length of message blocks. In addition, a forgery attack is presented against ΑVΑLΑNCHEv₁ which requires only one query and has the success probability of 1. The attacks reveal weaknesses in the structure of these first round candidates and inaccuracy of their security claims.
1

127
134


J.
Alizadeh
Iran
alizadja@gmail.com


M. R.
Aref
Iran
aref@sharif.edu


N.
Bagheri
Iran
nbagheri@srttu.edu


H.
Sadeghi
Iran
sadeghihassan64@gmail.com
Authenticated Encryption
CAESAR
ΑES _ CMCCv₁
ΑVΑLΑNCHEv₁
CLΟCv₁
SILCv₁
Distinguishing Attack
Forgery Attack
[[1] Mihir Bellare and Chanathip Namprempre. Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm. J. Cryptology, 21(4):469491, 2008. ##[2] Shengbao Wu, Hongjun Wu, Tao Huang, Mingsheng Wang, and Wenling Wu. LeakedStateForgery Attack Against The Authenticated Encryption Algorithm ALE. ASIACRYPT 2013, 2013. ##[3] CAESAR. CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness, 2013. http://competitions.cr.yp. to/caesar.html. ##[4] Farzaneh Abed, Christian Forler, and Stefan Lucks. Classification of the CAESAR Candidates. IACR Cryptology ePrint Archive, 2014. ##[5] Jonathan Trostle. AESCMCC v1. CEASAR Cryptographic Competitions, 2014. http://http://competitions.cr.yp.to/ round1/aescobrav1.pdf. ##[6] Basel Alomair. AVALANCHEv1. CEASAR Cryptographic Competitions, 2014. http://competitions.cr.yp.to/round1/avalanchev1.pdf. ##[7] Basel Alomair. AVALANCHEv1. CAESAR mailing list, 2014. ##[8] Tetsu Iwata, Kazuhiko Minematsu, Jian Guo, and Sumio Morioka. CLOC: Compact LowOverhead CFB. CEASAR Cryptographic Competitions, 2014. http://competitions.cr.yp.to/caesarsubmissions.html. ##[9] Tetsu Iwata, Kazuhiko Minematsu, Jian Guo, Sumio Morioka, and Eita Kobayashi. SILC: SImple Lightweight CFB. CEASAR Cryptographic Competitions, 2014. http://competitions.cr.yp.to/caesarsubmissions.html. ##[10] Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES  The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002. ##[11] Guy Barwell. FORGERY ON STATELESS CMCC WITH A SINGLE QUERY. CEASAR Cryptographic Competitions mailing list, 2014. ##[12] Andrey Bogdanov, Martin M. Lauridsen, and Elmar Tischhauser. Cryptanalysis of AVALANCHEv1. CEASAR Cryptographic Competitions mailing list, 2014. http://martinlauridsen.info/pub/avalanchev1.pdf. ##[13] Tetsu Iwata, Kazuhiko Minematsu, Jian Guo, and Sumio Morioka. CLOC: Compact LowOverhead CFB. FSE 2014, 2014. ##[14] Tomoyasu Suzaki, Kazuhiko Minematsu, Sumio Morioka, and Eita Kobayashi. TWINE: A Lightweight Block Cipher for Multiple Platforms. In Selected Areas in Cryptography, pages 339354, 2012.##]
Enhancing privacy of recent authentication schemes for lowcost RFID systems
2
2
Nowadays Radio Frequency Identification (RFID) systems have appeared in lots of identification and authentication applications. In some sensitive applications, providing secure and confidential communication is very important for endusers. To this aim, different RFID authentication protocols have been proposed, which have tried to provide security and privacy of RFID users. In this paper, we analyze the privacy of two recently proposed RFID authentication protocols in 2012 and 2013. We present several traceability attacks including traceability, backward traceability and forward traceability against the first protocol. We also show that, the second protocol not only suffers from DenialofService (DoS) attack, but also it is vulnerable to traceability and backward traceability attacks. We present our privacy analysis based on a wellknown formal RFID privacy model which has been proposed by Ouafi and Phan in 2008. Then, in order to overcome the weaknesses, we apply some modifications on these protocols and propose two modified versions.
1

135
149


K.
Baghery
Iran
baghery.karim@yahoo.com


B.
Abdolmaleki
Iran
abdolmaleki.behzad@yahoo.com


B.
Akhbari
Iran
akhbari@eetd.kntu.ac.ir


M. R.
Aref
Iran
aref@sharif.edu
RFID Authentication Protocol
security
privacy
EPC C1 G2 Standard
[[1] D. Heyden, "RFID Applications," Available: http://www.fibre2fashion.com/industryarticle/11/1023/rfid applications1.asp. ##[2] S. Maharjan, "RFID and IOT: An overview," Simula Research Laboratory University of Oslo, 2010. ##[3] L. Yang, P. Yu, W. Bailing, Q. Yun, B. Xuefeng, and Y. Xinling, "Hashbased RFID Mutual Authentication Protocol," International Journal of Security & Its Applications, vol. 7, no. 3, pp. 17389976, 2013. ##[4] B. Song and C. J. Mitchell, "Scalable rfid security protocols supporting tag ownership transfer," Comput. Commun., vol. 34, pp. 556566, 2011. ##[5] A. Juels, "RFID security and privacy: A research survey," IEEE Journal on Selected Areas in Communications, vol. 24, no. 2, p. 381394, 2006. ##[6] A. Juels, and S.A Weis, "Defining strong privacy for RFID," in Proceedings of PerCom'07, pp. 342347, 2006. ##[7] B. Alomair, A. Clark, J. Cuellar, and R. Poovendran, "Scalable RFID systems: a privacypreserving protocol with constanttime identification," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 8, pp. 15361550, 2012. ##[8] K. Ouafi, "Security and privacy in RFID systems," PhD Thesis, Ecole Polytechnique Federale DE Lausanne, 2008. ##[9] M. R. Alagheband, and M. R. Aref, "Simulationbased traceability analysis of RFID authentication protocols," Wireless Personal Communications, vol. 77, no. 2, pp. 10201038, 2014. ##[10] B. Hameed, I. Khan, F. Durr, and K. Rothermel, "An RFID based consistency management framework for production monitoring in a smart realtime factory," in 2nd International Conference on the Internet of Things (IoT), Tokyo, 2010. ##[11] D. He, and Sh. Zeadally, "An analysis of RFID authentication schemes for Internet of things in healthcare environment using elliptic curve cryptography," IEEE Internet of Things Journal, vol. 2, no. 1, pp. 72  83, 2015. ##[12] G. Avoine and X. Carpent, "Yet another ultralightweight authentication protocol that is broken," in Workshop on RFID SecurityRFIDSec'12, Nijmegen, 2012. ##[13] M. Asadpour, and M. T. Dashti, "A privacyfriendly RFID protocol using reusable anonymous tickets," in 10th International Conference on Trust, Security and Privacy in Computing and Communications, Changsha , 2011. ##[14] Z. SohrabiBonab, M. Alagheband, and M. R. Aref, "Traceability analysis of quadratic residuebased RFID authentication protocols," in Eleventh Annual International Conference on Privacy, Security and Trust (PST), Tarragona , 2013. ##[15] M. R. Alagheband, and M. R. Aref, "Unified privacy analysis of new founded RFID authentication protocols," Security and Communication Networks, vol. 6, no. 8, pp. 9991009, 2013. ##[16] M. H. Habibi, M. R. Aref, and Di Ma, "Addressing flaws in RFID authentication protocols," Progress in Cryptology, INDOCRYPT 2011, LNCS 7107, vol. 7, p. 216235, 2011. ##[17] P. Babvey, H. A. Yajam, and T. Eghlidos, "Security analysis of SKI protocol," in 11th International ISC Conference on Information Security and Cryptology (ISCISC), Tehran, 2014. ##[18] "EPC global Inc.," Available: http://www.epcglobalinc.org. ##[19] H. Y. Chien, and C. H. Chen, "Mutual authentication protocol for RFID conforming to EPC Class 1 Generation 2 standards," Computer Standards & Interfaces, vol. 29, no. 2, pp. 254259, 2007. ##[20] E.J. Yoon, "Improvement of the securing RFID systems conforming to epc class 1 generation 2 standard," Expert Syst. Appl., vol. 39, no. 11, p. 15891594, 2012. ##[21] M.H. Habibi, M. R. Alaghband, and M. R. Aref, "Attacks on a lightweight mutual authentication protocol under EPC C1 G2 standard," in Information Security Theory and Practice. Security and Privacy of Mobile Devices in Wireless Communication, Springer, 2011, pp. 254263. ##[22] T. C. Yeh, Y. J. Wanga, T. Ch. Kuo, and S. S. Wanga, "Securing RFID systems conforming to EPC Class 1 Generation 2 standard," Expert Systems with Applications, vol. 37, p. 76787683, 2010. ##[23] F. Xiao, Y. Zhou, J. Zhou, H. Zhu, and X. Niu, "Security protocol for RFID system conforming to EPCC1G2 standard," Journal of Computers, vol. 8, no. 3, pp. 605612, 2013. ##[24] M. Safkhani, N. Bagheri, P. PerisLopez, A. Mitrokotsa, J. C HernandezCastro, "Weaknesses in another Gen2based RFID authentication protocol," in IEEE International Conference on RFIDTechnologies and Applications (RFIDTA), 2012. ##[25] D. N. Duc, J. Park, H. Lee, and K. Kim, "Enhancing security of EPC global Gen2 RFID tag against traceability and cloning," in Symposium on Cryptography and Information Security (CSIS), pp. 1720, 2006. ##[26] S. Karthikeyan, and M. Nesterenko, "RFID security without extensive cryptography," in 3rd ACM Workshop on Security of Ad hoc and Sensor Networks (SASN), pp. 6367, 2005. ##[27] S. Vaudenay, "On privacy models for RFID," in ASIACRYPT 2007, LNCS 4833, pp. 6887., 2007. ##[28] I. Coisel, and T. Martin, "Untangling RFID privacy models," Journal of Computer Networks and Communications, pp. 126, 2013, doi:10.1155/2013/710275. ##[29] G. Avoine, "Adversarial model for radio frequency identification," Cryptology ePrint Archive, report 2005/049. http://eprint.iacr.org/2005/049, 2005. ##[30] C. H. Lim, and T. Kwon, "Strong and robust RFID authentication enabling perfect ownership transfer," in Proceedings of ICICS '06, LNCS 4307, pp. 120, 2006. ##[31] K. Ouafi and R. C.W. Phan, "Privacy of recent RFID authentication protocols," in 4th International Conference on Information Security Practice and Experience (ISPEC), Springer, 2008. ##[32] R. H. Deng, Y. Li, M. Yung, and Y. Zhao, "A new framework for RFID privacy," in 15th European Symposium on Research in Computer Security (ESORICS), Athens, 2010. ##[33] D. Moriyama, S. Matsuo, and M. Ohkubo, "Relation among the security models for RFID authentication," in 17th European symposium on research in computer security (ESORICS), pp. 661678, 2012. ##[34] M. Safkhani, N. Bagheri, S. K. Sanadhya, and M. Naderi, "Cryptanalysis of improved Yeh et al.'s authentication Protocol: An EPC Class1 Generation2 standard compliant protocol," http://eprint.iacr.org/2011/426.pdf, 2011. ##[35] A. Mohammadali, Z. Ahmadian, and M. R. Aref, "Analysis and Improvement of the securing RFID systems conforming to EPC Class 1 Generation 2 standard," IACR Cryptology ePrint Archive, vol. 66, pp. 19, 2013. ##[36] K. Baghery, B. Abdolmaleki, B. Akhbari, and M. R. Aref, "Privacy analysis and improvements of two recent RFID authentication protocols," in 11th International ISC Conference on Information Security and Cryptology (ISCISC), Tehran, 2014. ##[37] S.P. Wang, Q.M. Ma, Y. L. Zhang, and Y.S. Li, "A HMACBased RFID Authentication Protocol," in 2nd International Symposium on Information Engineering and Electronic Commerce (IEEC), 2010. ##[38] J.S.Cho, S.S. Yeo, and S. K. Kim, "Securing against bruteforce attack: A hashbased RFID mutual authentication protocol using a secret value," Computer Communication, vol. 34, pp. 391397, 2011. ##[39] J. Cho, SC. Kim, and S. K. Kim, "Hashbased RFID tag mutual authentication scheme with retrieval efficiency," in 9th IEEE International Symposium on Parallel and Distributed Processing with Applications, 2011. ##[40] S. W. Jung, and S. Jung, "HMACbased RFID authentication protocol with minimal retrieval at server," The Fifth International Conference on Evolving Internet, pp. 5255, 2013. ##[41] Y. C. Huang, and J. R. Jiang, "Ultra lightweight RFID readertag mutual authentication revisited," in IEEE International Conference on Mobile Services (MS), New York, 2015. ##[42] D. Z. Sun, and J. D. Zhong, "A hashbased RFID security protocol for strong privacy protection," IEEE Transactions on Consumer Electronics, vol. 58, no. 4, pp. 12461252, 2012. ##[43] B. Abdolmaleki, K. Baghery, B. Akhbari, and M. R. Aref, "Attacks and improvements on two newfound RFID authentication protocols," in 7th International Symposium on Telecommunications (IST), Tehran, 2014.##]
A collusion mitigation scheme for reputation systems
2
2
Reputation management systems are in widespread use to regulate collaborations in cooperative systems. Collusion is one of the most destructive malicious behaviors in which colluders seek to affect a reputation management system in an unfair manner. Many reputation systems are vulnerable to collusion, and some modelspecific mitigation methods are proposed to combat collusion. Detection of colluders is shown to be an NPcomplete problem. In this paper, we propose the Colluders Similarity Measure (CSM) which is used by a heuristic clustering algorithm (the Colluders Detection Algorithm (CDA)) to detect colluders in O (n2m + n4) in which m and n are the total number of nodes and colluders, respectively. Furthermore, we propose an architecture to implement the algorithm in a distributed manner which can be used together with compatible reputation management systems. Implementation results and comparison with other mitigation methods show that our scheme prevents colluders from unfairly increasing their reputation and decreasing the reputation of the other nodes.
1

151
166


M.
Niknafs
Iran
m.niknafs@vru.ac.ir


S.
Dorri Nogoorani
Iran
dorri@ce.sharif.edu


R.
Jalili
Iran
jalili@sharif.edu
Attack resistance
Collusion
Reputation
Trust
[[1] Sepandar D. Kamvar, Mario T. Schlosser, and Hector GarciaMolina. The Eigentrust algorithm for reputation management in P2P networks. In Proceedings of the 12th international conference on World Wide Web, pages 640651, Budapest, Hungary, 2003. ACM Press Press. ##[2] Li Xiong and Ling Liu. Peertrust: Supporting reputationbased trust for peertopeer electronic communities. IEEE Transactions on Knowledge and Data Engineering, 16(7):843857, 2004. ##[3] Anupam Das and Mohammad Mahfuzul Islam. Securedtrust: a dynamic trust computation model for secured communication in multiagent systems. Dependable and Secure Computing, IEEE Transactions on, 9(2):261274, 2012. ##[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms, volume 2. MIT Press, Cambridge, MA, USA, 2001. ##[5] Audun Jøsang, Roslan Ismail, and Colin Boyd. A survey of trust and reputation systems for online service provision. Decision support systems, 43(2):618644, 2007. ##[6] Xinlei Wang, Kannan Govindan, and Prasant Mohapatra. Collusionresilient quality of information evaluation based on information provenance. In Proceedings of the 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), pages 395403, Salt Lake City, UT, USA, 2011. IEEE. ##[7] Audun Jøsang, Ross Hayward, and Simon Pope. Trust network analysis with subjective logic. In Proceedings of the 29th Australasian Computer Science ConferenceVolume 48, pages 8594. Australian Computer Society, Inc., 2006. ##[8] Kevin Hoffman, David Zage, and Cristina NitaRotaru. A survey of attack and defense techniques for reputation systems. ACM Computing Surveys (CSUR), 42(1):1, 2009. ##[9] Félix Gómez Mármol and Gregorio Martínez Pérez. Security threats scenarios in trust and reputation models for distributed systems. Computers & Security, 28(7):545556, 2009. ##[10] Xiaoning Jiang and Lingxiao Ye. Reputationbased trust model and antiattack mechanism in p2p networks. In Proceedings of the Second International Conference on Networks Security Wireless Communications and Trusted Computing (NSWCTC), volume 1, pages 498501, Wuhan, Hubei, China, 2010. IEEE. ##[11] Mudhakar Srivatsa, Li Xiong, and Ling Liu. TrustGuard: countering vulnerabilities in reputation management for decentralized overlay networks. In Proceedings of the 14th International Conference on World Wide Web, pages 422431, Chiba, Japan, 2005. ACM Press Press. ##[12] Runfang Zhou and Kai Hwang. Powertrust: A robust and scalable reputation system for trusted peertopeer computing. IEEE Transactions on Parallel and Distributed Systems, 18(4):460473, 2007. ##[13] Ze Li, Haiying Shen, and K. Sapra. Collusion detection in reputation systems for peertopeer networks. In Parallel Processing (ICPP), 2012 41st International Conference on, pages 98107, Sept 2012. ##[14] Gayatri Swamynathan, KevinC. Almeroth, and BenY. Zhao. The design of a reliable reputation system. Electronic Commerce Research, 10(34):239270, 2010. ##[15] Ze Li, Haiying Shen, and K. Sapra. Leveraging social networks to combat collusion in reputation systems for peertopeer networks. In Parallel Distributed Processing Symposium (IPDPS), 2011 IEEE International, pages 532543, May 2011. ##[16] Reid Kerr and Robin Cohen. Detecting and identifying coalitions. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems  Volume 3, AAMAS '12, pages 13631364, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems. ##[17] Gianluca Ciccarelli and Renato Lo Cigno. Collusion in peertopeer systems. Computer Networks, 55(15):35173532, 2011. ##[18] Bao Yu, Cao Tianjie, and Zeng Guosun. Resisting collusion by game in culture web. In Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2011 20th IEEE International Workshops on, pages 262267, June 2011. ##[19] Roberto Aringhieri, Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, and Pierangelo Samarati. Fuzzy techniques for trust and reputation management in anonymous peertopeer systems. Journal of the American Society for Information Science and Technology, 57(4):528537, 2006. ##[20] Ayman Tajeddine, Ayman Kayssi, Ali Chehab, and Hassan Artail. Fuzzy reputationbased trust model. Applied Soft Computing, 11(1):345355, 2011. ##[21] Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data, pages 303336. Springer, USA, 2010. ##[22] Yunpeng Zhao, Elizaveta Levina, and Ji Zhu. Community extraction for social networks. Proceedings of the National Academy of Sciences, 108(18):73217326, 2011. ##[23] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):78217826, 2002. ##[24] Gaoxia Wang, Yi Shen, and Ming Ouyang. A vector partitioning approach to detecting community structure in complex networks. Computers & Mathematics with Applications, 55(12):27462752, 2008. ##[25] Xutao Wang, Guanrong Chen, and Hongtao Lu. A very fast algorithm for detecting community structures in complex networks. Physica A: Statistical Mechanics and its Applications, 384(2):667674, 2007. ##[26] Mark E. J. Newman. Detecting community structure in networks. The European Physical Journal BCondensed Matter and Complex Systems, 38(2):321330, 2004. ##[27] Rui Xu and Donald C. Wunsch II. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645678, 2005. ##[28] Audun Jøsang, Roslan Ismail, and Colin Boyd. A survey of trust and reputation systems for online service provision. Decision Support Systems, 43(2):618644, 2007. ##[29] Wang Miao, Xu Zhijun, Zhang Yujun, and Zhang Hongmei. Modeling and analysis of peertrustlike trust mechanisms in p2p networks. In Global Communications Conference (GLOBECOM), 2012 IEEE, pages 26892694. IEEE, 2012. ##]
Persian Abstract
2
2
1

167
172