An authentication communication system includes an storage medium having an area for storing digital information and an access device for reading/writing digital information from/into the area. The access device authenticates whether the storage medium is authorized according to a challenge-response authentication protocol in which scrambled access information generated by scrambling the access information which shows the area is used. The storage medium authenticates whether the access device is authorized. When the access device and the storage medium have authenticated each other as authorized devices, the access device reads/writes digital information from/into the area in the storage medium according to the access information separated from the scrambled access information by the access device.