• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Su, Shenghui (Su, Shenghui.) | Lu, Shuwang (Lu, Shuwang.) | Fan, Xiubin (Fan, Xiubin.)

Indexed by:

EI Scopus SCIE

Abstract:

It is well known that the inverse function of y = x with the derivative y' = 1 is x = y, the inverse function of y = c with the derivative y' = 0 is nonexistent, and so on. Hence, on the assumption that the noninvertibility of the univariate increasing function y = (x) with x > 0 is in direct proportion to the growth rate reflected by its derivative, the authors put forward a method of comparing difficulties in inverting two functions on a continuous or discrete interval called asymptotic granularity reduction (AGR) which integrates asymptotic analysis with logarithmic granularities, and is an extension and a complement to polynomial time (Turing) reduction (PTR). Prove by AGR that inverting y equivalent to x(x) (mod p) is computationally harder than inverting y equivalent to g(x) (mod p), and inverting y equivalent to g(xn) (mod p) is computationally equivalent to inverting y equivalent to g(x) (mod p), which are compatible with the results from PTR. Besides, apply AGR to the comparison of inverting y equivalent to x(n) (mod p) with y equivalent to g(x) (mod p), y equivalent to g(g1x) (mod p) with y equivalent to g(x) (mod p), and y equivalent to x(n) + x + 1 (mod p) with y equivalent to x(n) (mod p) in difficulty, and observe that the results are consistent with existing facts, which further illustrates that AGR is suitable for comparison of inversion problems in difficulty. Last, prove by AGR that inverting y equivalent to x(n)g(x) (mod p) is computationally equivalent to inverting y equivalent to g(x) (mod p) when PTR cannot be utilized expediently. AGR with the assumption partitions the complexities of problems more detailedly, and finds out some new evidence for the security of cryptosystems. (C) 2011 Elsevier B.V. All rights reserved.

Keyword:

Polynomial time reduction Transcendental logarithm problem Provable security Public key cryptosystem Asymptotic granularity reduction

Author Community:

  • [ 1 ] [Su, Shenghui]Beijing Univ Technol, Coll Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Lu, Shuwang]Chinese Acad Sci, Grad Sch, Beijing 100039, Peoples R China
  • [ 3 ] [Fan, Xiubin]Chinese Acad Sci, Inst Software, Beijing 100080, Peoples R China

Reprint Author's Address:

  • [Su, Shenghui]Beijing Univ Technol, Coll Comp, Beijing 100124, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2011

Issue: 39

Volume: 412

Page: 5374-5386

1 . 1 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 8

SCOPUS Cited Count: 11

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 5

Online/Total:746/10633873
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.